## Round Robbin’

Posted by Chris on June 17, 2013 – 4:53 pm

Seven gents A,B,C,D,E,F and G play a silly game. In order of their names, each doubles the amount of money that the others have in their pockets (from his own pocket). i.e. the money simply gets redistributed.

When all seven have taken their turn, each ends up with $128.

How much money did each of the gents start out with?

June 18th, 2013 at 12:17 am

After the first round A’s amount gets doubled six times to get to $128. So he must have $2 after round 1. By the same token B must have $4 after round 2, C must have $8 after round 3 and so on.

The total pool of money is seven times $128, i.e. $896. At the start of the game player A doubled each other person’s pile and had $2 left over he must have distributed half of $894, i.e. $447. So A must have started with $449.

B had $4 left after round 2. So he must have distributed half of $892 or $446 during the round and therefore had $450 at the start of the round. Half of that would have come from A’s distribution in tound 1, so he must have had $225 at the start of the game.

Likewise C would have distributed half of $888 and therefore had $444 plus $8 at the start of tound 3. Since this is the result of two rounds od doubling he would have started with $113.

By similar reasoning we get starting amounts of $57 for D, $29 for E and $15 for F

After round 6 A through F must have $64 each as their amounts get doubled out of G’s pocket. So G has 6 times $64 plus the $128 that he ends up with at this stage, i.e. $512. This comes after six rounds of doubling, so G must have started with $8.

These starting amounts for A to G add up to $896 as required.

I’m sure you’re going to tell us that there’s an easier way to solve this!

June 18th, 2013 at 12:24 am

A:449

B:225

C:113

D: 57

E: 29

F: 15

G: 8

June 18th, 2013 at 8:26 am

Ah I didn’t notice the answer before me. I guess I should say how I did it.

I started with the end situation:

A:128

B:128

C:128

D:128

E:128

F:128

G:128

Now G had to double everyone last so the situation before the end is:

A:128<- 64

B:128<- 64

C:128<- 64

D:128<- 64

E:128<- 64

F:128<- 64

G:128<-512

Before that F had to double everyone etc:

A:128<- 64<- 32<- 16<- 8<- 4<- 2<-449

B:128<- 64<- 32<- 16<- 8<- 4<-450<-225

C:128<- 64<- 32<- 16<- 8<-452<-226<-113

D:128<- 64<- 32<- 16<-456<-228<-114<- 57

E:128<- 64<- 32<-464<-232<-116<- 58<- 29

F:128<- 64<-480<-240<-120<- 60<- 30<- 15

G:128<-512<-256<-128<- 64<- 32<- 16<- 8

June 18th, 2013 at 8:31 am

Two correct answers. How did you do it jan – was it the same as Wiz’s way or something else?

As you say, Wiz, there is a slicker answer, and it let’s you rattle of the numbers no matter how many people were playing the game.

June 18th, 2013 at 8:54 am

In turn, jan’s post 3 was sent whilst I was typing mine.

Thanks for posting your method, jan. Although the underlying logic is the same (not really a lot of choice about that), both methods “feel” very different.

I liked both arguments. I liked jan’s table best though, as it’s easier to see what’s happening.

June 18th, 2013 at 2:34 pm

Hint: try to solve the problem with n players and with different (but common) final amount (such as $4096).

I’ve now written up my solution. I first get a general formula, but almost perversely, turn it into a recursive formula so that I can rattle off the answers on a 10¢ calculator.

June 19th, 2013 at 8:37 am

Perhaps the following solution isn’t particularly slick. The source that I got the problem from found the equation in less steps – but didn’t really explain the apparent short-cut. I’ve noticed that the provided solutions are often just a statement of the answer, but give little or no clue about how to derive it. The book is so old, that the original answer to this problem was given in Farthings and the final amount was 2s 8d (two shillings and eight pence).

Take advantage of jan’s table to help follow the following (:))

For n people, let the final amount that each ends up with be F = M 2

^{n}=> M = F/2^{n}. For this problem M = 1. For convenience, let the total pot be T = n F = n M 2^{n}.We want to find m(r), r = 1 to n, where m(r) is the amount of money that player r started with.

Immediately before player r takes his turn, he must have m(r) 2

^{r-1}. He must use that to pay out (T- m(r) 2^{r-1}) and be left with M 2^{r}. So, using T = n M 2^{n}=>m(r) 2

^{r-1}= (n M 2^{n}– m(r) 2^{r-1}) + M 2^{r}. That easily rearranges to :m(r) = (1 + n 2

^{n-r}) M, and that’s the general formula.I could stop there, but as that’s a pain for calculating with, let’s try for a recursive formula. As m(n) is the smallest starting amount, that suggests trying:

m(r-1) – m(r) = n M (2

^{n-r+1}– 2^{n-r}) = n M 2^{n-r}.But m(r) = (1 + n 2

^{n-r}) M => n M 2^{n-r}= m(r) – M, so use that to get:m(r-1) = 2 m(r) – M, and that is a nice recurser.

The initialiser is, using the general formula, m(n) = (1+n) M.

For the posted problem, n = 7, M = 1 so m(7) = 8, then recurse to get

m(6) = 2*8 -1 = 15, m(5) = 2*15 -1 = 29, m(4) = 2*29 -1 = 57,

m(3) = 2*57 -1 = 113, m(2) = 2*113 -1 = 225 and m(1) = 2*225 -1 = 449.

For what it’s worth, m(0) = M + T. I can’t think of a sharp observation for that.

June 21st, 2013 at 1:41 pm

Soon after this problem was posted I began to solve it but decided to wait and see what others’ came up with. My method was essentially the same Jan’s (from post #3), which works the problem backwards starting with the last person. Before completing my solution I scrolled down and saw that Wiz and Jan had already solved it the way I was about to, so my input was unnecessary (althought Wiz works the problem forwards, which is backwards from the way I would have).