Почему в «Тетрис» невозможно выиграть❓

Одну из самых культовых игр в истории написал советский программист Алексей Пажитнов на «Электронике-60» в 1984 году.

Наверное, каждый из нас думал, что при должной сноровке партия «Тетриса» может длиться бесконечно. Но математика утверждает обратное:

🟢В основе игры — семь геометрических фигур из четырёх квадратов, тетрамино (от «тетро» — четыре, по аналогии с домино): I, O, T, L, J, S и Z. Игроку нужно вращать и складывать их так, чтобы заполнить горизонтальную линию.

🟢 Причина проигрышей — в самих фигурах. Самые коварные — S и Z: они создают наклоны и пустоты, которые почти невозможно закрыть.

🟢Ещё один важный нюанс: поле в классическом «Тетрисе» имеет ширину 10 клеток. Но если взять все семь фигур и сложить их без единого пробела, получится прямоугольник шириной в 8 клеток. То есть поле устроено так, что возникают промежутки, которые уже нельзя закрыть.

«Непобедимость» игры подтверждают и теоретические результаты

Сам вопрос — можно ли, имея фиксированный порядок фигур и стартовое поле, полностью очистить его в конце игры, — сводится к классической NP-полной задаче 3-разбиения. Алгоритм, который всегда играл бы идеально, потребовал бы ресурсов, растущих экспоненциально.

В терминах теории сложности это одна из тех задач, которые слишком трудны для эффективного решения даже компьютером. Вот доказательства:

🤒 статья исследователей из MIT 2002 года, где показано, что решение требует экспоненциального времени и универсальной «выигрышной» стратегии не существует

🤒 брошюра учёных из Лейденского университета: они доказали, что даже если оставить только «палку» — самую удобную фигуру, — при определённых условиях задача всё равно может стать неразрешимой

🤒 видео о школьнике из США, который в 2023 году «прошёл» игру до конца. Он продержался 38 минут, набрал максимальные 999 999 очков и дошёл до 157 уровня — раньше это удавалось только ИИ. Дальше игра зависла из-за ограничений кода

Мораль: на практике у любой идеи есть технический предел. В «Тетрис» невозможно выиграть, но можно бесконечно пытаться.

✅Делитесь своими рекордами в комментариях! И ставьте реакции, если интересно прочитать разбор ещё одной культовой игры. Есть догадки, о чём мы хотим рассказать?

#как_устроено

Математический анализ — это праздник, который всегда с тобой 🔗

Помните задачу про гипотезу Мизохаты-Такеучи, которую мы разбирали вот здесь? Так вот, источником вдохновения для нас тогда стал паблик «Ёжик в матане» — и сегодня мы его рекомендуем!

Эта группа ВК — настоящая математическая энциклопедия. В ней вы найдёте:

▶️подборки книг #ёжик_читает
▶️разборы задач #ёжик_решает
▶️лекции ВМК МГУ #колючие_лекции
▶️полезные видео #ёжик_смотрит_youtube

Более того, в комментариях всегда идёт диалог, так что ни один вопрос не останется без экспертного ответа.

Ещё авторы ведут одноимённый телеграм-канал @math_hedgehog. Подписывайтесь и читайте!

Это, пожалуй, одна из немногих площадок на русском языке, где собран и фундаментальный материал, и свежие статьи для самой широкой публики: от школьников до специалистов ❤️

#рекомендуем

Что тяжелее: килограмм железа или килограмм ваты❓

Ладно… Тема плотности на самом деле намного серьёзнее, чем эта детская загадка. И в сегодняшней задаче мы как раз будем её искать.

🔸Условие: в магазине игрушек продаются коробки с деревянными кубиками. На одной коробке написано, что в ней 360 кубиков. Под частично прозрачной упаковкой видно, что по самой короткой стороне уложено пять рядов кубиков. При этом самая длинная сторона коробки имеет длину 288 мм, а масса кубиков без коробки (нетто) составляет 2 488,32 г.

🔸Вопрос: какова плотность дерева, из которого сделаны кубики?

🔸Подсказка: визуально материал кубиков похож на сосну, то есть плотность точно выше 400 кг/м³.

Голосуйте за правильный ответ в опросе ниже и пишите ход решения в комментариях.

Завтра опубликуем решение от автора задачи — методиста Яндекс Лицея Нелли Шишковой. Прошлую задачу от неё можно решить здесь ❤️

#задача

Обращение математической редакции к подписчикам ⚡️

Друзья, с каждым днём нас становится всё больше. Очень рады всем, кто присоединяется, и советуем в первую очередь заглянуть в закрепы. Там навигация по каналу, пост для вопросов по курсу и тренажёру, а также мини-сериалы.

Мы хотим сделать канал ещё интереснее и уютнее. Поэтому нарисовали набор эмодзи. Их можно забирать себе в личное пользование.

👀 А чтобы всё это заработало в реакциях, нам нужно набрать голоса.

Поддержите канал бустом, а мы, в свою очередь, обещаем радовать вас полезными постами, интересными задачами и философскими инсайтами.

Кстати, что ещё вам хотелось бы видеть в канале?

▶️ больше мемов и видеоматериалов
▶️ задачи посложнее на логику и вычисления
▶️ прикладную математику из реальной жизни

Делитесь в комментах своими пожеланиями и предложениями — возьмём в работу. И спасибо, что вы с нами ❤️

Так математики видят зарождение вселенной ⬆️

Ну не все, а только те, кто имел дело с клеточными автоматами.

🔸Это математическая модель пространства, разделённого на ячейки. Каждая ячейка может находиться в одном из заданных состояний, а смена состояния зависит от соседей и правил. Несмотря на простоту, системы рождают удивительно сложное поведение.

🔸Первым клеточными автоматами серьёзно озадачился Джон фон Нейман — мы писали о нём здесь и здесь. Его занимал вопрос самовоспроизводящихся машин. В 1940-х он предложил квадратную схему решётки из ячеек, где каждая имела целых 29 возможных состояний, и могла себя копировать.

🔸Спустя двадцать лет его коллега Станислав Улам предложил более простые варианты. Но настоящую славу клеточным автоматам принёс Джон Конвей — он придумал игру «Жизнь» (1970). Это, пожалуй, самая известная модель. Она отличается простотой и элегантностью правил, а ещё плодовитостью вытекающих из них результатов.

Зачем нужны клеточные автоматы 👀

Эти системы применяются в разработке игр, криптографии, биологии, моделировании физических процессов и даже поведения людей. И, конечно, они красивы с точки зрения математики.

Накидайте реакций, и мы расскажем, причём тут зарождение Вселенной. Спойлер: будем говорить об игре «Жизнь».

#как_устроено