Wednesday, July 23, 2008

Common Puzzles

Most of my friends are geeks. So when we get together on a friday night (or) driving to a conference, we don't talk about politics, movies or celebrities. Instead we throw math puzzles at each other. Here are some of the common puzzles I ran into....

  • The Banana-eating Camel : You have 3,000 bananas that must be transported across a desert that is 1,000 kilometers wide. You have a camel that has a 1,000 banana capacity. However, the camel must eat one banana for each kilometer that it walks. What is the largest number of bananas that can be transported across the desert?

  • 12 Balls : There are 12 balls. They all look alike but one of them is faulty; it weights differently. It is not known, if this ball is heavier or lighter than the other balls. How to find the faulty ball by three weighs on a simple balance ?
  • Linked Lists : You are given a pointer to the head of a singly linked list that might (or might not) have a loop somewhere (i.e., an element pointing back to an element). The length of the list is finite, but unknown. Devise an algorithm that detects if there is a loop. You must use only a constant amount of memory space and not destroy the list.
  • Two Integers : I'm thinking of two integer numbers, each if them is more than 1 and their sum is less than 100. I tell my friend A the sum of these two numbers, and another friend B, product of these two numbers. Then such a dialog took place:
    B: I can't determine what are these numbers.
    A: Ah, i knew you wouldn't be able to do this.
    B: Oh, then i know what they are!
    A: Oh, then i know them too!

    Can you determine the numbers?
  • Stick triangle : A stick is broken at random into three pieces. What is the probability that the pieces can form a triangle?

These are the easiest ones (the appetizers). Have fun solving them. I will add more difficult puzzles in future posts...


Suresh said...

hmm. I'm thinking that both (8,11) and (8,17) could yield the same exchange between A and B.

Shiva Kintali said...

Suresh, there is a unique pair (x,y) that yields the above exchange.

pushkar said...

the answer is 4 and 13...this is the famous dijkstra puzzle. One of his students gave it to him. Spent the entire night tryingg to figure it out and missed the class next day. Then he later remarked, it was worth missing the class for this puzzle.