Maths Olympiad Prep

Library / /27 of 27

Combinatorics Difficulty 6.9 National olympiad Find the answer

There are 20182018 players sitting around a round table. At the beginning of the game we arbitrarily deal all the cards from a deck of KK cards to the players (some players may receive no cards). In each turn we choose a player who draws one card from each of the two neighbors. It is only allowed to choose a player whose each neighbor holds a nonzero number of cards. The game terminates when there is no such player. Determine the largest possible value of KK such that, no matter how we deal the cards and how we choose the players, the game always terminates after a finite number of turns.

A number or a short expression. Spacing and $ signs are ignored.

Solution

Consider 20182018 players sitting around a round table, and a deck of KK cards distributed among them. The rules of the game allow a player to draw one card from each of their two neighbors, provided both neighbors have at least one card. The game ends when no player can make such a move. We need to determine the maximum KK such that, regardless of the initial distribution of cards, the game ends after a finite number of turns.

### Analysis

The critical realization here is that the game only continues as long as there exists at least one player who can draw cards from both neighbors, which necessitates that both neighbors have at least one card.

#### A Useful Observation

If a player is able to draw from both neighbors, each with at least one card, at least two cards are transferred between players in that turn. Specifically, the number of cards held by the neighbors decreases by two while the number held by the player drawing increases by two.

#### Total Cards and Rounds

Assume the total number of cards in the game is K K . Since the player drawing gains precisely as many cards as the neighbors lose, the total number of cards among all players remains constant throughout the game.

The central aspect of this problem is understanding when the game ends. It ends precisely when no player is able to draw from their neighbors, meaning every segment of consecutive players with one or more cards is reduced in size such that at least one player in that segment cannot draw cards from both neighbors.

#### Key Insight

The game can terminate naturally when:
1. Single Player or Empty Spaces: There cannot be segments in the setup where every player in a contiguous segment has one or more cards, except isolated single players amongst players with no cards.

During the game, a key point is that it can't continue indefinitely unless a cycle is formed where all players continuously acquire exactly enough cards to allow their neighbors to always draw from them. However, creating such a cycle with cards becomes the crux of the issue.

#### Maximum Value of K K

Consider a simple scenario: for 20182018 players in a circular setup, the maximum number of cards where still no uninterrupted segment of playable moves occurs is if K=2017K = 2017.

Why? With 2017 cards, not all players can have a card. Thus, at least one player must have zero cards initially. Given any contiguous distribution of cards, some subset sums to exactly the number of players involved minus one when up to 20172017 cards are distributed. As a result, there'll always be at least one segment interrupting potential moves, ensuring the game's termination.

Therefore, for the game to always end regardless of initial card distribution and choices during play, the largest possible K K is:

2017 \boxed{2017}

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.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.