Art of Puzzle Solving



Summary of the deck

What is puzzle solving? Solving math puzzles really reflects training of the mind. It is not about smartness, intelligence or IQ; it is about how well you have trained your mind to solve problems.

How to train your mind. When you see a puzzle, ask yourself:

  • How do I solve the problem?
  • Once I have solved it or seen the solution: what are the ways I could have solved this problem?
  • Is there a way to sanity-check my solution intuitively?
  • If I could not solve it: what concept did I learn from the solution, and which other situations can this concept be applied to?

Types of math puzzles. Most math puzzles come from five topics: casual puzzles, combinatorics/probability, algorithms, engineering mathematics, and coding (C/C++).

How to prepare - books by topic:

  • Casual puzzles: Mathematical Puzzles: A Connoisseur's Collection by Peter Winkler; Entertaining Mathematical Puzzles by Martin Gardner; Mathematical Puzzles of Sam Loyd
  • Combinatorics / Probability: Probability, Random Variables and Stochastic Processes by Papoulis; Fifty Challenging Problems in Probability with Solutions
  • Algorithms: Introduction to Algorithms by Cormen, Leiserson and Rivest; Algorithms by Robert Sedgewick
  • Engineering Mathematics: Advanced Engineering Mathematics by Kreyszig; Linear Algebra and Its Applications by Gilbert Strang; What Is Mathematics? by Richard Courant
  • Coding (C/C++): C++: The Complete Reference; The C++ Programming Language by Stroustrup; Programming in C++ by Cohoon and Davidson

Puzzle blogs and resources listed in the deck: CSE Blog, Gurmeet Singh Manku's blog, CMU's The Puzzle Toad, IBM Ponder This, William Wu's puzzle collection, C Puzzles by Gowri Kumar, Cotpi, A Puzzle Blog, Me, Myself and Mathematics, Tanya Khovanova's Math Blog, Gowers's Blog, Terry Tao, The Math Less Traveled, Wild About Math!, and Combinatorics and more.

The 10 puzzles from the deck (each links to the full problem and its discussion on this blog):

  1. Conway's Soldiers (CheckerBoard Unreachable Line) - prove that no finite series of moves can take a soldier more than four rows above the line.
  2. Determinant of Binary Matrix - an N x N matrix of 0s and 1s with consecutive 1s in every row has determinant -1, 0 or 1.
  3. Hats in a Circle - n friends in a circle shout their own hat colour simultaneously; find a strategy with a good chance of success.
  4. Correct Letters - n letters go into n envelopes at random; find the expected number of correctly matched envelopes.
  5. Don't roll more - I roll a die at most three times and pay you the last face; when should you stop me?
  6. Lion in a Circular Cage - lion and lion tamer move at equal speed inside a circle; can the lion catch the tamer?
  7. Consecutive Heads - tosses until 2 vs 3 consecutive heads: P{X>Y}, E[X] and E[Y].
  8. Coins Puzzle - blindfolded, split 100 coins so both piles have the same number of tails up.
  9. Arithmetic Puzzle: Broken Calculator - only scientific functions work; turn the displayed 0 into 2, then into 3.
  10. Number of Locks and Keys - 7 thieves, locks must open only for a majority of 4 or more; find the minimum locks and keys.

Comments

Post a Comment

Popular posts from this blog

Polya's Urn Problem: Expected Balls in the Smaller Urn

Puzzle: There are two urns with one ball each. Each of subsequent n-2 balls is placed into one of these urns, with probability proportional to the number of balls already in that urn. What is the expected number of balls in the smaller sized urn? Source: P. Winkler's Puzzles book. (Chapter: Probability). Solution: Highlight the part between the * symbols for the answer. * This problem can be reformulated as the following problem. Suppose I have a stack of black cards and one red card. Initially I take red card in my hand. Now I add black cards randomly between any two cards (so, initially its either above or below red). Note that the probability that I add the card above the red card, when x-1 is the number of cards above red and y-1 is the number of cards below red is x/(x+y). Let the problem be if red card is dividing the black cards into two sets, what is the expected number of black cards in the smaller section. So, we see that the two problems are equivalent. No...
Read more

Expected Tosses for Consecutive Heads: 2 Heads vs 3 Heads Puzzle

Let's say A keep tossing a fair coin, until he get 2 consecutive heads, define X to be the number of tosses for this process; B keep tossing another fair coin, until he get 3 consecutive heads, define Y to be the number of the tosses for this process. 1) Calculate P{X>Y} 2) What's the expected value of X 3) What's the expected value of Y This is probably the hardest puzzle I have ever put on my blog. Hence, I will post its solution in the post directly rather than on comment. Solution: 1) (Solved by me finally after 13 months :)) Make a state diagram. Let the state be (a,b) where a is the number of consecutive heads streak "A" is on currently and b is the number of consecutive heads streak "B" is on currently. So, (0,3) (1,3) are final accepted states and (2,0) (2,1) (2,2) (2,3) are failure states. If you get tails, your contribution to the state reaches to "0" f(State) = P(X>Y | "State" configuration initially) ...
Read more

Lion and Man in a Circular Cage: Can the Lion Catch the Tamer?

Source: Asked to me by Pramod Ganapathi (PhD Student at Stony Brook University) Problem: A lion and a lion tamer are enclosed within a circular cage. If they move at the same speed but are both restricted by the cage, can the lion catch the lion tamer? (Represent the cage by a circle, and the lion and lion tamer as two point masses within it.) Solution: Highlight the part between the * symbols for the answer. * Answer: surprisingly, no - the tamer can avoid being caught forever. This is the famous Lion and Man problem, posed in the 1930s and settled by Besicovitch; the proof appears in Littlewood's "A Mathematician's Miscellany" (and opens Bollobas's "The Art of Mathematics"). What the lion CAN do (Rado's strategy): move to the center, then always stay on the radius through the tamer, using any spare speed to move outward. Since the lion runs on a smaller circle, it can match the tamer's angular position while steadily increasing its radiu...
Read more