1) 100 blk and wht socks, how many to pull out before guaranteed a pair? 2) 3 boxes with Blk,wht,blk/wht balls. All are labelled incorrectly. What is the min number of balls that need to be pulled before you can relabel the boxes? 3) 2 strings burn continuously and reversibly in 1 min. Have unlimited matches. How to measure 45 sec? 4) Circular table and quarters to be placed non overlappingly on table. You alternate with opponent. Last person to place a quarter on the table wins. Do you want to start or go second? 5) How many zeros at the end of 1000! ? 6) Deck of cards. 5 cards randomly picked. You can have a decoding system with your partner. You transfer 4 cards to the partner and he after looking at the 4 cards must guess your card. 7) 10 balls on a balance, one is heavier. You have 2 weighings, can you determine the heavier ball, if so how? 8) 12 balls, 3 weighings. One has different weight. Can you determine which one, if so how? 9) 3 doors, behind one a prize. You pick a door. I open one of the other doors that is empty. Do you now want to switch doors? 10) Arrange 6 match sticks so that 4 equilateral triangles are formed. 11) You are given 13 coins, 12 genuine and 1 counterfeit. It is given that the counterfeit coins and genuine coins have different weights. You are also given a scale which when given a pair (A,B) of disjoint subsets of the 13 coins returns how the weights of A and B compare (equal, greater, or less). If you are allowed at most 3 uses of the scale, how would you determine which coin is counterfeit? Can you generalize this problem? (With an appropriately generalized solution, of course!) 14) A chessboard can be tiled with 32 dominos. Suppose we remove the left top and right bottom corner of the board. Can the remaining 62 squares be tiled by 31 dominos? 15) You are given a bar of chocolate with 50 squares (5 x 10). What is the minimum number of breaks necessary to break the bar into 50 individual squares? A bar (or a piece of it) can only be broken along a straight line that runs from one side to the other. Pieces cannot be stacked while breaking. 16) Given two positive numbers, what is the probability that they are relatively prime? (Assume a uniform distribution.) 17) Show that a path on an m by n square grid which starts at the northwest corner, goes through each point exactly once, and ends at the southeast corner divides the grid into two equal halves: (a) those regions opening north and east; and (b) those regions opening south or west. 18) Adam, Rajit, Rob and Rohit are sitting on the beach at Malibu around 3am. Rob: "I just picked two integers greater than one." "Adam, their sum is ..." (he whispers it to Adam). "Rohit, their product is..." (he whispers it to Rohit). Adam: "Rohit, we don't know the numbers." Rohit: "Now I do." Adam: "Me too". Rajit, what were the numbers? 19) Person A and B play the following game. Person A makes a bet of x dollars on heads or tails. Person B then tosses a fair coin. If the outcome matches A's guess, A receives 2x dollars; otherwise, A loses his bet. Consider the following strategy for A: x:=1 initially; if win, then x:=1; otherwise x:=x*3. Now, if A wins at any point, he makes a profit. This means that A will always make a profit. What (if anything) is wrong with this strategy? 20) There are 100 light bulbs and 100 people, both numbered from 1 to 100. Initially, all the light bulbs are off. Person number k toggles all the light bulbs that are divisible by k. For example, person 2 toggles bulbs 2, 4, 6, ..., 100. After all 100 people have finished toggling the light bulbs, which light bulbs are on? 21) Four cars that all move with the same speed of 60 mph start off at the four corners of a square of side 1 mile. Label the cars in clockwise order 1,2,3,4. At every instant, car 1 moves in the direction of car 2, car 2 in the direction of car 3, car 3 in the direction of car 4 and car 4 in the direction of car 1. Where will the cars eventually meet and how far will each car have travelled. 22) 50 disks are stacked on a peg in decreasing size (the largest on the bottom). Two empty pegs A and B are available. How many moves need to be made to transfer all the disks onto peg A if at no time a larger disk can be placed on top of a smaller one. 23) This is a game for 2 players. There are three stacks of coins. The players take it in turns to remove some number of coins (greater than zero) from only one of the stacks. a) the stacks contain 19,8, and 22 coins. Do you want to play first and if so, what is your move and why? If not, what is your strategy? b) the stacks contain 19,7, and 22 coins. Do you want to play firsr and if so, what is your move and why? If not, what is your strategy? Can you generalize to N stacks. With three stacks, the game is called NIM. 24) The queens puzzle: There are 100 men and women in the island and a queen. The queen declares that at least one husband is unfaithful. There is no conversation between women. However every woman sees that all other husbands are unfaithful. Queen says that if you find that your husband is unfaithful, you may kill at exactly midnight on the day that you find out. What happens in this society? 25) In a room of 100 politicians, at least 1 is honest and in every pair, at least one is dishonest. How many honest politicians are there, if every politician is either honest or dishonest. 26) An archaelogist and his assistant are working. The assistant makes a great find, and thinking that he will get a promotion boasts it off to his master. Look here is a Roman coin: one side had 44 BC printed on it and one had an imprint of an olive tree. The archaelogist immediately fired the assistant. Why? 27) I started up a hill at sunrise and arrived at the top at sunset. The next day at sunrise I started back down and reached the bottom at sunset. If the sun rises and sets at tghe same time every day, is there a point in time where I was at the same place on my upward as well as downward journey? 28) In a chess board with 64 by 64 squares, how many squares of any size can be formed? 29) Which is larger, e^pi or pi^e? 30) What is the probability that if you cut a stick at 2 arbitrary places you can form a triangle? 31) Write code to swap two variables A, and B without using a third variable. 32)