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

MouseHunt Math Quiz #2: Hunting Strategy

* MICE

there are unlimited numbers of mice but there are only two breeds of mice, white and brown.

a white mouse will give you 50 points and 75 gold.
a brown mouse will give you 150 points and 25 gold.

75% of mouse population are white.

on average, one mouse, randomly, visits your camp every hour. but only cheese can attracts the mouse to your trap. you can

place only one cheese at a time on your trap. unfortunately, there are only two kinds of cheese.

* CHEESE

a cheddar costs 5 gold.
a brie costs 50 gold.

cheddar has a 50% probability of attracting a white mouse (to the trap) and 25% probability of attracting a brown mouse.
brie has a 25% probability of attracting a white mouse and 75% probability of attracting a brown mouse.

* TRAP

there are also only two kinds of traps. you already have both traps in possession. after you cheese successfully attracts a mouse, it is now the job of your trap to catch it.

glue has a 50% probability of catching a white mouse and 25% probability of catching a brown mouse.
deathbot has a 25% probability of catching a white mouse and 75% probability of catching a brown mouse.

* LOCATION

there are also only two locations.

in the town, if you successfully attract a mouse but fail to catch it, you lose just the bait (just one piece of cheese).

in the lab, there is 220% gold bonus (for example, 240 gold for white mouse) but if you fail to catch it. the mouse will steal something in addition to the bait:
a white mouse -> 20% steals 500 gold, 80% steals 5 points.
a brown mouse -> 80% steals 250 gold, 20% steals nothing else than the bait.

traveling is free.

you start with a large number of gold.

* QUESTION

as a hunter, what is your hunting strategy if you want to maximize points but do not want to lose gold in the long run?

* UPDATE (Clarification)

1. no mixing two cheeses together to create a new kind of cheese
2. no mixing two traps together to create a new kind of trap
3. you can assume no staleness should cheese fails to attract a mouse.
4. if the bait successfully attracts a mouse, the bait (cheese) will be gone, no matter you can catch it or not.
5. you can use only one trap and one cheese at a time.
   

---

* SOLUTION

step 1: establish understanding

note that there are three possible outcomes:
1) fail- fail to attract a mouse
2) catch- successfully catch a mouse
3) steal- a mouse steals your cheese (and probably something else)

step 2: calculate hunting results probabilities

(lab/cheddar/deathbot example)

brown mouse calculation:

a cheddar has 25% attraction rate to brown mice, and deathbot has 75% success rate to catch a brown mouse.

fail% = 100% - attraction rate = 75%
catch% = successful attraction and successful catch = 25% * 75% = 18.75%
steal% = successful attraction but unsuccessful catch = 25% * (100% - 75%) = 6.25%

similarly, white mouse calculation:

fail% = 50%
catch% = 12.5%
steal% = 37.5%

overall mouse hunting results probabilities:

note that brown mice account for 25% and white mice account for 75%.

brown mouse fail% = 25% * 75% = 18.75%
brown mouse catch% = 25% * 18.75% = 4.6875%
brown mouse steal% = 25% * 6.25% = 1.5625%
white mouse fail% = 75% * 50% = 37.5%
white mouse catch% = 75% * 12.5% = 9.375%
white mouse steal% = 75% * 37.5% = 28.125%

what does this mean? this means that every 100 hours, you can expect 18.75 times, on average, that you fail to catch a brown mouse.

step 3: calculate hourly-average stats (or per-mouse stats)

(lab/cheddar/deathbot example)

net points and profit (gold) are two important derived variables.

revenue is generated only when you successfully catch a mouse (220% bonus at lab)
cheese cost incurs only when a mouse is successfully caught or it steals your cheese
steal cost incurs only when a mouse steals your gold

revenue = brown catches + white catches = (25*320%*4.6875%) + (75*320%*9.375%) = 26.25 gold
cheese cost = brown catches + brown steals + white catches + white steals = 5 * (4.6875%+1.5625%+9.375%+28.125%) = 2.1875 gold

steal cost = brown steals + white steals = (250*80%*1.5625%) + (500*20%*28.125%) = 31.25 gold

profit = revenue - cheese cost - steal cost = -7.1875 gold (loss)

points earned = brown catches + white catches = (150*4.6875%) + (50*9.375%) = 11.71875 points

points stolen = white steals = 5*80%*28.125% = 1.125 points

net points = points earned - points stolen = 10.59375 points


step 4: Set up optimization model

Please note that you are free to change trap/cheese/location at any time.
So you should set time-allocation strategy wisely.

location	cheese	trap	profit	net point	time allocation
town	cheddar	glue	12.265625	11.71875	x1
town	cheddar	deathbot	6.015625	11.71875	x2
town	brie	glue	-10.546875	11.71875	x3
town	brie	deathbot	-11.71875	23.4375	x4
lab	cheddar	glue	15.9375	10.96875	x5
lab	cheddar	deathbot	-7.1875	10.59375	x6
lab	brie	glue	-30	11.34375	x7
lab	brie	deathbot	-19.6875	22.875	x8

Objective: maximize points; 11.71875x₁ + 11.71875x₂ + … + 22.875x₈

Constraints:

• sum of time allocation is 100%; x₁+x₂+…+x₈ = 1
• time allocation is between 0 and 100%; 0 <= x₁, x₂, …, x₈ <=1
• profit is non negative; 12.265625x₁ + 6.015625x₂ - … - 19.6875x₈ >= 0

This is a linear programming model. You can run it on Excel (Solver add-in) or use matrix algebra like the Simplex method. If you'd like, you can exclude x₂ from the model because x₁ is always a better choice (and so on).

The model result: x₄ = 57.6271%, x₅ = 42.3729%, other x's = 0%.

step 5: ANSWER

you should spend about 57.63% of the time in the town using brie/deathbot to earn points and about 42.37% of the time in lab using cheddar/glue to recover gold. The hourly- average points (or points per mouse) = 18.1541 points. The hourly-average profit = 0.00 gold.

This solution is better than town/cheddar/glue alone in terms of net points earned.

MouseHunt Math Quiz #1: Combinatorics

Question:
There are P possibilities that ten different hunters are hunting ten different mice.
There are Q possibilities that ten different hunters are hunting ten identical mice.
P+Q = ?

Example:
There are 20 possibilities that 3 different hunters are hunting 3 identical mice.
There are 64 possibilities that 3 different hunters are hunting 3 different mice (see below).

3 identical mice and 3 different hunters, namely (A, B, C).
possibility 1: (0, 0, 0) no mouse is caught at all
possibility 2: (1, 0, 0) hunter A catches a mouse
possibility 3: (0, 1, 0) hunter B catches a mouse
possibility 4: (0, 0, 1) hunter C catches a mouse
possibility 5: (1, 1, 0) hunter A and B catch a mouse each
possibility 6: (1, 0, 1) hunter A and C catch a mouse each
possibility 7: (0, 1, 1) hunter B and C catch a mouse each
possibility 8: (1, 2, 0) hunter A catches a mouse and hunter B catches 2 mice
possibility 9: (1, 0, 2) hunter A catches a mouse and hunter C catches 2 mice
possibility 10: (2, 1, 0) hunter B catches a mouse and hunter A catches 2 mice
possibility 11: (0, 1, 2) hunter B catches a mouse and hunter C catches 2 mice
possibility 12: (2, 0, 1) hunter C catches a mouse and hunter A catches 2 mice
possibility 13: (0, 2, 1) hunter C catches a mouse and hunter B catches 2 mice
possibility 14: (2, 0, 0) hunter A catches two mice
possibility 15: (0, 2, 0) hunter B catches two mice
possibility 16: (0, 0, 2) hunter C catches two mice
possibility 17: (3, 0, 0) hunter A catches all the mice
possibility 18: (0, 3, 0) hunter B catches all the mice
possibility 19: (0, 0, 3) hunter C catches all the mice
possibility 20: (1, 1, 1) hunter A, B and C catch a mouse each

3 different mice (x, y, z) and 3 different hunters (A, B, C).
possibility 1: no mouse is caught at all
possibility 2: hunter A catches mouse x
possibility 3: hunter A catches mouse y
possibility 4: hunter A catches mouse z
possibility 5: hunter B catches mouse x
possibility 6: hunter B catches mouse y
possibility 7: hunter B catches mouse z
possibility 8: hunter C catches mouse x
possibility 9: hunter C catches mouse y
possibility 10: hunter C catches mouse z
possibility 11: hunter A catches mouse x and y
possibility 12: hunter A catches mouse x and z
possibility 13: hunter A catches mouse y and z
possibility 14: hunter B catches mouse x and y
possibility 15: hunter B catches mouse x and z
possibility 16: hunter B catches mouse y and z
possibility 17: hunter C catches mouse x and y
possibility 18: hunter C catches mouse x and z
possibility 19: hunter C catches mouse y and z
possibility 20: hunter A catches mouse x and hunter B catches mouse y
possibility 21: hunter A catches mouse x and hunter B catches mouse z
possibility 22: hunter A catches mouse y and hunter B catches mouse x
possibility 23: hunter A catches mouse y and hunter B catches mouse z
possibility 24: hunter A catches mouse z and hunter B catches mouse x
possibility 25: hunter A catches mouse z and hunter B catches mouse y
possibility 26-31: hunter A and hunter C catches one mouse each
possibility 33-37: hunter B and hunter C catches one mouse each
possibility 38-40: a hunter catches all the mice
possibility 41-43: hunter A catches two mice and hunter B catches the last one
possibility 44-46: hunter A catches two mice and hunter C catches the last one
possibility 47-49: hunter B catches two mice and hunter A catches the last one
possibility 50-52: hunter B catches two mice and hunter C catches the last one
possibility 53-55: hunter C catches two mice and hunter A catches the last one
possibility 56-58: hunter C catches two mice and hunter B catches the last one
possibility 59-64: each hunter catches a mouse

---

Solution:

This quiz is all about combinatorics. Read more here:
http://en.wikipedia.org/wiki/Combinatorics

P = 11^10
P is quite easy. Each mouse has 11 possibilities (not caught at all, caught by hunter#1, .., caught by hunter#10). 10 mice -> 11^10

Q = Combination (20, 10) = Factorial (20) / (Factorial (10)*Factorial(10)) = (20*19*18*17*..*11) / (10*9*8*...*1)

http://en.wikipedia.org/wiki/Stars_and_bars_(probability)

It is like you have 10 stars (10 mice) and 10 bars (10 hunters + one fake hunter for mice that are not caught at all).