## Circle of Friends

Posted by Chris on October 30, 2013 – 10:27 am

Some friends sat in a circle. Each had a whole number of dollars. The first had $1 more than the second, who had $1 more than the third, and so on. The first gave $1 to the second, who gave $2 to the third, and so on, each giving $1 more than s/he received, as long as possible. There were then 2 neighbours, one of whom had 4 times as much as the other. How many friends were there and how much had the poorest friend at first?

October 30th, 2013 at 2:10 pm

I have what I think is a correct solution. I used brute-force, and so I am not convinced that it is the only correct solution. Without directly answering the question, but hinting at my solution… there was a total of $10 between the friends.

October 30th, 2013 at 3:16 pm

Hi DP. If the source site isn’t in error, then it’s more than $10.

If there’s more than one solution, then I’d like to see all of them.

I haven’t tried to solve it yet – and I haven’t checked the reasoning given (on the source site).

October 30th, 2013 at 3:18 pm

I just tried your numbers. I see how that’s a possibility if no coins are passed on.

October 30th, 2013 at 3:40 pm

Modulo my standard arithmetic problems, I expect that the total amount of money on the table to be $49. I don’t want to spoil the fun of the rest, so I’ll not answer the 2 posted questions, yet

October 30th, 2013 at 3:43 pm

P.S. Actually, I did spoil the fun, since there is only one way to have a total amount of $49 and the two answers follow directly from my hint

October 30th, 2013 at 5:42 pm

Hi Slavy. $49 doesn’t agree with the source site. I probably won’t look at this until tomorrow.

October 31st, 2013 at 2:49 am

DP and Slavy seem to have a better understanding of the problem than I do. What do you mean when you say that each player gives $1 more than s/he receives “as long as possible”? On the one hand, does the game stop the first time this happens? Then how are the “two neighbours” chosen? Or, on the other hand, does that player hand over whatever s/he has and drop out, and the game continues until only two players are left?

If the latter, and one has four times the other, then the total money pool must be a multiple of five, so Slavy’s $49 must be wrong.

October 31st, 2013 at 9:05 am

Hi WIz. The friends are in a circle, so each has two neighbours (assuming, correctly, that there are at least 3 friends).

e.g. if there were 12 friends, you could label them 1 to 12 just like on a clock dial. For convenience I’d make friend #1 be the richest and friend #12 be the poorest. #1 gives $1 to #2, #2 gives $2 to #3, …, #11 gives $11 to #12, #12 gives $12 to #1, #1 gives $13 to #2, … until #x is unable to pass on the appropriate amount (e.g. #x is meant to pass on $30 but doesn’t have $30). The process ends immediately when that happens.

October 31st, 2013 at 12:48 pm

Yeah, Chris. I was a victim of my own arithmetical skills once again Now the problem was distinguishing between 7 and – 7 Let me try again, then. $35 in total on the table

October 31st, 2013 at 1:21 pm

Hi Slavy. Phew! Your $35 is what I expect. I imagine that your proof will be better than that on the source site.

I still haven’t looked at it myself. What little spare time I had I used on the Integer Arithmetic page. Would you believe that I’ve only just got round to adding your proof that all common multiples are a multiple of the least common multiple.

October 31st, 2013 at 1:56 pm

I see the problem with my original answer. I chose to not read where you said “as long as possible”.

In my solution person #1 started with $4, #2 w/ $3, #3 w/ $2, and #4 w/ $1. #1 passes $1 to #2, #2 passes $2 to #3, and #3 passes $3 to #4. #3 ends w/ $1 and #4 w/ $4 (there’s the multiple of 4). What I didn’t do was have #4 hand $4 to #1 and so on. If so, #1 ends with $2, #2 w/ $1, #3 w/ $0, and #4 w/ $7. That is not a solution to the problem.

I haven’t completely solved the problem, but have made some interesting finds as far as patterns go… Maybe useful to the solution.

I, like Chris, make person #1 the richest and person #n the poorest.

For n=2; #1 always ends up with $0 and #2 with all the money.

For n=3; #1 always ends up with $1, #2 with $0, and #3 with the rest.

Maybe some more useful/general finds:

As should be obvious by the problem statement: after each iteration (person #1 passes to #2, …, #n to #1) persons #2 through #n decrease their total by $1 and Person #1 increases their total by $(n-1) until the final iteration. It is always person #n that cannot continue the cycle. Person #(n-1) always ends up with $0, person #(n-2) with $1, and so on. Person #1 ends with $(n-2).

I haven’t tried to take this and make some general observations mathematically (ex: total money [T] must be less than four times the amount of people [n]; T<4n).

It appears that person #n will have 4 times the amount of person #1.

November 1st, 2013 at 9:51 am

Now I will expand on my previous post..

T = total money on the table

n = total number of friends

i = initial amount of money held by person #n

f = final amount of money held by person #n

x = integer variable

Like I said before, person #n will end up with 4 times the amount as person #1, who ends with $(n-2).

f=4(n-2)

And I previously explained how the money is divided, so the total is:

T = f + sum(x=0->{n-2})[x]

The total in terms of the initial amount person #n has; everyone will have at least $i plus $1 per position away from the last person

T = i*n + sum(x=1->{n-1})[n-x]

If you were to re-arrange this equation to find the initial amount person #n has (i) you would see that there is a term T/n. Since we are only dealing with integers this term must also be an integer. So the total must be divisible by the number of people.

for n=2: f=0, T=0, T/n=0 *fail*

for n=3: f=4, T=5, T/n=1.667 *fail*

for n=4: f=8, T=11, T/n=2.75 *fail*

for n=5: f=12, T=18, T/n=3.6 *fail*

for n=6: f=16, T=26, T/n=4.333 *fail*

for n=7: f=20, T=35, T/n=5 *success*

for n=7, i=2

For good measure, person #1 will end with $(n-2)=$5, which is 4 times less than the $20 person #7 ends up with.

note: sorry, I’m not sure how to show summation function correctly on here. When I say sum(x=0->99)[x] I mean the sum from x=0 to x=99 of [x].November 1st, 2013 at 10:15 pm

Hi DP. That’s right. I’m sure that I can assume that Slavy will agree.

Needless to say, there is a neater solution.

If I wanted to sum e.g. f(n), I’d write something like:

Sum(n = 1 to 10, f(n))

Would you believe, I still haven’t tried to crack this problem.

November 3rd, 2013 at 3:35 pm

Yep, I agree with Chris DP’s answer is correct and he got most of the important moments. The “guessing” at the end is not neat enough and no uniqueness of the solution can be shown…

November 4th, 2013 at 7:42 am

I would have to agree with that. I did not come up with a way to show if that is the only solution to the problem, and will likely not be able to.

Chris, you mentioned a cleaner way to solve this. Is there a way to maybe start with 2 equations 2 unknowns (n and T), then solve for the rest after? Maybe one of those is T=m*n where m is simply an integer multiplier.

I’m interested to see the final solution and see where I could improve on my problem-solving skills. Thanks for keeping the site alive Chris.

November 5th, 2013 at 2:32 am

Hi DP,

you simply need to further explore the benefits of having T expressed in 2 different ways. Namely, the identity

4(n-1)+(n-2)(n-1)/8 =T= n*i+n(n-1)/2

After having expanded both the sides and having simplified the expressions, you derive (3-i)n=7. The right-hand-side is a prime number, while the left-hand-side is a product of 2 positive integers (since n is positive, so should be 3-i). Hence, either 3-i=1 and n=7, or 3-i=7 and n=1. The second option is impossible, since i should be positive.

November 5th, 2013 at 4:01 pm

Very nice. Thanks for the pointer slavy. At first I didn’t follow the terms in your equation, but have worked it out.

Basically I can take my first two equations and substitute in ‘f’. Set the second and third equations equal, then expand.

T = 4(n-2) + Sum[x=0 to (n-2), x] = i*n + Sum[x=1 to (n-1), (n-x)]

expand:

4n-8 + [0+1+2+...+(n-4)+(n-3)+(n-2)] = i*n + [(n-1)+(n-2)+(n-3)+...+(n-[n-3])+(n-[n-2])+(n-[n-1])]

All terms within the Sum-expansion on the left-hand-side show up on the right-hand-side, so we are able to cancel those terms. The only remaining term on the right-hand-side within the Sum-expansion is (n-1), so we end up with:

4n – 8 = i*n + n – 1

combine terms and we get what slavy has shown:

(3-i)n = 7

Since i and n are integers and 7 is prime, either (3-i)=1 and n=7 or n=1 and (3-i)=7. There is no positive value for i such that (3-i)=7, so it must be that n=7 and i=2.

It may look like I copied what slavy was saying. That was not my intent. I was simply trying to solve the problem myself here, even at the cost of redundancy. As it is math(s), our calculations are similar, and it can only be a good thing that we both show the same results.

I guess the point is that for the given problem statement, this now proves to be the only correct solution. Yay.

November 7th, 2013 at 11:44 am

Wiz, do you have any calculations to show that the answer must be a multiple of 5 (post #7) ? I agree that the total held between the 2 individuals to be compared must be a multiple of 5, but what about the other people at the table?

November 12th, 2013 at 2:31 am

Hi DP,

Sorry for the delay in replying – I didn’t realise anyone was speaking to me!

In post # 7 I was asking if the game continued until only two players remained and they accumulated all the money between them. If this were the case then the two neighbours at the end holding 4:1 must between them hold a multiple of $5.

However, this was an incorrect interpretation. The game stopped earlier. So, even though the total pool at the end did turn out to be a multiple of $5 (in fact $35), it was not because of my “proof” which was based on a misunderstanding.

November 12th, 2013 at 8:04 am

My first (incorrect) answer was also based on a misinterpretation. I guess now we wait for Chris to get a few minutes to solve this one himself then post the pretty version of the correct solution.

November 13th, 2013 at 10:29 am

I doubt that there is a more elegant solution. Anyway, since I have plenty of free time (jobless for 13 days now, looking for industrial research-oriented positions for Mathematicians – if somebody knows something let me know ) I played a little with the problem and slightly increased its difficulty level. So, I ask the following question:

Same game as before and same original money distribution (e.g., $1 less budget for every next neighbor). However, in the new formulation we have at the start 2 neighbors, one of whom had k times as much dollars as the other (k greater than 2), and also at the end there are 2 neighbors, one of whom had k times as much dollars as the other. Find k.

November 19th, 2013 at 8:26 am

I’m sorry that I’ve been quiet for so long. Here’s a way of doing it.

Let f = #friends, p = amount the poorest (i.e. the last) has. The richest initially has $(p + f – 1). After one circuit (assuming a whole circuit can be done), each is $1 poorer, and the moving heap would contain $f (i.e. just before passing it to the first friend). Hence after p complete circuits, each is $p poorer, the last friend now having nothing and the first having $(f – 1), and the moving heap contains $fp.

The next circuit cannot be completed, but friends 1 to f-1 can do their bit and so each becomes $1 poorer – friend #1 ending up with $(f-2), friend #(f-1) with $0 and the last friend in possession of $( f(p+1) -1) = $(fp + f – 1), which s/he is unable to pass on with the required extra $1.

Now either the first now has 4 times as much as the last or the last has 4 times as much as first, i.e.

fp + f − 1 = 4(f − 2) or 4(fp + f − 1) = f − 2.

The first => 7 = f(3 – p) => f = 7, p = 2 as the only non-negative integer solution.

The second => f(4p + 3) = 2 and that has no non-negative integer solution.

Hence the answer is 7 friends and the poorest had $2. For interest only, the total amount of money is f (p + (p + f -1))/2 = $35

November 19th, 2013 at 9:45 pm

I forgot to mention that that was another problem by Lewis Carroll.

Hi slavy, I’ll have a think about your problem. If I’ve understood it correctly, the two neighbours must be the first and last ones at both the beginning and at the end.

November 20th, 2013 at 12:04 am

I think that the only (non-negative integer) solutions to slavy’s problem are:

(f,p) = (0,2), (1,0), (2,0).

I simply took (f+p-1)/p = (fp+f-1)/(f-2), multiplied by p(f-2) and asked Mathematica to treat it as an integer problem.

Of course, if allowed that the initial values weren’t whole dollars, there may be many solutions and the special pairs won’t necessarily be the first and last friends or the same pair for the initial and final state.

November 20th, 2013 at 8:16 am

Hi Chris,

you are wrong There is at least one more integer solution, while all the three solutions you proposed don’t lead to anything meaningful. (0,2) corresponds to zero players the last one among whom had $2!!! (1,0) corresponds to one person with zero money playing with himself! (2,0) corresponds to 2 players, one with $1 and the other with $0 and here k is infinity!!!

Hint: Don’t try to get rid of k in the equations! It’s simpler if you keep it there. That’s why I asked for its value at the end – to stress its role in the analysis.

November 20th, 2013 at 10:59 am

Hi slavy. Ooops, I hadn’t checked to see if those solutions were physically meaningful – silly me.

I can see that keeping k (explicitly) would be crucial if k is an integer. I had assumed it to be a rational. k being an integer readily shows that gcd(f,p) = 1 for instance.

On a personal note. That you have excellent mathematical ability is beyond doubt. At least as important is that you don’t live in an ivory tower and you are accessible. You have joie de vivre. I think anyone that employs you will be very lucky.