Personal Blogs

Going through a desk that belonged to my Grandad, I found an old bill but unfortunately the first and last digits of the total had faded and were no longer legible. All that can still be read is

72 turkeys £_67.9_

where the underscores represent the unreadable digits.

What was the price of each turkey?

I found this nice puzzle on Cut-The-Knot, that treasure store of problems. It was original a question in a Stanford examination. You can find my solution further down the page.

Solution

We can ignore the decimal point for the moment and just try to deduce the missing digits, let's call them X and Y, from the fact that X679Y must be divisible by 72, the number of turkeys. 72 is even, so Y must be an even digit; 0, 2, 4, 6, or 8.

Moreover 72 is a multiple of 9, and a number is only divisible by 9 if the sum of its digits is divisible by 9. The digit sum of the known digits is 24 and for each possible value of Y we can then work out what the corresponding value of X must be for the digit sum to meet this condition.

The possible combinations are

We also know that 72 is divisible by 8 and so the number we want must be divisible by 8 also. So now we test the candidate numbers in turn and only 36792 passes the test.

Finally 36792/72 = 511, so the price per turkey back then must have been £5.11

The Pigeonhole Principle says, of course, that if there are more pigeons than pigeonholes then we must be able to find a pigeonhole with more than one occupant.

The Cut The Problem ask for a proof (using the Pigeonhole Principle) that there is a power of whose last three digits are , which sounds quite surprising.

But let's imagine we have pigeonholes numbered . Calculate distinct power of , divide each by and find the remainder, then put that power in the pigeonhole with the same number as the remainder.

There is one more 'pigeons' than pigeonholes, so there must be a pigeonhole with two occupants, that it, two powers that leave the same remainder on division by .

Suppose these are and , being the smaller. Because they leave the same remainder when divided by , must be a multiple of .

can't divide a power of , so it must divide . This means when worked out ends in three zeros , which in turn means ends in .

We can run a computer search quite easily and we find that in fact

fits the bill.

This result can be generalised of course and we can prove that for example there must a power of that ends in a trillion zeros followed by , although given that even the zeros would take up nearly GB the browser is too small to display it.