There are 24*60 minutes in a day (ignoring the imperfections of the natural world, the Earth and Sun). So there are 24*60 valid 24 hour times (excluding seconds) on a digital clock.
Each of these can be rotated 4 ways, by 0,1,2 or 3 places. For example :
- 12:34
- 23:41
- 34:12
- 41:23
In which case only 1 and 2 are valid 24 hour times.
How many of these 4*24*60 rotations are also valid minutes? (What is the fastest way to find this out?)
Also, what is the minimum generating set for all 24*60 valid 24 hours times. So can I find the minimal set of Lyndon words (the earliest 24 hour times) that generate all 24 hours times? How many of these minutes are there? So out of 24*60 minutes in a day, 1 day is actually just generated by x of these significant minutes.
(This is not a homework question)
$\endgroup$ 11 Answer
$\begingroup$The easier part is the rotation by two digits: This yields a valid time iff the minutes are less than $24$, which happens in $24^2=576$ cases.
If we rotate by one to the right, the ones of the minutes become the tens of the hours, so they must be between $0$ and $2$, which is the case in $18$ out of $60$ minutes. The ones of the hours become the tens of the minutes, so they must be between $0$ and $5$, which is the case in $16$ out of $24$ hours. Thus the number of valid rotations is $18\cdot16=288$.
If we rotate by one to the left, the number of valid rotations must be the same as if we rotate by one to the right, so that makes another $288$ valid rotations. Obviously if we don't rotate at all, all $24\cdot60=1440$ times are valid, so the total is $1440+576+288+288=2592$ valid rotations out of $4\cdot24\cdot60=5760$, slightly less than half.
Counting the size of a minimum generating set would be rather cumbersome by hand; at least I don't see an easy way to do it. That sort of thing is better left to our electronic friends – here's code that checks the above result and finds that a minimal generating set contains $999$ times. I wonder whether that's a coincidence...
$\endgroup$ 6
