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. Solution: Highlight the part between the * symbols for the answer. * Answer: 2^14 / 255 = 64 + 64/255 = 64.251 flips (each flip = both coins tossed together). Why it is not just 2^7/2 = 64 or 2^6 = 64: the 7-bit target HHTHHTT is not aligned to the coin-pair boundaries, and a flip is consumed even when the pattern completes on its first coin. Model it as a Markov chain on the longest suffix of the bit stream matching a prefix of HHTHHTT (7 transient states + absorbing). Each flip moves two bits at once; solving the 7 linear equations E_s = 1 + (1/4) * sum over the four two-bit outcome...

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. Solution: Highlight the part between the * symbols for the answer. * Proof (Baire category theorem; n ranges over the positive integers). Fix eps > 0 and for N = 1,2,... let E_N = { x >= 1 : |f(nx)| = N }. Each E_N is closed: it is an intersection of preimages of the closed interval [-eps,eps] under the continuous maps x -> f(nx). Since f(nx) -> 0 for every real x, every x >= 1 belongs to some E_N, so the E_N cover [1, infinity). By Baire's theorem some E_N has non-empty interior, i.e. it contains a closed interval [a,b] with 1 = N of the intervals [na, nb]. Now (n+1)a = a/(b-a), so beyond n0 = max(N, ceil(a/(b-a))) the intervals [na,nb] overlap or touch and their union contains the whole hal...

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. Solution: Highlight the part between the * symbols for the answer. * Assuming a two-pan balance (weights may go on either pan, as in Vinod Reddy's setup): Part 1: minimum number of weights = the smallest m with (3^m - 1)/2 >= n, i.e. m = ceil(log_3(2n + 1)), using weights 1, 3, 9, ..., 3^(m-1). Upper bound: each weight has 3 states (left pan, right pan, unused), giving at most (3^m - 1)/2 distinct positive outcomes. Achievability: balanced ter...