# Swedish mathematical competition problem for pre-tertiary students

In a class of students, one student is given a bag of 2014 coins whilst none of the other students in the class receive any coins at all. Every time two students meet, if they have an even amount of coins together then they split the coins equally, while if they have an odd number of coins together then they put one coin in the class's cash register and then split the coins equally. After a long time with alot of trades, it so happens to be that every single coin is in the class's cash register. What is the least number possible of students in the class?

Before reading my solution feel free to try solving the problem by yourself. Also, the questions I have regarding this problem is: Do there exists more sophisticated maths that could be used such as recursions, sets etc. to shorten the proof and make it look nicer? Any improvments overall on my solution? Any suggestions for proofs on the second part? Plesase keep those questions in mind as you proceed to read through my solution.

.

.

.

.

.

My solution:

Consider the case where every student in the class have a positive number of coins, we find that there is no way of reaching $$0$$ coins for any of the students in this case, for if we have two distict students $$A$$ and $$B$$ with $$a$$ and $$b$$ number of coins respectively with $$a,b \geq 1$$ it will result in $$a+b \geq 2$$ and so both $$A$$ and $$B$$ will be left with $$\geq 1$$ number of coins after the trade. Thus the condition that no students have any money left cannot be fulfilled.

We understand that at least one of the students must have $$0$$ coins. We investigate further around a student with $$0$$ coins and since trading is a central part of the problem, naturally we want to see what happens when a student (or two) with $$0$$ coins makes a trade. Let $$N$$ denote the student with $$0$$ coins. Now if $$N$$ trades with someone who has $$\geq 2$$ coins, we find that both $$N$$ and the other student will leave with $$\geq 1$$ coins and we are up to no good. However, if $$N$$ trades with someone who has exactly $$1$$ coin, we find that both $$N$$ and the other student will be left with $$0$$ coins after the trade(!). We conclude that in order for the number of students with $$0$$ coins to increase in the class without adding more students to the class, the only way of doing so is having a student with $$0$$ coins, $$N$$, trade with someone who has $$1$$ coin.

Unavoidably, we then must have students reaching $$1$$ coin in the process, and so we aim our investigation towards that goal. Also note that, since the students split the coins equally, if we have one student left with $$1$$ coin after a trade then there exist another student with $$1$$ coin aswell. Now trivially, I would argue that the fastest and most sufficient way of reaching two students with $$1$$ coin each under the given restrictions, is just dividing the same student's amount of coins by two over and over again by adding more students to the class. With that as our choice of strategy combined with some numerical investigation, we are able to conjecture the following:

Conjecture: "Under the given conditions and initially starting with $$c$$ coins for some integer $$c$$, the number of students it takes for two students to be able to leave a trade with $$1$$ coin each is in total only one student short of being a sufficient solution for the problem"

For example; for the picture below, let the capital letter denote a distinguishable student and let the number describe the amount of coins that student has. Initially, student $$A$$ starts with $$10$$ coins and is required to trade with $$3$$ other students, namely $$B,C$$ and $$D$$, in order for $$A$$ to reach $$1$$ coin. We see that is takes a total of $$4$$ students to reach two students who both have $$1$$ coin each and by our conjecture, $$5$$ students will be enough and sufficient as a solution to the problem. Proof of conjecture: That one student we are short of is $$N$$. $$N$$ has $$0$$ coins and will only be involved whenever a student has $$1$$ coin, $$N$$ will then trade with that student to bring it down to $$0$$ coins. Let student $$A$$ initially start with all the $$A_0$$ coins. After the first trade, $$A$$ has $$A_1$$ coins left. For each trade the coins is reduced all the way until $$A$$ has $$A_r$$ coins left which is equal to $$1$$ coin. It is clear to see that student $$A$$ required $$r$$ additional students with $$0$$ coins each to trade with in order for $$A$$ to reach $$1$$ coin. Note that each and every one of the $$r$$ students have a different amount of coins left and it can only be one of the same amounts of coins that $$A$$ once had after trade $$A_i$$, $$1 \leq i \leq r$$. With $$B_i$$ denote the student that is left with $$A_i$$ coins, for $$1 \leq i \leq r$$. If we unravel it all backwards, after trading with $$N$$, both $$A_r$$ and $$B_r$$ now have $$0$$ coins each. Now $$B_{r-1}$$ will require as many trades as $$A_{r-1}$$ required to reach $$1$$ coin, which was one student with $$0$$ coins. Since both $$A_r$$ and $$B_r$$ currently have $$0$$ coins, $$B_{r-1}$$ can be brought down to $$0$$ coins aswell. Next, in order for $$B_{r-2}$$ to reach $$1$$ coin, we need two students with $$0$$ coins each, which we obviously have. Next we do $$B_{r-3}$$ and then $$B_{r-4}$$ and so on. As the "number of kids with $$0$$ coins required to trade with" increases with one at a time, and as the "number of kids with $$0$$ coins" available starts of with one more and increases at the same rate, we will be able to bring every student down to $$0$$ coins eventually and hence we have proved our conjecture. □

Now we only have to find the answer to "what is the minimum amount of students needed in order for two of them to reach $$1$$ coin". It is not hard to see that it requires $$1$$ trade from $$2$$ coins, $$1$$ trade from $$3$$ coins but $$2$$ trades from $$4$$ coins ... $$2$$ trades from $$5$$ coins, $$2$$ trades from $$6$$ coins, $$2$$ trades from $$7$$ coins but $$3$$ trades from $$8$$. If we write it up, we see that if the initial amount of money is $$c$$, for $$2^n \leq c \lt 2^{n+1}$$, then $$n$$ additional students are required from the start which puts us at: $$n +$$ "The initial student with all the money" $$+ N$$ $$=$$ $$n+2$$ students in total. (My proof of this part is not that great and even "wordier" than the first one so I will leave it out)

As $$c$$ is $$2014$$ in this problem and we have $$2^{10} \leq 2014 \lt 2^{10+1}$$, therefore the least number of students possible is $$10 +2 = 12$$, and we are done.

My questions: Do there exists more sophisticated maths that could be used such as recursions, sets etc. to shorten the proof and make it look nicer? Any improvements overall on my solution? Any suggestions for proofs on the second part?