CSE Blog - quant, math, computer science puzzles

Source: Asked to me by Prateek Srivastava (IITB CSE Alumnus 2010 and Yahoo! Software Engineer) (also asked in a quant firm placement test) Problem: We have an unlimited number of dice at our disposal. Let's roll the die. If the outcome is 1, 2, or 3, we stop; otherwise, if it is 4, 5, or 6, a corresponding number of dice are rolled. For example, if the first roll gives 5, then we roll 5 dice, and so on. This procedure continues for every rolled dice whose outcome is 4, 5, or 6. Let N denote the N-th round of rolls. What is the total expected value at the end of the N-th round of rolls? Update (17 July 2011): Solution posted by Unknown in comments. There is a slight ambiguity in the problem statement, so please do not waste a lot of time. Thanks.

Problem 1: Each cell in a square table contains a number. The sum of the two greatest numbers in each row is  a , and the sum of the two greatest numbers in each column is  b . Prove that  a = b . Problem 2:  Given some m x n table, and some numbers in its fields. You are allowed to change the sign in one row or one column simultaneously. Prove that You can obtain a table, with non-negative sums over each row and over each column. Update (11th June 2011): Solution to both problems posted by NG [Nikhil Garg (CSE IIT Delhi final year undergraduate student)] in comments! Thanks. Confession: I could never solve Problem 1 even after spending hours. :P :(