задачка про алиса, боба и сумму

Dec 31, 2024 16:34

Мне нравится эта задача тем, что в ней очень простое условие, не нужно вообще никакой продвинутой математики, все, что нужно, чтобы ее решить - это внимание и чуть-чуть смекалки; но почти у всех заплетаются мозги и они попадают в одну из нескольких коварных ловушек по дороге ( Read more... )

задачка

Leave a comment

Comments 35

simtmaster December 31 2024, 14:51:21 UTC
> Запрещается выбирать число, которое на предыдущем ходу выбрал второй игрок (но вообще повторять числа можно, просто не подряд).

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

Reply

ny_quant December 31 2024, 15:53:04 UTC

Начать с маленьких N, а потом сводить задачу к ранее решенной.

Reply

simtmaster December 31 2024, 17:25:43 UTC
Процитированный фрагмент сводит задачу от стейта N к стейту (N, last_chosen). Т.к. фактически к квадратичной / 2.

Reply

ny_quant December 31 2024, 17:46:11 UTC

Ключевой момент в том, что если при неком начальном N выигрывает, скажем, Боб, то для N+1 ... N+9 выигрывает Алиса, а при N+10 опять Боб. Понятно почему?

Reply


janatem December 31 2024, 15:00:30 UTC
> Запрещается выбирать число, которое на предыдущем ходу выбрал второй игрок

Интересная модификация. Без этого правила получается известная и простая в анализе игра Ним, точнее, ее частный случай - игра Баше.

Reply


shlem59 December 31 2024, 15:47:03 UTC

Думал 10 - но нет. Алиса выберет 5, а повторять нельзя. Зато 11 подходит. Если Алиса 1 - то Боб 5, а если не 1 - добиваем до 11. Так что любое кратное 11 годится. Боб всегда добивает до 11.

Reply

talk_a_bit January 1 2025, 04:41:20 UTC
N = 33
А: 1, Б: 5
А: 8, Б: 3
А: 5, Б: 6
А: 5, finita la comedia

Reply

ile_eli January 1 2025, 09:59:44 UTC
Так зачем же он ответил Б:3? Можно было Б:4.

Reply

talk_a_bit January 1 2025, 17:07:54 UTC
Комментарий выше предлагал стратегию «1 → 5, x → 11−x», вот я ее и опробовал на N=33.

При N=33 Алиса выигрывает в любом случае, например:
А: 1, Б: 5
А: 8, Б: 4
А: 5, Б: x
А: 10−x, happy end

Reply


ny_quant December 31 2024, 15:50:33 UTC

В смысле для каких трех наименьших?

Reply

avva December 31 2024, 16:56:12 UTC
Да

Reply


ny_quant December 31 2024, 15:57:45 UTC

Наименьшее очевидно 10.

Reply

firanx December 31 2024, 16:33:55 UTC
Алиса делает ход 5.

Reply

ny_quant December 31 2024, 16:37:47 UTC

Так, условия задачи надо читать внимательнее. 11

Reply


Leave a comment

Up