Pages

Bookmark and Share
Showing posts with label Algebra. Show all posts
Showing posts with label Algebra. Show all posts

Wednesday, March 2, 2022

Hyper-triangular numbers

Triangular number $T_n$ is defined as $T_n = 1 + 2 + \dots + n$.

Tetrahedral number $R_n$ is defined as $R_n = T_1 + T_2 + \dots + T_n$.

Let $T^k_n$ denote the $k$-th dimensional triangular numbers, with $T^1_n = 1+1+\dots+1 = n$, $T^2_n = T_n$, and $T^3_n = R_n$. Specifically, the higher dimensional triangular numbers are defined as: $$ T^{k+1}_n = T^k_1 + T^k_2 + \dots + T^k_n$$ Prove that: $$T^k_n.T^m_1 + T^k_{n-1}.T^m_2 + \dots + T^k_1.T^m_n = T^{k+m+1}_{n+1}$$

Tuesday, March 1, 2022

Number of contiguous blocks containing black balls over all permutations

$k$ black balls and $n-k$ white balls are arranged on a straight line, where $n \geq 1$, $0 \leq k \leq n$. The score of the said arrangement is the number of contiguous subsequences that contain at least one black ball. For example, the arrangement $W W B W B$ has two subsequences of length 1, and three subsequences of length 2 that contain at least one black ball. Of course there are subsequences of length 3 or higher as well, so the total score for this arrangement is 11.

What is the sum of the score of all $\binom{n}{k}$ arrangements? You may express this quantity in a recursive formula computable in $O(n^2)$ time, $O(n \log n)$ time, or $O(n)$ time.

Solution 1

We give a recursion formula computable in $O(n^2)$ time with DP.

More to come...

Solution 2A

We prove that the number is $\binom{n+2}{k+2} . \binom{k+1}{2}$ which is computable in $O(n)$ time simply by calculating the factorial table

First let $T_n$ be the $n$-th triangular number, $T_n = n(n+1)/2 = \binom{n+1}{2}$. And we also will use the following well-known identity a lot: $$\sum_{i=1}^{n} \binom{i+p-1}{p} = \binom{n+p}{p+1}, p \geq 0$$ It can be proven many ways, either with induction on $n$ keeping $p$ fixed, induction on $p$ keeping $n$ fixed, or telescoping sum, or using combinatorial arguments (choosing $p+1$ items, and condition on the first item chosen). For $p = 0$ it is a trivial sum, and for $p = 1$ it is the definition of triangular numbers.

Note that if all balls were black, then every single contiguous blocks would contribute to the score. There are $1 + 2 + \dots + n = T_n$ such blocks and that is the score. But if there are white balls, then we want to calculate how many scores are lost due to these pockets of white balls, over the course of all different arrangements.

Now given a particular arrangement of $k$ black balls and $n-k$ white balls, we come with an associated sequence of $k+1$ integers denoting the number of white balls in between black balls, including before the first black ball and after the last black ball. For example, the sequence WWBWWWBBBW corresponds to the sequence $(2, 3, 0, 0, 1)$. Each element in this sequence must be non-negative and they must add up to $n-k$, and there must be exactly $k+1$ integers.

Lemma

Suppose $A$ is the set of all sequences of non-negative integers with length $m \geq 2$ that sum up to $M$, that is $$ A = \{ (a_1, \dots, a_m) | a_i \geq 0, a_1 + \dots + a_m = M \}$$ then:

1. There are $|A| = \binom{M+m-1}{m-1}$ possible sequences.

2. If $m \geq 2$, the number $t \in [0,M]$ occurs $m \binom{M-t+m-2}{m-2}$ times in $A$, in any position.

We prove by induction. For $m=2$, the possible sequences are $A = \{(M,0), (M-1,1,), \dots, (0,M)\}$ so $|A| = M+1$ and there are two occurrences of each number.

Now suppose it holds for $m$, now for $m+1$, consider the first element $a_1 \in [0,M]$. Once its value is chosen, then we have $m-1$ numbers that need to sum up to $M - a_1$. So there are $\binom{M-a_1+m-2}{m-2}$ ways to do this, by induction hypothesis. The total number of ways is the sum of that expression when $a_1$ ranges from $0$ to $M$. $$\sum_{a_1 = 0}^M \binom{M-a_1+m-2}{m-2} = \sum_{i=m-2}^{M+m-2} \binom{i}{m-2} = \sum_{j=1}^{M+1} \binom{j+(m-2)-1}{m-2} = \binom{M+m-1}{m-1}$$ The first two equalities are change of variables, but the last one utilizes the identity above. We have proved the first assertion. For the second assertion, consider the case where the first element $a_1 = t$. The rest of the $m-1$ elements must sum up to $M-t$, so there are $\binom{M-t+m-2}{m-2}$ ways to complete the sequence. However, the number $t$ may appear in any of the other positions as well, so in total there are $m$ times that amount.

One might ask that sometimes the number $t$ itself my appear as a duplicate in multiple elements. For example for $m=4$ and $M=11$, we have have a sequence $(2,2,5,2)$ which should only be counted once. Indeed, when we consider $a_1=1$, we contributed one count towards the total number of "2" appearing. Likewise, when we consider $a_2=2,a_4=2$ we also added one count each time, but the sequence itself contributes three counts towards the appearance of "2." So the total amount is exact and correct, and there is no need to compensate for double counting. Thus the lemma is proven

Alternatively, one could also prove the first assertion by using a combinatorial argument. Consider $M+m-1$ spaces and we are to choose $m-1$ spaces to serve as separators. The spaces between the separators will be the numbers in the sequence.

Now observe that each arrangement corresponds one-to-one with a sequence like we described above. The process to convert from an arrangement to a sequence is invertible. Therefore, the total number of contiguous blocks in all arrangements is $$ T_n \binom{(n-k)+(k+1)-1}{(k+1)-1} = T_n \binom{n}{k} $$ But a lot of these blocks would contribute zero towards the total score. That is, for each sequence $(a_1, \dots, a_{k+1})$, the total loss of scores is the number of contiguous blocks that are contained fully within those pockets of white balls, that is: $$T_{a_1} + \dots + T_{a_{k+1}}$$ So we have to add these over all the possible sequences whose sum is $n-k$. This is where we utilize the lemma. Each time the number $t$ appears, it contributes $T_t$ towards the total loss of score. But thanks to the lemma, we know that the number $t$ appears exactly $$(k+1) \binom{(n-k)-t+k-1}{k-1} = (k+1) \binom{n-t-1}{k-1}$$ times. So the total loss of scores is the sum of this quantity as $t$ ranges from one to $n-k$. (Technically $t=0$ is a valid scenario but it incurs no loss of score because $T_0 = 0$ so we ignore it). $$\sum_{t=1}^{n-k} (k+1) \binom{n-t-1}{k-1} T_t $$ At this point, this sum can be computed in $O(n \log n)$ times using FFT technique, as it's a sum of terms expressed in $t$ and $n-t$, but we can simply the terms further to arrive at a closed form solution, by repeated use of the identity above. Let $B_i = \binom{i+k-2}{k-1}$ (where $k > 0$ is fixed), and for any $m > 0$: $$ B_1 + \dots + B_m = \sum_{i=1}^{m} \binom{i+k-2}{k-1} = \binom{m+k-1}{k}$$ by direct application. Then: $$ \sum_{i=1}^{m} (m+1-i). \binom{i+k-2}{k-1} = m.B_1 + (m-1).B_2 + \dots + 1.B_{m} = B_1 + (B_1+B_2) + \dots + (B_1 + \dots + B_m) = \sum_{i=1}^{m} \binom{i+k-1}{k} = \binom{m+k}{k+1}$$ One more time: $$ \sum_{i=1}^{m} T_{m+1-i}. \binom{i+k-2}{k-1} = T_m.B_1 + T_{m-1}.B_2 + \dots + 3.B_{m-1} + 1.B_{m} $$ $$ = [1+2+ \dots + m]B_1 + [1+2+ \dots + (m-1)]B_2 + \dots + [1+2]B_{m-1} + 1.B_m$$ $$ = 1.B_1 + (2.B_1 + 1.B_2) + (3B_1 + 2B_2 + B_3) + \dots + (m.B_1 + \dots + 1.B_m)$$ $$ =\sum_{i=1}^m \binom{i+k}{k+1} = \binom{m+k+1}{k+2}$$ Now, the total loss of scores becomes: $$ \sum_{t=1}^{n-k} (k+1) \binom{n-t-1}{k-1} T_t = (k+1) \sum_{i=1}^{n-k} T_{n-k+1-i} \binom{i+k-2}{k-1}$$ due to change of variable. Now we apply the latest identity above, with $m=n-k$: $$ = (k+1) \sum_{i=1}^{n-k} T_{n-k+1-i} B_i = (k+1) \binom{n+1}{k+2}$$

So the total score is then: $$ T_n \binom{n}{k} - (k+1) \binom{n+1}{k+2} = \frac{n(n+1) n!}{2. k!(n-k)!} - \frac{(k+1)(n+1)!}{(k+2)!(n-k-1)!} = \frac{(n+1)!}{k!(n-k-1)!} \left(\frac{n}{2(n-k)} - \frac{(k+1)}{(k+2)(k+1)} \frac{n-k}{n-k} \right)$$ $$ \frac{(n+1)!}{k!(n-k)!} \left(\frac{n}{2} - \frac{n-k}{k+2} \right) = \frac{(n+1)!}{k!(n-k)!} \frac{kn+2n-2n+2k}{2(k+2)} = \frac{(n+1)!}{k!(n-k)!} \frac{k(n+2)}{2(k+2)}.\frac{k+1}{k+1} = \frac{(n+2)!}{(k+2)!(n-k)!} \frac{k(k+1)}{2} = \binom{n+2}{k+2} . \binom{k+1}{2}$$

Solution 2B

We also prove that the number is $\binom{n+2}{k+2} . \binom{k+1}{2}$ but using a different (simpler) combinatorial argument.

Given $n+2$ tokens in row, mark $k+2$ of these as blue and $n-k$ as red. There are $\binom{n+2}{k+2}$ ways to choose. And now, among the blue tokens, further mark 2 tokens as "start" and "end", with the condition that "start" must come before "end", and there must be at least one blue token between them. There are $\binom{k+2}{2} - (k+1) = \binom{k+1}{2}$ ways to choose. So the end result is an arrangement of red and blue tokens, and two tokens marked start and end containing at least a blue token in between. We will show that this arrangement corresponds to exactly one score-producing contiguous block in a particular arrangement of black and white balls, and that the mapping is invertible and thus we obtain a bijection.

Arrange the balls according to the $n$ unmarked tokens, where all $n-k$ red tokens correspond to white balls, and $k$ unmarked blue tokens correspond to black balls. The contiguous block is represented by the tokens between start and end, including all red and blue tokens. Because the start and end must flank at least one blue token, then this contiguous block contributes one point towards the score.

On the reverse, given an arrangement of balls, create the corresponding arrangement of red and blue tokens. And then insert the start token to the space right before the first ball in the contiguous block, and the end token to the space right after the last ball. Thus we have a bijection, and the number of total score is $\binom{n+2}{k+2} . \binom{k+1}{2}$.

Solution 3

We present a different combinatorial argument, this time in the permutation space, not a combination space.

First we label all the balls from $1,\dots,n$ such that all the black balls are labeled $1,\dots,k$ and the white balls are labeled $k+1, \dots, n$. Consider any given permutation of the balls, and define the score of this permutation the same way as the problem statement: the number of contiguous blocks that contain at least one black balls. Then we also consider the total number of scores of all $n!$ permutations.

Note that each arrangement of unlabeled balls corresponds to $k! (n-k)!$ permutations of labeled balls, all having the same score. So the total number of scores of all $n!$ permutations is $k! (n-k)!$ times the total score of all arrangements. We will show that the total number of scores of all permutations is $\frac{(n+2)!}{2} \frac{k}{k+2}$.

First we arrange the items $1,\dots,n, X, Y$ in a row, with the condition that $X$ happens before $Y$. There are $\frac{(n+2)!}{2}$ ways to do so. This permutation corresponds to permutation of balls, and the contiguous block is represented by the items between $X$ and $Y$. There may be some permutations where $X$ and $Y$ are next to each other, which means the contiguous block is empty, but that's okay for now. Because we have conditioned that $X$ happens before $Y$, the mapping is injective, meaning no two item permutation map to the same (ball permutation, contiguous block) tuple.

However, not all of those permutations will produce a score. In order for it to produce a score, there must be at least one of $1,\dots,k$ between $X$ and $Y$. So now we consider the permutations of these $k+2$ items. Each of the $n+2$-item permutations has a unique corresponding $k+2$-item permutation, but every $(n-k)!$ of the large permutations produces the same smaller permutation.

There are $\frac{(k+2)!}{2}$ smaller permutations because they still all have $X$ before $Y$. We want to exclude the ones where $X$ and $Y$ are together in this permutation (even if in the original permutations there may be numbers larger than $k$ between them). There are $(k+1)!$ such permutations. So the remaining permutations are: $$\frac{(k+2)!}{2} - (k+1)! = \frac{(k+2 - 2}{2} (k+1)! = \frac{k}{2} (k+1)! = \frac{k}{k+2} \frac{(k+2)!}{2} $$ In other words, the good permutations are only $k/(k+2)$ of the total number of permutations, when we consider all small permutations. But since all large permutations map to the small permutations evenly ($(n-k)!$ to one), then the number of good large permutations is $\frac{(n+2)!}{2} \frac{k}{k+2}$. Then, we map it back to the space of ball arrangement, where each permutation corresponds to $k!(n-k)$ arrangements, so the total number of score of arrangements is: $$\frac{(n+2)!}{2} \frac{k}{k+2} . \frac{1}{k!(n-k)!} .\frac{k+1}{k+1} = \frac{(n+2)!}{(n-k)!(k+2)!} \frac{(k+1)k}{2} = \binom{n+2}{k+2} \binom{k+1}{2}$$

Thursday, February 24, 2022

Neighboring non coprime

Let $n > 1$. A sequence $A_n$ of integers greater than 1 having length $n$ is called nice if any two elements are not coprime. That is, $$\gcd(A_i, A_{i+1}) > 1 \forall i, 1 \leq i \leq n-1$$

Find the smallest real number $t$ such that, given any sequence of integers $A_n$ of integers greater than 1 having length $n$, there exists a sequence of positive integers $B_n$ of length $n$ such that:

1. $\max{B_i} \leq n \max {A_i}$

2. $B_n$ differs from $A_n$ in at most $\lceil tn \rceil$ elements.

Solution

Note that for $t=1$ we can just change every single element to a small number like 2. We can try to do better. Satisfying condition 2 is easy, because for $t = 1/2$ we can just change every other element to the the LCM of it's neighboring elements, but this would make it failr condition 1. For example, suppose the sequence consists of very large primes, then this strategy would cause every other element to be the product of the two large primes, failing condition 1.

We propose that $t = 2/3$ satisfies the condition. That is, if $$A_n = a_1, a_2, a_3,a_4,a_5,a_6,\dots,a_n$$ $$B_n = 2a_2, a_2, 2a_2, 2a_5, a_5, 2a_5, \dots$$

We can see that every two neighboring elements are not coprime, and that the maximum of $B_i$ is at most twice that of $A_i$. We show that there is no smaller $t$ that can satisfy, using a series of counter examples.

For $n=3$, consider the sequence $p_1,p_2,p_3$ of very large primes. There is no way to only change one element to be nice, while keeping the maximum element manageable. The only way to change one element to be nice is to change $p_2 \to p_1p_3$, which then would fail condition 1. So we must change at least 2 elements, which means $\lceil 3t \rceil \geq 2$, so $t > \frac{1}{3}$

For $n=5$ consider the sequence $p_1,p_2,p_3,p_4,p_5$. If we were to change only 2 elements, either we change $p_2,p_4$, or we leave two neighboring primes intact. But if we change $p_2,p_4$, this could mean we have to change $p_2$ to LCM of $p_1,p_3$ and so on, violating condition 1. So we must change at least 3 elements, which means $\lceil 5t \rceil \geq 3$ so $t \frac{2}{5}$

Thursday, February 10, 2022

Expected number of throws

$n$ fair coins are thrown all at once. Those that show Head are removed from the game, and the rest are thrown again. This process is repeated until there are no more coins left. What is the expected number of throws? Find a closed form formula, meaning that it may still be expressed as a sum but may not be expressed as a recurrence relation.

Solution Let $f(n)$ be the desired result. There is a $\binom{n}{k} / 2^n$ chance that $k$ of them will show heads, and the process is repeated with $n-k$ coins now. The rest of the game is expected to take $f(n-k)$ throws. If $k=0$ then we still have the same situation as before. If $k=n$, we have 0 throws left. In all of these situations, we do have to spend 1 turn doing the throw. So the recurrence relation is:

$$f(n) = 1 + \sum_{k=1}^{n-1} \frac{\binom{n}{k}}{2^n} f(k) + \frac{1}{2^n}f(n)$$ $$f(n) = \frac{2^n + \sum_{k=1}^{n-1} \binom{n}{k} f(k)}{2^n-1} $$

Given a large $n$, computing this would take $O(n^2)$ time as we have to calculate and store the previous $f(k)$ values, and each take $O(k)$ time. We can manipulate this expression further to come with a summation formula for $f(n)$ that would allow it to be computed in linear time.

First we claim and prove the following lemma. For $1 \leq m < n$

$$ \sum_{k=m}^{n} \binom{n}{k}\binom{k}{m} = \binom{n}{m}2^{n-m}$$

Proof: given $n$ white balls, we wish to pick $m$ of them and paint them black, and the rest may stay white or be painted gray. The RHS side is obvious, there are $\binom{n}{m}$ ways to choose black balls, and the rest may be painted white or gray.

To show the LHS, first we pick a number $k \in [m,n]$. We choose $k$ balls and paint them gray. Out of these $k$, we further choose $m$ to be painted black.

Alternatively we can prove the lemma by dividing both sides by $\binom{n}{m}$: $$ \sum_{k=m}^{n} \frac{n!}{k!(n-k)!} \frac{k!}{m!(k-m)!} \frac{m!(n-m)!}{n!} = 2^{n-m}$$ $$ \sum_{k=m}^{n} \frac{(n-m)!}{(n-k)!(k-m)!} = 2^{n-m}$$ $$ \sum_{i=0}^{n-m} \frac{(n-m)!}{(n-m-i)!i!} = 2^{n-m}$$

which is a well-known identity

Given the lemma, now we claim the following statement: let $a_n = \frac{2^n}{2^n-1}$ then: $$f(n) = \binom{n}{1}a_1 - \binom{n}{2}a_2 + \binom{n}{3}a_3 + \dots + (-1)^{n+1} \binom{n}{n}a_n$$ We will show that this formula matches our recurrence relation above by strong induction. Suppose they hold for $1,2,\dots,n-1$, then we first evaluate the following expression: $$\sum_{k=1}^{n-1} \binom{n}{k}f(k) = \binom{n}{1}f(1) + \binom{n}{2}f(2) + \dots + \binom{n}{n-1}f(n) $$ $$= \sum_{k=1}^{n-1} \binom{n}{k} \sum_{m=1}^{k} (-1)^{m+1} \binom{k}{m}a_m $$ we rearrange and collect each $a_m$ terms: $$= \sum_{m=1}^{n-1} (-1)^{m+1}a_m \sum_{k=m}^{n-1} \binom{n}{k} \binom{k}{m} $$ Apply the lemma: $$= \sum_{m=1}^{n-1} (-1)^{m+1}a_m \left(\binom{n}{m}2^{n-m} - \binom{n}{m} \right) = \sum_{m=1}^{n-1} (-1)^{m+1} \binom{n}{m} a_m \left(2^{n-m} - 1 \right) $$ We can plug this expression to our recurrence formula and compare against our claim (induction hypothesis). After multiplying both sides by $2^n-1$, we are left to show that: $$(2^n-1) a_n + \sum_{m=1}^{n-1} (-1)^{m+1} \binom{n}{m} a_m \left(2^{n-m} - 1 \right) = (2^n-1) \left( \sum_{m=1}^{n-1} (-1)^{m+1} \binom{n}{m}a_m + (-1)^{n+1}a_n \right)$$ Collect $a_n$ terms to the LHS, and the rest of the terms to RHS: $$(2^n-1)(1 + (-1)^n)a_n = \sum_{m=1}^{n-1}a_m(-1)^{m+1} c_m $$ where $$c_m = (2^n-1)\binom{n}{m} - \binom{n}{m}(2^{n-m}-1) = \binom{n}{m}(2^n - 2^{n-m}) = \binom{n}{m}2^{n-m}(2^m-1) = \binom{n}{m}2^{n-m} \frac{2^m}{a_m}$$ so what we need to show becomes: $$(2^n-1)(1 + (-1)^n)a_n = \sum_{m=1}^{n-1}a_m(-1)^{m+1} \binom{n}{m}2^{n-m} \frac{2^m}{a_m} $$ $$2^n(1 + (-1)^n) = \sum_{m=1}^{n-1}(-1)^{m+1} \binom{n}{m}2^{n} $$ $$1 + (-1)^n = \sum_{m=1}^{n-1}(-1)^{m+1} \binom{n}{m} $$ $$1 + \sum_{m=1}^{n-1}(-1)^{m} \binom{n}{m} + (-1)^n = 0$$ $$(1 -1)^n = 0$$

Friday, August 13, 2021

Evolving Polynomial

On the Cartesian field, each lattice point $(x,y)$ is initially assigned the number $x^2+y^2-1$.

At each step, if $A(x,y)$ represents the number on $(x,y)$, that number is increased by: $$\frac{(x-y) \left( A(x+1,y) + A(x,y-1) - A(x-1,y) - A(x,y+1) \right)}{4}$$

All the additions are done simultaneously.

1. Prove that the numbers at each point are always integers

2. Prove that, aside from the initial configuration, there is never a number that is divisible by 3

Solution

The recursion formula guarantees that $A(x,y)$ is always a polynomial in $x,y$, with real coefficients. In the initial configuration, $B(x,y) = A(x,y) + 1 = x^2+y^2$ is homogeneous in $x,y$ with degree 2. That is, $B(kx,ky) = k^2 A(x,y)$. We will show that this homogeneity is maintained by the recursion formula, and therefore will hold true at all times.

Suppose $A(x,y) = P.x^2 + Q.xy + R.y^2 - 1$ for some real numbers $P,Q,R$ then the recursion formula maintains it. This is because $A(x+1,y) - A(x-1,y)$ cancels out the $x^2,xy,y^2,1$ terms, so only $x,y$ terms are left. Similarly $A(x,y+1) - A(x,y-1)$ will also only preserve $x,y$ terms. So the second factor is homogenous with degree 1, but the factor $(x-y)$ is also homogenous with degree 1, so the added number is homogeneous with degree 2. Therefore, the final number is still of the form $A(x,y) = P'.x^2 + Q'.xy + R'.y^2 - 1$ (for some $P',Q',R'$ constants that may be different from the previous iteration).

Now we also notice that $A(x,y) = A(y,x)$ for all time. This property is preserved in the beginning, but also preserved by the recursion, so the numbers are symmetric with respect to $x,y$. Therefore $P = R$.

Next, we notice that for $x=y$, the additions are always zeros, so $A(x,x) = 2x^2-1$ for all time. Therefore $A(x,x) = (2P+Q)x^2-1 = 2x^2-1$ so $2P+Q = 2$.

This means that, because $Q = 2- 2P$, $A(x,y) = Px^2 + (2-2P)xy + Py^2 - 1= (x^2+y^2 - 1) + (P-1)(x-y)^2$ for some $P$ real (not necessarily integer) that depends on $t$. So we've shown that $A(x,y)$ has the form $(x^2+y^2-1) + K_t(x-y)^2$ for some $K_t$, where $K_0 = 0$.

Then, plugging in to the original recursion formula, we can see: $$(K_{t+1} - K_t)(x-y)^2 = \frac{x-y}{4} ( 4x - 4y +K_t(2(x-y+1)^2 -2(x-y-1)^2))$$ $$(K_{t+1} - K_t)(x-y)^2 = \frac{x-y}{4} ( 4x - 4y +8K_t(x-y))$$ $$K_{t+1} = 3K_t + 1$$ From there, it's a simple matter to see that $K_t = \frac{3^t-1}{2}$ because $K_0 = 0$, but we didn't need to solve the recursion. The fact that $K_0 = 0$ is enough to prove that $K_t$ is always an integer, and that, except for $t=0$, it's always $\equiv 1 \mod 3$.

Because $K_t$ is always an integer then $A(x,y)$ is also integral everywhere. And because $K_t \equiv 1 \mod 3$ then we can check that for any combinations of $x,y \mod 3$, $A(x,y)$ will never be $\equiv 0 \mod 3$.

Thursday, July 22, 2021

Positive-definite Polynomial Game

Given $n$ a positive even number. Alice and Bob are playing a game as follows. On the board initially there are $n+1$ unassigned numbers: $a_0, a_1, \dots, a_n$.

With Alice going first, each player alternatingly chooses an unassigned number and assigns a positive real value to it. Once all numbers have been assigned values, polynomial $P(x)$ is defined as:

$$P(x) = a_nx^n + \dots + a_1x +a_0$$

If $P(x) > 0$ for all $x \in R$ then Alice wins, otherwise Bob wins. Determine who has a winning strategy.

Variant 1: if the number $a_0$ is already fixed to 1, so there are only $n$ numbers on the board, who has a winning strategy?

Variant 2: if the winning condition is flipped: Alice wins if there exists an $x$ such that $P(x) < 0$.

Solution

The player who moves last has a winning strategy, regardless of winning condition. Variant 1 merely flips who moves last. If Variant 1 is in play and Alice moves first, then Bob moves last and Bob has a winning strategy. Note that $P(x)$ is positive definite iff $tP(x)$ for all $t$ positive numbers, so the magnitude of each number doesn't matter, only the relative magnitude of all coefficients. Therefore, the number "1" set by variant 1 is arbitrary and the variant merely ensures Bob's ability to win. For the rest of this solution, we assume that variant 1 is not in play and Alice goes first, and she should assign $a_0 = 1$. The rest of the proof can then be extensible to variant 1 while flipping the name Alice and Bob.

Lemma: polynomial $P(x)$ with positive coefficients are positive definite if and only if $P(1/x) > 0$ for all $x \neq 0$. This lemma is easy to see because $P(0) > 0$ anyways.

Part 1: proving that Alice can ensure positive definiteness.

Assume that $a_0 = 1$ has already been assigned. Now divide the remaining coefficients into pairs: $(a_1,a_2), (a_3,a_4), \dots, (a_{n-1},a_n)$. Whenever Bob makes a move and assigns a value to a coefficient, Alice assigns a value to its pair accordingly. We claim that Alice will be able to choose her value such that the resulting polynomial $Q_k(x) = a_{2k}.x^{2k} + a_{2k-1}.x^{2k-1} + 2/n$ is positive definite.

Proof: From the lemma, $Q_k$ is positive definite iff $R_k(x) = \frac{2}{n}x^{2k} + a_{2k-1}x + a_{2k}$ is positive definite.

If Bob chooses $a_{2k-1}$ then Alice can choose $a_{2k}$ large enough to make $R_k(x)$ positive definite. Whichever local minimum may exist due to Bob's choice, Alice can compensate it enough by adding a positive constant term to the whole polynomial.

If Bob chooses $a_{2k}$ then there exists an $a_{2k-1}$ small enough to make $R_k(x)$ positive definite. If $x \geq 0$ positive then $R_k(x) > 0$ because all coefficients are positive. But if $x < 0$ then by AM-GM:

$$ \frac{2}{n}x^{2k} + a_{2k} = \frac{2}{n}x^{2k} + \frac{a_{2k}}{2k-1} + \dots + \frac{a_{2k}}{2k-1} \geq 2k \sqrt[2k]{\frac{2}{n}.\left(\frac{a_{2k}}{2k-1}\right)^{2k-1}}.(-x) > -a_{2k-1}x$$

for small enough positive value of $a_{2k-1}$.

The final polynomial can be expressed as the sum:$P = Q_1 + \dots + Q_{n/2}$, and because at each step Alice can always ensure that the resulting $Q_k(x)$ is positive definite no matter what Bob chooses, then the final polynomial is also guaranteed to be positive definite.

Part 2: proving that Alice can ensure non-positive definiteness.

If $n=2$ then Alice can always ensure that the discriminant of the quadratic polynomial is positive, therefore the polynomial has two real roots. For $n > 2$, the general strategy is as follows: divide the coefficients into pairs as above, and Alice's assignment is always the pair of Bob's assignment as well. But this time the difference is that, after each of her move, Alice ensures that the TOTAL polynomial $P(x)$ is negative for some values of $x$ and maintains this invariant throughout the game.

First note that if Bob ever chooses an even coefficient $a_2,a_4,\dots$ then Alice's job is really easy. Take the current value of $P(-1)$ (after including Bob's addition), and by choosing her corresponding odd coefficient large enough, she can make $P(-1)$ negative because she's adding a multiple of $x^{2k-1}$ which is negative at $x=-1$.

Consider the first round. If Bob chooses $a_{2k}$ then Alice chooses large enough $a_{2k-1}$ as described above. But if Bob chooses $a_{2k-1}$, Alice can choose small enough $a_{2k}$ to ensure non-positive definiteness. The current resulting polynomial is $a_{2k-1}x^{2k-1}+1 < 0$ as $x \to -\infty$, so pick any $y$ such that $a_{2k-1}y^{2k-1}+1 < 0$. Then Alice chooses $a_{2k}$ small enough such that $0 < a_{2k} < \frac{-a_{2k-1}y^{2k-1}-1}{y^{2k}}$ so that $a_{2k}y^{2k}+a_{2k-1}y^{2k-1}+1 < 0$

So once the invariant is established after the first round, then Bob has no choice but to keep choosing even coefficients. If Bob chooses an odd coefficient, then whichever value of $x$ caused $P(x)$ to be negative at the end of last round will continue to be (even more) negative, so Alice simply chooses a very small value of the corresponding even coefficient as described above. But even if Bob chooses an even coefficient, Alice can counter by choosing a large enough odd coefficient. Therefore she maintains the invariant of $P$ being non-positive definite until the end of the game.

Thursday, March 28, 2019

Finite difference

Define sequences $x_i,y_i,i=1,2,\dots$ as follows: $$x_{n+1} = x_n^2 - 20$$ $$y_{n+1} = y_n^2 - 30$$ And define $d_i = x_i - y_i$. Find all possible starting pairs $(x_1,y_1)$ such that the set $\{d_1, d_2, \dots \}$ contains only a finite number of elements. Solution Just the outlines. If $x_1 = \pm 4 , \pm 5$ then $x_n$ is bounded, likewise if $y_1 = \pm 5, \pm 6$ it is bounded. It's easy to show that for other possibilities $x_n,y_n$ are both unbounded, and will be positive except for the first few terms.

If $x_n,y_n$ are bounded then they assume a finite number of values, therefore $d_i$ also assume a finite number of values, at most the combinatorial pairs of their images, but most likely much less. However, if one of them is unbounded, then say $x_n$ is unbounded, EVEN IF $y_n$ is bounded, then $x_n+y_n$ is unbounded. At this point it's easy to show that $x_n+y_n$ is monotonically increasing and unbounded (excxept for the first few terms) because once $x_n$ gets large enough, $y_n$'s fluctuation is not enough to make the sum decrease.

Now, if $x_n-y_n$ is unbounded, then $x_n^2 - y_n^2$ is unbounded. If $x_n - y_n$ is bounded then $x_n^2 - y_n^2$ is unbounded, EXCEPT if $x_n = y_n$ identically. But because they have different recursion formula, they can't always be identical. Meaning they're identical at most every other term. On the terms that they are not identical, $x_n-y_n$ is non-zero, and because $x_n+y_n$ is monotonically increasing and unbounded, then $x_n^2 - y_n^2$ is also unbounded. Therefore $d_n +10$ is also unbounded, so it assumes an infinite nunmber of values

Monday, February 11, 2019

Game making expression positive definite

On the board there are six numbers $A,B,C,D,E,F$, all initially zero. Mary and Nancy are playing a game as follows. On Mary's turn, she increases one of $A,B,C$ by 1, and on Nancy's turn, she increases one of $D,E,F$ by 1. They take turns alternatingly until each has gone 2019 times. Each pair of turns is called a "set" (for example if Mary moves first, then 1 set consists of Mary's move followed by Nancy's move).

Winning condition: Mary wins if at any point at the end of a set the following inequality is true for all $x,y$ real numbers: $$Ax^2 + By^2 + C \geq Dxy + Ex + Fy$$ Determine who has the winning strategy if:

1. Mary goes first

2. Nancy goes first

Solution

If Mary goes first Nancy has a winning strategy.

Replace $x$ with $x/z$ and $y$ with $y/z$ to make the inequality homogeneous: $$Ax^2 + By^2 + Cz^2 \geq Dxy + Exz + Fyz$$ Note that the following form is always true if $u,v,w \geq 0$ $$u(x-y)^2 + v(x-z)^2 + w(y-z)^2 \geq 0$$ So if at any point after a set the inequality can be reduced to that form, then Mary wins. We claim the following two things:

1. That Nancy can always avoid that form, and

2. That if the form is not achieved then there exists a $x,y,z$ to make the inequality false

First to prove 1, note the following rearrangement: $$u(x-y)^2 + v(x-z)^2 + w(y-z)^2 \geq 0$$ $$(u+v) x^2 + (u+w)y^2 + (v+w)z^2 \geq 2u xy + 2v xz + 2w yz$$ Therefore if $D = (A+B-C), E = (A+C-B), F = (B+C-A)$ then that form is achieved. This is the unique solution to achieve that form, and that solution may be negative. If the solution to that form contains negative number then no matter what Nancy does, that form is not achieved. But even if it is a triple of non-negative integers, Nancy has 3 choices of moves to make, so she still has at least 2 moves that won't result in that form.

Now to prove 2, we show that we can find $x,y,z$ that violates the inequality.

First, if $A,B,C$ do not form a triangle, then $A>B+C$ (or its permutation). Note that if we assume (WLOG) that $A>B+C$ then $A+B>C,A+C>B$. Furthermore WLOG we may assume that $B \geq C$. $$Ax^2 + By^2 + Cz^2 \geq Dxy + Exz + Fyz$$ $$\iff (A+B-C)(x-y)^2 + (A+C-B)(y-z)^2 + (B+C-A)(x-z)^2 \geq -(2A+2B-2C-2D)xy - (2A+2C-2B-2E)yz - (2B+2C-2A-2F)xz$$ In that case we can choose the following variables. Let $S,R$ be large numbers. Let $x= 1/R, y = R + 1/R, z = SR + 1/R$. Then $$ (A+B-C)R^2 + (A+C-B)(S-1)^2R^2 \geq (A-B-C)S^2R^2 + ...$$ The "..." part in RHS consists of terms $SR^2$ or lower. As we let $S,R$ become large, the dominant terms are $(S-1)^2R^2$ versus $S^2R^2$. For large enough $S$, $(A+B-C)+(A+B-C)(S-1)^2 < (A-B-C)S^2$. At that point we just fix $S$ but let $R$ become larger. Since the coefficient of $R^2$ in the RHS is larger, then the RHS grows faster, invalidating the inequality.

Now if $A,B,C$ form a triangle, $$\iff (A+B-C)(x-y)^2 + (A+C-B)(y-z)^2 + (B+C-A)(x-z)^2 \geq (2A+2B-2C+2D)xy + (2A+2C-2B+2E)yz + (2B+2C-2A+2F)xz$$ Note that the sum of coefficients in RHS is zero, so the terms are not all positive. We shall divide into two cases: one positive two negatives or vice versa

Case 1: if the RHS is of the form $Uxy + Vxz - (U+V) yz$ with $U,V \geq 0$. Then $$RHS = Uy(x-z) + Vz(x-y)$$ Then we set $x = R+1/R, y = R, z= R$. The terms in LHS will be zero or $(1/R^2)$ whereas the terms in RHS will be $(U + V)$. By setting $R$ large enough we can make LHS < RHS.

Case 2: if the RHS is of the form $(U+V)xy - Uyz - Vxz$ with $U,V \geq 0$ Then $$RHS = Uy(x-z) + Vx(y-z)$$ Then we set $x = R+1/R, y = R+1/R, z= R$. The terms in LHS will be zero or $(1/R^2)$ whereas the terms in RHS will be $(U + V)(1+1/R)$. Again, by setting $R$ large enough we can make LHS < RHS.

Challenge Can you generalize this to third power and four variables? In other words, can the game be extended into the following inequality? $$Ax^3 + By^3 + Cz^3 + Dw^3 \geq Exyz + Fxyw + Gxzw + H yzw$$ Answer: yes. We make use of the following property: $f(a,b,c) = a^3 + b^3 + c^3 - 3abc = (a+b+c)((a-b)^2 + (b-c)^2 + (c-a)^2)/2 \geq 0$ If the inequality can be expressed as a positive sum of $f(x,y,z), f(x,y,w), f(x,z,w), f(y,zw)$ then the inequality holds. If not, then there are two cases:

1. One or more of the $f$ form occurs on the RHS, in which case we choose $x,y,z,w$ to maximize the growth of the ones in the RHS. For example, $x=y=1/R, z = R+1/R, w = SR + 1/R$ for large $S,R$.

2. The $f$ forms all occur on the LHS, so there are terms of $xyz$ etc on the RHS whose coefficients all sum to zero. We can pick $x,y,z,w$ whose differences are small but themselves are large, such as $x=R, Y = R+1/R, z = R+2/R, w = R+3/R$. That way, the values of $f$ will be small but values of $xyz$ will be big. By judiciously permuting those values depending on which coefficients are negative, we can make LHS to be < RHS.

Saturday, December 8, 2018

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

Monday, October 1, 2018

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.

Saturday, July 14, 2018

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

Tuesday, May 15, 2018

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

Friday, May 11, 2018

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.

Wednesday, May 9, 2018

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

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

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