Задачка про очень большую шоколадку с ожидаемым сюрпризом.

Previous Entry Поделиться Пожаловаться Next Entry
22 мая, 9:10
e_kaspersky
Контраст текущих событий делает не только здоровье крепче (если правильно им пользоваться), но и жизнь увлекательнее! Посему я стараюсь всячески разнообразить публикуемые здесь листовки с наглядной агитацией.

Мы посмотрели далёкие красивые заморские страны, почитали правильные книжки, [я бы ещё кинцо какое-нибудь свежее порекомендовал, но, увы, не снимают больше хороших фильмов], окунулись в историю, держимся в курсе новостей про мировое кибер-зловредство и противостоящих ему технологий... И так далее.

Сейчас готовится список Топ-100 самой большой земной красоты для услады глаз и любопытствов :), а кроме этого ещё и задачки умные и попроще для тренировки ума тоже есть. Вот только про еду с аппетитом что-то давно я не отчитывался... Исправляюсь! Есть у нас и про еду =>

Задачка про шоколадку. Вот такая:

Редакция ЖЖ решила в этом году поздравить не только самых лучших блогеров, но и наоборот. А именно: по результатам года будут выбраны два блогера, которые вели себя совсем плохо. Им будет вручена огромная плитка шоколада размером 2020 на 2021 кусочек. При этом один из кусочков с неприятным вкусовым "сюрпризом" (например, перец чили... а может и пурген, крысиный яд... или какая ещё фантазия придёт в голову). Кусочек отличается по цвету от остальных одинаковых кусочков. Правила следующие: блогеры поочерёдно отламывают шоколадку по линии слома и съедают отломанную часть.

Вопрос: кому из них при правильной игре достанется последний, самый "вкусный" ядовитый кусочек? :)


Ещё раз: большая плитка шоколада, "нехороший" кусочек другого цвета (его видно), ломать только по одной линии поочерёдно. Как они должны играть так, чтобы последний гадкий кусочек достался противнику?

До Нового года времени пока полно, можно подумать и разработать стратегию правильной игры. Успеете?



Вы спросите - а где правильное решение предыдущей задачки про "невпихуемое"? Ответ пока не показываю, поскольку всё ещё не прекращаются попытки протащить за угол конструкцию площадью больше двух единиц. Не буду портить этот процесс :) Ведь вы тоже можете прямо сейчас к нему присоединиться!

Метки:
Previous Entry Поделиться Пожаловаться Next Entry

Записи из этого журнала по тегу «math»

  • Субботнее головоломство.

    Всем привет! Лето постепенно оттягивает народное внимание и энтузиазм в сторону леса-речки-шашлыков, плюс открываются магазины-салоны и прочие…

  • "Чпок", "тцик" и логика налаживания межкультурного диалога.

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

  • Едем в Африку гулять!

    А давайте немного пофантазируем на тему летних отпусков. Ведь лето жаркое наступило окончательно и бесповоротно, так почему бы не помечтать, что нет…


Здравствуйте!
Система категоризации Живого Журнала посчитала, что вашу запись можно отнести к категории: Еда.
Если вы считаете, что система ошиблась — напишите об этом в ответе на этот комментарий. Ваша обратная связь поможет сделать систему точнее.
Фрэнк,
команда ЖЖ.

По-моему, решение банально:
Выигрывает первый со следующей игровой стратегией: он должен отламывать такую часть, чтобы второму оставался квадратный кусок (с "сюрпризом").

Тогда второму игроку неизбежно придется нарушить "квадратность" и в конце концов ему достанется итоговый кусок " с сюрпризом" формата 1х1

Предположим, что "сюрприз" лежит по координатам 1010x10 и второй ломает так, что получается полоса 1010x20 с "сюрпризом" посередине. Такая штука никак не квадратится..

ломать так, чтобы сопернику доставался кусок с перцем. Исход игры будет зависеть от первоначального расположения перченого куска, в конце игры останется только одна полоска, проиграет тот, кто получит три куска включая перченый, поэтому вся стратегия состоит в том, чтобы вручить сопернику эти три куска. Допустим осталась полоска в 10 кусков, перченый - первый, второй, третий с края, тут все просто, отламываем по перченому и выиграли. Но если он четвертый, пятый (или дальше), то придется отломить кусок с противоположно края и передать ход сопернику.

А если соперник использует ту же самую стратегию?

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

стратегия зависит от того как близко к краю последней полоски окажется выделенная плитка. Если на краю, второй или третьей позиции - игрок на своем ходе выиграет всегда, если дальше - зависит от четности (например полоска в пять плиток и выделенная посередине - получивший проигрывает всегда). Так что выигрышная стратегия в начале игры будет зависеть только от расположения выделенной плитки и очередности хода. И сводится к тому, чтобы на своем ходе получить требуемую комбинацию из трех плиток с выделенной на краю (или второй или третьей позиции с краю).

смотрим где выделенная плитка, от этого зависит стратегия. Это же типичная топологическая задача с параметром. Параметр - локализация. Задача сводится к тому, чтобы передать сопернику на его ходе последние три плитки с выделенной.

Посчитаем разность расстояний от меченой плитки до левого и правого краев, а потом такую же разность для верхнего и нижнего краев.
Стратегия первого игрока - выравнивать эти две разности. Первым ходом он, очевидно, сможет это сделать, т.к. это два числа разной четности.

А если второй будет играть по той же стратегии, но "лево-верх" и "право-низ"?

Кто начинает, тот и выигрывает. Покажем, как.
1. Пусть для определенности шоколадка имеет 2020 строк и 2021 столбцов.
2. Пусть N – число строк над ядовитым кусочком, S – число строк под ядовитым кусочком, E – число столбцов левее ядовитого кусочка, W – число столбцов правее ядовитого кусочка. N+S=2019, E+W=2020.
3. Представим N, S, E, W в двоичном виде. Пусть, например  N=999, S=1020, E=530, W=1490.
Тогда в двоичной форме
N = 01111100111
S = 01111111100
E = 00100010010
W = 10111010010
4. Выполним поразрядное сложение N, S, E, W по модулю 2. В данном примере получим результат М
M = 10011011011
ВАЖНО. Можно показать, что для данных начальных условий (2020*2021) М никогда не будет равна 0 в каждом разряде независимо от положения ядовитого кусочка.
5. Первым ходом уменьшаем одно из четырех чисел (соответствует съедению нескольких смежных рядов или столбцов шоколадки) так, чтобы новое  поразрядное сложение N, S, E, W по модулю 2 дало 0 во всех разрядах.
ВАЖНО. Можно показать, что если исходная М не  равна 0 в каждом разряде, то это всегда можно сделать хотя бы одним способом.
В данном примере это можно сделать только одним способом, а именно уменьшая W с 1490 до 265 = 00100001001
Теперь
N = 01111100111
S = 01111111100
E = 00100010010
W = 00100001001
M = 00000000000
6. ВАЖНО. Можно показать, что любой ход противника превратит нулевую поразрядную сумму М в ненулевую. Нашим следующим ходом мы вернем ее в нулевую.
7. Будем продолжать в том же духе, возвращая своим ходом М к поразрядному нулю после хода противника. Поскольку какждый ход уменьшает одно из чисел, то процесс сходится. После нашего последнего хода  N=S=E=W=0, и противнику придется выпить йаду сьесть отравленный кусочек.


Edited at 2020-05-23 03:11 (UTC)

Привет!
Поздравляем, ваш ответ правильный :) А чтобы получить ваш приз, напишите, пожалуйста, на почту sp@kaspersky.com с указанием, что вы выиграли.
Удачи.

Вместо E = 00100010010 должно быть E = 01000010010. Тогда W = 01000001001 (521).
В остальном, по-моему, все правильно. Хорошее решение.

Исправляю опечатку, замеченную коллегой Gr Bear.

Кто начинает, тот и выигрывает. Покажем, как.
1. Пусть для определенности шоколадка имеет 2020 строк и 2021 столбцов.
2. Пусть N – число строк над ядовитым кусочком, S – число строк под ядовитым кусочком, E – число столбцов левее ядовитого кусочка, W – число столбцов правее ядовитого кусочка. N+S=2019, E+W=2020.
3. Представим N, S, E, W в двоичном виде. Пусть, например  N=999, S=1020, E=530, W=1490.
Тогда в двоичной форме
N = 01111100111
S = 01111111100
E = 01000010010
W = 10111010010
4. Выполним поразрядное сложение N, S, E, W по модулю 2. В данном примере получим результат М
M = 11111011011
ВАЖНО. Можно показать, что для данных начальных условий (2020*2021) М никогда не будет равна 0 в каждом разряде независимо от положения ядовитого кусочка.
5. Первым ходом уменьшаем одно из четырех чисел (соответствует съедению нескольких смежных рядов или столбцов шоколадки) так, чтобы новое  поразрядное сложение N, S, E, W по модулю 2 дало 0 во всех разрядах.
ВАЖНО. Можно показать, что если исходная М не  равна 0 в каждом разряде, то это всегда можно сделать хотя бы одним способом.
В данном примере это можно сделать только одним способом, а именно уменьшая W с 1490 до 521 = 01000001001
Теперь
N = 01111100111
S = 01111111100
E = 01000010010
W = 01000001001
M = 00000000000
6. ВАЖНО. Можно показать, что любой ход противника превратит нулевую поразрядную сумму М в ненулевую. Нашим следующим ходом мы вернем ее в нулевую.
7. Будем продолжать в том же духе, возвращая своим ходом М к поразрядному нулю после хода противника. Поскольку какждый ход уменьшает одно из чисел, то процесс сходится. После нашего последнего хода  N=S=E=W=0, и противнику придется выпить йаду сьесть отравленный кусочек.

?

Log in

No account? Create an account