0

How many numbers do there exist having 2013 digits, in which every two-digit number composed of two consecutive digits is a multiple of either 17 or 23? (Taken from Singapore and Asian Schools Math Olympiad)

pirsquare
  • 721
  • Have you made a list of all two-digit numbers that are multiples of 17 or 23? Which pairs of these can form consecutive pairs, overlapping as required by the problem? – hardmath Oct 09 '14 at 23:49

1 Answers1

3

Allowable pairs of consecutive digits are $17, 23, 34, 46, 51, 68, 69, 85, 92, 00$. Since the second number in each pair must be the first number of a new pair, the digits, $1, 5, 7, 8$ quickly lead to dead ends.

This leaves us with a cycle $\overline{23469}$. Starting where you wish in this cycle gives $5$ possibilities. You probably would not count the sequence of $2013$ zeros, as a $2013$-digit number

Thanks to hardmath for seeing where to get four more sequences: You get extra solutions by attaching some of the 'dead end' strings at the very end. So you can get four additional solutions ending in 68; 685; 6851; 68517. I think these sequences would start respectively with 4; 6; 9; 2.

paw88789
  • 40,402
  • Thanks! But the answer states 9 possibilities. – pirsquare Oct 08 '14 at 09:58
  • Interesting, but if I understand the problem correctly, I am not seeing where any other possibilities would come from. Of course I could be missing something. – paw88789 Oct 08 '14 at 10:00
  • Just trying to comprehend this problem. I thought in 46, 4 and 6 are not consecutive numbers as in the case 23 or 34. – pirsquare Oct 08 '14 at 10:22
  • I understood consecutive digits to be adjacent digits in the sequence, not consecutive in the sense of ordering the digits 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 – paw88789 Oct 08 '14 at 10:24
  • Ok. Trying to figure out the 9 possibilities. – pirsquare Oct 08 '14 at 10:35
  • 2
    Some additional solutions arise because when we near the end of the required 2013 digits, we can depart from the repetition of $\overline{23469}$. For example, instead of $69$ we could put $68$, and either end there or add further $85$ and end there, or add further $51$ and end there, or add further $17$. These four extra possibilities plus the five already identified make 9 solutions. – hardmath Oct 10 '14 at 05:47
  • @hardmath: Very nice! – paw88789 Oct 10 '14 at 10:37
  • @paw88789: Feel free to edit into your Answer! – hardmath Oct 10 '14 at 11:38
  • @hardmath: I did edit your idea into the post. Thanks! – paw88789 Oct 10 '14 at 12:36
  • @hardmath Many thanks! 17 can only come right at the end of the string – pirsquare Oct 11 '14 at 02:15
  • @pirsquare: Indeed all the solutions can be strung together with the least significant digits $17$, and you can snip the nine distinct solutions of length $2013$ out of that "master path". – hardmath Oct 11 '14 at 02:55
  • @hardmath Absolutely! – pirsquare Oct 11 '14 at 15:08