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 2013a_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$? Solution 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?