Преобразования конечных двоичных последовательностей - Шулеры, или Математическое исследование одной карточной игры
Пусть по окружности в некотором порядке расположены N единиц и нулей (исходное состояние S0). Некоторые нули разрешается заменять на единицы в соответствии с правилами игры (N, k) (пп. 1.1-1.2.).
- 1) При каких условиях из произвольной последовательности S0 Можно получить последовательность, состоящую из одного нуля и N-1 единицы? 2) При каких условиях мы можем получить последовательность, состоящую из T = D(N, k) единиц?
Две конечные последовательности эквивалентны, если обе при правильной игре типа А или В приводятся к одной и той же конечной последовательности нулей и единиц.
Теорема 5. Если при перестановке типа PK из последовательности S0 получится двоичное число (2P-1)2Q, где 0 ? P+Q ? N, то последовательность S0 эквивалентна последовательности (1,1,...,1,0)
Теорема 6. Если при перестановке типа PK из последовательности S0 получится двоичное число вида ((2PJ-1)2QJ)2KJ, где 0 ? P+Q ? n/D, то последовательность S0 эквивалентна последовательности (111...110111...1110). (d отрезков последовательности, каждый из которых состоит из -1 единиц и одного нуля)
Теорема 7. Последовательность S0 мы можем получить из нулевой последовательности тогда и только тогда, когда ни одна компонента последовательности S0 не состоит из одних единиц.
Доказательство теоремы 5. Если перестановка PK имеет вид 00...00111...111000, то метод, по которому все остальные нули, кроме одного, превращаются в единицы, описан в п. 2.1. Из того же пункта можно видеть, что перестановки типа PK другого вида к искомой последовательности не приводится.
Теорема 6 доказывается аналогично.
7. Докажем сначала для k=1.
Пронумеруем числа (как на исходном кругу, так и на нулевом кругу) числами от 1 до N по часовой стрелке. Пусть K-ое число на исходном кругу - нуль. Тогда будем двигаться по нулевому кругу, взяв за начало движения K-ый нуль и двигаясь против часовой стрелки, и будем рассматривать каждый встречающийся нам нуль. Пусть сейчас мы рассматриваем M-тый нуль. Тогда, если m-тое число на исходном кругу - единица, заменим на нулевом кругу M_Тый нуль единицей (мы можем это сделать, т. к. M-1-ое число на нулевом кругу на данной стадии нуль). Таким образом, обойдя нулевой круг, мы превратим его в исходный.
Исключение составляет случай, когда исходный круг состоит из одних единиц (то, что мы не можем получить такой круг, мы уже доказали - аналогичное утверждение доказывалось нами при рассмотрении карточной задачи).
При K > 1 утверждение доказывается аналогично.
Похожие статьи
-
Заключение - Шулеры, или Математическое исследование одной карточной игры
В результате нашего исследования полностью изучена игра ( N, k ) для одного игрока: получены условия простоты игры (теорема 1), полностью рассмотрены...
-
Игра для двух игроков - Шулеры, или Математическое исследование одной карточной игры
Пусть на круге ( N, k ) играют два игрока. Они делают ходы по очереди. Проигрывает тот, кто не может сделать ход. Кто выигрывает при правильной игре?...
-
При решении экономических задач часто анализировать ситуации, в которых сталкиваются интересы двух или более конкурирующих сторон, преследующих различные...
-
Влияние семейного дохода на количество автомобилей, приходящееся на одного человека
Как показывает опыт изучения вопроса закономерностей формирования уровня автомобилизации, зарубежные ученые большое внимание уделяют зависимости...
-
ПОНЯТИЕ ФУНКЦИИ Если некоторому множеству значений поставлено по определенному правилу F во взаимнооднозначное соответствие некоторое множество, то тогда...
-
Метод конечных элементов - МАтематическое моделирование в экономике
- Метод конечных элементов: триангуляция - Метод конечных элементов ( МКЭ ) -- численный метод решения задач прикладной механики. - Широко используется...
-
Уравнение Пелля и диофантовые уравнения
С помощью алгебраических чисел получены явные выражения и нелинейные рекуррентные соотношения для решений диофантовых уравнений, что позволило найти...
-
В данной работе доказывается методами элементарной математики "большая" или "последняя" теорема Ферма. Некоторая, излишняя в обычных случаях, подробность...
-
Понятие числовой последовательности - Свойства функций
Числовой последовательностью называется числовая функция, определенная на множестве натуральных чисел . Если функцию задать на множестве натуральных...
-
Теорема 1. Предел постоянной равен самой постоянной. . Доказательство. f(x)=с, докажем, что . Возьмем произвольное e>0. В качестве d можно взять любое...
-
Классификация математических моделей - Построение и классификация математических моделей
К классификации математических моделей разные авторы подходят по-своему, положив в основу классификации различные принципы. Можно классифицировать...
-
Статистическая обработка результатов эксперимента - Основы научных исследований
Включает в себя определение дисперсии эксперимента, проверку постоянства дисперсии воспроизводимости и определение абсолютных и относительных...
-
Необходимость введения нового ограничения может возникнуть, например, когда первоначально для сокращения затрат машинного времени некоторые интуитивно...
-
Решение: Коэффициент использования (количество заявок, поступающих за время использования одной заявки) A) Вероятность того, что оба канала свободны: B)...
-
Выделим случай, когда входной сигнал X ( T ) является элементарной функцией 1( T ). Реакцию системы на воздействие 1( T ) можно компактно: [1] Где...
-
Сначала обсудим один из широко применяемых методов кластер-анализа - с метода k-средних. Он предназначен для разбиения исходного множества элементов...
-
Модели временных последовательностей, Критерии производительности - Прогнозирующие системы
Используемые для наших целей временные последовательности представляют собой последовательность наблюдений за интересующей переменной. Переменная...
-
Доказательство теоремы - Об одной теореме теории чисел
Доказательство теоремы проводится отдельно для случая, когда (т. е. показатель степени в равенстве (2) - НЕЧЕТНОЕ число) и когда (т. е. показатель...
-
Сходящиеся последовательности, Основные свойства сходящихся последовательностей: - Свойства функций
Говорят, что Последовательность сходится, если существует число такое, что для любого существует такое , что для любого , выполняется неравенство: ....
-
Пусть имеется конечное число объектов, которые будем обозначать натуральными числами 1, 2, 3, ..., K и называть "носителем". Под кластеризованной...
-
Система "Диспетчер" апробирована на реальных исходных данных двух регионов Нефтяной Компании "Юкос" (Липецкая и Воронежская области) и показала свою...
-
Последовательность организации эксперимента - Основы научных исследований
Для всех видов физических экспериментов последовательность их организации стандартизована и состоит из следующих этапов: 1. Аналитический (литературный)...
-
Математическое моделирование - Основы научных исследований
Выше уже указывалось, что Математическое моделирование - это получение решений уравнений, составляющих математическую модель объекта, при изменении...
-
Эксперименты физические и математические - Основы научных исследований
Эксперимент (от лат. experimentum - проба, опыт) - метод познания, при помощи которого в контролируемых условиях изучаются явления имманентного мира. В...
-
Метод конечных разностей -- широко известный и простейший метод интерполяции. Его суть заключается в замене дифференциальных коэффициентов уравнения на...
-
После проведения регрессионного анализа получается модель объекта исследований в виде некоторой функции. В простейшем случае линейной регрессии она имеет...
-
Модели теории игр. Основные определения и термины В разных областях целенаправленной деятельности, например при разработке и эксплуатации АСУ, часто...
-
Выбор группировочных признаков всегда должен быть основан на анализе качественной природы исследуемого явления. Всесторонний теоретико-экономический...
-
Решение транспортной задачи методом потенциалов - Математическая модель решения транспортной задачи
Этот метод позволяет автоматически выделять циклы с отрицательной ценой и определять их цены. Пусть имеется транспортная задача с балансовыми условиями...
-
В 2011 - 2015 гг. в серии статей в научных журналах и докладов на международных, зарубежных и всероссийских научных конференциях была представлена...
-
Ответ: Функция f ставит в соответствие числу х число у, а функция g числу у число z. Говорят что h есть сложная функция составленная из функций g и f, и...
-
Теорема: Непрерывная на сегменте функция интегрируема на этом сегменте. Теорема: Если функция определена и ограничена на сегменте, и если для любого...
-
Непрерывность функции - Свойства функций
Рассмотрим функцию, определенную на промежутке Пусть. Функция называется непрерывной в точке, если Функция называется Непрерывной слева (справа) в точке,...
-
Бесконечные пределы - Свойства функций
Функция называется Бесконечно малой при (или, или ) если для сколь угодно малого положительного числа найдется такое положительное число (), что для всех...
-
Принцип сходимости, Предел функции. Теорема Гейне - Свойства функций
Рассмотрим вопрос о существовании пределов последовательностей концевых точек бесконечной системы промежутков, вложенных друг в друга. Лемма Кантора ....
-
Сравнение множеств Определение. Множества A и B называются равномощными, если между A и B существует взаимно однозначное соответствие. Утверждение....
-
Доказательство теоремы Ферма Уважаемый Григорий Яковлевич! Обращается к Вам Черепанов Николай Михайлович, математик из Барнаула. В 2004 году, я...
-
В школьной алгебре одночленом от некоторой буквы x называется алгебраическое выражение вида, где a - некоторое число, x - буква, m - целое...
-
Еще одним подходом к проблеме формализации алгоритма являются, так называемые, рекурсивные функции. Исторически этот подход возник первым, поэтому в...
-
Решая проблему синтеза адаптивных систем для радиофизических исследований (АСРФИ), необходимо, как отмечалось выше, иметь возможность цифровой...
Преобразования конечных двоичных последовательностей - Шулеры, или Математическое исследование одной карточной игры