Вы и ваша подруга Карина решили сразиться в конфетном турнире. У вас есть вазочка со 100 карамельками и одной мятной шоколадкой. Вы с Кариной собираетесь по очереди тянуть из вазочки конфеты (как минимум одну и не больше пяти за один подход). Кто заберет последнюю карамельку — заберет и мятную шоколадку. А вы обожаете мятные шоколадки.
Допустим, Карина предложила вам решить, кто ходит первым. Как вам обеспечить себе выигрыш шоколадки? (Определите, кто ходит первым и по сколько конфет вы сами будете брать).
Посмотреть решениеНаилучший способ решения этой задачи — двигаться с конца.
Предположим, очередь Карины брать конфеты, а в вазочке осталось 5 или меньше карамелек. Тогда она просто заберет их все плюс шоколадку. Значит, вам нужно сделать так, чтобы к последнему ходу Карины непременно осталось больше 5 карамелек.
Как насчет 6?
Если в вазочке будет 6 карамелек, Карина сможет взять максимум 5, и тогда как минимум 1 карамелька останется вам (вместе с шоколадкой). Если в вазочке будет 7, 8, 9, 10 или 11 карамелек, Карина сможет взять столько, сколько нужно, чтобы оставить вам 6 штук, и это обеспечит ей победу.
Поэтому вам нужно, чтобы на последнем ходе Карины перед ней было 6 карамелек. Вы сможете это сделать, если на предыдущем ходе Карины перед ней будет 12 карамелек. Она возьмет сколько-то конфет, оставив вам 7, 8, 9, 10 или 11, из которых вы сможете взять столько, сколько нужно, чтобы оставить Карине 6.
Чтобы к ходу Карины в вазочке оказалось 12 карамелек, к ее предыдущему ходу вам нужно оставить ей 18. Вы сможете оставить ей 18 карамелек, если на предыдущем ходе ей будут оставаться 24 карамельки. Тут уже можно заметить паттерн: вам нужно сделать так, чтобы к каждому ходу Карины в вазочке оставалось количество карамелек, кратное 6.
Число 100 не кратно 6. Значит, вы не можете позволить Карине ходить первой. Ближайшее кратное 6 число — 96. Таким образом, вам надо ходить первым и взять 4 карамельки, оставив Карине 96.
Сколько конфет будет брать Карина, — не важно. Главное, чтобы вы брали столько, чтобы ко второму ее подходу в вазочке оставалось 90, к третьему — 84, к четвертому — 78, и так до 16-го подхода Карины, когда в вазочке должно остаться 6 карамелек. Она возьмет, сколько захочет, оставив вам последнюю карамельку и мятную шоколадку.
У этой стратегии есть любопытный побочный эффект: Карина может неплохо разжиться конфетками. Если она будет все время забирать максимальное количество конфет (5), всего она заберет 80 карамелек из 100. Хорошо, если вы и правда обожаете мятные шоколадки…