Extremely Hot Chocolate!

Probability Level 5

Today, Brian is generous and wants to offer a hot chocolate to all of his $n$ friends. Unfortunately, Brian has enough money only for $n-1$ hot chocolates, so he decided to play a game.

The game starts by placing his $n$ friends around a table, and numbering them from 0 to $n-1$ in clockwise order.

Person 0 starts off with an empty plastic cup.
Every person who directly receives the cup from another person around the table, wins a hot chocolate and leaves the game.
Once person $p$ is gone, the cup is taken by the person to the left of $p$ .
The game ends when there is only one person left, who unfortunately will not receive a hot chocolate.
In the first move, person 0 gives the cup to person 1.

Let us denote as $L_n$ the last person in a game of $n$ people.

For example with 5 people the game would play out as:

$0\rightarrow\boxed{1}\rightarrow2\rightarrow\boxed{3}\rightarrow4\rightarrow\boxed{0}\rightarrow2\rightarrow\boxed{4}\rightarrow2$

So $L_5=2$ .

What is the digit sum of $\; (L_{2^{150}-1}\mod(10^9+7)) \;\;?$

Image Credit: Wikipedia .

The answer is 43.

1 solution

Brian Riccardi
Feb 24, 2016

The idea is to construct the solution from smaller values of the table, in particular:

$L_n = \begin{cases} 0 & if \;\;n=1 \\ {2}\times{L_{n/2}} & if \;\;n\;\;even \\ L_{n-1}+2 & if\;\;n\;\;odd \end{cases}$

The base case is obvious, let's see the recurrence relations:

if $n$ is even, after the first round of moves all odd numbers are gone, so remains $\frac{n}{2}$ people; we can now re-map them from $0$ to $\frac{n}{2}-1$ , calculate who lose and then reconstruct the initial mapping
otherwise we can eliminate person $1$ and reduce the problem to $n-1$ people rotated counter-clockwise; like the even case we just re-map, solve and reconstruct the solution

It seems a Computer Science problem, but it is not diffcult to see a pattern in this sequence:

$0,0,2,0,2,4,6,0,2,4,6,8,10, \dots$

with a little bit of creativity we can build up a closed form:

$L_n = 2\times(n - 2^{\lfloor log_2(n)\rfloor})$

and prove it by induction (I leave this to the reader).

Once we have the closed-form it's easy to find the $mod$ solution: $\boxed{769740172}$ .

And then it's digit sum: $\boxed{43}$ .

PS: obviously there are different approaches and many of them are more efficient in the odd case!

Extremely Hot Chocolate!

Image Credit: Wikipedia .

The answer is 43.

1 solution

0 pending reports