KGS math club/solution 11 23

Revision as of 16:37, 16 April 2013 by YogSothoth (talk | contribs) (Created page with "Notation: Let's call the bucket with smallest amount of pebbles in the beginning A, the one with most pebbles C and the remaining one B. Let's say that initially A has a pebbles,...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Notation: Let's call the bucket with smallest amount of pebbles in the beginning A, the one with most pebbles C and the remaining one B. Let's say that initially A has a pebbles, B has b and C has c pebbles.

The algorithm to obtain an empty bucket: if the integer quotient of B/A is even, move pebbles from C to A. If it is odd, move pebbles from B to A. Repeat until A has more pebbles than B. Then rename the buckets so that the new A again has smallest amount of pebbles and C largest. Repeat. Eventually this will lead into an empty bucket.

Proof: We prove the claim by first proving that

CLAIM 1: after some steps, bucket A will have less pebbles than a.

Let's say q is the integer quotient of b/a, i.e. b = q * a + t, where t < a.

Let's first assume 2a > b. Then we have q = 1 and the algorithm results in moving pebbles from B to A, giving the new bucket A the amount of b - a = t stones, which is less than a, proving CLAIM 1.

Let's then assume 2a <= b. If q is even, say q = 2u, we move pebbles from C to A, resulting in A having 2a pebbles and B having b pebbles. We see that b = qa + t = 2ua + t = u * (2a) + t, so remaider t doesn't change in this case. If q is odd, say q = 2u + 1, we move pebbles from B to A, resulting in A having 2a pebbles and B having b - a pebbles. We see that b - a = qa + t - a = (2u + 1) * a + t - a = u * (2a) + t, so remaider t doesn't change in this case either. From the above calculations we see that in both cases B has more pebbles than A after the operation. After some amount of steps, we will have the situation where B has exactly t more pebbles than A, resulting in the new bucket A (after renaming) having t < a pebbles, again proving CLAIM 1.

By induction CLAIM 1 results in bucket A eventually having 0 pebbles, which proves the theorem.