Pages

Saturday, April 21, 2018

maximum minimum of function

For $A,B,C$ non-negative angles such that $A+B+C = \pi / 2$, find the maximum and minimum of: $$ f = \sin A + \sin B + \sin C + \sin^2 A + \sin^2 B + \sin^2 C$$ and $$g = \cos A (\sin A -1) + \cos B (\sin B - 1) + \cos C (\sin C - 1)$$

AM-GM-HM

From OSP SMA 2018 For positive $a,b,c$ such that $1/a + 1/b + 1/c = 3$ prove that: $$a+b+c + \frac{4}{1+(abc)^\frac{2}{3}} \geq 5$$

Collinear marbles

From OSP SMA 2018. On a 200x200 checkerboard, we place red and blue marbles, at most 1 marble per cell. Two marbles are considered "collinear" if they are on the same column or row. For each red marble, there are exactly 5 collinear blue marbles, and for each blue marble, there are exactly 5 collinear red marbles. Find the maximum number of marbles on the board.

Tuesday, April 3, 2018

Uniquely Reachable Numbers

Let $n > 1$ be an integer. Given set $A_n = \{ 1, 1, \dots, 1, 2, 2, \dots, 2, \dots, n-2, n-2, n-1, n \}$ where there are:

$2^{n-1}$ number $1$

$2^{n-2}$ number $2$

$\dots$

$2^2$ number $n-2$

$2$ number $n-1$

$1$ number $n$

$1$ number $n+1$

(As you can see, there are a total of $2^n$ numbers in $A_n$). A positive integer is called "reachable" if it can be expressed as a sum of $2^{n-1}$ numbers in $A_n$. A reachable number is called "uniquely reachable" if that sum is unique (not counting permutations of the summands).

For example, for $n=3$, we have $A_3 = \{1,1,1,1,2,2,3,4\}$. The number 10 is uniquely reachable because it can be expressed as $10 = 1+2+3+4$ and this representation is unique (we consider $1+2+3+4$ and $3+4+2+1$ to be the same way). However, the number $6$ is not unique because $6 = 1+1+2+2 = 1+1+1+3$.

Find all the uniquely reachable numbers.

Solution

Answer: the only uniquely reachable numbers are $2^{n-1}, 2^{n-1}+1, 3.2^{n-1}-2,3.2^{n-1}-1$.

Proof:

We prove by induction. Now first note a few things:

The sum of all numbers in $A_n$ is $2^{n+1}-1$. So the number $k$ is reachable iff the number $2^{n+1}-1-k$ is reachable. Similarly, $k$ is uniquely reachable iff the number $2^{n+1}-1-k$ is uniquely reachable. We prove this by simply taking the complement of the numbers chosen to represent $k$. There are exactly half of the numbers in the set, so the sum of the numbers that are not chosen to represent $k$ will be $2^{n+1}-1-k$.

Also, the range of reachable numbers is from $2^{n-1}$ to $3.2^{n-1}-1$ (by taking the $2^{n-1}$ smallest numbers, that is all ones, all the way to the largest numbers, that is everything but ones). So any number outside of this interval is clearly not reachable by any choice of $2^{n-1}$ numbers in $A_n$.

We shall prove the following statements in tandem:

1. All numbers in the interval $[2^{n-1}, 3.2^{n-1}-1]$ are reachable

2. The uniquely reachable numbers are $2^{n-1}, 2^{n-1}+1, 3.2^{n-1}-2,3.2^{n-1}-1$.

These statements are easy to verify for $n=2$. Now suppose they all hold for $n-1$.

Claim 1: If $k$ is (uniquely) reachable in $A_{n-1}$ (it can be expressed as sums of $2^{n-2}$ numbers in $A_{n-1}$) then $k+2^{n-2}$ is (uniquely) reachable in $A_n$.

Proof: Take $k$ and its representation of $2^{n-2}$ summands, and add $2^{n-2}$ ones to it. This new representation is valid in $A_n$ because there are at most $2^{n-2}$ ones in $A_{n-1}$, and by adding $2^{n-2}$ more ones, we are using at most $2^{n-1}$ ones. The other numbers that are represented in $A_{n-1}$ are unchanged and still available to use in $A_n$. Each distinct representation of $k$ will yield a new representation of $k + 2^{n-2}$, so the uniqueness of reachability also transfers to the new representation.

Claim 2: If $k$ is (uniquely) reachable in $A_{n-1}$ then $k + 3.2^{n-2}$ is (uniquely) reachable in $A_n$.

Proof: If $k$ is (uniquely) reachable in $A_{n-1}$ then $2^n-1-k$ is (uniquely) reachable in $A_{n-1}$, then by claim 1, $2^n-1-k+2^{n-2}$ is (uniquely) reachable in $A_n$, therefore $2^{n+1}-1-(2^n-1-k+2^{n-2}) = k + 3.2^{n-2}$ is also (uniquely) reachable in $A_n$.

From the two claims above, because all numbers in the interval $[2^{n-2}, 3.2^{n-2}-1]$ are reachable in $A_n$, now we apply claim 1 to this interval. We have the interval $[2^{n-1}, 2^n-1]$ reachable in $A_n$. Similarly, we apply claim 2 to this interval, we have $[2^n, 3.2^{n-1}-1]$ reachable in $A_n$. By combining these two intervals, we have $[2^{n-1}, 3.2^{n-1}-1]$ reachable in $A_n$. Thus we have proven statement 1 of the induction hypothesis.

Now we prove uniqueness. By induction hypothesis, the numbers in the interval $[2^{n-2}+2, 3.2^{n-2}-3]$ are reachable but not uniquely in $A_{n-1}$. By claim 1, we can the interval $[2^{n-1}+2, 2^{n}-3]$ is reachable but not uniquely. Likewise, we can claim 2 to establish that the interval $[2^n+2, 3.2^{n-1}-3]$ is reachable but not uniquely. Then now we know that all numbers in the interval $[2^{n-1}+1, 3.2^{n-1}-3]$ are reachable but not uniquely, except of the following four numbers: $2^n-2, 2^n-1, 2^n, 2^n+1$. They are reachable but not yet proven as uniquely reachable.

Claim 3: If $k$ is (uniquely) reachable in $A_{n-1}$ then $k + 2^{n-1}$ is (uniquely) reachable in $A_n$.

Proof: First note that $A_n$ can be formed by adding one to each element of $A_{n-1}$ and then adding $2^{n-1}$ to it. Now, take any representation of $k$ in $A_{n-1}$. Add 1 to each summand, and then add $2^{n-2}$ ones to it. Now we have $2^{n-1}$ summands, and only $2^{n-2}$ are ones. The rest (the higher summands) are valid in $A_n$ because they were 1 more than the summands that were valid in $A_{n-1}$. The new sum is $k + 2^{n-2} + 2^{n-2} = k+2^{n-2}$. Distinct representations in $A_{n-1}$ would also result in distinct representations in $A_n$.

Because $n \geq 4$, we have $2^{n-2}+2 \geq 2^{n-1}-2$ and $2^{n-1} \leq 3.2^{n-1}-3$, so by induction hypothesis, $2^{n-1}-2$ and $2^{n-1}$ are non-uniquely reachable in $A_{n-1}$, then $2^n-2$ and $2^n$ are non-uniquely reachable in $A_n$. Then, their complements $2^n-1$ and $2^n+1$ are also non-uniquely reachable. This completes our proof of statement 2

Friday, March 23, 2018

Integral and Inequality

Suppose $f(x)$ is a continuously differentiable function on $[a,b]$ satisfying: $$f(a) = f(b) = 0$$ $$\int_a^b (f(x))^2 dx = 1$$ Then show that: $$\int_a^b x^2 (f'(x))^2 dx \geq \frac{1}{4}$$

Solution

By Cauchy: $$\int_a^b x^2(f'(x))^2 dx = \int_a^b (f(x))^2 dx . \int_a^b x^2(f'(x))^2 dx \geq (\int_a^b xf'(x)f(x)dx)^2$$ The last integral can be evaluated using integration by parts, using $u=x$ and $dv = f'(x)f(x)dx$ which yields $v = (f(x))^2/2$, so that: $$\int_a^b xf'(x)f(x)dx = \frac{bf^2(b) - af^2(a)}{2} - \frac{1}{2} \int_a^b (f(x))^2 dx = -\frac{1}{2}$$ so: $$\int_a^b x^2 (f'(x))^2 dx \geq \frac{1}{4}$$

Friday, December 15, 2017

Monic polynomial divisible by 2018

Let $P(x)$ a monic polynomial (polynomial having leading coefficient one) with integer coefficients such that $P(k)$ is divisible by 2018 for all integer $k$. Find the smallest possible degree of $P$

Solution

Note that $P(x) = x(x+1)(x+1) \dots (x+1008)$ is always divisible by 1009, because one of the factors is always divisible by 1009. It's also even. Therefore $P(x)$ is a polynomial that satisfies the problem requirement, having degree 1009. We shall show that this degree is minimal.

We call a polynomial (not necessarily monic) "good" if it has property that $P(k)$ is divisible by 2018 for all integer $k$.

Suppose $P_n(x)$ is a good monic polynomial having degree $n$, then we apply the following procedure: let $P_{n-1}(x) = P_n(x+1) - P_n(x)$. Then $P_{n-1}$ is a polynomial of degree $n-1$ (because the $x^n$ terms cancel out). Because $P_n$ is good, then $P_{n-1}$ is also good. Furthermore, the leading coefficient of $P_{n-1}$ is $n$, because the only source of $x^{n-1}$ terms is from the expansion of $(x+1)^n$. The other $x^{n-1}$ terms cancel out as well.

We continue this process to obtain $P_{n-2}, P_{n-3},$ and so on. At each step, define $P_m(x) = P_{m+1}(x+1) - P_{m+1}(x)$. We claim the following facts:

1. $P_m$ is good

2. The leading coefficient of $P_m$ is $n(n-1)(n-2) \dots (m+1) = \frac{n!}{m!}$

The two facts can be shown simultaneously using induction. It's obviously true for $m=n$, and as we demonstrated, it's also true for $m=n-1$. If it's true for $m+1$ then it's easy to see that it's true for $m$ as well, using the same argument we showed above.

Thus, at some point, we will arrive at $P_0$ having leading coefficient $n!$. That is, $P_0(x) = n!$ for all $x$, and this must be divisible by 2018 because $P_0$ is good. Therefore $n!$ is divisible by 2018.

What we showed was the necessary condition for a monic polynomial to be good. That is, if it has degree $n$ then $n!$ is divisible by 2018. The smallest possible such $n$ is 1009 because 1009 is prime. But we also showed a sufficient condition, that there exists a polynomial with degree 1009 that's both monic and good. Thus the answer is 1009.

Wednesday, December 13, 2017

Non-attacking rooks

Given an $n \times n$ chess board and $2n+1$ rooks placed on it, prove that we will always be able to choose 3 rooks who can't attack each other.

Solution

Partition the board into $n$ groups in a "broken diagonal" pattern. That is, cell $(i,j)$ belongs to group $i+nj \mod n$. Two cells in the same group can't attack each other (easily shown either by diagonal argument or modular analysis).

Because there are $2n+1$ rooks, then there are 3 rooks that sit on the same group.