CSE Blog - quant, math, computer science puzzles

Source:  (Romanian Informatics Olympiad ONI'03, extended team selection) ( ^ Representative diagram of Huffman Encoding. No relevance in the problem) 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.

Source: Puzzle collection by Raphael Reischuk Problem: 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...

Source:  xkcd wiki Problem: 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 "...

Problem 1: Lion in a Circular Cage Puzzle Original Link: http://pratikpoddarcse.blogspot.in/2012/02/lion-in-circular-cage-puzzle.html 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.) Problem 2: Geometry Puzzle: Center of Square in Circle Original Link: http://pratikpoddarcse.blogspot.in/2012/11/geometry-puzzle-center-of-square-in.html Source: Asked to me by a lot of people from IIT Bombay on email and posted by a few on " Post a Question " page. Problem: 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 d...

Source:  Flipkart Interview Question from Interview Street (taken from  Chinmay - CSE IITB Blog ) Problem: 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.

Source: Asked to me by Sankeerth Rao (EE IITB 4th year Student) Problem: Given any two triangles in a plane construct a line which bisects both their areas. Background: 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.

Source:  Video of a course in Algorithms on Udacity - Asked by Prof. Peter Winkler Problem: 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...

Source: Mailed to me by Sudeep Kamath (PhD Candidate UC Berkeley, EE IITB 2008 Alumnus) Problem: 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.