## Posts

Showing posts from June, 2011

### Coin Chain Reaction

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.

### Moscow Math Olympiad Problems

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 :(