Game picking cards so that sum is divisible by $25$

55 Views Asked by At

Adele and Bryce play a game. There are $50$ cards, numbered $1,2,\ldots,50$. They take turns alternately picking a card, with Adele going first. If at the end, the sum of the numbers on Adele's cards is divisible by $25$, she wins. Can she win?

Consider the second-to-last move of Bryce. If at that point, only one of the the $3$ numbers left will make Adele win, Bryce can choose that number and prevent Adele from winning. That means Adele needs to make sure that after her second-to-last move, $2$ of the remaining $3$ numbers will make her win (and these two must be the same modulo $25$.)

[Source: Russian competition problem]

1

There are 1 best solutions below

0
On BEST ANSWER

Note there are exactly two cards for each residue class mod $25$

Adelle can make sure she wins. To do this Adelle makes sure Bryce never gets two numbers in the same congruence class, she can so this by taking the other card with the same congruence class each time Bryce picks a card for which the other card is still available.

At the end Alice will have one card of each congruence class, so the sum of her numbers mod 25 will be $0+1+2\dots+24=\frac{25\cdot24}{2}=25*12\equiv0\bmod25$. So Alice can win.


We can generalize this further. If there are $2n$ cards on the table and Alice needs to get a sum multiple of $n$ then Alice wins if and only if $n$ is odd.

To see this notice when $n$ is odd Alice can use the stategy above.

When $n$ is even Bryce can win by making sure Alice doesn't get two cards in the same residue class. so the sum of her cards will be

$0+1+2\dots +n-1=\frac{n\cdot (n+1)}{2}\bmod n$ but in this case this number is not a multiple of $n$ since it is less divisible by $2$ than $n$.