By Department of Mathematics
Editor’s Note: The Department of Mathematics at Gettysburg College hosts a problem of the week challenge to determine each semester’s Paul Mugabi problem-solving award recipient(s). Each week’s entries are scored by a panel of faculty judges, and winner(s) from each week will receive a Problem Of the Week (P.O.W.) button. The Gettysburgian is not involved in or responsible for accepting or evaluating students’ submissions to this contest.
The contest is open to all Gettysburg College students. Up to three people may work together on a submission. Make sure your name is on your submission and that any sources are properly cited! Send solutions to email@example.com or put solutions in the marked envelope in the hallway outside Glatfelter 215. This problem was posted on Friday, February 1 and solutions are due on Friday, February 8 by 5:00 p.m.
Every night I feed my pet walrus exactly one of the following for dinner: fish, pizza, or tacos. My walrus loves pizza and tacos, but fish are better for him, so I adhere to the following rule: if I feed my walrus something other than fish on any particular night, I will feed him fish the following night. (If I feed my walrus fish on any particular night, I can give him anything the following night).
According to the above rule, then, the following is a valid “10-night menu”:
F, P, F, F, T, F, F, T, F, P
The following is not a valid “10-night menu”:
F, P, T, F, T, F, F, T, T, F
How many valid 10-night menus are there? If n is a positive whole number, how many valid n-night menus are there?
If you’re feeling adventurous, generalize to the case where there are k “unhealthy” options (that is, k things other than fish that I might feed my walrus).