Univ Studies 3: Cyber-Puzzlers -- Fall 2013

• Class meetings
• Lectures: Friday 11-11:50am in Donald Bren Hall 1431
• Note: there is no class on November 8, 2013, because of the instructor needing to attend the 2013 ACM GIS conference.
• Note: there is no class on November 29, 2013, because of Thanksgiving

• Instructor
• Professor Michael Goodrich -- goodrich (at) uci.edu

• Class Requirements
• no homeworks or examinations
• grades are given based on class participation, i.e., attendence and discussion

• Course Goals
This seminar explores problem solving and critical thinking through the study of puzzlers and brain teasers, focusing on problems related to computer science, which are typically used as interview questions for such companies as Google and Microsoft.
Problem solutions need only high school mathematics and logic.

• Sample problems
• It is said that potatoes are 99% water and 1% potato. So, say you take a bunch of potatoes, like 100 pounds of potatoes, and you set them out on your back porch to dry out. As they begin to dry out, the water starts to evaporate. And after a while enough water has evaporated so that the potatoes are now 98% water. If you were to weigh those potatoes at that moment when they are 98% water, how much would they weigh?
• Three different numbers are chosen at random, and one is written on each of three slips of paper. The slips are then placed face down on the table. The objective is to choose the slip upon which is written the largest number. Here are the rules: You can turn over any slip of paper and look at the amount written on it. If for any reason you think this is the largest, you're done; you keep it. Otherwise you discard it and turn over a second slip. Again, if you think this is the one with the biggest number, you keep that one and the game is over. If you don't, you discard that one too, in which case you're stuck with the third one.
The chance of getting the highest number is one in three. Or is it? Is there a strategy by which you can improve the odds?
• How can you identify the one heavy coin out of fifty in just four weighings using a balance scale?
• In how many ways can you change one dollar (allowing pennies, nickels, dimes, quarters, half dollars)?
• At one point, a remote island's population of chameleons was divided as follows: 13 red chameleons, 15 green chameleons, 17 blue chameleons. Each time two different colored chameleons would meet, they would change their color to the third color. Is it ever possible for all chameleons to become the same color? Why or why not?

Michael Goodrich
Computer Science Department
University of California, Irvine, CA 92697-3435
goodrich at ics.uci.edu