## Posts

Recent posts

### Solving IMO 1989 #6 using Probability and Expectation

IMO 1989 #6: A permutation $$\{x_1, x_2, \ldots , x_m\}$$ of the set $$\{1, 2, \ldots , 2n\}$$, where $$n$$ is a positive integer, is said to have property $$P$$ if $$| x_i - x_{i+1} | = n$$ for at least one $$i$$ in $$\{1, 2, ... , 2n-1\}$$. Show that for each $$n$$ there are more permutations with property $$P$$ than without.

### The Kelly Criterion and a Sure Thing

The Kelly Criterion is an alternative to standard utility theory, which seeks to maximize expected utility. Instead, the Kelly Criterion seeks to maximize expected growth. That is, if we start out with an initial bankroll $$B_0$$, we seek to maximize $$\mathrm{E}[g(t)]$$, where $$B_t = B_0\cdot e^{g(t)}$$.
As a simple example, consider the following choice. We can have a sure $3000, or we can take the gamble of a $$\frac{4}{5}$$ chance of$4000 and a $$\frac{1}{5}$$ chance of \$0. What does Kelly say?
Assume we have a current bankroll of $$B_0$$. After the first choice we have $$B_1 = B_0+3000$$, which we can write as $\mathrm{E}[g(1)] = \log\left(\frac{B_0+3000}{B_0}\right);$for the second choice we have $\mathrm{E}[g(1)] = \frac{4}{5} \log\left(\frac{B_0+4000}{B_0}\right).$And so we want to compare $$\log\left(\frac{B_0+3000}{B_0}\right)$$ and $$\frac{4}{5} \log\left(\frac{B_0+4000}{B_0}\right)$$.
Exponentiating, we're looking for the positive root of ${\left({B_0+3000}\righ… ### Prime Divisors of $$3^{32}-2^{32}$$ Find four prime divisors < 100 for $$3^{32}-2^{32}$$. Source: British Math Olympiad, 2006. This factors nicely as $$3^{32}-2^{32} = \left(3^{16}+2^{16}\right)\left(3^{16}-2^{16}\right)$$, and we can continue factoring in this way to get \[3^{32}-2^{32} = \left(3^{16}+2^{16}\right)\left(3^8+2^8\right)\left(3^4+2^4\right)\left(3^2+2^2\right)\left(3^2-2^2\right).$The final three terms are $$5, 13, 97$$, so we have three of the four required primes. For another prime divisor, consider $$3^{16}-2^{16}$$. By Fermat's Little Theorem $$a^{16}-1\equiv 0 \bmod 17$$ for all $$a$$ with $$(a,17)=1$$, and so it follows that $$3^{16}-2^{16}\equiv 0 \bmod 17$$, and we therefore have $$17$$ as a fourth such prime divisor.
Alternatively, note $$\left(\dfrac{3}{17}\right)=-1, \left(\dfrac{2}{17}\right)=1$$, hence by Euler's Criterion $$3^8\equiv -1 \bmod 17$$ and $$2^8\equiv 1 \bmod 17$$, giving $$3^8+2^8\equiv 0\bmod 17$$.

### Highest Powers of 3 and $$\left(1+\sqrt{2}\right)^n$$

Let $$\left(1+\sqrt{2}\right)^{2012}=a+b\sqrt{2}$$, where $$a$$ and $$b$$ are integers. What is the greatest common divisor of $$b$$ and $$81$$?
Source: 2011-2012 SDML High School 2a, problem 15.

Let $$(1+\sqrt{2})^n = a_n + b_n \sqrt{2}$$. I've thought about this some more, and there's a nice way to describe the highest power of $$3$$ that divides $$b_n$$. This is probably outside of the scope of the intended solution, however.

First note that $$(1-\sqrt{2})^n = a_n - b_n \sqrt{2}$$, and so from $$(1+\sqrt{2})(1-\sqrt{2})=-1$$ we get $$(1+\sqrt{2})^n (1-\sqrt{2})^n = {(-1)}^n$$. This gives ${a_n}^2 - 2 {b_n}^2 = {(-1)}^n.$ Now define the highest power of a prime $$p$$ that divides $$n$$ to be $$\operatorname{\nu}_p(n)$$.
From cubing and using the above result it's straightforward to prove that if $$\operatorname{\nu}_3(b_n) = k > 0$$ then $$\operatorname{\nu}_3(b_{3n}) = k+1$$.
Note $$(1+\sqrt{2})^4 = 17 + 12\sqrt{2} \equiv -1+3\sqrt{2} \pmod{3^2}$$. Cubing and using…