A positive integer N contains each 2-digit combination exactly once:
00, 01, ..., 99.
(A) What is the smallest number of digits N could have?
(B) What is the largest number of digits N could have?
(C) What is the smallest possible value of N?
(D) What is the largest possible value of N?
(no leading zeros)
(In reply to
Parts A and B (spoiler) by Steve Herman)
Consider a smaller problem where the only digits are 0,1,2:
1001120221 would be such a number. It has 10 digits.
There are 3^2 2-digit combinations of 0,1,2
So for A&B, such a number should have 10^2 + 1 or 101 digits.
I believe such numbers must exist using a graph theory argument:
Consider a graph with 10 nodes, one for each digit. Each node/digit connects to every other node with 2 pathways. Each node also has one path connecting to itself. Each node has an even number of connections. So a circuit that covers every path exactly once ought to be possible. (But I am uncertain if this is all that is necessary to prove it exists.)
If true, a few observations follow:
- the path seems like it must start and stop at the same node
- each node will be touched 10 times except for the first/last node which is visited 11 times.
In the small example above, there are four 1s, three 0s, three 2s. Also the number begins and ends with the same digit.
|
Posted by Larry
on 2024-05-15 09:39:40 |