, 2017

Dave, Yona and Tam have 6, 4 and 8 candies, respectively.

Since they each have an even number of candies, then no candies are discarded.

During Step 2, Dave gives half of his 6 candies to Yona and accepts half of Tam’s 8 candies so that he now has $6-3+4=7$ candies.

Similarly, Yona gives half of her 4 candies to Tam and accepts half of Dave’s 6 candies so that she now has $4-2+3=5$ candies.

Tam gives half of his 8 candies to Dave and accepts half of Yona’s 4 candies so that he now has $8-4+2=6$ candies.

Since Dave has 7 candies, and Yona has 5 candies, they each discard one candy while Tam, who has an even number of candies, does nothing.

These next two steps are summarized in the table to the right.

Following the given procedure, we continue the table until the procedure ends, as shown.

When the procedure ends, Dave, Yona and Tam each have 4 candies.

Dave
Yona
Tam

Start
3
7
10

After Step 1
2
6
10

After Step 2
6
4
8

After Step 2
7
5
6

After Step 1
6
4
6

After Step 2
6
5
5

After Step 1
6
4
4

After Step 2
5
4
4

After Step 1
4
4
4

Dave, Yona and Tam begin with 16, 0 and 0 candies, respectively.

The results of each step of the procedure are shown in the table. (We ignore Step 1 when each of the students has an even number of candies.)

Each student has 4 candies when the procedure ends.

Dave
Yona
Tam

Start
16
0
0

After Step 2
8
8
0

After Step 2
4
8
4

After Step 2
4
6
6

After Step 2
5
5
6

After Step 1
4
4
6

After Step 2
5
4
5

After Step 1
4
4
4

We begin by investigating the result that Step 2 has on a student’s number of candies.

Assume Yona has $c$ candies, and Dave (from whom Yona receives candies), has $d$ candies.

Further, assume that $c$ and $d$ are both even integers.

During Step 2, Yona will give half of her candies away, leaving her with $\dfrac c2$ candies.

In this same Step 2, Yona will also receive $\dfrac d2$ candies from Dave (one half of Dave’s $d$ candies).

Therefore, Yona completes Step 2 with $\dfrac c2 +\dfrac d2=\dfrac{c+d}{2}$ candies, which is the average of the $c$ and $d$ candies that Yona and Dave respectively began the step with.

On Wednesday, Dave starts with $2n$ candies, and each of Yona and Tam starts with $2n+3$ candies.

Since $2n+3$ is 3 more than a multiple of 2, then $2n+3$ is an odd integer for any integer $n$.

That is, we begin the procedure by performing Step 1 which leaves Dave with $2n$ candies ($2n$ is even and so no candies are discarded), and each of Yona and Tam with $2n+2$ candies.

After Step 2, Yona will have the average of her number of candies, $2n+2$, and Dave’s number of candies, $2n$, or $\dfrac{(2n+2)+2n}{2}=\dfrac{4n+2}{2}=2n+1$.

Tam will have the average of his number of candies, $2n+2$, and Yona’s number of candies, $2n+2$, which is $2n+2$.

Dave will have the average of his number of candies, $2n$, and Tam’s number of candies,

$2n+2$, or $\dfrac{(2n+2)+2n}{2}=\dfrac{4n+2}{2}=2n+1$.

Since Yona and Dave each now have an odd number of candies, Step 1 is performed.

The procedure is continued in the table shown.

Dave
Yona
Tam

Start
$2n$
$2n+3$
$2n+3$

After Step 1
$2n$
$2n+2$
$2n+2$

After Step 2
$2n+1$
$2n+1$
$2n+2$

After Step 1
$2n$
$2n$
$2n+2$

After Step 2
$2n+1$
$2n$
$2n+1$

After Step 1
$2n$
$2n$
$2n$

At the end of the procedure, each student has $2n$ candies.
On Thursday, Dave begins with $2^{2017}$ candies, gives one half or $\frac12\times2^{2017}=2^{2016}$ to Yona, receives 0 from Tam, and thus completes the first Step 2 having $2^{2016}$ candies.

In the table shown, we proceed with the first few steps to get a sense of what is happening early in the procedure. (We again ignore Step 1 when each student has an even number of candies.)

Dave
Yona
Tam

Start
$2^{2017}$
0
0

After Step 2
$2^{2016}$
$2^{2016}$
0

After Step 2
$2^{2015}$
$2^{2016}$
$2^{2015}$

After Step 2
$2^{2015}$
$$\begin{aligned} & 2^{2014}+2^{2015} \\ & =2^{2014}+2\times2^{2014} \\ & =3\times2^{2014} \end{aligned}$$
$$\begin{aligned} & 2^{2015}+2^{2014}\\ &=2\times2^{2014}+2^{2014}\\ &=3\times2^{2014} \end{aligned}$$

After Step 2
$$\begin{aligned} & 2^{2015}+2^{2013}\\ &=2^2\times2^{2013}+2^{2013} \\ & =5\times2^{2013} \end{aligned}$$
$$\begin{aligned} & 2^{2013}+2^{2015}\\ & =2^{2013}+2^2\times2^{2013}\\ & =5\times2^{2013} \end{aligned}$$
$$\begin{aligned} & 2^{2015}+2^{2014}\\ &=2\times2^{2014}+2^{2014}\\ &=3\times2^{2014} \end{aligned}$$

As was demonstrated in part (c), each application of Step 2 gives the average number of candies that two students had prior to the step.

If each of the three students has a number of candies that is divisible by $2^k$ for some positive integer $k$, then after performing Step 2, each student will have a number of candies that is divisible by $2^{k-1}$. Why?

If Yona has $a$ candies and Dave has $b$ candies, where both $a$ and $b$ are divisible by $2^k$, then after Step 2, Yona’s number of candies is the average $\dfrac{a+b}{2}=\dfrac a2+\dfrac b2$.

Since $a$ is divisible by $2^k$, then $\dfrac a2$ is divisible by $2^{k-1}$ and similarly $\dfrac b2$ is divisible by $2^{k-1}$ and so their sum is at least divisible by $2^{k-1}$ (and possibly more).

We proceed by introducing 4 important facts which will lead us to our conclusion.

Important Fact #1:

We are starting with $2^{2017}$, 0 and 0 candies, each of which is divisible by $2^{2017}$.

The first application of Step 2 gives three numbers, each of which is divisible by $2^{2016}$.

The second application of Step 2 gives three numbers, each of which is divisible by $2^{2015}$.

The third application of Step 2 gives three numbers, each of which is divisible by $2^{2014}$, and so on. (We can verify this in the table above.)

That is, starting with $2^{2017}$, 0 and 0 candies, we are able to apply Step 2 2017 times in a row.

We note that at each of these 2017 steps, the number of candies that each student has is even, and therefore Step 1 is never applied (no candies have been discarded), and so the total number of candies shared by the three students is still $2^{2017}$.

Important Fact #2:

If we begin Step 2 with $2a,2a$ and $2b$ candies (exactly two students having an equal number of candies), then the result after applying Step 2 is $a+b,2a$, and $a+b$ candies.

That is, there are still exactly two students who have an equal number of candies.

Important Fact #3:

If we begin Step 2 with $2a,2a$ and $2b$ candies where $a<b$, then we call this a “2 low, 1 high state” (the two equal numbers are less than the third).

Applying Step 2 to $2a,2a$ and $2b$ (a “2 low, 1 high state”), gives $a+b,2a$, and $a+b$ which is a “2 high, 1 low state”. (Since $a<b$, then $a+a<b+a$ or $2a<a+b$.)

Similarly, applying Step 2 again to this “2 high, 1 low state” gives a “2 low, 1 high state”.

Since we begin with $2^{2017}$, 0 and 0 candies, which is a “2 low, 1 high state”, then after 2017 applications of Step 2, we will be at a “2 high, 1 low state”.

Important Fact #4:

Beginning with $2a,2a$ and $2b$ candies, the positive difference between the high number of candies and the low number of candies is $2b-2a$ (or $2a-2b$ if $a>b$).

After applying Step 2, we have $a+b,2a$, and $a+b$ candies and the positive difference between the high and low numbers of candies is $b-a$ (or $a-b$ if $a>b$).

That is, applying Step 2 once decreases the positive difference between the high and low numbers of candies by a factor of 2 (that is, $a-b=\frac{1}{2}(2a-2b)$).

Therefore, beginning with $2^{2017}$, 0 and 0 candies, whose positive difference is $2^{2017}$, and applying Step 2 2017 times gives a “2 high, 1 low state” where the positive difference between the high and low numbers is 1.

That is, after applying Step 2 2017 times, the number of candies is $n+1, n+1$ and $n$ for some non-negative integer $n$.

Conclusion:

Since we haven’t applied Step 1, then there are still $2^{2017}$ candies shared between the three students.

If $n$ is odd, then the number of candies, $3n+2$, is odd.

Since $3n+2$ is equal to $2^{2017}$, this is not possible and so $n$ is even.

Since $n$ is even, then $n+1$ is odd and so we apply Step 1 to $n+1, n+1$ and $n$ candies so that each student has an equal number of candies, $n$.

Two candies were discarded in the application of Step 1 and so there are now $2^{2017}-2$ candies remaining.

Since each student has an equal number of candies, and there are $2^{2017}-2$ candies in total, the procedure ends with each student having $\dfrac{2^{2017}-2}{3}$ candies.