Yet Another Million Dollar Question (Tuklas Vol. 15, No. 5 - January 11, 2014)

YET ANOTHER MILLION DOLLAR QUESTION

EXPECTED VALUES

The outcome of a statistical experiment (e.g., tossing a coin, drawing a card from a deck) is usually expressed as a random variable, a variable whose value is subject to chance. The expected value of a random variable is the weighted average of the values it could take on based on their probabilities.

If you let $X$ denote the outcome of, say, rolling a fair die, then $X$ is a random variable that takes on one of the values in the set $\{1,2,3,4,5,6\}$. Because the die is fair, the probability of getting any of the numbers on it is $\frac{1}{6}$. Hence, the expected value of $X$ is  $$\mathbb{E}(X) = \sum_{i=1}^{6}{i \cdot \text{Pr}(i)} = \sum_{i=1}^{6}{i\cdot \frac{1}{6}} = 3.5,$$ where $\text{Pr}(i)$ is the probability of getting $i$ on a roll.

Note that it is impossible to roll a 3.5 with any standard die. This fact, however, does not impair the descriptive capacity of the expected value. Recall that averages sometimes fail to "make sense" as well. If a community comprising 20 families has 70 children, then the average number of children per family is 3.5.

THE PARADOX

Suppose there exists a creature called The Predictor, the predictions of which have yet to fail. You have accepted its invitation to play a game and are standing in front of two boxes, one transparent and one opaque. The transparent box contains $\$1,000$.
The Predictor, now but a shadow on the wall, says, "You are to acquire the contents of either just the opaque box or both boxes. As you might expect, I have already predicted what you will do. Know this: if I have predicted that you will select the opaque box alone, then it contains one million dollars. If I have predicted that you will select both boxes, then the opaque box contains nothing. That is all."

If you wish to maximize the money you will gain, what should you do?

Let us call choosing just the opaque box "one-boxing" and choosing both boxes "two-boxing." Setting The Predictor's words aside and working solely with what the opaque box could contain, one-boxing yields either $\$1,000,000$ or 0, and two-boxing yields either $\$1,001,000$ or $\$1,000$.

Let $M_o$ denote the money you will gain from one-boxing and $M_t$ denote the money you will gain from two-boxing. The problem is equivalent to determining and comparing the expected monetary gains from one-boxing and two-boxing---i.e., the values of $\mathbb{E}(M_o)$ and $\mathbb{E}(M_t)$. If $\mathbb{E}(M_o) > \mathbb{E}(M_t)$, you will be better off one-boxing, and vice versa.

There are two approaches to answering the problem:

1. You could base what you expect to gain on The Predictor's words. Under this approach, one-boxing yields $\$1,000,000$ with probability $100\%$ and 0 with probability $0\%$ , and two-boxing yields $\$1,001,000$ with probability $0\%$ and $\$1,000$ with probability $100\%$. Hence, $$\begin{align*} \mathbb{E}(M_o) &= \$1,000,000\cdot 100\% + 0\cdot 0\% = \$1,000,000, \qquad \text{and} \\ \mathbb{E}(M_t) &= \$1,001,000\cdot 0 + \$1,000\cdot 100\% = \$1,000. \end{align*}$$ Since $E(M_o) > E(M_t)$, you will be better off one-boxing.
2. You could base what you expect to gain on the fact that the opaque box either contains or does not contain the $\$1,000,000$. If it does, $M_o = \$1,000,000$ and $M_t = \$1,001,000$. If it does not, $M_o = 0$ and $M_t = \$1,000$. Since in both cases, $M_t > M_o$, $\mathbb{E}(M_t) > \mathbb{E}(M_o)$, and you will be better off two-boxing.

The two approaches above are both logical, but they advise you to take contradictory courses of action. It may be clear to most people what they would choose given the problem's premises, but that does not take us any closer to reaching consensus on the matter. In fact, Robert Nozick, an American philosopher and former professor at Harvard University, said, "To almost everyone it is perfectly clear and obvious what should be done. The difficulty is that these people seem to divide almost evenly on the problem, with large numbers thinking that the opposing half is just being silly." [1]

What are you to do, then?

ABOUT THE AUTHOR:
Juan Carlo Mallari is a Lecturer at the Ateneo de Manila University. He obtained his B.S. in Applied Mathematics major in Mathematical Finance at the Ateneo de Manila University in 2013 and is currently taking his Master's degree in Applied Mathematics major in Mathematical Finance at the same university.

REFERENCES:

[1] Nozick, Robert. "Newcomb's Problem and Two Principles of Choice." (1969) Retrieved from http://faculty.arts.ubc.ca/rjohns/nozick_newcomb.pdf.

[2] Speaks, Jeff. "Newcomb's problem, expected utility, and dominance." Retrieved from http://www3.nd.edu/~jspeaks/courses/2007-8/20229//_HANDOUTS/newcomb.pdf.

OLYMPIAD CORNER

from the USAMO, 1998

Problem: Prove that for each $n\geq 2$, there is a set $S$ of $n$ integers such that $(a-b)^{2}$ divides $ab$ for every distinct $a,b\in S$.

Solution: 

We will show this by induction.

For $n=2$, we can easily see that the set $S_{2}=\{1,2\}$ satisfies the condition.

Next we assume that it holds for $n=k$, in which there is a set $S_{k}=\{a_{1},a_{2},...,a_{k}\}$ such that $\left( a_{i}-a_{j}\right) ^{2}$ divides $a_{i}a_{j}$ for distinct $i$ and $j$. 

Now we will show this condition holds for $n=k+1$. Let $m$ be any multiple of $a_{1},a_{2},...,a_{k}$, and consider the set $S_{k+1}=\{b_{0},b_{1},b_{2},...,b_{k}\}$ where $b_{0}=m$ and $b_{i}=m+a_{i}$ for $i=1,2,...,k$.

Note that for $i\neq 0$, $\left( b_{i}-b_{0}\right) ^{2}=a_{i}^{2}$. Since $a_{i}$ divides $b_{0}=m$ and $b_{i}=m+a_{i}$, then $\left(b_{i}-b_{0}\right) ^{2}$ divides $b_{i}b_{0}$.

For distinct nonzero $i$ and $j$, $\left( b_{i}-b_{j}\right) ^{2}=\left(a_{i}-a_{j}\right) ^{2}$. From the inductive hypothesis, it follows that $\left( b_{i}-b_{j}\right) ^{2}$ divides $a_{i}a_{j}$. This also means that $\left( b_{i}-b_{j}\right) ^{2}$ divides $a_{i}m,a_{j}m$ and $m^{2}$. Therefore $\left( b_{i}-b_{j}\right)^{2}$ divides $a_{i}a_{j}+a_{i}m+a_{j}m+m^{2}=\left( m+a_{i}\right) \left( m+a_{j}\right) = b_{i}b_{j}$.

SOLUTIONS

(for December 7, 2013)

13. Suppose $n \geq 3$. Show that an even number of the fractions $$\frac{1}{n},\frac{2}{n},\frac{3}{n},\ldots,\frac{n-1}{n},$$ are in lowest terms. (Chinese Mathematical Olympiad 2007 Day One)
    (solved by Jan Kendrick Ong [Chang Kai Shek College] and Farrell Eldrian Wu [MGC New Life Academy]; partial credit for Jayson Dwight S. Catindig [Ateneo de Manila HS])
    
    
    SOLUTION: 
    If we are looking for fractions in lowest terms, then the numerator and denominator should be relatively prime. What we want to show is that the fractions actually come in pairs.
    
    Note that if $d|k$ and $d|n$, then $d|\left(n-k\right)$. The converse is also true. That is, if $d|\left(n-k\right)$ and $d|n$, then $d|k$. This means that if $k$ and $n$ are relatively prime, then so is $k$ and $n-k$.
    
    This means that if $\dfrac{k}{n}$ is a fraction in lowest terms, then $\dfrac{n-k}{n}$ also is. So the number of fractions come in pairs if $\dfrac{n-k}{n}\neq\dfrac{k}{n}$. Now, $\dfrac{n-k}{n}=\dfrac{k}{n}$ only if $n=2k$.
14. For every positive integer $n > 1$, prove that there exists $n$ factorials, each $> 1$, whose product is also a factorial, i.e. $x_{1}!x_{2}! \ldots x_{n}! = y!$. (Taken from Principles of Mathematical Problem Solving by Erickson and Flowers)
    (solved by Farrell Eldrian Wu [MGC New Life Academy]; partial credit for Jan Kendrick Ong [Chang Kai Shek College])
    
    
    SOLUTION: 
    We prove this by induction.
    
    Suppose $n=2$. Then if $x_{1}=5$ and $x_{2}=3$, then $5!3!=720=6!$.
    
    Let $n=k$. Suppose there exists $\left(x_{1},x_{2},\dots,x_{k}\right)$ and an integer $y$ such that $x_{1}!x_{2}!\dots x_{k}'!=y!$.
    
    We need to show that there exists $y'$ and $\left(x_{1}',x_{2}',\dots,x_{k+1}'\right)$ such that $x_{1}'!x_{2}'!\dots x_{k+1}'!=y'!$.
    
    By the induction hypothesis $$x_{1}!x_{2}!\dots x_{k}!=y!.$$ We need to find $x_{k+1}$ such that $$\left(x_{1}!x_{2}!\dots x_{k}!\right)x_{k+1}!=y!x_{k+1}!.$$ Let $x_{k+1}=y!-1$. This is greater than $1$ because $y!>2$, by definition of $y!$ being a product of factorials greater than 1. Then $x_{k+1}!=\left(y!-1\right)!$ and $$x_{1}!x_{2}!\dots x_{k}!x_{k+1}!=\left(y!\right)!.$$ We were able to find $k+1$ factorials such that the product is another factorial. By induction, we are done.
15. Find all prime numbers $a$ and $b$ such that $a^{b}+b^{a}$ is also a prime and show that there are no other prime pairs $\left(a,b\right)$ satisfying this property other than the pairs that you have.
    (solved by Jayson Dwight S. Catindig [Ateneo de Manila HS], Hans Jarrett Ong [Chang Kai Shek College], Jan Kendrick Ong [Chang Kai Shek College] and Farrell Eldrian Wu [MGC New Life Academy])
    
    
    SOLUTION: 
    Suppose $a$ and $b$ are both odd. Then $a^{b}+b^{a}\equiv0\mod2$, and $a^{b}+b^{a}$ will be greater than $2$, so $a^{b}+b^{a}$ is not prime.
    
    This means that either $a$ or $b$ is $2$. Without loss of generality, let $a=2$. Then we have $b^{2}+2^{b}$. We now consider three cases modulo $3$.
    
    If $b=3$ (the only prime multiple of $3$), then $3^{2}+2^{3}=17$, which is prime. Therefore, one pair of solutions $\left(a,b\right)$ is $\left(2,3\right)$ and $\left(3,2\right)$.
    
    Note that $b$ can only be odd. If $b\equiv2\mod3$ or $b\equiv1\mod3$, then $b^{2}\equiv1\mod3$. Since $b$ is odd,   $$2^{b}=2^{2k}2\equiv2\mod3.$$ This means that $b^{2}+2^{b}\equiv0\left(\mod3\right)$, where $b^{2}+2^{b}>3$. So $b^{2}+2^{b}$ is not prime.
    
    The only solutions are $\left(2,3\right)$ and $\left(3,2\right)$.
16. Suppose that $A$ is a finite set of points in the plane with the property that evey line determined by two points of $A$ contains a third point of $A$. Prove that $A$ is a set of collinear points.
    (solved by Hans Jarrett Ong [Chang Kai Shek College] and Farrell Eldrian Wu [MGC New Life Academy])
    
    
    SOLUTION: 
    Suppose not. Let $x$ and $y$ be two points and the line they determine $xy$, and the distance between them $\left|xy\right|$. For each $\left\{ x,y\right\} \in A$ and each point $z$ not on $xy$, consider the distance from $z$ to $xy.$ Let $x$, $y$, $z$ be points such that this distance is as small as possible, say $d$. Let the altitude from $z$ to $xy$ intersect $xy$ at $p$. Since $d$ is minimal, $p$ should lie between $x$ and $y$. Let $w$ be
    the third point on $xy$. $w$ cannot lie between $x$ and $y$. Without loss of generality, suppose $y$ is between $x$ and $w$. Then $\left|zw\right|<d$, which is a contradiction.
17. Find the real roots of the equation $$x^{3}+2ax+\frac{1}{16}=-a+\sqrt{a^{2}+x-\frac{1}{16}}\quad\left(0 < a < \frac{1}{4}\right).$$
    
    
    SOLUTION: 
    (This question was voided.)
18. Let $ABCD$ be a square, and let $k$ be the circle with center $B$ passing through $A$, and let $l$ be the semicircle inside the square with diameter $AB$. Let $E$ be a point on $l$ and let the extension of $BE$ meet circle $k$ at $F$. Prove that $\angle DAF\cong\angle EAF$. (AMOC Correspondence Problem, 1986–1987, Set One, Q1)
    (solved by Hans Jarrett Ong [Chang Kai Shek College], Jan Kendrick Ong [Chang Kai Shek College] and Farrell Eldrian Wu [MGC New Life Academy])
    
    
    SOLUTION: 
    We refer to the figure below.
    
    

    

    
    Consider arc $AF$. Note that this arc is subtended by central angle $\angle ABF$, so $m\angle ABF=mAF$.
    
    On the other hand, $\angle DAF$ is an angle whose vertex is an endpoint of the circle intercepting the same arc. This time, $m\angle DAF=\frac{1}{2}mAF$. This means that $m\angle DAF=\frac{1}{2}m\angle ABF$.
    
    We want to show that $m\angle EAF$ is also equal to $\frac{1}{2}m\angle ABF$ as well.
    
    First, note that $$\begin{align*} \angle EAF & = \angle DAB-\angle DAF-\angle BAE\\  & = 90^{\circ}-\angle DAF-\angle BAE\\  & = 90^{\circ}-\frac{1}{2}m\angle ABF-\angle BAE. \end{align*}$$ Now, observe that $\angle AEB$ intercepts a semicircle, so $\angle AEB=90^{\circ}$. In $\triangle AEB$, $$\begin{align*} 180^{\circ} & = \angle AEB+\angle BAE+\angle ABE\\  & = 90^{\circ}+\angle BAE+\angle ABF\\ 90^{\circ}-\angle ABF & = \angle BAE. \end{align*}$$ Substituting this back into the previous equation for $\angle EAF$, $$\begin{align*} \angle EAF & = 90^{\circ}-\frac{1}{2}m\angle ABF-\angle BAE\\  & = 90^{\circ}-\frac{1}{2}m\angle ABF-\left(90^{\circ}-\angle ABF\right)\\  & = \frac{1}{2}m\angle ABF. \end{align*}$$ This means that $\angle DAF=\angle EAF$.

ERRATA

Hans Jarret Ong was not noted as one of the problem-solvers for numbers 15, 16 and 18.
Minor grammatical errors in the article were corrected.