A king has 10 fools. Each fool amuses the king by weeks that start and end at Sunday midnight, whereby for every , there exists a fool whose every two consecutive working weeks are separated by exactly free weeks. When no fool is present, the king feels bored. How many consecutive days at most is it possible to avoid the king feeling bored under such circumstances?
Solution
Let be a work schedule of the fools that enables the maximum number of consecutive joyful weeks. If 2 and 4 have a common working week then every working week of 4 is also a working week of 2. Consecutively, in the schedule obtained from by shifting the working weeks of 4 by one week, all weeks that are joyful in are still joyful. Analogously, if 8 shares a working week with 2 or 4 then the working weeks of 8 can be shifted so that they would not coincide with that of 2 or 4 while no joyful week would be lost. Thus, without loss of generality, assume that the working weeks of 2, 4 and 8 do not coincide in . Then precisely every 8th week has the property that noone of 2, 4 and 8 is working.
As 3 and 8 are coprime, 3 covers every 3rd of the weeks during which noone of 2, 4 and 8 is working. Analogously to what was done above, assume without loss of generality that the working weeks of 6 do not coincide with that of 2 or 3. Then also 6 covers every 3rd of the weeks during which noone of 2, 4 and 8 is working and precisely every 24th week has the property that noone of 2, 3, 4, 6 and 8 is working. Call these weeks suspicious.
Analogously to that was done above, assume without loss of generality that 9 covers some suspicious week. As , he covers every 3rd suspicious week. Also assume that 5 and 10 do not have common working weeks. As , each of them covers every 5th suspicious week. Also, 7 and 11 cover every 7th and every 11th suspicious week, respectively. Hence we are facing a subproblem that considers only the suspicious weeks and the schedule is made for one 3, two 5s, one 7 and one 11.
The relative position of the working weeks of one 3 and one 5 is not important (by Chinese remainder theorem). By symmetry, there are only two in principle different ways to insert the second 5: he is shifted with respect to the other 5 either by one or by two suspicious weeks. Correspondingly, we get the following schedules (where denotes suspicious weeks during which either 3 or one of the 5s is working and denotes the remaining suspicious weeks):
As 7 and 15 are coprime, each of the schedules (1) and (2) gives rise to only one schedule with 7 (by Chinese remainder theorem again). These are
respectively.
Adding 11 to schedule (1') leads to maximum 8 consecutive covered suspicious weeks, but adding it to schedule (2') gives maximum 11 of them. Thus, the maximum distance of two uncovered suspicious weeks is weeks and the corresponding number of consecutive joyful weeks is 287. Then the king can avoid feeling bored during days.