The integers $1,2,3,\ldots,n$ are to be arranged clockwise around a circle, such that adjacent integers always share a common digit (in their decimal representations).
(a) Find the smallest integer $n\ge3$ for which such an arrangement does exist.
(b) Find the largest integer $n\ge3$ for which such an arrangement does not exist.
(a) It's easy to see that n must be at least 29, since every number less than 10 must be paired with 2 neighbours, so you need 29 to pair with 9.
So 9 can be paired with 19 and 29, and then 8 with 18 and 28, etc upto 1 with 11 and 21.
If you put the number less than 10 in the middle, those groups of 3 can be easily chained together, because they all have a 1 on one end and a 2 on the other end, So you get the 1-group, 2-group, 3-group, etc.
Then 10 and 20 are left, which can be inserted on each end. They form the 0-group. You can put 0 in there to make it consistent.
End result: 20, 29,9,19, 18,8,28, 27,7,17, 16,6,26, 25,5,15, 14,4,24, 23,3,13, 12,2,22, 21,1,11, 10 [,20]
(b) If we take the sequence of (a), we can always insert the next number. 30 between 10 and 20,
31 between 11 and 21, 32 between 12 and 22, etc.
There is no number you can never fit. Every number ending in x can always be inserted into the x-group, because x is common inside that entire group.
Since n must be at least 29, the answer here is 28.
I think the answer is $a) 29$. Each digit from 3 to 9 must be bracketed by 2 other numbers with 3-9, the next 2 being the 20's. So, you'd have 13-3-23-24-4-14-15-5-25 etc.
You have to do a little juggling with 1, 2, 10, 20, but those are easy to insert into the chain. Same for 11, 12, 21, 22.
So, $b) 28$
"The integers 1,2,3,…,n are to be arranged clockwise around a circle, such that adjacent integers always share a common digit"
The way the puzzle is worded, it's not clear if
A.) adjacent numbers must share at least one digit or
B.) adjacent numbers must share exactly one digit.
If they can share more than one, the smallest n is 3: Ex. { 1, 12, 21 }
If exactly one digit must be common, the smallest n is 4: Ex. { 1, 12, 2, 21 }
Using the same reasoning as the posters above, a number satisfying the constraints can be inserted anywhere, and all numbers greater the min(n) are possible. Therefore, the largest n not satisfying the constraints would be n=2 for A.) and n=3 for B.).
