5
$\begingroup$

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 :

  1. 12:34
  2. 23:41
  3. 34:12
  4. 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$
1
  • $\begingroup$ What do you mean by rotate 4 ways? Do you mean rotate by $\frac {2 \pi}{4}$ each time? Oh wait, you might be thinking of this as digits instead? $\endgroup$
    – Calvin Lin
    Feb 20, 2013 at 12:51

1 Answer 1

Reset to default
8
$\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
  • $\begingroup$ 999 times? That is SO weird. Awesome answer @joriki! I ran your code (but have no looked at it in detail -- could you possibly briefly describe the code idea) and it gives 999 as you say. $\endgroup$
    – Cris Stringfellow
    Feb 20, 2013 at 16:42
  • $\begingroup$ @Cris: Sure. The code loops over all times, creates a four-digit string for each, loops over the four possible rotated strings, counts the number of rotated strings that represent valid times, and remembers all strings seen so far. For each time it checks whether the corresponding string has already been seen as a rotated string for another time; if not, it increases the generator count. Thus exactly one generator is counted for each group of times related by rotations. Incidentally it's the Lyndon word that's counted because the loops are in ascending order, but that's not important. $\endgroup$
    – joriki
    Feb 20, 2013 at 16:55
  • $\begingroup$ @joiki I just thought of an equivalent algorithm, could you let me know if you think it would work. Loop over all times in ascending order, create 4-digit string for each, list the 4 possible rotations, delete any that are not valid times, sort the remaining valid times in ascending order. If the time of the top loop is not at the first position in this list, then it has already been seen, otherwise, since it has not been seen, increase the generator count. Again, the Lyndon word is counted! :) $\endgroup$
    – Cris Stringfellow
    Feb 21, 2013 at 0:08
  • $\begingroup$ @Cris: Yes, that should work, too. Less space used, but more code to write :-) I figured that since we're only dealing with $4\cdot24\cdot60$ items the simplest algorithm would do. (Then again, simple may be in the eye of the beholder.) $\endgroup$
    – joriki
    Feb 21, 2013 at 0:27
  • $\begingroup$ @joriki I tried my hands using just combinations. I come up with 7*10*9*9*4 possibilities. Is that wrong? $\endgroup$
    – MonK
    Mar 16, 2015 at 12:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .