Question

Петя и Вася играют в игру. Мальчики по очереди (начинает Петя) отмечают натуральные числа, не превосходящие 1000. Запрещается отмечать любое уже отмеченное число, а также любое число, отличающееся от какого-то отмеченного на 1 или дающее в сумме с каким-то отмеченным 1001. Тот, кто не имеет хода, проигрывает. Кто выиграет при правильной игре?

Answer 1

ВЫГРАЕТ ТОТ КТО БУДЕТ ХОДИТЬ 2

Answer 2

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

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

Вершины, соответствующие числам, которые можно отметить на данном ходу, будут соединены ребрами с вершиной, соответствующей числу, которое было отмечено на предыдущем ходу. Например, если на предыдущем ходу было отмечено число 7, то на следующем ходу можно отметить число 6, 8 или любое число от 1001-7=994 до 1000, кроме чисел, которые уже отмечены или не могут быть отмечены в соответствии с правилами игры.

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

Следовательно, при правильной игре первый игрок выиграет, если начнет с отметки числа из любого из циклов длины 10 или 11 в графе игры. Если же он начнет с отметки числа из другой компоненты связности, то он проиграет, если второй игрок играет правильно.