A pairing strategy that makes the final sum vanish modulo p

redstone_raccoon·May 28, 2026(edited)

The running sum depends on the whole move history. Is there a response rule that makes the final sum independent of Richard's choices? Problem: Richard and Kaarel are taking turns to choose numbers from the set

\{1, \dots, p-1\}

where

p > 3

is a prime. Richard is the first one to choose. Any number which has been chosen by one of the players can be chosen again be neither of the players. Every number chosen by Richard is multiplied with the very next number chosen by Kaarel. Kaarel wins the game if at some moment during the game the sum of all the found products is divisible by

p

. Richard wins if this does not happen i.e. the players run out of numbers before any of the sums is divisible by

p

. Can either of the players guarantee their victory regardless of their opponent's moves and if so, which one? Source: Baltic Way 2020 · MNET-01H7

Open MNET-01H7 in the question bank →

4 replies

shulk_said_no·May 28, 2026(edited)

Pair each a with p−a. Whenever Richard chooses a, Kaarel chooses its partner. This is always available: after each complete round, every pair is either entirely used or entirely unused.

redstone_raccoon·May 28, 2026(edited)

Each product is −a² modulo p. But Richard chooses which element of each pair, so does the final square sum depend on him?

shulk_said_no·May 28, 2026(edited)

No, a² and (p−a)² agree modulo p. The final sum is therefore

-\sum_{a=1}^{(p-1)/2}a^2=-p(p^2-1)/24\pmod p

, which is zero because p>3 makes 24 invertible modulo p.

redstone_raccoon·May 29, 2026(edited)

So Kaarel is guaranteed a zero sum by the final round, and an earlier zero only helps. We don't need to control the intermediate sums at all.

A pairing strategy that makes the final sum vanish modulo p

redstone_raccoon·May 28, 2026(edited)

\{1, \dots, p-1\}

where

p > 3

p

. Richard wins if this does not happen i.e. the players run out of numbers before any of the sums is divisible by

p

. Can either of the players guarantee their victory regardless of their opponent's moves and if so, which one? Source: Baltic Way 2020 · MNET-01H7

Open MNET-01H7 in the question bank →

4 replies

shulk_said_no·May 28, 2026(edited)

Pair each a with p−a. Whenever Richard chooses a, Kaarel chooses its partner. This is always available: after each complete round, every pair is either entirely used or entirely unused.

redstone_raccoon·May 28, 2026(edited)

Each product is −a² modulo p. But Richard chooses which element of each pair, so does the final square sum depend on him?

shulk_said_no·May 28, 2026(edited)

No, a² and (p−a)² agree modulo p. The final sum is therefore

-\sum_{a=1}^{(p-1)/2}a^2=-p(p^2-1)/24\pmod p

, which is zero because p>3 makes 24 invertible modulo p.

redstone_raccoon·May 29, 2026(edited)

So Kaarel is guaranteed a zero sum by the final round, and an earlier zero only helps. We don't need to control the intermediate sums at all.

A pairing strategy that makes the final sum vanish modulo p

4 replies

Join the discussion

A pairing strategy that makes the final sum vanish modulo p

4 replies

Join the discussion