A very long number

From the 2000 University of Waterloo Cayley Contest:

The leftmost digit of an integer of length 2000 digits is 3. In this integer, any two consecutive digits must be divisible by 17 or 23. The 2000th digit may be either ‘a’ or ‘b’. What is the value of a+b?

It makes sense to begin by listing all the two digit multiples of 17 and 23:

17, 34, 51, 68, 85,

23, 46, 69, 92.

The first digit is 3, so the second digit must be 4, and the third must be 6. Now we have a choice for the fourth digit – 8 or 9.

Suppose we choose 8; then this must be followed by a 5, then a 1, then a 7, then… oh dear, we have no options at all. So in fact the fourth digit must be a 9, the fifth a 2, and the sixth a 3.

But we had a digit 3 at the beginning, so we are just going to cycle through the same logic over and over again, with the pattern ‘34692’ repeating for almost the entire length of the number. I say almost, because after the 399th block of ‘34692’, we will have only five digits left to fill, and so picking 8 instead of 9 wouldn’t be such a disaster: in this case the final five digits would be ‘34685’.

This means the two possible choices for the final digit are 2 and 5, and so a + b = 7.

I think this is a great little problem, well designed and accessible to many.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s