CSE Blog - quant, math, computer science puzzles

Source: IBM Ponder This Dec 12 ( http://domino.research.ibm.com/comm/wwwr_ponder.nsf/challenges/December2012.html ) - Mailed to me by Aashay Harlalka (Final Year Student, CSE, IITB) Problem: 36 people live in a 6x6 grid, and each one of them lives in a separate square of the grid. Each resident's neighbors are those who live in the squares that have a common edge with that resident's square. Each resident of the grid is assigned a natural number N, such that if a person receives some N>1, then he or she must also have neighbors that have been assigned all of the numbers 1,2,...,N-1. Find a configuration of the 36 neighbors where the sum of their numbers is at least 90. As an example, the highest sum we can get in a 3x3 grid is 20: 1 2 1 4 3 4 2 1 2 Update (24 June 2014): Solution:  Available on  IBM Research Ponder This - December 2012 Solution

Source: Mailed to me by Vashist Avadhanula (PhD Student at Columbia Business School, EE IITB 2013 Alumnus) Problem: Consider a case where you flip two fair coins at once (sample space is HH, HT, TH & TT) you repeat this experiment many times and note down the outputs as a sequence. What is the expected number of flips (one flip includes tossing of two coins) to arrive at the sequence HHTHHTT.

Source: Mailed to me by Sudeep Kamath (PhD Student, UC at Berkeley, EE IITB Alumnus 2008) Problem: Tricky Question. Let f be a continuous, real-valued function on reals such that limit_{n \rightarrow \infty} f(nx) = 0 for all real x. Show limit_{x\rightarrow \infty} f(x) = 0.

Source: Sent to me by Aashay Harlalka (Final Year Student, CSE, IITB) Problem: For a given positive integer n, what would be the minimum no. of weights required so that we can weigh all positive integers <= n Follow up Generalized problem: If we have k copies of each distinct weight, then what is the minimum no. of distinct weights required ? Old Related Puzzle: There is a very different popular problem but knit in the same story (posted 4 years back on the blog): Weighing Problem Note : Weights are of integer values only.

Source: Sent to me by Vinayak Gagrani (CSE IITB Alumnus 2013) Problem: There are 289 students. We have to divide them into 17 groups of 17 each every day. The groups have to be such that no two students who have been previously on some group together can be formed a group again. How many days can we do this ? Extension: Can this be generalized for any N^2 students?

Source: IBM Ponder This - June 2012 - Sent to me by Aashay Harlalka (Final Year Student, CSE, IITB) Problem: Two players starts with the number N and play in turns. In each turn the player chooses a prime power p^m > 1, which divides N and updates N to be N/(p^m). The player who sets N to be 1 - wins. What are all the winning moves from the initial state of N=1,506,009,006,001,500,000,000 ? We are looking for all the moves the first player can make which, assuming he plays correctly, can guarantee him winning the game. Update (24 June 2014): Solution:  Posted by Gowtham Kumar (PhD Student, Stanford, IITM Alumnus) and me in comments!

Source: http://thomer.com/riddles/ Problem: If you have an array with random odd and even numbers, what is the most efficient algorithm you can think of to put all even numbers on one side and all odd numbers on the other side in this array? What is the complexity of your algorithm? Update ( 21 June 2014) Solution posted by nick, Abhishek, Khalil Sawant, Sandeep, Stainless (Ameya Ranade - CSE IITB 2009 Alumnus, Google Engineer, Facebook Engineer), Piyush Sao, Sakshi, Kaushal and Pankaj Jindal in comments! Thanks.