• Brain Teasers & Puzzles

    Questions Per Page:
    • A spy is located on a one-dimensional line.  At time 0, the spy is at location A.  With each time interval, the spy moves B units to the right (if B is negative, the spy is moving left).  A and B are fixed integers, but they are unknown to you.  You are to catch the spy.  The means by which you can attempt to do that is:  at each time interval (starting at time 0), you can choose a location on the line and ask whether or not the spy is currently at that location.  That is, you will ask a question like “Is the spy currently at location 27?” and you will get a yes/no answer.  Devise an algorithm that will eventually find the spy.

      Submit Solution
      • 1,430.7K views
      • 0 answers
      • 0 votes

    • You are given four points (on a Euclidian plane) that make up the corners of a square.  You may change the positions of the points by a sequence of moves.  Each move changes the position of one point, say p, to a new location, say p’, by “skipping over” one of the other 3 points.  More precisely, p skips over a point q if it is moved to the diametrically opposed side of q.  In other words, a move from p to p’ is allowed if there exists a point q such that q = (p + p’) / 2.

      Find a sequence of moves that results in a larger square.  Or, if no such sequence is possible, give a proof of why it isn’t possible.  (The new square need not be oriented the same way as the original square.  For example, the larger square may be turned 45 degrees from the original, and the larger square may have the points in a different order from in the original square.)

      View Solution
      Submit Solution
      • 1,430.4K views
      • 1 answers
      • 1 votes


    • Recently, I received a wonderful cookbook.  In an appendix, it shows a table that converts oven temperatures between Celsius and Fahrenheit.  (Side remark: Approximate oven temperatures are actually really simple to convert in your head–just double the number of degrees Celsius to get the number of degrees Fahrenheit.  For oven temperatures, this will be within 10 F of the exact answer.)

      The table has a footnote that says “If your oven has a fan, reduce the recipe temperature by 68 F”.  I have a strong hunch that this footnote suffers from a translation error.  How many degrees Fahrenheit should it have said to reduce the temperature by?  (No knowledge of convection ovens required.)

      View Solution
      Submit Solution
      • 1,430.2K views
      • 1 answers
      • 0 votes



    • Consider the following array operations.  Init(N,d) initializes an array of N elements so that each element has value d.  Once Init has been called, the following two operations can be applied:  For any i such that 0 <= i < N, Get(i) returns the array element at position i and Set(i,v) sets the array element at position i to the value v.

      Given any amount of memory you want, implement the three operations so that each operation has an O(1) time complexity.

      Submit Solution
      • 1,430.3K views
      • 0 answers
      • 0 votes

    • You are given a balance (that is, a weighing machine with two trays) and a positive integer N.  You are then to request a number of weights.  You pick which denominations of weights you want and how many of each you want.  After you receive the weights you requested, you are given a thing whose weight is an integer between 1 and N, inclusive.  Using the balance and the weights you requested, you must now determine the exact weight of the thing.

      As a function of N, how few weights can you get by requesting?

      View Solution
      Submit Solution
      • 1,430.2K views
      • 1 answers
      • 1 votes

    • 100 prisoners agree on a strategy before playing the following game:  One at a time (in some unspecified order), each of the prisoners is taken to a courtyard where there is a line of 100 boxes.  The prisoner gets to make choices to open 50 of the boxes.  When a box is opened, it reveals the name of a prisoner (the prisoners have distinct names).  The names written in the boxes are in 1-to-1 correspondence with the prisoners; that is, each name is found in exactly one box.  If after opening 50 boxes, the prisoner has not found his own name, the game is over and all the prisoners lose.  But if the prisoner does find the box that contains his name among the 50 boxes he opens, then the prisoner is taken to the other side of the courtyard where he cannot communicate with the others, the boxes are once again closed, and the next prisoner is brought out into the courtyard.  If all prisoners make it to the other side of the courtyard, they win.

      One possible strategy is for each prisoner to randomly select 50 boxes and open them.  This gives the prisoners 1 chance out of 2100 to win–a slim chance, indeed.  But the prisoners can do better, using a strategy that for a random configuration of the boxes will give them a larger chance of winning.  How good a strategy can you develop?

      Submit Solution
      • 1,430.2K views
      • 0 answers
      • 0 votes



    • A park contains paths that intersect at various places.  The intersections all have the properties that they are 3-way intersections and that, with one exception, they are indistinguishable from each other.  The one exception is an intersection where there is a restaurant.  The restaurant is reachable from everywhere in the park.  Your task is to find your way to the restaurant.

      The park has strict littering regulations, so you are not allowed to modify the paths or intersections (for example, you are not allowed to leave a note an intersection saying you have been there).  However, you are allowed to do some bookkeeping on a pad of paper that you bring with you at all times (in the computer-science parlance, you are allowed some state).  How can you find the restaurant?

      You may assume that once you enter an intersection, you can continue to the left, continue to the right, or return to where you just came from.

      Submit Solution
      • 1,430.3K views
      • 0 answers
      • 0 votes

    • The harmonic series–that is, 1/1 + 1/2 + 1/3 + 1/4 + …–diverges.  That is, the sum is not finite.  This is in difference to, for example, a geometric series–like ½0 + ½1 + ½2 + ½3 + …–which converges, that is, has a finite sum.

      Consider the harmonic series, but drop all terms whose denominator represented in decimal contains a 9.  For example, you’d drop terms like 1/9, 1/19, 1/90, 1/992, 1/529110.  Does the resulting series converge or diverge?

      Hint: More generally, you may consider representing the denominator in the base of your choice and dropping terms that contain a certain digit of your choice.
      Consider again the harmonic series, but drop a term only if the denominator represented in decimal contains two consecutive 9’s.  For example, you’d drop 1/99, 1/992, 1/299, but not 1/9 or 1/909.  Does this series converge or diverge?

      View Solution
      Submit Solution
      • 1,430.9K views
      • 1 answers
      • 0 votes

    • You have 240 barrels of wine, one of which has been poisoned.  After drinking the poisoned wine, one dies within 24 hours.  You have 5 slaves whom you are willing to sacrifice in order to determine which barrel contains the poisoned wine.  How do you achieve this in 48 hours?

      View Solution
      Submit Solution
      • 1,431.5K views
      • 2 answers
      • 1 votes



    • A ledge is 1 meter long.  On it are N lemmings.  Each lemming travels along the ledge at a constant speed of 1 meter/minute.  A lemming continues in the same direction until it either falls off the ledge or it collides with another lemming.  If two lemmings collide, they both immediately change their directions.  Initially, the lemmings have arbitrary starting positions and starting directions.  What is the longest time that may elapse before all lemmings have fallen off the ledge?

      Hint: Suppose the ledge is not horizontal, but is leaning.  A lemming now travels up the ledge at a speed of 1 meter/minute and travels down the ledge at a speed of 2 meters/minute.  What is the longest time before all lemmings have fallen off?

      View Solution
      Submit Solution
      • 1,431.1K views
      • 1 answers
      • 0 votes

  • More puzzles to try-