Problem of the Month for February, 2007

Problem:

Seven pennies all lie heads-up in a straight line on a table. You are allowed to make the following type of move: choose any four of these pennies (but you must choose exactly four of them) and flip those four pennies over. Using a sequence of such moves (flipping exactly four at a time), can you get all seven pennies to lie tails-up on the table? If so, show how and explain whether or not your method is most efficient (in terms of taking the fewest total number of moves). If not, explain why not.

Possible Extensions/Generalizations to consider:

Suppose all seven pennies are heads-up and that you are allowed to make the following type of move: choose any five of these pennies (but you must choose exactly five of them) and flip those five pennies over. Using a sequence of such moves (flipping exactly five at a time), can you get all seven pennies to lie tails-up on the table? If so, show how and explain whether or not your method is most efficient (in terms of taking the fewest total number of moves). If not, explain why not. What if you have n pennies that are all heads up and you are allowed to flip exactly i (with i < n) of them in each move. Are there conditions on the values of i and n that will allow you to decide whether or not you can convert, through a sequence of such moves, all the heads to tails or not? Can you use a sequence of such moves (say, exactly 5 at a time) to go from the arrangement HHTHHTH to THHHHHH? Show how (and discuss efficiency) or explain why not.

Rules

1. You must be a Bethel University student during the given month.
2. Your solution should be written in complete sentences (at least if you want to win) and either typed or written very neatly by hand. Equations and diagrams may be included by hand or by computer as necessary.
3. Your solution must be turned in to P.O. 95 by 4 PM on the last day of classes of the given month.
4. The winner will be the person who does the best job answering the problem as judged by a faculty member of the math and computer science department. If more than one person answers the problem correctly, the person who does the best job in communicating their solution and/or considering generalizations of the given problem will win. If no one answers the problem correctly, the best attempt will win.
5. Do not put your name on your solution paper. Instead, put your Bethel ID number in the top right corner of your solution paper.

Suggestions

1. Be thorough, yet concise. Be sure to answer the question completely and in such a way that clearly communicates your solution, while at the same time being as efficient in your communication as possible.
2. If you think other people will also answer the question correctly and are also good writers, you can increase your chances of winning by considering and writing about possible generalizations of the given problem and the solutions to those generalizations. However, a correct answer to the original problem that does not consider generalizations will beat out an incorrect answer to the original problem that does consider generalizations. In short, make sure your answer to the original problem is correct before considering any generalizations.
3. Neatness counts. Grammar and spelling count. When relevant, pictures are helpful.
4. Explicitly state any assumptions you are making. If you are unsure whether a particular assumption is "allowed", say so in your write-up but then answer the question by either making the assumption in question or by stating why you think you can't or shouldn't make the assumption.

Prizes and Benefits

1. Your picture and a short biographical sketch will be posted, as well as your solution, for all to admire. This will be done temporarily in the math and computer science hallway, and, perhaps, for as long as Bethel exists on the internet. You can inspire and show your accomplishment to your friends, children, grandchildren, your future bosses, and more!
2. You will win a $25 gift certificate from House of Wong restaurant.
3. You will earn some extra credit in your math and computer science courses of the given month (amount to be determined by your professor).
4. You might be able to get an extension on an assignment for your math/cs courses if you are working on the problem of the month (discuss this with your professor).