Monotonically increasing sequences with sums

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

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

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

$a_0 = b_0$

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

What are the possible values of $S$?

Solution

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

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

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

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

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

At this point, we have established the following fact:

• The first $k$ numbers in $a_i$ and $b_i$ are chosen, and the next $k$ numbers are not chosen.
• The last $k$ numbers in $a_i$ and $b_i$ are not chosen, and the previous $k$ numbers are chosen.

We would like then to claim that this pattern would have to continue itself all the way to the "middle" of the sequences, which finally means that $2k$ divides 2014. Formally, we claim that for each $m \geq 0$, we have the following:

• $2km, \dots, (2m+1)k-1$ are chosen in $a_i$ and $b_i$.
• $(2m+1)k, \dots, (2m+2)k-1$ are not chosen in $a_i$ and $b_i$.
• $2013-((2m+1)k-1), \dots, 2013-2km$ are not chosen in $a_i$ and $b_i$.
• $2013-((2m+2)k-1), \dots, 2013-(2m+1)k$ are chosen in $a_i$ and $b_i$.

The case of $m=0$ has been proven above. Now suppose it holds for $m$.

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

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

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

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

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

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

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

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

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

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

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

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

Marble distribution

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

Integer solutions

Let $f(t) = t(t-1)$. Find all positive integers $x,y$ such that $$f(x) + f(y) = f(x+y) / 2$$ First Solution Expanding and canceling, we have: $$x^2+y^2-2xy = x+y$$ It's easy to see that there's no solution for $x=y$. The above equation is now equivalent to: $$16x^2+16y^2+1-8x-8y+32xy = 64xy+8x+8y+1$$ $$(4x+4y-1)^2 = (8x+1)(8y+1)$$ Because both quantities are positive, we have: $$4x+4y-1 = \sqrt{8x+1} \sqrt{8y+1}$$ Once again rearranging, $$(8x+1) - 2\sqrt{8x+1} \sqrt{8y+1} + (8y+1) = 4$$ $$(\sqrt{8x+1} - \sqrt{8y+1})^2 = 4$$ If $x=y$, then there is no solution WLOG, we may assume that $x > y$, so that $$\frac{\sqrt{8x+1}}{2} - \frac{\sqrt{8y+1}}{2} = 1$$ Note that $g(t) = \frac{1+\sqrt{8t+1}}{2}$ is the reverse triangular number function. Thus, any two consecutive triangular numbers (for example 3 and 6, 6 and 10, and so on) are a solution.

Now we show that there's no other solution. The equation is equivalent to $g(x) - g(y) = 1$. In order for $g(x)$, to be an integer, we must have $8x + 1 = k^2$ for some $k$. But $k$ is odd, so $8x+1 = 4m^2 + 4m + 1$ which means $x = m(m+1)/2$ is a triangular number

Now suppose $g(x)$ is not an integer, then it will be irrational, and so will $g(y)$. They both have form of $a+\sqrt{b}$ with $a,b$ rational, but with different $b$s, because $x \neq y$. The difference can't be rational, a contradiction.

Thus, the only solutions are two consecutive triangular numbers. Second Solution Let $d = \gcd(x,y)$, and $x = dm, y = dn$ with $m,n$ coprime. Upon substitution and rearranging, we have: $$d(m-n)^2 = m+n$$ Clearly $m=n$ is not a solution. Now wlog let $m < n$ and $n = m + k$ $$dk^2 = 2m+k$$ Because $k$ divides $dk^2$ and $2m$ then $k$ divides $2m$. Because $m$ and $n$ are coprime, then $k$ and $m$ are coprime. Thus we have $k=1$ or $k=2$.

For $k=1$, $d = 2m+1, n=m+1$, so $x = (2m+1)m,y=(2m+1)(m+1)$.

For $k=2$, $d = (m+1)/2, n=m+2$, and obviously we can only use odd values of $m$. Suppose $m = 2l+1$, then $d = l+1, n=2l+3$, so $x=(l+1)(2l+1), y =(l+1)(2l+3)$. Interestingly, this form is the same as the case for $k=1$, except we substitute $m = l + 1/2$

Combining the two cases, we can conclude that the solution must have form of $m(2m+1),(m+1)(2m+1)$ for $m$ multiples of 1/2, or equivalently, $k(k+1)/2, (k+1)(k+2)/2$ for $k$ any integers. In other words, they must be two consecutive triangular numbers.

Charged pendulum

From brilliant.org: Two point charges, each of charge q and mass m, are hung from 1 m long cords and constrained to move in the xy-plane. The charge and mass are chosen such that the when the charges are in their equilibrium position the angle $/theta$ the cords make with the vertical is 0.1 radians. The masses are placed in their equilibrium positions and then each is pulled out by some small angle 0.01 radians and released. What is the period of the resulting oscillation in seconds?

Sum of products of 3

Let $p>3$ be a prime number, and let $S={2,3,\dots,p-1}$ Let $X = \sum_{ i < j < k \in S} ijk$, prove that $X + 1$ is divisible by $p$.

Solution

Because $p$ is odd, let $p = 2m+1$. First we calculate $1^2 + \dots + (p-1)^2 \mod p$. We do this by realizing that $1^2 = (p-1)^2 \mod p, 2^2 = (p-2)^2 \mod p$ and so on. Every term will have a "pair", so the sum is: $$1^2 + \dots + m^2 + (m+1)^2 + \dots + (p-1)^2$$ $$ \equiv 2 (1 + \dots + m^2) \mod p$$ $$ \equiv m(m+1)(2m+1) \equiv 0 \mod p$$ because $2m+1 = p$. This means that $2^2 + \dots + (p-1)^2 \equiv -1 \mod p$

Next we calculate $1^3 + \dots + (p-1)^3 \mod p$. We do this by realizing that $p = 1 + (p-1) | 1^3 + (p-1)^3, p=2+(p-2) | 2^3+(p-2)^3$ and so on. Like above, each term will have a pair that it cancels out with. Thus $1^3 + \dots + (p-1)^3 \equiv 0 \mod p$, so $2^3 + \dots + (p-1)^3 \equiv -1 \mod p$.

Now we also have that $1+\dots + (p-1) \equiv 0 \mod p$, so $2 + \dots + (p-1) \equiv -1 \mod p$. From this, we have: $$ 2\sum_{i < j \in S} ij \equiv (-1)^2-(-1) \equiv 2 \mod p $$ $$\sum_{i < j \in S} ij \equiv 1 \mod p$$ because $p$ is odd.

Now, for any real numbers $a_1, \dots, a_n$, let us define the following variables: $$A = a_1 + \dots + a_n$$ $$B = \sum_{i < j} a_i a_j$$ $$C = \sum_{i \neq j } a_i^2 a_j$$ $$D = \sum_{i < j < k} a_i a_j a_k$$ $$E = a_1^2 + \dots + a_n^2$$ $$F = a_1^3 + \dots + a_n^3$$ Then we have: $$AB = (a_1+\dots+a_n)(a_1a_2 + a_1a_3 + \dots + a_{n-1}a_n) = C + 3D$$ The identity from middle to right is because for each $a_i$ in $A$, it's either paired with $a_ia_j$ or $a_j a_k$ in B. If it's paired with $a_i a_j$ then it would contribute towards $C$, otherwise it would contribute towards $3D$. Likewise, each term in $C$ and $3D$ can be traced back to $AB$. Each term $a_i^2 a_j$ in $C$ comes from $a_i$ in $A$ and $a_i a_j$ in $B$. Each term $3a_i a_j a_k$ in $3D$ comes from three sources: $a_i$ in $A$ and $a_j a_k$ in $B$ and its permutations. To further convince ourselves, $A$ has $n$ terms, and $B$ has $n(n-1)/2$ terms, so $AB$ has $n^2(n-1)/2$ terms. $3D$ has $n(n-1)(n-2)/2$ terms and $C$ has $n(n-1)$ terms, so altogether they have $n^2(n-1)/2$ terms.

Furthermore: $$C = a_1^2(A-a_1) + a_2^2(A-a_2) + \dots + a_n^2(A-a_n) = AE - F$$ So: $$3D = AB-C = F + AB-AE$$ This identity holds for any real numbers $a_i$, and it's based on pure algebraic manipulation. We can apply this identity to our set $S$. We already know that $F \equiv -1, A \equiv -1, B \equiv 1, E \equiv -1 \mod p$. From there, we have $3D \equiv -3 \mod p$, which means $(3D+3)$ is divisible by $p$. Because $p > 3$ then $D+1$ is divisible by $p$.

An equilateral with side $n$ is divided into smaller equilaterals with size 1 so that they form a triangular lattice. Each segment of length 1 is colored either red, blue, or green. A coloring is called "good" if every equilateral has sides of three different colors. How many good colorings are there? Two colorings are called distinct if at least one segment is colored differently. For example, with $n=1$, there are 6 good colorings. With $n=2$, there are 48 colorings.

Sum of randomly selected numbers

In a class with 10 students, each student is allowed to choose a number from the following list: 100,101,102,300,301,302. The teacher then collects all chosen numbers and calculates the sum. How many ways are there for the sum to be 2012? Two "ways" are considered distinct if there is at least one student who chooses different numbers.

Variant: In a class with $2n+1$ students, each student is allowed to choose a number from the following list: $n, n+1, -n, -n-1$. The teacher then collects all chosen numbers and calculates the sum. How many ways are there for the sum to be zero?

Solution Suppose the number of students who chose 100,101,102,300,301,302 are $a,b,c,d,e,f$ respectively, so we have: $$a+b+c+d+e+f = 10$$ and $$100.a + 101.b + 102.c + 300.d + 301.e+ 302.f = 2012$$

Note that we can write 100=201-100-1, 101 as 201-100, 102 as 201-100+1, 300 as 201+100-1, 301 as 201+100, 302 as 201+100+1, so the second equation becomes: $$201(a+b+c+d+e+f) + 100(d+e+f-a-b-c) + (c+f-a-d) = 2012$$ Since $a+b+c+d+e+f = 10$ then: $$100(d+e+f-a-b-c) + (c+f-a-d) = 2$$

Now, since $|c+f-a-d| \leq 10$ then it must be the case that: $$d+e+f-a-b-c = 0$$ and $$c+f-a-d = 2$$

We also note that when the students choose one of the numbers, they're essentially making two choices: first, they choose if they want to choose small or big numbers (be included in $a+b+c$ or $d+e+f$), and second, they choose if they want their number to end with 0,1, or 2 (be included in $a+d, b+e$ or $c+f$).

Thus, the number of ways to satisfy the first constraint $a+b+c = d+e+f = 5$ is 10C5, which means 5 students choose the small numbers and the rest choose the big numbers.

In order to satisfy $c+f - a - d = 2$, we make the following substitutions: $x = a+d, y = b+e, z = c+f$. Then $x+y+z = 20, z-x = 2$. We divide the cases by the values of $z$. Note that once a student chooses to be included in $x$ or $y$ or $z$, he only needs to choose if he wants to choose a big or small number, since each of $x,y,z$ contains exactly one big and one small number.

If $z > 6$ then $x > 4$, impossible.

If $z = 6$, then $x = 4, y = 0$. There are 10C6 = 210 ways to choose this.
If $z = 5$, then $x = 3, y = 2$, there are 10! / 2! 5! 3! = 2520 ways.
If $z = 4$, then $x = 2, y = 4$, there are 10! / 4! 4! 2! = 3150 ways.
If $z = 3$, then $x = 1, y = 6$, there are 10! / 3! 6! 1! = 840 ways.
If $z = 2$, then $x = 0, y = 8$, there are 10C8 = 45 ways.

If $z < 2$ then $x < 0$, impossible.

So the total number of ways is $$_{10}C_{5} (210+2520+3150+840+45) = _{10}C_{5} 6765 = 1 704 780$$

Solution to variant

Suppose the number of students who chose $-n-1, n+1, -n, n$ are $a,b,c,d$ respectively, so we have: $$a+b+c+d = 2n+1$$ $$(n+1)(b-a) + n(d-c) = 0$$

Note that because $n$ and $n+1$ are relatively prime, so we must have $n+1 | d-c$. But $|d-c|$ can take any values from $0$ to $2n+1$, so $d-c = 0, n+1, -(n+1)$.

If $d-c=0$, then $b-a=0$, which means $a+b+c+d$ would be even, impossible.

If $d-c=n+1$, then $b-a = -n$. Combined with $a+b+c+d = 2n+1$ we have $(a,b,c,d) = (n,0,0,n+1)$. (Remember that $a,b,c,d$ have to be non-negative).

This means that $n$ of the students choose $-n-1$ and the other $n+1$ choose $n$. There are $_{2n+1}C_{n}$ ways to do that.

The case of $d-c = -n-1$ is similar, where $(a,b,c,d) = (0,n,n+1,0)$, and there are $_{2n+1}C_{n}$ ways. Note that all these ways are disjoint, so the total number of ways is $ 2_{2n+1}C_{n}$