To cook instant noodles, it is necessary to cook the noodles for exactly 3 minutes. Marking exactly 3 minutes is very complicated without a clock, but it is possible if you have certain hourglasses that mark exact times in minutes. For example, suppose you have two hourglasses, one that marks exactly 7 minutes and another that marks exactly 4 minutes. Just turn them over at the same time and, when the 4-minute one finishes, put the noodles in the pot. You should remove them from the pot when the 7-minute one finishes. Thus, the noodles will have cooked for exactly $7-4=3$ minutes.

a) A certain type of instant rice needs to cook for exactly 4 minutes. Show that it is possible to time the cooking of this rice using only hourglasses of $9 \mathrm{mi}$ nutes and 7 minutes. What is the minimum total time required to complete this task?

b) Would it be possible to mark 9 minutes if we only had hourglasses of 6 and $10 \mathrm{mi}$ nutes?
Solution

a) To mark 4 minutes, we should flip the 9-minute and 7-minute hourglasses several times so that the difference in time is 4 minutes. Since $2 \cdot 9 - 2 \cdot 7 = 4$, one procedure would be to flip the 9-minute hourglass twice and the 7-minute hourglass also twice. Initially, both should be flipped at the same time, and when the 7-minute hourglass finishes for the second time, we start counting the 4 minutes. When the 9-minute hourglass finishes for the second time, we will have completed the desired time count.

There are other combinations, for example, $7 \cdot 7 - 5 \cdot 9 = 4$. This means we could have flipped the 7-minute hourglass seven times and the 9-minute hourglass five times. In this case, we would have spent 49 minutes to mark the 4 minutes of rice cooking!

To determine the minimum time, note that the marked time is obtained by subtracting a multiple of 9 from a multiple of 7 or vice versa. Thus, the total time is either a multiple of 7 plus 4 or a multiple of 9 plus 4. Analyzing the multiples of 9: 9, 18, 27, ...; we notice that 18 is the first of them that leaves a remainder of 4 when divided by 7, and indeed we showed at the beginning that we can mark the desired time in 18 minutes. Analyzing now the multiples of 7: 7, 14, 21, ...; we can see that the first of them that leaves a remainder of 4 when divided by 9 is 49. Since $49 > 18$, the minimum time is 18 minutes.

Notice also that the analysis above allows us to obtain other ways to mark 4 minutes, for example, since $9 \cdot 9 = 81$ leaves a remainder of 4 when divided by 7, we can obtain the multiple $11 \cdot 7$ of 7 and write $9 \cdot 9 - 11 \cdot 7 = 4$. It would suffice to use the 9-minute hourglass 9 times and the 7-minute hourglass 11 times. The total time spent would be 81 minutes!

b) Since 6 and 10 are even, the differences of their multiples are even numbers and consequently, only even times can be marked. Therefore, it is not possible to mark 9 minutes because 9 is odd.