Positive integers are written on cards, one number on each side. On the first card, numbers and are written, on the second, and , ..., on the th, and . All cards are arranged in line along a table. Two players play the following game. During each move a player chooses cards and swaps them. If after his move the set of numbers face up is the same as after one of previous turns, he loses. Which of the players has a winning strategy?
Solution
Доведемо, що виграє перший гравець. Для цього йому достатньо розбити всі можливі способи розташування чисел на пари, узявши до однієї пари два розташування, які відрізняються одне від одного лише зміною перших п'яти чисел розташувань. Тоді виграшна стратегія першого гравця полягає в тому, щоб завжди перевертати лише перші п'ять карток. Після першого ходу він створює розташування чисел, яке утворює пару з початковим розташуванням чисел. Далі, кожний наступний хід другого гравця буде створювати розташування чисел, яке не зустрічалося раніше (інакше він програє) і входить до нової пари розташувань, а наступним ходом перший гравець створює розташування чисел, яке також не зустрічалося раніше і є другою компонентою цієї пари. Оскільки усіх можливих розташувань чисел скінченна кількість (а саме, ), то в деякий момент другий гравець уже не зможе створити розташування цих чисел, яке раніше не зустрічалося.
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.