MouseHunt Math Quiz #3: 'Orny 'Unting

* HUNTERS

There is a group of five mouse hunters. They are you, John, Joe, Jack and Jim (in order of seniority - you are the most senior). You guys are hanging out at night in the mountain.

* HUNTER'S HORN

The five hunters share the same Hunter's Horn. Only when this Horn is sounded, a mouse visits each hunter's trap, and on average (per mouse visit) awards you 199 points. The Horn cannot be sounded again until 15 minutes after previous sounding.

When you sound a horn, you get a courage award of [hunting size]*100 points. The hunting size is determined by the number of active hunters in your hunting group. A hunter is active for 60 minutes after the last time he "visits" the Horn (no matter he sounds the horn or not).

* EXAMPLE

For illustration, John visits and sounds the Horn at 9:45. Joe visits the Horn at 9:50 and cannot sound the Horn because it is just 5 minutes after previous sounding. So, John is active from 9:45 to 10:44, and Jack is active from 9:50 to 10:49. If no one else is active and you sound the Horn between 10:00 and 10:44 (inclusive), then the hunting size is 3 (you and John and Joe) and you can expect 300+199 points from this hunting. Later if anyone sounds the Horn while you are still being active, you can expect 199 points from each sounding too.

* THE AGREEMENT

OK Now it is so late. You are going to your own tent. So are your friends. But because you guys are so addicted to mouse hunting.... that each of you agrees to wake up at their wish and visit the Horn exactly four times between 1:00 AM and 8:00 AM (inclusive). Very sleepy, your friends will wake up, visit the Horn, sound it if possible, and then go back to bed immediately. If more than one person visit the Horn at the same time, the most senior one will sound the Horn.

* THE PROPHECY

Fortunately, you are a fortune teller and can tell the exact times that your friends will visit the Horn. This is your prophecy:

Wake-up times:

John: 1 AM, 3 AM, 4:45 AM, 6:30 AM
Joe: 1:30 AM, 1:45 AM, 2:30 AM, 5:15 AM
Jack: 3:15 AM, 3:45 AM, 6 AM, 7 AM
Jim: 2 AM, 3 AM, 3:15 AM, 4:45 AM

* OBJECTIVE

You too, have only four chances to visit the Horn (because of the agreement). However, you are not sleepy at all. You look forward to earn as many points as possible.

* QUESTION

What are the four times between 1:00 AM and 8:00 AM (inclusive) that you should visit the Horn?

* UPDATE (Clarification)

• only John is active as of 1 AM (he sounds the Horn at that time).
• the last time that the Horn was sounded is a long time ago.

---

* SOLUTION

1. Set up time line when each hunter will sound (please see the following table). Who will eventually sound it is not important.
2. Calculate hunting size (including yourself).
3. Determine whether or not this time is horn time by other people (Column "Horn time"; Y=Yes; N=No).
4. Calculate courage points if you sound the horn yourself (Courage pts = Hunting size * 100).
5. Calculate active points if you are still active at the time and somebody else sounds the horn (Active pts = if Horn time = 'Y' then 199 else 0).
6. Calculate total points if you sound the horn at the exact times. For example, if you sound the horn at exactly 1:15, you will get courage points of 200 plus active points til 2:14 (199 at 1:30+199 at 1:45+199 at 2:00).
7. Calculate total points if you sound the horn a bit later than the times in the first column (1-14 minutes late). Examples:
   
• If you sound the horn at 1:16, you will get courage points of 200 plus active points from 1:31 til 2:15 (199 at 1:45 + 199 at 2:00 + 0 at 2:15). Please note that Joe will be unable to sound the horn at 1:30; thus, you cannot collect active points at 1:30.
  
• You cannot sound the horn a bit late than 1:00 (that is, 1:01 to 1:14). This is because John will sound it at 1:00. You have to wait for 15 minutes after the previous sounding.
  
8. Optimize.

Please note that Pts (exact time) and Pts (a bit late) columns are assuming that you do not sound the horn more than once within an hour. One way to solve it is ignoring the that assumption and conducting a brute-force search. But this case is a bit obviously easy, as there are not many times that give higher points than 600.

We can try a bit of greedy algorithm. Start with selecting four highest total points (in red). You can see that 3:00 and 3:15 are two times within an hour. You should get rid of one of the two times. If you get rid of 699, the best replacement is 598 (any time between 4:16 and 4:30). But if you get rid of 798, the best replacement is 698 at 2:15. The latter is a better replacement. You can also see that this is already optimized as further replacements will do more harms than good.

* ANSWER

The four times are:

• 1:15
• 2:15
• 3:15
• between 5:31 and 5:44

Total points earned = 797+698+699+798 + (199*4 from hunts when you sound the horn yourself) = 3788 points.

199*4 does not affect the optimization process at all because you will sound the horn four times anyway. This is fixed.

Time	John	Joe	Jack	Jim	Hunting size	Horn time	Courage pts	Active pts	Pts (exact time)	Pts (a bit late)
1:00	Sound				2	Y	200	199	598	-99999
1:15	Active				2	N	200	0	797	598
1:30	Active	Sound			3	Y	300	199	698	-99999
1:45	Active	Sound			3	Y	300	199	698	-99999
2:00		Active		Sound	3	Y	300	199	499	-99999
2:15		Active		Active	3	N	300	0	698	698
2:30		Sound		Active	3	Y	300	199	698	-99999
2:45		Active		Active	3	N	300	0	698	698
3:00	Sound	Active		Sound	4	Y	400	199	798	-99999
3:15	Active	Active	Sound	Sound	5	Y	500	199	699	-99999
3:30	Active		Active	Active	4	N	400	0	599	400
3:45	Active		Sound	Active	4	Y	400	199	400	-99999
4:00			Active	Active	3	N	300	0	499	499
4:15			Active		2	N	200	0	399	598
4:30			Active		2	N	200	0	598	399
4:45	Sound			Sound	3	Y	300	199	499	-99999
5:00	Active			Active	3	N	300	0	499	499
5:15	Active	Sound		Active	4	Y	400	199	599	-99999
5:30	Active	Active		Active	4	N	400	0	599	798
5:45		Active			2	N	200	0	598	399
6:00		Active	Sound		3	Y	300	199	499	-99999
6:15			Active		2	N	200	0	598	399
6:30	Sound		Active		3	Y	300	199	499	-99999
6:45	Active		Active		3	N	300	0	499	300
7:00	Active		Sound		3	Y	300	199	300	-99999
7:15	Active		Active		3	N	300	0	300	300
7:30			Active		2	N	200	0	200	200
7:45			Active		2	N	200	0	200	200
8:00					1	N	100	0	100	100