Monday, August 5, 2013

Fractional inequality

Let $x, y > 0$, $x \neq y$, and let $n > 1$ be an integer.

If $x^n - y^n = x^{n+1} - y^{n+1}$, show that $$1 < x+y < \frac{2n}{n+1}$$

Solution Let $f(x) = x^n ( 1 - x)$ and we have $f(x) = f(y)$. WLOG, we may assume that $x If $y > 1$ then $f(y)$ is negative, so that $f(x)$ is negative, which means $x > 1$ as well. But $f(x)$ is monotonically decreasing for $x > 1$ (because $x^n$ is monotonically increasing and $1-x$ is monotonically decreasing). Contradiction.

If $y=1$ then $f(x) = f(y) = 0$ impossible for $x>0$. Contradiction.

If $0 < x < y < 1$, we draw the graph of $f(x)$. It starts off at (0,0), going up to a maximum between 0 and 1, and goes back down to (1,0). This graph can be deduced easily be realizing that $f(x) = x(1-x) . x^{n-1}$. Because $x(1-x)$ only has one turning point and $x^{n-1}$ is monotonically increasing (or constant), then $f(x)$ also only has one turning point.

We can find that turning point by using AM-GM: $$f(x) = x.x\dots x.(1-x)$$ $$ = \frac{1}{n} x.x\dots x.(n-nx)$$ $$ \leq \frac{1}{n} (\frac{n}{n})^n = \frac{1}{n}$$ Equality happens when $x = n-nx$ or $x = \frac{n}{n+1}$. Note that for $n>1, \frac{n}{n+1} = 1 - \frac{1}{n+1}> 1/2$

Monotonically increasing sequences with sums

Let $a_1, \dots, a_{1007}$ and $b_1, \dots, b_{1007}$ be monotonically increasing sequences such that:

For all $i$, $0 \leq a_i \leq 2013$ and $0 \leq b_i \leq 2013$.

For $i \neq j$, $a_i + a_j \neq 2013$ and $b_i + b_j \neq 2013$

$a_0 = b_0$

There exists a real number S such that for all $i$, $a_i + b_{1008-i} = S$.

What are the possible values of $S$?


Note that for $a_i$ and $b_i$, we need to choose 1007 numbers from 2014 numbers (0,1,...,2013) and no two of those chosen ones may add up to 2013. Thus, from each of the following pairs of numbers $(0,2013), (1,2012), \dots, (1006,1007)$ we must choose exactly one number. Thus, at most one of 0 or 2013 may be chosen. For now, let's assume that $a_1 = b_1 = 0$, which means 2013 is not chosen in both $a_i$ and $b_i$. We'll deal with the other cases later.

Let $k$ be the first number that is not chosen in $a_i$. That means $0, \dots, k-1$ are all chosen, so we have $a_1 = 0, a_2 = 1, \dots, a_k = k-1$.

This also means that $2013, \dots, 2013-(k-1)$ are not chosen but $2013-k$ is chosen. In other words, $2013-k$ is the largest chosen number in $a_i$, so $a_{1007} = 2013-k$. Because $b_1 = 0$ then $S = 2013-k$. That means $b_{1007}=2013-k - a_0 = 2013-k$

Because $2013-k$ is the largest chosen number in $b_i$, then $2013-k+1,\dots,2013$ are not chosen in $b_i$, therefore $0,\dots,k-1$ are chosen in $b_i$ and $k$ is not chosen in $b_i$.

Because $0,\dots,k-1$ are chosen in $b_i$, and $S = 2013-k$, that means $2013-k, 2013-k-1, \dots, 2013-(2k-1)$ are chosen in $a_i$, which means $k,k+1,\dots,2k-1$ are not chosen in $a_i$. Likewise, because $0,\dots,k-1$ are chosen in $a_i$, and $S = 2013-k$, that means $2013-k, 2013-k-1, \dots, 2013-(2k-1)$ are chosen in $b_i$, which means $k,k+1,\dots,2k-1$ are not chosen in $b_i$.

At this point, we have established the following fact:

  • The first $k$ numbers in $a_i$ and $b_i$ are chosen, and the next $k$ numbers are not chosen.
  • The last $k$ numbers in $a_i$ and $b_i$ are not chosen, and the previous $k$ numbers are chosen.
We would like then to claim that this pattern would have to continue itself all the way to the "middle" of the sequences, which finally means that $2k$ divides 2014. Formally, we claim that for each $m \geq 0$, we have the following:
  • $2km, \dots, (2m+1)k-1$ are chosen in $a_i$ and $b_i$.
  • $(2m+1)k, \dots, (2m+2)k-1$ are not chosen in $a_i$ and $b_i$.
  • $2013-((2m+1)k-1), \dots, 2013-2km$ are not chosen in $a_i$ and $b_i$.
  • $2013-((2m+2)k-1), \dots, 2013-(2m+1)k$ are chosen in $a_i$ and $b_i$.
The case of $m=0$ has been proven above. Now suppose it holds for $m$.

Because $(2m+1)k, \dots, (2m+2)k-1$ are not chosen in $a_i$ and $S = 2013-k$ then $2013-k-((2m+2)k-1), \dots, 2013-k-(2m+1)k$ are not chosen in $b_i$. In other words, $2013-((2m+3)k-1), \dots, 2013-(2m+2)k$ are not chosen in $b_i$. Similarly, they're not chosen in $a_i$ as well.

Now because those are not chosen in $b_i$, then $(2m+2)k,\dots,(2m+3k)-1$ are chosen in $b_i$. Similarly, chosen in $a_i$ as well.

Because $S=2013-k$ and $(2m+2)k,\dots,(2m+3k)-1$ are chosen in $b_i$ then $2013-((2m+4)k-1), \dots, 2013-(2m+3)k$ are chosen in $a_i$, and similarly, chosen in $b_i$ as well.

Because the above are chosen, then $(2m+3)k, \dots, (2m+4)k-1$ are not chosen in $a_i, b_i$, and this completes the induction step.

So now that our claim is proven, we note that this pattern must continue for all values of $m$ as long as no index becomes negative. There is no restriction of the value of $m$ in our proof of the claim. That means that towards the end of the sequence, our pattern must "line up" with what we know about $a_{1007}$ and $b_{1007}$, namely, that $2013-k$ is the largest chosen number in the sequence. This means that the sequence of numbers from 0 to 2013 is divided into an even number of groups, each having $k$ elements. Each group would alternate between all being chosen and all being not chosen. It's easy to check that this configuration matches the conditions above.

From there, we know that $2k | 2014$ or $k | 1007$. Because $1007 = 19 \times 53$, then we have four possible values of $k$.

If $k=1$, then both sequences look like this: $0,2,4,\dots, 2012$. Then $S=2012$.

If $k=19$, then both sequences look like this: $0,1,2,\dots,17,18,38,39,\dots,55,56,\dots, 988$. Then $S=1994$.

If $k=53$, then both sequences look like this: $0,1,2,\dots,51,52,106,107,\dots,158,159,\dots, 988$. Then $S=1960$.

If $k=1007$, then both sequences look like this: $0,1,2,\dots,1006$. Then $S=1006.

Now, we have to address the case where 0 is not chosen in $a_i$ and $b_i$. We define new sequences $c_i = 2013-a_{1008-i}$ and $d_i = 2013-b_{1008-i}$. It's easy to see that $c_i,d_i$ satisfy the conditions of the problem, and since $0$ is not chosen in $a_i,b_i$ then 2013 must be chosen in them, which means $0$ is chosen in both $c_i,d_i$. This reduces $c_i,d_i$ to the case above, except $S$ is replaced with $4026-S$.

Because the possible values for $S$ in the first case is $1007,1960, 1994, 2012$ then the possible values for $S$ in this case is $2014,2032,2134,3020$.

Marble distribution

In a class, the teacher gives each student $n$ marbles, and each marble was either red, blue, or green. Each student gets a different combination of marbles (i.e. no two students get the same number of red, blue, and green marbles altogether). Also, no two students have a total of exactly $n$ marbles of any color between them. What is the maximum number of students in the class?