Posts

Conway's Soldiers (CheckerBoard Unreachable Line)

Source: Asked to me by Amol Sahasrabudhe (Morgan Stanley Quant Associate) Problem: An infinite checkerboard is divided by a horizontal line that extends indefinitely. Above the line are empty cells and below the line are an arbitrary number of game pieces, or "soldiers". A move consists of one soldier jumping over an adjacent soldier into an empty cell, vertically or horizontally (but not diagonally), and removing the soldier which was jumped over. The goal of the puzzle is to place a soldier as far above the horizontal line as possible. Prove that there is no finite series of moves that will allow a soldier to advance more than four rows above the horizontal line. I could get the correct direction in 5 min. Spent enough time on the problem but could not solve it. :( Give it a go! \m/ Update: Sep 07, 2010 Solution: Posted by Siddhant Agarwal (Senior Undergraduate, Elec IITB) in comments!!

Magic Money Machine

Source: CMU Puzzle Toad Problem: The wizards at Wall Street are up to it again. The Silverbags investment bank has invented the following machine. The machine consists of 6 boxes numbered 1 to 6. When you first get the machine, it contains 6 tokens, one in each box. You have two buttons A, B on the machine and you can press them as many times as you like and in any order. Button A Choose a number i from 1 to 5 and then take one token from box i and magically two tokens will be added to box i + 1 . Button B Choose a number i from 1 to 4 and then take one token from box i and then the contents of boxes i + 1 and i + 2 will be interchanged. The machine sells for one trillion dollars. The contract says that you can take the machine back to the bank at any time and then the bank will give you one dollar for each token in the machine. Is the machine worth buying? Update (Nov 10, 2010): This problem is an IMO 2010 Problem. Solution available at artofproblemsolving lin...

Number of Sons

Problem: A man has two children. He says one of them is a son. What is the probability that the other one is also a son? (Hint: Answer is not 0.5 :P) I have read this problem many times in many different forms. But still looks fresh :P Solution: Read the wikipedia article of a famous and related problem ( Link )

Puzzle on Sorting

Source: Saurabh Joshi's Blog Problem: (copy-pasting from the source) Suppose we have 13 cards arranged in descending order: K Q J 10 9 8 7 6 5 4 3 2 1 At any move, you can take a substring of cards and move it elsewhere. For example, 10 9 8 could be move to the right by 2 steps to get K Q J 7 6 10 9 8 5 4 3 2 1. The goal is to sort the string in increasing order minimize the number of such moves. It must be absolutely obvious that you can do it with 12 moves but the very fact that I’m asking you this question means that you can do better. How many moves do you need? Now the obvious extension to this problem is to generalize this technique for any n. Awesome Problem!! Update (Sep 07, 2010): Solution: At Saurabh Joshi's blog ( Link )

Hats and Rooms

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...

Coin conundrum

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!

Differing views

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)