Dec 31, 2012

Romanian Informatics Olympiad - Modified Huffman Encoding

Source: (Romanian Informatics Olympiad ONI'03, extended team selection)

File:Huffman tree 2.svg

( ^ Representative diagram of Huffman Encoding. No relevance in the problem)

A telegraph machine can transmit only lines and dots; it takes 2 seconds to transmit a line, but only 1 second to transmit a dot. We generally want to transmit texts containing letters of the English alphabet, and digits (so we have N<=36 symbols in total). Therefore, a prefix-free encoding using lines and dots is needed. Given the frequencies of the N symbols in a large text, find the minimum time it takes to transmit the text using a suitable encoding. The solution should run in O(N^4) time, and use O(N^3) space.

Dec 30, 2012

Coin Puzzle: Predict the Other's Coin

Source: Puzzle collection by Raphael Reischuk

File:1884 trade dollar rev.jpg

Assume the following 3-player game consisting of several rounds. Players A and B build a team, they have one fair coin each, and may initially talk to each other. Before starting the first round, however, no more communication between them is allowed until the end of the game. (Imagine they are separated in different places without any communication infrastructure.)

A round of the game consists of the following steps: 
(1) the team gives one dollar to player C. 
(2) Both A and B toss their coins independently. 
(3) Both A and B try to predict the other's coin by telling the guess to C. (No communication: A does not know the outcome of B's coin toss, and vice versa, nor the guess). 
(4) If C verifies that both A and B guess the other's coin correctly, then C has to give 3 dollars back to the team. 

Should C play this game?

Previously Asked Coin Puzzles:
Coin Balancing
Coins Puzzle
Consecutive Heads
Five Thieves and Bounty

Discussion on Hacker News:

Update: (29 Jan 2013)
Correct solution by: Takaki, Andre, Felix, JDGM in comments!
Correct strategy (but not so correct calculation) by Joshua, Shubham Mittal in comments!
If you are just looking for the solution, Perfect solution by Andre. Thanks

Dec 29, 2012

Pizza Distribution Puzzle

Source: xkcd wiki

The king of the universe has decided to play a game. To start, he selects 1 person. He then flips two fair coins - if they both come up heads, the person gets a free pizza and the game is over. For any other result, he sends the person home and selects 2 new people, where he does the same 2-coin flip to decide if they each get a pizza. If they don’t, he picks 4 people at random, then 8, and so on, doubling each round. If you are selected but don’t win, you can’t be selected again – and you can assume the population is extremely large so there’s no chance of running out of contestants.

You are sitting at home when you get a call – you have been selected to play the game. What is the chance that you will get a free pizza?

You don't know which round number it is, but if you ask, the king will tell you. Does it matter?

Disclaimer: Very easy problem!

Update (31 January 2013):
Title changed to "Pizza Distribution Puzzle" from "Pizza Paradox Puzzle" - as pointed out by Vivek Ranjan Nema in comments, there is no paradox. My mistake. Apologies.
Solution posted by Rushabh Sheth, Pratyush Rathore, Nathan Jacobson, Marjansek, Shyam Raj in comments!

Dec 21, 2012

Most Popular Math Puzzles in 2012

Problem 1: Lion in a Circular Cage Puzzle

Original Link:

Source: Asked to me by Pramod Ganapathi (PhD Student at Stony Brook University)

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

Problem 2: Geometry Puzzle: Center of Square in Circle

Original Link:

Source: Asked to me by a lot of people from IIT Bombay on email and posted by a few on "Post a Question" page.

What is the probability that two uniform random points (to be precise: i.i.d. with respect to Lebesgue measure) in the square are such that center of the square lies in the circle formed by taking the points as diameter.

Problem 3: Consecutive Heads

Original Link:

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

Problem 4: Coins Puzzle

Original Link:

There are 100 coins on the table out of which 50 are tail-face up and 50 are head face up. You are blind folded and there is no way to determine which side is up by rubbing, etc. You have to divide the 100 coins in two equal halves such that both have equal number of coins with tails face up. (This obviously implies that the two have equal number of coins with heads face up)

Second part: There are 100 coins on the table out of which 10 are tail-face up and 90 are head face up. You are blind folded and there is no way to determine which side is up by rubbing, etc. You have to divide the 100 coins in two halves (not necessarily equal) such that both have equal number of coins with tails face up.

Problem 5: Arithmetic Puzzle: Broken Calculator

Original Link:

Source: Quantnet Forum

There is a calculator in which all digits(0-9) and the basic arithmetic operators(+,-,*,/) are disabled. However other scientific functions are operational like exp, log, sin, cos, arctan, etc. The calculator currently displays a 0. Convert this first to 2 and then to 3.

Dec 16, 2012

Snakes and Ladders Optimization

Source: Flipkart Interview Question from Interview Street (taken from Chinmay - CSE IITB Blog)


Find the smallest number of jumps (i.e. optimal number of dice throws) needed to win a snakes and ladders game. Assume you are given a board with all the necessary inputs like start/end positions of all ladders and snakes.

Dec 13, 2012

Geometry Contruction - Bisect Areas of 2 Triangles

Source: Asked to me by Sankeerth Rao (EE IITB 4th year Student)

Given any two triangles in a plane construct a line which bisects both their areas.

In fact the existence of such a line is true in a very general setting - for any two polygons in a plane there exists a line which bisects both their areas. In fact its true for any two Jordan measurable sets in a plane. Further generalized version is called the Ham Sandwich Theorem and is proved using Borsuk Ulam Theorem.

Dec 6, 2012

Spy Control Problem - Peter Winkler

Source: Video of a course in Algorithms on Udacity - Asked by Prof. Peter Winkler


A spy in an enemy territory is trying to convey information to her control, but the only means she has for conveying information is that there is a 15-bit radio broadcast every morning, and she has the ability if she wishes to alter 1 bit of that broadcast. But she doesn't know in advance what the broadcast will be. So, this is a case where, potentially, there are 16 different things she can do. There are 15 bits she can alter, or she can choose not to alter any bit, which means that in theory perhaps she could convey as many as 4 bits of information this way.

Well, surprisingly, she can actually do that.

Repeating the problem to make sure that we understand the setup here. So, I'm a spy, and I'm in enemy territory, and I've got a message --0110-- that I need to transmit to my boss. Now, that's going to be tricky to do, because I don't want anybody to know that I'm a spy in enemy territory. Fortunately, there is a radio broadcast tower in enemy territory, and everyday it sends out a 15-bit message. There's an example of a 15-bit message. Now, I can use that message to communicate with my boss, but I can't just change it arbitrarily to something completely different, because then people will know that something weird has happened. But I can flip just 1 bit. I can zap the message and change just one of the bits, and my boss then is going to hear that, and we'd like him to actually interpret that as the message that I want to send. How should I do that such that, when the boss receives the broadcast, he is like - Hmm...based on the 15-bit broadcast I'm hearing, and the protocol that my spy and I arranged in advance, I know that the message he is sending to me is 0110. Nice work, agent P.

Peter Winkler's video with Problem and Solution:


Peter Winkler gave the solution in the video. Wrote the solution in comments!

Dec 1, 2012

Hanging Picture Puzzle

Source: Mailed to me by Sudeep Kamath (PhD Candidate UC Berkeley, EE IITB 2008 Alumnus)


Suppose we have a portrait hung on a wall using one nail. Now, suppose we hammer another nail next to the existing one and try to use both nails to hang the portrait. If any nail breaks, the portrait continues to hang safely. Can we hang the portrait in such a way that if any one nail breaks the portrait must fall down?

Generalize to k nails: Hang a portrait on k nails such that if any one nail breaks, the portrait must fall down.

Fraction Brainteaser

Source: Sent to me by Gaurav Sinha Problem: Siddhant writes a Maths test and correctly answers 5 out of 6 Arithmetic questions and 20...