CSE Blog - quant, math, computer science puzzles

Source: Tanya Khovanova’s Math Blog Problem: The Sultan decided to test the wisdom of his wizards. He collected them together and gave them a task. Tomorrow at noon he will put hats of different colors on each of the wizard’s heads. The wizards have a list of the available colors. There are enough hats of each color for every wizard. The wizards also have a list of rooms. There are enough rooms to assign a different room for every color. Tomorrow as the Sultan puts hats on the wizards, they will be able to see the colors of the hats of the other wizards, but not the color of their own. Without communicating with each other, each wizard has to choose a room. The challenge comes when two wizards have the same hat color, for they must choose the same room. On the other hand, if they have different hat colors, they must choose different rooms. Wizards have one day to decide on their strategy. If they do not all complete their task, then all of their heads will be chopped off. What str...

Source: Australian Mathematical Society Gazette Puzzle Corner Problem: There are coins of various sizes on a table, with some touching others. As often as you wish, you may choose a coin, then turn it over, along with every other coin that it touches. If all coins start out showing heads, is it always possible to change them to all tails using these moves? Update (Nov 15, 2010): Solution: Solution from the gazette author posted by me in comments! Interesting linear algebra solution posted by Siddhant Agarwal (EE, Senior Undergraduate, IITB) in comments!

Source: Australian Mathematical Society Gazette Puzzle Corner Problem: An optimist and a pessimist are examining a sequence of numbers. The optimist remarks, ‘Oh jolly! The sum of any eight consecutive terms is positive!’ But the pessimist interjects, ‘Not so fast, the sum of any five consecutive terms is negative.’ Can they both be right? How long can this sequence of numbers be? Incentive: Treat at H8 Canteen/Sodexho Cafeteria for the first person to solve it :P Update (27/07/10): Solution: Posted in comments by Varun Jog (Berkeley Grad Student, EE IITB Alumnus) and Siddhant Agarwal (EE Senior Undergraduate, IITB)

Source: Plus Magazine Issue 55 Problem: Let's witness a game. The game involves flipping a coin, which you assume has equal probability of coming up heads or tails. The game is played by two players, A and B, who each select a sequence of three flips. For example, assume that Player A selected "heads-heads-heads" (HHH) and Player B has selected "tails-heads-heads" (THH). Then the coin is flipped repeatedly, resulting in a sequence like the following: HTHTHHHHTHHHTTTTHTHH... The player whose sequence showed up first (HHH for Player A or THH for Player B) is declared the winner. A chooses first and you have to help B. Show that given what A has chosen, B can always choose a sequence such that B is in a better position than A. For example: If A chooses HHH, B chooses THH to make sure that now it has 7/8 probability to win. Update (27/07/10): Solution: Posted in comments by me!

Source: CMU Spring 2010 Course on Great Theoretical Ideas in Computer Science Problem: 10% of the surface of a sphere is colored green, and the rest is colored blue. Show that no matter how the colors are arranged, it is possible to inscribe a cube in the sphere so that all of its vertices are blue. Hint: Use probabilistic analysis. Consider a random cube and calculate the expected number of vertices that are blue. (Update 23/06/10): Solution: Posted by connect2ppl - Giridhar Addepalli (CSE, IITK alumnus and Yahoo! Sr. Software Engineer) in comments!

Source: 2010 Euler math Olympiad in Russia to Eighth graders. The author of the problem is Alexander Shapovalov Problem: Among 100 coins exactly 4 are fake. All genuine coins weigh the same; all fake coins, too. A fake coin is lighter than a genuine coin. How would we find at least one genuine coin using two weighings on a balance scale? By the way, ten eighth grade students in Russia solved this problem during the competition. :P Best of Luck! I am sure solving this problem will make you happy :) Update(26-06-10) Solution: Posted by Nikhil in comments!

Source: Gazette of the Australian Mathematical Society Problem: A balance scale sits on the teacher’s table, currently tipped to the right. There is a set of weights on the scales, and on each weight is the name of at least one student. The teacher chooses a set of students to enter the classroom. One by one, each chosen student will move each weight carrying his or her name to the opposite side. Prove that the teacher can always choose a set of students to tip the scales to the left. Update (June 17, 2010) Solution: Posted by me in comments!