Математика и игра 2048
Впервые игру 2048 представили на Хабрахабр здесь. Не прошло и пяти дней, как раскрыли тайну простой стратегии ее прохождения. Она действительно проста — нужно строить змейку из тайлов (как на картинке).
Это вдохновило меня доработать и оформить в виде поста начатые ранее размышления об игре 2048. Речь идет не о стратегии и тактике прохождения, а о таких вопросах, как:
— действительно ли 2 17 является максимально возможным блоком?
— какое количество очков можно в принципе набрать по пути к неизбежному концу игры?
— сколько ходов позволяет сделать головоломка?
Чтобы разобраться понадобится немного математики…
Максимально возможный тайл
Основная идея – абстрагироваться от того, как расположены тайлы на игровом поле, сосредоточив внимание только на их значениях. С этой точки зрения состояние игры можно описать упорядоченным по возрастанию набором 16 чисел, представленных в данный момент на экране (пустой клетке соответствует ноль).
В случае как на картинке состоянием будет набор (4, 4, 8, 16, …, 65536). А в самом начале игры оно может быть, например, вектором (0, 0, …, 0, 2, 2). Каждый ход (как человека, так и машины) приводит к новому состоянию, которое, однако, не может быть произвольным. Так, правила игры не позволяют перескочить разом с (0, …, 0, 2, 2, 8) до (0, …, 0, 4, 16).
Опишем все возможные переходы от одного состояния к другому:
— в ход человека – либо ничего не меняется, либо одна или несколько пар одинаковых чисел заменяются на сумму элементов в паре, затем добавляется необходимое количество нулей и вектор упорядочивается;
— в ход машины – либо в набор добавляется (так, чтобы не нарушить порядок) одна двойка или одна четвёрка, а один ноль убирается, либо (если нулей в состоянии нет) объявляется проигрыш игрока.
Исходным состоянием (то есть состоянием на момент начала головоломки) может быть (0, …, 0, 2, 2), (0, …, 0, 2, 4) или (0, …, 0, 4, 4). Человек и машина ходят по очереди, игрок начинает первым.
Таким образом, для ответа на вопрос «точно ли 131 072 является максимально возможным тайлом?», остается доказать, что перейти в модели к состоянию с числом 2 18 никогда не удастся.
Замечание: некоторые состояния и переходы возможны только в рассматриваемой нами модели, им нет аналогов в игре 2048, что не влияет на ход доказательства.
Каждый следующий этап подобных рассуждений приводит к увеличению как минимум на единицу количества строго заданных компонент вектора, обязанного присутствовать в цепи. При этом наименьшее из фиксированных значений сокращается вдвое.
Однако игрок не мог оказаться в такой ситуации, так как после действия машины наименьшее из представленных в векторе чисел может быть только 0, 2 или 4. Пришли к противоречию, которое опровергает наше исходное предположение от противного, тем самым доказывая требуемое.
В итоге, 2 17 действительно является максимально возможным тайлом в игре 2048. Это означает также, что проходя головоломку можно сделать не более чем какое-то фиксированное количество ходов, набрав при этом ограниченное число очков. Интересно, сколько же именно баллов и действий в нашем распоряжении?
Максимально возможное число очков
Отметим также, что на пути к желанному финалу, машина может выдавать большее или меньшее количество четвёрок. Чем чаще игрок получает такие «подарки», тем хуже будет его результат по очкам. Поэтому давайте считать, что машина во всех (за исключением оговоренных далее) случаях выдаёт двойку. Чтобы дойти до конца необходимо получить всего 15 четвёрок — для сбора блока 131 072, расположенного рядом с ним тайла 65 536, и так далее до 8.
Получаем f (2) = 4. Далее:
f (3) = 16 (по 4 балла мы получим за каждый из двух необходимых блоков 4, затем ещё 8 — за их объединение в восьмёрку),
f (4) = 48 (= 16 + 16 + 16),
f (5) = 128 (= 48 + 48 + 32) и т. д.
Собирая тайл 2 17 мы получим на 4 очка меньше, чем предсказывает выведенная формула, так как вынуждены будем использовать одну подаренную нам машиной четвёрку. То есть f (17) = 2 17 *16 — 4 или 2 097 148.
Вычислив сумму f (17) + f (16) — 4 + f (15) — 4 +… + f (3) — 4, получим 3 932 100, что является максимально возможным количеством очков в игре 2048.
Максимально возможное количество ходов игрока
Итак, g (2) = 2 (для сбора четвёрки нужно слить 2 двойки), g (3) = 4 (для сбора восьмёрки нужно слить две четвёрки, производство каждой из которых требует по 2 двойки), g (4) = 8 (= 4 + 4) и так далее. Простое рекуррентное соотношение g (n) = 2g (n — 1) даёт формулу g (n) = 2 n — 1 для 3 ≤ n ≤ 16.
Теперь вернемся к нашей задаче. Два тайла 2 нам даются с самого начала. Чтобы получить оставшиеся 131 036 (не считая последней в одном из финалов) необходимо совершить соответствующее количество действий (ведь каждый ход машина выдаёт нам ровно одну двойку). Плюс понадобится еще 15 четвёрок (также не считая последней в одном из финалов). И, наконец, еще одно действие приведёт к появлению последней двойки или четвёрки.
Итого, волей-неволей придётся сделать 131 036 + 15 + 1 = 131 052 нажатий на клавиши (или прикосновений к сенсорному экрану) — это и есть искомое максимальное количество ходов пользователя в игре 2048.
Анализ моих текущих достижений в игре 2048
В завершение позволю себе применить изложенные выше результаты и подходы для анализа моего недавнего успеха в игре 2048. Мне показалось удивительным и интересным то, что оказывается можно определить точное количество ходов, требуемое для достижения отраженной на картинке ситуации. Конечно, при этом не учитываются те действия, которые я совершал, неоднократно переигрывая отдельные эпизоды с последнего сохранения (сейвы можно делать, банально дублируя вкладки с игрой). А без этого собрать максимально возможный блок крайне маловероятно.
Итак, следуя опробованным ранее рассуждениям, если бы всю игру мне выпадали только двойки и одна четвёрка, то в результате g (16) + g (15) +… + g (2) + 1 — 2 = 65 533 ходов я должен был набрать целых f (16) + f (15) + f (14) +… + f (2) = 1 835 012 очков. Однако, как видно, заработано всего 1 811 320. Не хватает 23 692, то есть машина выдала мне 5 923 четвёрки, лишив возможности добрать очки, но сэкономив соответствующее число ходов.
Выводы:
— к настоящему моменту я сделал порядка 60 тыс. правильных действий на пути к полной победе в игре 2048;
— до одного из двух неизбежных финалов осталось еще около 71 тыс. нажатий на клавиши (при идеальной игре и везении);
— общее количество полученных мной очков (после сбора максимального тайла и четырёхтысячного блока рядом с ним) составляет 2 117 800, то есть
54% от максимально возможного. Больше половины! Даже с учетом невосполнимых потерь в размере почти 24 тыс. баллов из-за генератора случайных чисел.
Если вдруг добью игрушку до конца — выложу картинку в этот пост. Всем хорошего настроения!
UPD: 
Появившаяся сразу после снимка экрана фраза Game over кажется мне в этом случае не совсем уместной. Ведь на пути к одному из двух возможных финальных состояний победный блок 2048 пришлось собрать 127 раз. Всего сделано 119 322 правильных хода. Машина выкинула на поле 11 730 четверок (не считая последней в левом верхнем углу), что ускорило победу, но лишило 46 920 очков.
Из цифр двух натуральных чисел создать наименьшее возможное число, сохраняя порядок следования цифр
Требуется написать программу, которая из цифр двух натуральных чисел создает наименьшее возможное число, сохраняя при этом порядок следования цифр в этих числах.
Входной поток содержит два натуральных числа, записанных в двух строках. Числа больше нуля и меньше 10^255. (например, 125 и 34)
В единственную строку выходного потока нужно вывести наименьшее возможное число, удовлетворяющее условию задачи. (например, 12345)
12 и 21 неверно, но 21 и 12 работает 77 и 70 неверно, но 70 и 77 работает
2 ответа 2
Чтобы принять правильное решение, надо заглянуть за эти одинаковые цифры и двигаться по тому числу, у которого за этой одинаковой цифрой следует цифра меньшая, чем у другого числа.
Продолжаем. Интересный момент здесь состоит в том, что таких одинаковых цифр в числах может идти больше одного подряд. Таким образом, нам нужно «заглядывать» за такие цепочки одинаковых цифр в обоих числах.
И наконец, последний нюанс. Число может заканчиваться этой цепочкой одинаковых цифр. Если оба числа ими заканчиваются, то все одинаковые цифры просто окажутся в конце результата. Если только одно число заканчивается такой цепочкой, то надо смотреть на цифру, идущую после цепочки в другом числе. Если эта цифра меньше одинаковых цифр, то надо выводить цифры этого числа и не продвигаться в другом. И наоборот.
Наибольшее и наименьшее значение функции
На практике довольно часто приходится использовать производную для того, чтобы вычислить самое большое и самое маленькое значение функции. Мы выполняем это действие тогда, когда выясняем, как минимизировать издержки, увеличить прибыль, рассчитать оптимальную нагрузку на производство и др., то есть в тех случаях, когда нужно определить оптимальное значение какого-либо параметра. Чтобы решить такие задачи верно, надо хорошо понимать, что такое наибольшее и наименьшее значение функции.
Основные определения
Начнем, как всегда, с формулировки основных определений.
Зачем нам нужно знать, что такое стационарные точки? Для ответа на этот вопрос надо вспомнить теорему Ферма. Из нее следует, что стационарная точка – это такая точка, в которой находится экстремум дифференцируемой функции (т.е. ее локальный минимум или максимум). Следовательно, функция будет принимать наименьшее или наибольшее значение на некотором промежутке именно в одной из стационарных точек.
Еще функция может принимать наибольшее или наименьшее значение в тех точках, в которых сама функция является определенной, а ее первой производной не существует.
Первый вопрос, который возникает при изучении этой темы: во всех ли случаях мы может определить наибольшее или наименьшее значение функции на заданном отрезке? Нет, мы не можем этого сделать тогда, когда границы заданного промежутка будут совпадать с границами области определения, или если мы имеем дело с бесконечным интервалом. Бывает и так, что функция в заданном отрезке или на бесконечности будет принимать бесконечно малые или бесконечно большие значения. В этих случаях определить наибольшее и/или наименьшее значение не представляется возможным.
Более понятными эти моменты станут после изображения на графиках:
Наибольшее и наименьшее значение функции на отрезке
Разберем подробно случай, указанный на втором графике. Изменим значение отрезка на [ 1 ; 6 ] и получим, что наибольшее значение функции будет достигаться в точке с абсциссой в правой границе интервала, а наименьшее – в стационарной точке.
Наибольшее и наименьшее значение функции на открытом интервале
Наибольшее и наименьшее значение функции на бесконечности
Как найти наибольшее и наименьшее значение непрерывной функции на заданном отрезке
В этом пункте мы приведем последовательность действий, которую нужно выполнить для нахождения наибольшего или наименьшего значения функции на некотором отрезке.
Посмотрим, как правильно применить этот алгоритм при решении задач.
Решение:
Теперь вычисляем производную функции согласно правилу дифференцирования дроби:
y ( 1 ) = 1 3 + 4 1 2 = 5 y ( 2 ) = 2 3 + 4 2 2 = 3 y ( 4 ) = 4 3 + 4 4 2 = 4 1 4
Второй отрезок не включает в себя ни одной стационарной точки, поэтому нам надо вычислить значения функции только на концах заданного отрезка:
Как найти наибольшее и наименьшее значение непрерывной функции на открытом или бесконечном интервале
Перед тем как изучить данный способ, советуем вам повторить, как правильно вычислять односторонний предел и предел на бесконечности, а также узнать основные методы их нахождения. Чтобы найти наибольшее и/или наименьшее значение функции на открытом или бесконечном интервале, выполняем последовательно следующие действия.
Решение
Первым делом находим область определения функции. В знаменателе дроби стоит квадратный трехчлен, который не должен обращаться в 0 :
Мы получили область определения функции, к которой принадлежат все указанные в условии интервалы.
Теперь выполним дифференцирование функции и получим:
Следовательно, производные функции существуют на всей области ее определения.
Сопоставим то, что у нас получилось в каждом вычислении, с графиком заданной функции. На рисунке асимптоты показаны пунктиром.
Это все, что мы хотели рассказать о нахождении наибольшего и наименьшего значения функции. Те последовательности действий, которые мы привели, помогут сделать необходимые вычисления максимально быстро и просто. Но помните, что зачастую бывает полезно сначала выяснить, на каких промежутках функция будет убывать, а на каких возрастать, после чего можно делать дальнейшие выводы. Так можно более точно определить наибольшее и наименьшее значение функции и обосновать полученные результаты.
Какое 6-значное число является наименьшим?
(iv) При добавлении единицы к наибольшему пятизначному числу получаем 100000 которое является наименьшим шестизначным числом.
Кроме того, что такое хороший 6-значный код доступа?
Как и ожидалось, 123456 возглавляет список, за ним следуют 111111 и 123123.…
При этом, какое число из 6 цифр является наибольшим?
Какое наибольшее и наименьшее шестизначное число?
Какой 6-значный код-пароль самый сложный?
Почему шестизначный PIN-код не лучше для безопасности, чем четырехзначный.
| Четыре цифры | Шесть цифр |
|---|---|
| 0000 | 654321 |
| 2580 | 111111 |
| 1111 | 000000 |
| 5555 | 123123 |
Какой самый сложный 4-значный пароль?
Все 10.000 одинаково сложно, если вы выберете один случайным образом. 1111 математически угадать не легче, чем 3861. Поскольку люди имеют тенденцию отдавать предпочтение шаблонам, выбор последовательности, которая не является широко используемым шаблоном, вероятно, лучше.
Какие пароли из 6 цифр являются наиболее распространенными?
Общие шестизначные PIN-коды
Какое наибольшее число?
Что такое 7 цифр?
Этот номер называется один миллион.
Что такое 8-значное число?
Какое 9-значное наибольшее число?
Наибольшее 9-значное число
Какое шестизначное число является вторым по величине?
В чем разница между самой большой шестизначной цифрой?
Как мне ввести 6-значный код доступа на свой iPhone?
Какие бывают хорошие цифровые пароли?
Сколько существует возможных комбинаций для трехзначного замка?
Существуют 10,000 возможных комбинаций что цифры 0-9 могут быть преобразованы в четырехзначный код.
Какой хороший четырехзначный пароль?
Какой хороший четырехзначный пароль?
Группа DataGenetics обнаружила, что три самых популярных комбинации:1234, 1111 и 0000— приходится около 20 процентов всех четырехзначных паролей.
Какой хороший четырехзначный пароль?
Какие бывают уникальные пароли?
Пример надежного пароля: «Cartoon-Duck-14-Coffee-Glvs ». Он длинный, содержит прописные буквы, строчные буквы, цифры и специальные символы. Это уникальный пароль, созданный генератором случайных паролей, и его легко запомнить.
Какие пароли из 4-х цифр хороши?
Исследователи из компании Data Genetics, занимающейся анализом данных, обнаружили, что три самых популярных комбинации:«1234», «1111» и «0000»— приходится около 20 процентов всех четырехзначных паролей.
Сколько времени нужно, чтобы взломать 4-значный PIN-код?
Это займет до 112 часов перебором 4-значного ПИН-кода, потому что каждый ввод ПИН-кода занимает 40 секунд.
Что такое число 1000000000000000000000000?
Некоторые очень большие и очень маленькие числа
| Имя и фамилия | Номер | Символ |
|---|---|---|
| септильонов | 1,000,000,000,000,000,000,000,000 | Y |
| секстиллионов | 1,000,000,000,000,000,000,000 | Z |
| нониллион | 1,000,000,000,000,000,000 | E |
| квадрильон | 1,000,000,000,000,000 | P |
Какое 4-значное наибольшее число?
наибольшее четырехзначное число 9999.
Какое 4-значное наименьшее число?
Информатика ЕГЭ 15 задание разбор
15 задание ЕГЭ «Основные законы алгебры логики»
15-е задание: «Основные законы алгебры логики»
Уровень сложности — повышенный,
Требуется использование специализированного программного обеспечения — нет,
Максимальный балл — 1,
Примерное время выполнения — 5 минут.
Проверяемые элементы содержания: Знание основных понятий и законов математической логики
Плейлист видеоразборов задания на YouTube: 
Задания с множествами
Элементами множества А являются натуральные числа. Известно, что выражение
Ответ: 12
Элементами множества А являются натуральные числа. Известно, что выражение
Ответ: 18
Определите наибольшее возможное количество элементов в множестве A .
Ответ: 7
Элементами множества А являются натуральные числа. Известно, что выражение
Определите наименьшее возможное количество элементов множества A.
Ответ: 1
Задания с отрезками на числовой прямой
Отрезки на числовой прямой:
На числовой прямой даны два отрезка: P=[44,48] и Q=[23,35].
Укажите наибольшую возможную длину отрезка А, для которого формула
тождественно ложна, то есть принимает значение 0 при любом значении переменной x.
Ответ: 4
✎ Решение 2 (программирование):
Внимание! этот способ подходит НЕ для всех заданий с отрезками!
Python:
def f(a1,a2,x): return((44 maxim: maxim=a2-a1 print(a1,a2, a2-a1) # сами точки отрезка и длина
PascalABC.net:
Отрезки на числовой прямой:
На числовой прямой даны два отрезка: P = [10,20] и Q = [30,40].
Укажите наибольшую возможную длину отрезка A, для которого формула
тождественно истинна, то есть принимает значение 1 при любом значении переменной x.
Ответ: 10
Отрезки на числовой прямой:
На числовой прямой даны два отрезка: P = [3, 20] и Q = [6, 12].
Укажите наибольшую возможную длину отрезка A, для которого формула
тождественно истинна, то есть принимает значение 1 при любом значении переменной x.
Ответ: 8
Далее возможно 2 способа решения.
✎ 2 способ:
После того, как мы избавились от импликации, имеем:
Отрезки на числовой прямой:
На числовой прямой даны два отрезка: P = [11, 21] и Q = [15, 40].
Укажите наибольшую возможную длину отрезка A, для которого формула
тождественно истинна, то есть принимает значение 1 при любом значении переменной x.
Ответ: 19
Задания с ДЕЛ
Поиск наибольшего А, известная часть Дел ∨ Дел = 1
Для какого наибольшего натурального числа А формула
тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной х)?
Ответ: 8
Далее можно решать задание либо с помощью кругов Эйлера, либо с помощью логических рассуждений.
Решение с помощью логических рассуждений:
Решение с помощью кругов Эйлера:
Результат: 8
✎ Решение 2 (программирование):
Python:
for A in range(1,500): OK = 1 for x in range(1,1000): OK *= ((x % 40 == 0) or (x % 64 == 0))
Поиск наименьшего А, известная часть Дел ∧ ¬Дел = 1
Для какого наименьшего натурального числа А формула
тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной х)?
Ответ: 3
Избавимся от импликации:
✎ Решение 2 (программирование). Язык Python, Pascal:
- Из общего выражения:
for A in range(1,50): OK = 1 for x in range(1,1000): OK *= (x % A == 0) 0)or (x mod 42 = 0)) = false then begin ok := 0; break; end; end; if (ok = 1) then begin print(A); break; end end; end.
Результат: 3
Для какого наименьшего натурального числа А формула
тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной х)?
Ответ: 285
✎ Решение 2 (программирование):
Python:
Из общего выражения: