There are $100$ boxes, each containing either a red cube or a blue cube. Alex has a sum of money initially, and places bets on the colour of the cube in each box in turn. The bet can be anywhere from $0$ up to everything he has at the time. After the bet has been placed, the box is opened. If Alex loses, his bet will be taken away. If he wins, he will get his bet back, plus a sum equal to the bet. Then he moves onto the next box, until he has bet on the last one, or until he runs out of money. What is the maximum factor by which he can guarantee to increase his amount of money, if he knows that the exact number of blue cubes is (a) $1$; (b) some integer $k$, $1 < k \leq 100$.
Problem
Source: Tournament of Towns 2007 - Fall - Senior A-Level - P7
Tags: geometry, 3D geometry, combinatorics unsolved, combinatorics
22.02.2017 20:52
Bump....
02.01.2020 20:00
(a) Note that Alex knows how many blue cubes are left at any point in the process. We let $f(n, a)$ be the largest factor by which Alex can increase his money, provided that there are $n$ cubes left and $a$ of them are blue. We seek to find $f(100, 1).$ It's apparent that $f(n, 0) = 2^n$ and $f(1, 1) = 2$, as for these situations Alex can go all-in every time. Claim. $f(a, b)$ is the harmonic mean of $f(a-1, b)$ and $f(a-1, b-1)$, whenever $0 < b < a.$ Proof. It's clear that the maximum amount of money that Alex can guarantee is $\max_{x \in (-1, 1)} {\min((1-x)f(a-1, b), (1+x)f(a-1, b-1))}.$ To maximize this, Alex should select $x$ so that $(1-x) f(a-1, b) = (1+x) f(a-1, b-1),$ and then we'd have $f(a, b) = (1-x)f(a-1, b) = (1+x) f(a-1, b-1).$ But then we have that $\frac{f(a, b)}{f(a-1, b)} + \frac{f(a, b)}{f(a-1, b-1)} = 2$, implying the claim. $\blacksquare$ From this and induction, we can deduce that $f(n, 1) = \frac{2^n}{n}$ for all $n \in \mathbb{Z}_{\ge 0},$ and the answer is $f(100, 1) = \frac{2^{100}}{100} = \boxed{\frac{2^{98}}{25}}.$ (b) This part is solved similarly. Let $t(n, a)$ denote the maximum factor by which Alex can increase his money, provided that there are $n$ cubes left and at least $a$ of them are blue. We seek to find $t(100, 2).$ In this case, we have that $t(n, 0) = 1$ because Alex has no information (so he has no way of guaranteeing even an increase in money because he could lose every time). It's also clear that $t(1, 1) = 2$ and $t(2, 2) = 4$ because Alex knows all cubes are blue. From here, we can finish in the same fashion as in part (a). Claim. $t(n, a)$ is the harmonic mean of $t(n-1, a-1)$ and $t(n-1, a)$, whenever $0 < a < n.$ Proof. This claim is proven in the same way as the claim in part (a). $\blacksquare$ This allows us to prove by induction that $t(n, 1) = \frac{2^n}{2^n-1}$ for all $n \in \mathbb{N}$ and $t(n, 2) = \frac{2^n}{2^n - n - 1}$ for all $n \in \mathbb{N}_{> 1}.$ Our answer is simply $\boxed{\frac{2^{100}}{2^{100} - 101}}.$ $\square$