Elegant number limited

A number is called "elegant" if it is equal to the sum of its digits raised to the consecutive powers in decimal respresentation. In other words, if $S = a_1 a_2 \dots a_n$ is elegant then $S = a_1^1 + a_2^2 + \dots + a_n^n$

For example, $89 = 8^1 + 9^2$ is an elegant number. Also, $$2646798 = 2^1 + 6^2 + 4^3 + 6^4 + 7^5 + 9^6 + 8^7$$ is an elegant number

Prove or disprove: there exists an infinite number of elegant numbers

Solution

We shall prove that there exists only a finite number of elegant numbers because for large enough $N$, it is impossible for an $N$-digit elegant number to exist.

If $S = a_1\dots a_N$ is elegant then $S \geq 10^{N-1}$ because $S$ is an $N$ digit number. But at the same time: $$S = a_1^1 + \dots + a_N^N \leq 9^1 + \dots + 9^N = \frac{9^{N+1}-1}{8}$$ So we have: $$10^{N-1} \leq \frac{9^{N+1}-1}{8}$$ The function on the LHS grows faster than the RHS because the exponentiation base is larger. So this inequality ceases to be true for large enough $N$. In fact: $$\iff (10/9)^{N+1} \leq 12.5$$ $$\iff N \leq \frac{\log (12.5)}{\log (10/9)} -1 \sim 22.9$$ So for $N = 23$ we already find that there cannot exist a 23-digit elegant number

Prove square root is irrational

Prove that for any positive integer $n$, then $$\sqrt{\frac{n}{n+1}}$$ is irrational.

Solution

If $n+1$ is a square then we only need to show that \sqrt{n} is irrational, which amounts to showing that it's not a square. This follows the fact that if $n+1$ and $n$ are both squares then $n=0$, contradicting problem condition.

If $n+1$ is not a square, then it has prime factors with odd powers in $n$. Let $k$ be the largest of such factor and $a$ is its power. Meaning, $k^a | n+1$ but $k^{a+1}$ does not divide $n+1$.

Now suppose there exist $p,q$ relatively prime such that $$\sqrt{\frac{n}{n+1}}=\frac{p}{q}$$ $$(n+1)p^2 = nq^2$$ Because $k^a | LHS$ then $k^a | RHS$. If $k^a | n$ then $k | (n+1)-n = 1$, a contradiction (because $k$ is a prime).

And because $k$ is prime then $k^a | q^2$ which means $k^{a+1} | q^2$ (because $a$ is odd). This means that $k$ divides $p$, contradicting our assumption that $p,q$ are relatively prime.

Sum over hypercube

Let $n$ be a positive integer, and suppose $a = a_1, \dots, a_{2019}$ is a sequence of integers each ranging from $1,\dots,n$. Determine the sum of $$\sum_a \frac{a_1 - a_2 + a_3 + \dots -a_{2018} + a_{2019}}{a_1 + \dots + a_{2019}}$$ Where the sum is taken over all possible sequences in that range.

Cube sum of digits

Find all integers that is equal to the cube of sum of its digits.

Solution

Clearly 0 satisfies the problem statement, and negative numbers cannot satisfy. So now we may assume that the integer is positive.

Suppose $N = a_1 \dots a_d$ where each $a_i$ is a single digit, and $a_1 \neq 0$. Because $N \geq {10}^{d-1}$ and $N = (a_1 + \dots + a_d)^3 \leq (9d)^3$ so we must have: $$10^{d-1} \leq 9d^3 $$

For large $d$ this inequality fails to hold. In fact, it's only true for $d \leq 4$. So $N$ is a 4-digit number, which is also a cube. Therefore $N \leq 21^3$ because $22^3 > 10^5$.

Now consider modulo 9: we know that $N \equiv (a_1 + \dots + a_d) \mod 9$ so: $$ N = (a_1 + \dots + a_d)^3 \equiv N^3 \mod 9$$ Among all the residues modulo 9, only 0, 1, 8 satisfy $x \equiv x^3 \mod 9$. Therefore $N \equiv 0, 1, 8 \mod 9$.

So now our candidates are: $N = 1^3, 8^3, 10^3, 17^3, 18^3$. By inspection, only $N = 1^3 = 1, 8^3 = 512, 17^3 = 4913, 18^3 = 5832$ satisfy.

Maximum point above triangle

In triangle $ABC$, $AD$ is an internal bisector. Choose point $X$ on $DA$'s extension, and let $Y,Z$ be on $XB$ and $XC$ so that $AY \perp XB$ and $AZ \perp XC$. Define $f(X)$ as: $$f(X) = \frac{AY}{XB} + \frac{AZ}{XC}$$ Find the point $X*$ along $DA$'s extension such that $f(X*)$ is maximum.

Solution

Let $\theta = \angle XAB = \angle XAC$. Easy to see that $\pi/2 < \theta < \pi$. Let $x = AX$.

Area of $\triangle ABX$ = $$\frac{1}{2}cx \sin \theta = \frac{1}{2} XB.AY$$ So: $$\frac{AY}{XB} = \frac{cx \sin \theta}{XB^2} = \frac{cx\sin \theta}{c^2+x^2-2cx \cos \theta}$$ And likewise: $$\frac{AZ}{XC} = \frac{bx\sin \theta}{b^2+x^2-2bx \cos \theta}$$ Now suppose WLOG $c > b$ and $c = tb$ (with $t > 1$). Then we need to maximize: $$\frac{cx}{c^2+x^2-2cx \cos \theta} + \frac{bx}{b^2+x^2-2bx \cos \theta}$$ $$ \frac{\frac{x}{bt}}{(\frac{x}{bt})^2 + 1 - 2 t\frac{x}{bt}\cos \theta }+\frac{\frac{x}{b}}{(\frac{x}{b})^2 + 1 - 2 \frac{x}{b}\cos \theta }$$ So if we let $y = x/b$, and $r = -2 \cos \theta$ (which means $0 < r < 2$), and $g(s) = s/(s^2+rs+1)$ then the problem is akin to finding the minimum of the following function for $y > 0$: $$h(y) = g(y) + g(\frac{y}{t})$$

Shifting matrix

An $n \times n$ matrix is filled with numbers, where there are $k$ number ones and the rest zero. The operation that is allowed on the matrix is to shift a single column down by one (so that each number in that column moves down by one, and the bottom most number goes to the top), or to shift a single row to the left by one.

Determine all $k$ such that, no matter how the initial condition is, through a series of operations, we can make it so that each column and each row has an even sum.

For $x,y,z$ positive numbers such that $xyz = 1$, prove that: $$2 \sqrt{2} (x^7+y^7)(x^7+z^7)(y^7+z^7) \geq \sqrt{(x^{16}+7)(y^{16}+7)(z^{16}+7)}$$

Solution

$$2(x^7+y^7)(x^7+z^7) = x^{14} + (x^{14} + 2x^7(y^7+z^7) + 2y^7z^7)$$ by AM-GM: $$ \geq x^{14} + 7x^6y^4z^4 = \frac{x^{16}+7}{x^2}$$ By multiplying similar inequalities and taking square root, we get the desired result

Find all m for inequality

Find all real number $m$ such that, for all positive real numbers $x,y,z$ the following is true: $$ \frac{x}{x^2 + myz} + \frac{y}{y^2 + mxz} + \frac{z}{z^2 + mxy} \geq \frac{9}{(m+1)(x+y+z)}$$

Solution

First we show that for $m \geq 8$ it's true. By Cauchy: $$\frac{x}{x^2 + myz} + \frac{y}{y^2 + mxz} + \frac{z}{z^2 + mxy} \geq \frac{(x+y+z)^2}{x^3 + y^3 + z^3 + 3m.xyz}$$ Then let $A = x^2 + y^2 + z^2,B = xy+yz+zx$. Because $x^3+y^3+z^3 = (x+y+z)(A -B)+3xyz$, $$ = \frac{A+2B}{(x+y+z)(A-B)+3(m+1)xyz} \geq \frac{9}{(m+1)(x+y+z)}$$ The last inequality is equivalent to (because $A \geq B$ we may multiply by the denominators without changing the sign): $$(A+2B)(x+y+z)(m+1) \geq 9(x+y+z)(A-B) + 27(m+1)(x+y+z)$$ $$\iff (x+y+z)[(m-8)A + (2m+11)B] \geq 27(m+1)xyz$$ Indeed by AM-GM: $$x+y+z \geq 3 \sqrt[3]{xyz}$$ $$ A \geq 3 \sqrt[3]{x^2y^2z^2}$$ $$ B \geq 3 \sqrt[3]{x^2y^2z^2}$$ So: $$ (x+y+z)[(m-8)A + (2m+11)B] \geq 3 \sqrt[3]{xyz} [3(m-8) \sqrt[3]{x^2y^2z^2} + 3(2m+11)\sqrt[3]{x^2y^2z^2} = 27(m+1)xyz$$ Now to show necessity, plug in $z = t, x=y=1$, then the left hand side is : $$ \frac{2}{1+mt} + \frac{t}{t^2+m} \geq \frac{9}{(m+1)(2+t)}$$ $$(2(t^2+m)+t(mt+1))(2+t)(m+1) \geq 9(t^2+m)(mt+1)$$ which has to be true for all $t \geq 0$. However, the coefficient of $t^3$ on the LHS is $m(m+1)$ and on the RHS is $9m$. Because this inequality has to be true for all $t$ no matter how big, then the coefficient on the LHS has to be greater than or equal to that of the RHS, otherwise we can choose $t$ large enough to violate that expression. $$m(m+1) \geq 9m$$ which means $m \geq 8$.

Inequality a b c

For $a,b,c \geq 0$ prove that: $$2(a+b+c)^2 + 3(ab+bc+ca) \geq (a+b+c)(\sqrt{a} + \sqrt{b} + \sqrt{c})^2$$

Solution

This is equivalent to: $$(a+b+c)^2 + 3(ab+bc+ca) \geq 6(a+b+c)(\sqrt{ab} + \sqrt{bc} + \sqrt{ca})$$ which is the cyclic sum of: $$(a+b+c)^2 + 9ab \geq 6 \sqrt{ab}(a+b+c)$$ which is true by AM-GM.

Generalization

Find all $\lambda$ such that this holds for all $a,b,c \geq 0$: $$(a+b+c)^2 + \lambda (ab+bc+ca) \geq \frac{\lambda + 3}{9}(a+b+c)(\sqrt{a}+\sqrt{b}+\sqrt{c})^2$$

Solution

For $0 \leq \lambda \leq 3/2$ we can show it by proving the original problem, and realizing that: $$3(a+b+c)^2 \geq (a+b+c)(\sqrt{a} + \sqrt{b} + \sqrt{c})^2$$ is just AM-RMS.

Inequality x y z

If $x,y,z$ are positive numbers such that $x+y+z = 1$ show that: $$ \frac{1}{x+y} + \frac{1}{x+z}+ \frac{1}{y+z} + \frac{9}{2} \geq \frac{3}{1 - (\frac{x-y}{2})^2} + \frac{3}{1 - (\frac{y-z}{2})^2} + \frac{3}{1 - (\frac{x-z}{2})^2}$$

(Hopefully) Correct Solution

WLOG we may assume that $x \geq y \geq z$. And for now we assume that $2y \geq x+z$ (the case where $2y < x+z$ is handled later below).

By AM-HM: $$\frac{1}{y+z} + \frac{1}{y+z} + \frac{1}{x+z} \geq \frac{9}{(y+z)+(y+z)+(x+z)} = \frac{9}{1+y+2z} = \frac{9}{2+z-x}$$ $$\frac{1}{y+z} + \frac{1}{x+z} + \frac{1}{x+z} \geq \frac{9}{1+x+2z} = \frac{9}{2+z-y}$$ Adding the two inequalities: $$ \frac{1}{y+z} + \frac{1}{x+z} \geq \frac{3}{2+z-x} + \frac{3}{2+z-y} $$ (Call this inequality 1).

Incorrect Solution

WLOG we may assume that $x \geq y \geq z$. Suppose $a = x-z, b = x-y$ so $a+b = 2x-y-z = 3x-1$. If $a=b=0$ then $x=y=z=1/3$ and equality happens. Thus at least one of $a,b$ is positive, so $a+b > 0$. Now, by Cauchy: $$(\frac{a}{a+b} . \frac{1}{y+z} + \frac{b}{a+b} . \frac{3}{2})(\frac{a(y+z)}{a+b} + \frac{2b}{3(a+b)}) \geq (\frac{a}{a+b} + \frac{b}{a+b})^2 = 1$$ So: $$\frac{a}{a+b} . \frac{1}{y+z} + \frac{b}{a+b} . \frac{3}{2} \geq \frac{3(a+b)}{3a(y+z) + 2b} = \frac{3}{2+z-x}$$ The last equality is equivalent to: $$ \frac{1(a+b)}{3a(y+z) + 2b} = \frac{1}{2+z-x} $$ $$ \iff (a+b)(2+z-x) = 3a(y+z) + 2b $$ Because $2+z-x \iff 3-2x-y$ and $y+z = 1-x$ $$ \iff (3x-1)(3-2x-y) = 3(x-z)(1-z) + 2(x-y)$$ Upon expanding and rearranging: $$ \iff 0 = 3(x-1)(x+y+z - 1) $$ which is true. On the other hand, using the same definition of $a,b$, we can also show: $$\frac{b}{a+b} . \frac{1}{y+z} + \frac{a}{a+b} . \frac{3}{2} \geq \frac{3(a+b)}{3b(y+z) + 2a} = \frac{3}{2+y-x}$$ (Using similar identity as above) Adding the two inequalities, we have: $$ \frac{1}{y+z} + \frac{3}{2} \geq \frac{3}{2+z-x} + \frac{3}{2+y-x}$$ And similarly: $$ \frac{1}{x+z} + \frac{3}{2} \geq \frac{3}{2+x-y} + \frac{3}{2+z-y}$$ $$ \frac{1}{x+y} + \frac{3}{2} \geq \frac{3}{2+y-z} + \frac{3}{2+z-x}$$ Now all we need to show is that the sum of LHS is equal to the LHS of the given problem. Indeed it is so because: $$ \frac{3}{2+y-x} + \frac{3}{2+x-y} = \frac{3(2+x-y) + 3(2+y-x)}{2^2 - (x-y)^2} = \frac{12}{4 - (x-y)^2} = \frac{3}{1 - (\frac{x-y}{2})^2}$$ Edit: what is wrong with this proof?

Inequality a,b,c

For $a,b,c$ non-negative real numbers such that $a+b+c=1$, prove that: $$(3a+1)(3b+1)(3c+1) \geq 3 \sqrt{3}(\sqrt{a} + \sqrt{b})(\sqrt{b}+\sqrt{c})(\sqrt{c}+\sqrt{a})$$

Solution

With Cauchy we have: $$(3a + 1)(1 + 3b) \geq (\sqrt{3a} + \sqrt{3b})^2 = 3(\sqrt{a} + \sqrt{b})^2$$ Multiplying all of the similar inequalities, we get the desired result. Equality happens if and only if $3a = 1/(3b), 3b = 1/(3c), 3c = 1/(3a)$, which means $a=b=c = 1/3$.

Tricolored polygon

Given a regular $(3n+2)$-gon, the vertices are colored with red, blue, or green such that there are $n+1$ green points, $n+1$ blue points, and $n$ red points. Prove that there exists a line going through a blue point and a green point, such that on one side of the line there are $k$ points of each color, and on the other side there are $(n-k)$ of each color (with $k \geq 0$).

Solution

First we claim that there is a way to pair each blue point with a green point such that the segments formed by each pair is non-intersecting. Proof:

Delete all the red points for now, so we are left with polygon with $(n+1)$ blue and green points each. Take any adjacent pair of a blue point and a green point, pair them, and then delete them. Now we are left with $n$ blue and green points each. Recursively apply this procedure until we are done. It's easy to see that the resulting segments are non-intersecting.

Now that we have $n+1$ such segments, label the points $(b_1, \dots, b_{n+1}, g_1, \dots, g_{n+1})$ where $b_i$ is a blue point that is paired with $g_i$. Let $S_i$ denote the segment formed by $b_ih_i$. Pick an arbitrary red point $R$. We define the following terminology: each segment divides the polygon into two. The "good" side of the segment is the side that contains $R$.

Since no two segments can intersect, then for two different segments $S_i,S_j$, one is fully on the good side of the other. If $S_i$ is fully contained in the good side of $S_j$ then we say that $S_j$ "covers" $S_i$. Note that for any two segments, if $S_i$ covers $S_j$ then $S_j$ does not cover $S_i$, and one necessarily covers the other.

Note the following properties. If $S_a$ covers $S_b$ and $S_b$ covers $S_c$ then $S_a$ covers $S_c$. Conversely, if $S_a$ and $S_b$ both cover $S_c$ then either $S_a$ covers $S_b$ or $S_b$ covers $S_a$. So we may define the relationship called "immediate covering." We say $S_a$ immediately covers $S_b$ if $S_a$ covers $S_b$ and there's no other $S_c$ such that $S_a$ covers $S_c$ and $S_c$ covers $S_b$.

Consider the graph with $n+1$ vertices $1,2,\dots,n+1$ and the edges where $i \to j$ if $S_i$ immediately covers $S_j$. Each segment can only be immediately covered by at most one other segment, so this graph is a tree. It cannot be a forest because for each root of each tree, one necessarily covers the other so there can only be one true root. Define the "height" of each node to be the distance between node $i$ to it's farthest leaf. So every leaf has height zero. If $i$ is a leaf and $S_j$ immediately covers $S_i$ (and only $S_i$), then $j$ has height 1, and so on. If a node has several children of differing heights, then the height of the node is 1 plus the maximum of its children's height.

Now also for each $i$, define $A_i$ to be the number of red points that are located on the good side of $S_i$. Define $B_i$ to be the number of descendants of $i$ in the above-mentioned graph. So, our aim is to show that there exists an $i$ such that $A_i = B_i$, because this would mean that on the good side of $S_i$, there are precisely $A_i$ red points, and $B_i$ segments, each of which contains $B_i$ blue points and $B_i$ green points. Now suppose, in our configuration, there is no $i$ such that $A_i = B_i$.

Our claim now is that for each $i$, $A_i > B_i$. We prove this by induction on the height of the nodes.

We start by looking at the leaves. If there's any leaf $i$ with $A_i = 0$ then there is a contradiction, because $B_i = 0$. So for each leaf $i$, $A_i \geq 1 > 0 = B_i$.

Now suppose that $A_i > B_i$ (which means $A_i \geq B_i + 1$) for each node of height $0, 1, \dots, k$, then let $S_a$ be a node of height $k+1$, and let its children be $S_{b_1}, \dots, S_{b_m}$. Its children has height at most $k$, so for each $i$, $A_{b_i} \geq B_{b_i}$ holds. Now, each red point on the good side of $S_{b_i}$ is also on the good side of $S_a$, therefore $$A_a \geq A_{b_1} + \dots + A_{b_m} \geq (B_{b_1} + 1) + \dots + (B_{b_m}+1) = m + \sum B_{b_i} = B_a$$ The first inequality is due to the fact that each red point in $A_{b_i}$ must be contained in $A_a$ as well (although there may be more red points in $A_a$. The second inequality is from induction hypothesis. The third inequality is by construction of the graph and definition of $B_a$, because the number of descendants of $S_a$ can be counted by summing the number of descendant of children, plus each of the children themselves.

So we established that $A_a \geq B_a$, but because we assumed that there is not $A_i = B_i$, then $A_a > B_a$. Thus, by induction on the height of each node, we can claim that $A_i > B_i$ for each $i$ in the whole graph.

Now consider the root node $r$. We concluded that $A_r > B_r$. But $A_r$ is the number of red points on the good side of $S_r$, which is at most $n$. $B_r$ is the number of descendants of $S_r$, which is $n$. Contradiction.

Thus there must be an $i$ such that $A_i = B_i$ and that is our desired segment.

Moving coins across the board

On a $1 \times 2018$ chess-board, the $n (n < 2018)$ left-most squares contain 1 coin each. Alice and Bob are playing a game, where on each turn the player may choose a coin and move it to the right one or two units. The only condition is that each square may only contain one coin at a time (no "stacking"), except the last square (right-most square). Alice goes first. The player who cannot make a legal move loses. Determine all $n$ such that Alice has a winning strategy.

Solution

Label each square by its distance from the right-most square. So the right-most square is called square zero, and the left-most square is called square 2017. Suppose $(a_1, a_2, \dots, a_k)$ denotes the condition that there is a coin on each of the cells $a_1, \dots, a_k$ and the rest of the coins are in the square zero. WLOG, we may assume $a_1 < a_2 < \dots < a_k$.

Claim:

We claim that $(a_1, \dots, a_k)$ is a losing position if and only if $a_1 + \dots + a_k$ is divisible by 3.

First note that the game ends only when there's no more legal move left, and that's when all the coins are on square zero. So as long as the sum of the coin numbers are greater than zero, there is always a legal move available. At the very least, the coin with the lowest number can be moved to the right 1 or 2 steps (possibly reaching zero in the process).

Lemma:

If the sum of the numbers are not divisible by 3, there is always a legal move to make it divisible by 3 within one turn.

Note that our claim is a corollary of the lemma. If the sum of the numbers is divisible by 3, then no matter what move you do, you can only reduce it by 1 or 2. Based on the lemma, the opponent can always counter it by bringing down to the next multiple of 3. Therefore, your opponent will never face the situation without any legal move. Conversely, if it's not divisible by 3, you can always bring it to a multiple of 3 within one turn so that your opponent is facing a losing position next. And your winning strategy is always to keep the sum of the numbers divisible by 3.

Proof of lemma:

If the the sum of the numbers is $3m+1$, then you only need to move the lowest-numbered coin down by 1. This is always possible because it is at least 1. If the sum of the numbers is $3m+2$, then you need to move ANY coin down by 2. Suppose that this is not possible, either due to prospect of collision or running against the end of the board. That means the following:

1. There are no two consecutive empty cells. If there are two or more consecutive empty cells, then the coin to the left of that block can be moved down by two. This means that $a_i - a_{i-1} = 1,2$ for each $i$.

2. There is nothing on cell 2, because otherwise we can always move it to cell 0 directly.

3. There is no "jumping over" possible. Meaning, if cell $x$ is empty but $x+1,x+2$ are both occupied, we can take $x+2$ and move it to $x$. So this configuration is not allowed: EMPTY, OCCUPIED, OCCUPIED.

This means cell 1 has a coin on it. $a_1 = 1$. Since 2 is empty, then 3 must have a coin on it ($a_2 = 3$). If 4 has a coin on it, then it violates condition 3 above, so 4 must be empty. That means 5 must be occupied (by condition 1). We can continue this pattern indefinitely, to arrive at the conclusion that current condition must be: $(1,3,5, \dots, 2k-1)$. The sum of the numbers is therefore $1 + 3 + \dots + 2k-1 = k^2$, which cannot be $3m+2$. Contradiction. Hence it's always possible to choose a coin to move down by 2. This completes our proof of the lemma.

Now, the initial condition is $(2018-(n-1), 2018-(n-2), \dots, 2018)$, so that the sum of the numbers is: $n(4037-n)/2$. For this to be divisible by 3, either $n$ is divisible by 3, or $n \equiv 2 \mod 3$. These are the losing positions. So in order for Alice to have winning strategy, $n \equiv 1 \mod 3$.

Marbles in 3 buckets

Given 3 buckets, each containing $n$ marbles. Alice and Bob are playing a game, where on each turn, the player may remove 1, 2, or 3 marbles from a single bucket. Alice goes first. The player who removes the last marble wins. Determine all $n$ such that Alice has a winning strategy.

Solution

If $n$ is divisible by 4 then Bob has a winning strategy, and if $n$ is not divisible by 4 then Alice has a winning strategy.

First note that $(4m,k,k)$ is a losing position for any $k \geq 0,m > 0$. Because if you remove $p$ marbles from the first bucket, your opponent may remove $4-p$ marbles to go back to $(4(m-1), k k)$. And if you remove from any of the second or third pile, your opponent may mirror that to go back to $(4m, k-p, k-p)$. Thus, no matter what you do, your opponent always has a legal move to make.

Therefore if $n$ is divisible by 4, assuming Bob plays optimally, Alice loses the game.

But if $n$ is not divisible by 4, say $n = 4m+a, a=1,2,3$. Then Alice may remove $a$ from the first bucket, to arrive at $(4m,n,n)$ which is a losing position for Bob.

Generalization

If there are $n$ buckets of $n$ marbles, we can employ the same strategy. The goal is to force your opponent into a "symmetric" situation where no matter what he/she does, you can always mirror it.

If $n$ is divisible by 4, then $(n,n,\dots,n)$ is a losing position because no matter what you do, your opponent can always mirror it. In general, the situation where there are an even number of buckets left and each pair of buckets contains the same number of marbles is a losing position.

If $n=4m+1,4m+3$, then you can employ the same strategy as above. Alice transforms the configuration into $(4m, a,a, b,b, \dots, z,z)$ and from there no matter what Bob does, Alice can always mirror it.

Variation

Now, suppose there's only $n$ marbles total and it is to be distributed among all 3 buckets, with each bucket containing at least one marble. Alice determines the distribution, and Bob makes the first "regular" turn. Determine all numbers $n$ such that there exists a way for Alice to distribute in such a way that Bob always loses.

Solution

At this point, we have to characterize the conditions in which configuration $(a,b,c)$ is a losing position. It's clear to see that $(a,0,0)$ is a losing position if and only if $a \equiv 0 \mod 4$.

Now consider the configuration $(a,b,0)$. If $a \equiv b \mod 4$ then this is a losing position, because the opponent can always mirror you move to keep the condition true. Therefore, if $a \neq b \mod 4$, it is a winning position because we can turn it into the above-mentioned losing position for our opponent.

Now consider the configuration where there are three non-zero buckets left. As we saw above, $(4a,b,b)$ is a losing position because your opponent can always mirror your steps, and restoring to original configuration, and consequently, $(a,b,b)$ is a winning position if $a \neq 0 \mod 4$ because you can turn it into the form $(4a,b,b)$.

We can take this reasoning one step further by claiming, the configuration $(a,b,c)$ where $b \equiv c \mod 4$ is a losing position if and only if $a \equiv 0 mod 4$. Indeed, if $a$ is divisible by 4, then any move you make in the first bucket will be countered in the first bucket, and any move you make in the second or third buckets will also be countered to keep $b \equiv c \mod 4$. Thus either you will bring $a$ below 4 and your opponent can empty the first bucket, leaving you to $(0,b,c)$ which is a losing position, or you will empty one of the second or third buckets first. In the latter case, then your opponent can still mirror it to arrive at $(a,0,c)$ where both $a,c$ are divisible by 4, which is a losing position. Conversely, if $a$ is not divisible by 4, you can make it divisible by 4 to be a losing position for your opponent.

Finally we prove that $(a,b,c) \equiv (1,2,3) \mod 4$ is a losing position, because any move that is made from here will result in a winning position. If we take from first bucket, we now get $(2/3/0, 2,3) \mod 4$ all of which are winning positions. If you take from second bucket, we get $(1, 3/0/1, 3)$ also winning positions, similarly if we do from third bucket. The point is that there is no way to avoid $(a,a,b)$ form where $b $ is not divisible by 4, or $(0,a,b)$ form.

Thus, if $n > 4$ is even, Alice has a winning strategy as follows. If $n = 4m$ then Alice distributes the marbles as $(4(m-1),2,2)$. If $n=4m+2$ she distributes it as $(4m,1,1)$. Both are losing positions Bob. But if $n=4$, then Bob has a winning strategy. Alice has no choice but to distribute the marbles as $(1,1,2)$ initially, and Bob can turn it into $(1,1,0)$ which is a losing position for Alice.

If $n$ is odd, Bob has a winning strategy no matter how Alice distributes the marbles. If all the three buckets contain odd number of marbles, then two of them will be congruent modulo 4, and the third one will not be divisible by 4, and that is a winning position for Bob. If two buckets contain even numbers and the third one odd, we have two choices. Either the two even buckets are both $\equiv 2 mod 4$, which means it's still a winning position for Bob, or at least one of them is divisible by 4, which is also a winning position for Bob.

Bottom line, Alice has a way to distribute the marbles into a losing position for Bob if and only if $n$ is even and $n > 4$.

Marking number game

Let $n > 2$ be an even number. On the board, there are numbers $1, 2, \dots, n$, and initially the number 1 is marked, and no other numbers are marked. Alice and Bob are playing a game, with Alice moving first. On each turn, they may choose a number $k$ that is currently unmarked, and mark it, provided: $k+1$ was previously marked, OR $k$ is even and $k/2$ was previously marked. The player who gets to mark the number $n$ wins the game.

Determine all $n$ such that Alice has a winning strategy.

Solution

As soon as one player marks $n/2$, then he/she loses, because the opponent can mark $n$ directly after that. Also, the number $n$ can be marked ONLY after $n/2$ is marked (by virtue of $n/2$ being marked, since there is no number $n+1$ on the board). Therefore, the crux of the game is to avoid the number $n/2$ at all costs.

Suppose $n = 2m$. Define the numbers in set $\{ 2,3,\dots, n-1 \}$ to be "accessible" if it can be marked without ever marking $m$. Obviously $m$ is not accessible. Let $A$ be the set of accessible numbers. For example, for $n=12$ the accessible numbers are: $A = \{ 2, 3, 4, 7, 8 \}$. Note that 6 is not accessible by definition. 5 is not accessible because in order to mark 5, we'd have to go through 6. 11 is not accessible because it can't be reached without marking 12, which has to go through 6. 10 is also not accessible because it can only be reached through 11 or 5, both of which are not accessible. Therefore 9 is also not accessible.

Now, as long as there's an unmarked number in $A$, then the current player can always choose a legal move to play. Not all unmarked numbers in $A$ will be eligible to be marked, but by the construction of $A$, we can reach that number through other numbers that have been marked (and therefore also in $A$), so as long as there exists an unmarked number in $A$, there is a legal move to be played.

As soon as all numbers in $A$ are marked, then the next person has to mark $m$, and the other player can win immediately. In the case of $n=12$ above, 10 will not ever be marked because as soon as 6 is marked, the next person marks 12. Therefore the winner of the game (assuming both sides play optimally) depends on the parity of $|A|$. Alice has a winning strategy if and only if $|A|$ is odd.

Generally all the numbers from $\{2, 3, \dots, 2m-2 \}$ are accessible, with a handful of exception. $m$ is by definition inaccessible, and $2m-1$ is also inaccessible. So we want to list all the numbers that are not accessible. We divide into two cases.

If $m$ is odd:

Consider the sequence: $1,2,4,3,6,5,8,7, \dots, 2k, 2k-1, 2k+2, 2k+1, \dots, 2m-2, 2m-3$. That is a legal sequence to mark numbers. Therefore, almost all numbers in the set $\{2, 3, \dots, 2m-2 \}$ are accessible except $m$, because we can simply go through the sequence, and only skipping $m$. No further interruption to the sequence will occur because the highest number in the sequence is $2m-2 < 2m$ so it's not affected by the fact that $m$ was never marked. Thus, $A = \{2, \dots, 2m-2 \} - \{ m \}$, and $|A| = 2m-4$. This means Alice does not have a winning strategy because Bob has a winning strategy.

If $m$ is even:

Same as before, we go through the sequence, but skipping $m$. This has several ramifications. First, because $m$ is even, then $m-1$ is not accessible. Thus, there are two numbers that are also "deleted" from that sequence later on: $2m-2, 2m-3$. The rest of the sequence is not affected, because $m+2, m+4,m+6,\dots, 2m-4$ can still be marked. Thus: $|A| = 2m-3 - 4 = 2m-7$. This means Alice has a winning strategy.

This reasoning breaks down when $m=2$ because then $2m-2 = 2$ so there was no other choice and Bob wins. But this is the only corner case. Therefore, Alice has a winning strategy if and only if $n > 4$ and $n$ is divisible by 4.

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.

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

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}$$