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

Triangular equations

A triangular series of equations is a system of $k$ equations where the $k$-th row consists of $k+1$ terms on the LHS and $k$ terms on the RHS. For example: $$a + b = c$$ $$d + e + f = g + h$$ $$i + j + k + l + m = n + o + p$$ $$...$$ Given the numbers $1, 2, \dots, n^2$ and one number with the same parity as $n$ is removed, prove that the rest of the numbers can be arranged into a triangular series of equations.

For example, out of $1,2,\dots,9$, 3 is removed, so the rest can be written as: $$ 1+4 = 5$$ $$2 + 6 + 8 = 7 + 9$$ Another example, out of $1,2,\dots, 16$, 10 is removed, so the rest can be written as: $$1+3 = 4$$ $$2 + 5 + 8 = 6 + 9$$ $$7 + 11 + 12 + 14 = 13 + 15 + 16 $$

Solution (In Progress)

Suppose we color all the numbers with the same parity as $n$ with red, and color all the numbers with the opposite parity with black. Also, call the number that was removed, the missing number, $x$. A number is called "good" if, when missing, the rest of the numbers can be written as triangular system.

Note the triangular system below: $$1+2 = 3$$ $$4+5+6 = 7+8$$ $$9+10+11+12 = 13+14+15$$ $$...$$ $$k^2 + \dots + (k^2+k) = (k^2+k+1) + \dots + (k^2+2k)$$ $$...$$ $$(n-1)^2 + \dots + ((n-1)^2+n-1) = ((n-1)^2+(n-1)+1) + \dots + (n^2-1)$$ We call this system A. This system is missing $n^2$, and the system is triangular and correct. (The correctness of said system can be verified by simple arithmetic series on the $k$-th row).

So we know that $n^2$ is good. Furthermore, note that each row has the same number of odd numbers (that is, $k$-th row has $k$ odd numbers if $k$ is odd and $k-1$ odd numbers if $k$ is even). So if we increase each odd number by two, we'll still get a correct triangular system: $$3+2 = 5$$ $$4+7+6 = 9+8$$ $$11+10+13+12 = 15+14+17$$ $$...$$ So if $n$ is odd, 1 is good. Call this system B.

Similarly, the $k$-th row has $k$ even numbers in the LHS and $k-1$ even numbers in the RHS. We can increase the even numbers by two, but then the equation will be incorrect. Call the "weight" of an equation to be its RHS - LHS. Obviously, an equation is correct only if it has weight zero. If we increase all the even numbers by two, then the weight of the new equation is -2, for example: $$6+5+8 > 7+10,w=-2$$ But note that now $(k^2+k+2)$ is in the LHS while $k^2+k+1$ is still in the RHS. In other words, the largest number in the LHS is exactly one more than the smallest number in the RHS, so if we switch those two, we restore the weight back to zero: $$6+5+7 = 8+10$$ So we can form a new system this way: $$1+3=4$$ $$6+5+7 = 8+10$$ $$9+12+11+13 = 14+16+15$$ $$...$$ Next, note that out of the $n$ rows in the equation, we can take the first $k$ rows from system A, and the $n-k$ last rows from system B or C. For example: $$1+2 = 3$$ $$4+5+6 = 7+8$$ $$11+10+13+12 = 15+14+17$$ $$...$$ Now we are ready to prove the main assertion by induction. We will show the base cases later. For now, suppose it holds for $n=2,3$. Then, if $x \leq (n-2)^2$, there is a way to arrange $\{1, 2, \dots, (n-2)^2\} \ \{x\}$ in triangular form by induction hypothesis, and the last two rows can be taken from the last two rows of system B (if $n$ is even) or system C (if $n$ is odd). So then we consider cases where the missing number is $x > (n-2)^2$. In system A above, it would be in the last two rows. We will divide into cases depending on the position of $x$ in system A. Note that the missing number is always red.

Suppose $x$ is red on the last row RHS (meaning the missing number is in the interval $x \ in [(n-1)^2+(n-1)+1, n^2-2]$). Take out that number and replace it with $n^2$. Then now the last row has weight a positive even number in the interval $[2, n-1]$. We can switch a number $k$ from LHS and $l$ from the RHS, and the weight would decrease by $2(l-k)$. But the difference of the numbers in RHS and LHS ranges from 1 to $2n-2 > n-2$, and each side has consecutive numbers. So we know there are numbers that we can pick to switch so that the weight is reduced back to zero.

Suppose the missing number is red on the last row LHS, meaning the missing number is in the interval $x \in [(n-1)^2+1, (n-1)^2+(n-1)]$. Take out that number and replace it with $n^2$. Then the last row has weight a negative even number in the interval $[-2n+2, -n]$. Now, there exists a number in RHS $y$ such that $y-n^2$ is exactly half the weight of the last row, because the numbers in RHS is in the range $[(n-1)^2+(n-1)+1,n^2-1]$ so those numbers subtracted by $n^2$ is in the range $[-n+1, -1]$ which encompasses $\frac{1}{2} [-2n+2, -n]$. If we switch this number $y$ and $n^2$, the weight of the last row is restored.

Suppose the missing number is red on the second-to-last (STL) row LHS, meaning the missing number is in the interval $x \in [(n-2)^2, (n-2)^2+(n-2)]$. Take out that number and replace it with $(n-1)^2+1$, and then in the last row, put $n^2$ to where $(n-1)^2+1$ used to be. The STL row now has weight negative even number in the interval $[-2n+2,-n]$, whereas last row has some other even number weight. The last row could be fixed with the procedure described above (as if $(n-1)^2+1$ was the missing number). However the STL row can be fixed by switching $(n-1)^2+1$ with an appropriate number in the STL RHS, because the numbers in STL RHS ranges from $[n^2-3n+3,n^2-2n]$ so the difference ranges from $[-n+1, -2]$ which encompasses $\frac{1}{2}[-2n+2,-n]$

Suppose the missing number is red on the STL row RHS. Same as before, take out that number, replace it with $(n-1)^2+1$, and then in the last row, put $n^2$ to where it used to be. Same as above, the last row can be fixed using the previous strategy, whereas the STL row can be fixed by switching two numbers in the STL (similar to if the missing number is from RHS last row).

Now all that remains is to prove the base cases. For $n=2$, we have either $1+3=4$ or $1+2=3$. For $n=3$, the missing numbers could be $x=1,3,5,7,9$, but $x=9$ is already covered by system A above, $x=1$ covered by system B, and $x=3$ is shown in the example. For $x=5$: $$1+2=3$$ $$4+7+6 = 9+8$$ For $x=7$: $$1+3=4$$ $$2+5+8 = 6+9$$ (Really we're just applying the algorithm described above but we're including here for the sake of proof completeness).

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.

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.

Spanning set

Let $S = \{0,1,2,\dots,10\}$.

A set of numbers $A \subset S$ is called "spanning" if the set $\{ x, x+1, x+2, x+3 \mod 11 | x \in A \} = S$.

And a set of numbers $B \subset S$ is called "potentially spanning" if there is an integer $k$ such that the set $\{kb \mod 11 | b \in B \}$ is spanning.

Prove that every subset of $S$ with four elements are potentially spanning, and prove that there exists a subset of $S$ with three elements that is not potentially spanning.

Solution First, we show that there is a subset of three elements that is not potentially spanning.

Note that for a set to be spanning, it has to be $\{c,c+4, c+8\}$ for some $c$ (here we assume everything is modulo 11, so we don't write it for notational simplicity). This is because the maximum distance between two adjacent element is 4, so the distances between 3 elements must be 4+4+3 (or its rotation).

Now we claim that a set $\{x,y,z\}$ is potentially spanning if and only if there exists $r \neq 0$ and $s$ such that $\{x,y,z\} = \{r+s, 2r+s, 3r+s \mod 11\}$. First, clearly if a set is spanning, then all of its "rotations" are also spanning sets. Likewise, if a set is potentially spanning, then all of its rotations are also potentially spanning. So wlog we may assume that $s=0$. Then the set $\{r,2r,3r\}$ is potentially spanning because we can always take $k = 4r^{-1} \mod 11$ so that $\{kr,2kr,3kr\} = \{4,8,12=1\}$ a spanning set. The inverse modulo is guaranteed to exist because 11 is prime and $r \neq 0$.

Now the other direction. Suppose $\{x,y,z\}$ is potentially spanning, such that $\{kx,ky,kz\}$ is spanning. As we've established above, it must have form $\{c,c+4, c+8\}$ for some $c$. Thus we can take $r = 4k^{-1} \mod 11$ and $s = (c-4)k^{-1} \mod 11$ so that $\{k(r+s),2kr,3kr\} = \{4+ks,8+ks,12+ks\} = \{c,c+4,c+8\}$.

So we have shown that the potentially spanning sets are generated by (and only by) the number of $(r,s)$ pairs we can choose. There are 10 choices for $r$ and 11 for $s$, so there are at most 110 potentially spanning sets. We say at most because some choices of $r$ and $s$ may "collide" (result in the same spanning triplet). However, there are ${11 \choose 3} = 165$ possible triplets, so there are some triplets that are not generated by the $(r,s)$ construction above and thus not potentially spanning.

Now we show that a subset $B = \{b_1,b_2,b_3,b_4\}$ is always potentially spanning. Note that if any three of $b_i$s form a potentially spanning triplet then $B$ is potentially spanning. In particular, if $B$ contains an arithmetic sequence modulo 11 then $B$ is potentially spanning. So we assume that $B$ is free from arithmetic progression.

Now let $d_i = b_{i+1} - b_i$ (of course we mean $b_5 = b_1$. Then among all four $d_i$s, let $d$ be the maximal distance. If the maximal distance is 4, then we are done because $B$ itself is spanning. So we assume that the maximal distance is at least 5. Wlog, we may assume that this maximal distance is $d_4$ and that $b_1 = 0$. So this means $0=b_1 < b_2 < b_3 < b_4 = 11-d$ and $b_i$ must not contain arithmetic sequence. It's easy to see that the only possible combinations are:

Case 1: $d=5$, so $0=b_1 < b_2 < b_3 < b_4 = 6$. The only combinations are $\{0,1,4,6\}, \{0,1,5,6\},\{0,2,5,6\}$. All the other combinations contain an arithmetic sequence. But in the first two cases, we can take $k=8$ to get: $\{0,4,8,10\}, \{0,4,7,8\}$ which contains arithmetic sequence thus potentially spanning, and for the third case we can take $k=3$ to get $\{0,4,6,7\}$ which is spanning.

Case 2: $d=6$, so $0=b_1 < b_2 < b_3 < b_4 = 5$. The only combinations are $\{0,1,4,5\}$ and $\{0,2,3,5\}$. We can take $k=4$ to get $\{0,4,5,9\}$ and $k=2$ to get $\{0,4,6,10\}, both spanning sets.

Case 3: $d=7$, so $0=b_1 < b_2 < b_3 < b_4 = 5$. The only combination is $\{0,1,3,4\}$. We can take $k=5$ to get $\{0,4,5,9\}$, a spanning set.

And there is no way to have $d > 7$ and still fitting $b_2$ and $b_3$ without getting an arithmetic progression. So our proof is complete.

Product of all numbers

A prime $p$ is called "good" if there is an $m$ such that $p$ divides $m^2 - 2$. For example, 7 and 17 are good primes. Suppose $p$ is a good prime. Consider all numbers in the form of $a\sqrt{2} + b$ where $a,b \in \{0, \dots, p-1\}$ and $(a,b) \neq (0,0)$. The product of all those numbers can be written as $s\sqrt{2} + t$ where $s$ and $t$ are integers. Find their remainders modulo $p$. What if $p$ is not a good prime?

Solution

If $p$ is a good prime then $s \equiv t \equiv 0 \mod p$. If $p$ is not a good prime, then $s \equiv 0, t \equiv -1 \mod p$

Proof:

Define the "~" (equivalency) as follows: two numbers $s \sqrt{2} + t$ and $u\sqrt{2} + v$ are equivalent if $s \equiv u$ and $t \equiv v \mod p$. Then we readily see that the following properties are easy to show:

$X \sim X$ (reflexivity).

$X \sim Y \iff Y \sim X$ (symmetry).

If $X \sim Y$ and $Y \sim Z$ then $X \sim Z$ (transitivity).

Given these three then equivalency divides all numbers in te form $s\sqrt{2}+t$ into equivalency classes. Furthermore we see that:

If $X \sim Y$ and $W \sim Z$ then $X+W \sim Y+Z$ and $XW \sim YZ$. It follows directly from the properties of modular arithmetics.

Now, if $p$ is a good prime, then note that $(\sqrt{2} + m)(\sqrt{2} + p-m) = (2-m^2 + pm) + p\sqrt{2} \sim 0$. Thus the product of all numbers in question is equivalent to zero.

If $p$ is not a good prime, it's a lot more complicated.

First we claim the following: given $X \nsim 0$, then there exists $Y$ such that $XY \sim 1$. We call this $Y$ the inverse of $X$.

Proof: Given a number $a\sqrt{2} + b$, first we define the number $r$ as follows: $r \in (0, \dots, p-1)$ such that $r(b^2-2a^2) \equiv 1 \mod p$.

This $r$ must exist, because $b^2 - 2a^2 \not\equiv 0 \mod p$, for otherwise we have $(ba^{-1})^2 \equiv 2 \mod p$, a contradiction.

Then consider the number $ar\sqrt{2}-br$. The product of this and $a\sqrt{2} + b$ is: $$(ar\sqrt{2}-br)(a\sqrt{2} + b) = (2a^2-b^2)r \sim 1$$

Then we prove the second claim: If $XY \sim 0$ then either $X \sim 0$ or $Y \sim 0$.

Proof:

Let $X = a\sqrt{2}+b, Y = c\sqrt{2}+d$ then $XY = (bc+ad)\sqrt{2}+(2ac+bd) \sim 0$ so we have: $$bc+ad \equiv 0 \mod p$$ $$2ac+bd \equiv 0 \mod p$$ Assuming that both $X,Y$ are not equivalent to zero, either $c \neq 0$ or $d \neq 0$ because otherwise $Y \sim 0$. If $d \neq 0$ then: $$abc \equiv -a^2d \mod p$$ $$2abc \equiv - b^2d \mod p$$ $$\Rightarrow b^2d \equiv 2a^2d \mod p$$ $$(ba^{-1})^2 \equiv 2 \mod p$$ A contradiction. If $c \neq 0$ then we similarly show: $$abd \equiv - b^2c \mod p$$ $$abd \equiv -2a^2c \mod p$$ $$(ba^{-1})^2 \equiv 2 \mod p$$ Also a contradiction. (The assumption that $X \nsim 0$ is needed to take inverse of $a$)

So based on the second claim, we now assert that each number in the problem statement has an inverse, and the inverse is unique. For if $XY \sim XZ \sim 1$ then $X(Y-Z) \sim 0$ so $Y \sim Z$. This means that a lot of pairs among those numbers would multiply 1. The only numbers left are those who are inverses with itself. To find such numbers, note the following:

$$X^2 = 2ab\sqrt{2} + (2a^2+b^2) \sim 1$$ $$\iff ab \equiv 0, 2a^2+b^2 \equiv 1 \mod p$$ If $a \equiv 0$ then $b^2 \equiv 1$, so $p$ divides $b^2-1 = (b+1)(b-1)$. The only possible $b$ are $1, p-1$, and these numbers are in the problem statement.

If $b \equiv 0$ then $2a^2 \equiv 1$ which means $2 \equiv (a^{-1})^2 \mod p$, a contradiction.

So the only numbers who don't "cancel out" with other numbers are 1 and -1, and they're included in the final product. Thus the product of all those numbers is $\sim -1$.

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.

Teacher distributing coupons

Let $n$ be a positive integer, and $N = n(n+1)(2n+1)$. In a class with $N$ students, each student has an ID number from $1$ to $N$. The teacher then gives each student red, green, and blue coupons as follows:

A student with id $k$ will receive $x$ red coupons, $y$ green groupons, $z$ blue coupons where
$1 \leq x \leq n, n | k-x$
$1 \leq y \leq n+1, (n+1) | k-y$
$1 \leq z \leq 2n+1, (2n+1) | k-z$.

For each student then the teacher gives him a penny based on the median number of coupons he receives. For example, if a student receives 2 red, 4 green, and 5 blue coupons, he gets 4 cents. If another student receives 2 red, 5 green, and 4 blue, he also gets 4 cents. If yet another student get 3 red, 5 green, 5 blue, he gets 5 cents.

Find the total number of money that the teacher has to pay to the entire class.

Solution

Note that $n, n+1, 2n+1$ are all pairwise prime, and $N$ is their LCM. By Chinese Remainder Theorem, we find that for each triplet $(x,y,z)$ such that $1 \leq x \leq n, 1 \leq y \leq n+1, 1 \leq z \leq 2n+1$, there is exactly one $k$ such that $1 \leq k \leq N, k \equiv x \mod N, k \equiv y \mod N, k \equiv z \mod N$. In other words, for each triplet of $(x,y,z)$ within the allowable coupon range, there is exactly one student who receives $x$ red, $y$ green, and $z$ blue coupons.

Solution 1

We divide the cases based on the amount of money a particular student receives. Suppose a student receives $k$ cents.

Case 1: $1 \leq k \leq n$.

Let $x,y,z$ be the number of red, green, and blue coupons he receives.

Case 1a: $x,y,z$ are all distinct.

If $x < y < z$, then $k = y$. For a student to be paid $k$ cents in this manner, $x$ must be from 1 to $k-1$, and $z$ must be from $k$ to $2n+1$, inclusive. Conversely, as long as $x$ is any value from $1$ to $k-1$, and $z$ is any value from $k+1$ to $2n+1$, then $(x,y,z)$ form a triple where the median is $k$. For each of these triples, there is exactly one student who gets paid $k$ cents. So the number of students who gets paid $k$ cents in this manner is $(k-1)(2n+1-k)$, so the total money spent on them is $k(k-1)(2n+1-k)$

Since $k$ is allowed to take range from $1$ to $n$, then the number of students who gets paid via $x < y < z$ configuration is
$$\sum_{k=1}^{n} k(k-1)(2n+1-k)$$

Now, that's just for $x < y < z$. There are 6 permutations of order, and we can repeat the same analysis for each. The total number or $x,y,z$ all distinct is:

$$2 \sum_{k=1}^{n} k(k-1)(n-k) + 2 \sum_{k=1}^{n} k(k-1)(n+1-k) + 2 \sum_{k=1}^{n} k(k-1)(2n+1-k)$$
$$ = 2 \sum_{k=1}^{n} k(k-1)(4n+2-3k) $$

Case 1b: two of them are the same, the third higher.

Suppose $x=y < z$, then $k = x = y$. Similar analysis as above, the number of students who gets paid this way is $(2n+1-k)$, and the total money spent on them is $k(2n+1-k)$. Summing from $k=1$ to $n$, and also taking into account cases of $x=z < y, y=z < x$, we have:

$$\sum_{k=1}^{n} k (4n+2-3k)$$

Case 1c: two of them are the same, the third lower.

Suppose $x < y= z$, then $k = y = z$. Again, the number of students is $k-1$, so total amount of money, including cases of $y < x= z, z < x=y$ is:
$$ 3 \sum_{k=1}^{n} k(k-1)$$

Case 1d: $x=y=z$

$$\sum_{k=1}^{n} k$$

Case 2: $k = n+1$.

Since $x \leq n$, then $x$ cannot be the median nor the top, and $y$ cannot be on top, so the only configuration left is $x < y \leq z$. There are $n$ values for $x$ and $n+1$ values for $z$ (from $n+1$ to $2n+1$). So the number of students is $n(n+1)$ and total amount paid is $n(n+1)^2$

These are all the cases, since the median cannot be greater than $n+1$. Summing over all the sums, we have:

(do the algebra here)

Solution 2:

We divide cases based on the range of $x,y,z$.

Case 1: $1 \leq x,y,z \leq n$

Recall that each triplet $(x,y,z)$ corresponds to exactly one student. We form student pairs as follows: student who receives $(x,y,z)$ is paired with the student who receives $(n+1-x, n+1-y, n+1-z)$. Note that if $n$ is even, then each student gets a pair, but if $n$ is odd, there is a student $((n+1)/2, (n+1)/2, (n+1)/2$ who is paired with himself.

Suppose student $A$ and student $B$ is a pair. Note that if $x < y < z$, then $n+1-x > n+1-y > n+1-z$, so if $A$ gets paid $y$, then $B$ gets paid $n+1-y$. The sum of payment from this pair is $n+1$. It's easy to check that this rule holds for all order configurations ($x = y < z, x < y = z$, etc). In other words, the average income of this pair is $(n+1)/2$. This holds for all pairs, even in the case where a student is paired to himself. The total amount of income for all students in this group is then $n^3 (n+1)/2$.

Case 2: $1 \leq x,y \leq n, z = n+1$.

In this case, since $z$ is the largest of all three, then the median is $\max(x,y)$, summed over all $1 \leq x,y \leq n$.

Case 2a: $x > y$.

Then $\max (x,y) = x$. For each $x$, there are $x-1$ possible values of $y$, meaning there are $x-1$ students, each of which are getting paid $x$ cents. So the total income here is:

$$\sum_{k=1}^{n} k(k-1)$$

Case 2b: $x < y$

By symmetry, it's identical to 2a.

Case 2c: $x = y$.

The total income here is $\sum_{k=1}^{n} k$

Case 3: $1 \leq x,z \leq n, y = n+1$.

By symmetry, it's identical to case 2

Case 4: $1 \leq x \leq n, y = z = n+1$.

The median here is $n+1$, and there are $n$ students, so total income here is $n(n+1)$.

Case 5: $1 \leq x \leq n, y = n+1, z > n+1$

The median here is $n+1$, and there are $n^2$ students, so total income is $n^2(n+1)$.

Case 6: $1 \leq x,y \leq n, z > n+1$

This case is similar to case 2. In fact, EACH value of $z$ is identical to case 2 in that we're summing $\max (x,y)$ over all $1 \leq x,y \leq n$. Case 6 is thus like $n$ instances of case 2.

non-injective power mapping

Suppose $p$ is a prime and $f(a) = a^m$ is defined for $a$ that are relatively prime to $p$, then prove that $f$ is injective if and only if $m$ does not divide $p-1$.

Replacing number on the board

In a blackboard, the number 2012 is initially written. On each turn, the student can choose on of the three numbers: 6, 1006, 1509, and multiply it with the existing number on the board. The existing number is then erased and replaced with the new product.

The teacher has a specific integer $k > 1$ in mind, and the goal for the student is to get the number of the board to have form $n^k$ where $n$ is an integer.

Determine all values of $k$ such that, after a finite number of turns, the number of the board will have the desired form.

Are you smarter than a 6th grader?

This problem was proposed to a math olympiad for 6th graders. The solution doesn't require any algebra nor any more advanced tools, other than simply logic.


Problem


Each apple costs 1 dollar and each orange costs 1.01 dollar. Johnny has 101 dollars. How many ways are there for him to buy fruits, including possibly not buying anything? Sarah has 99 dollars. How many ways are there for her to buy fruits, including possibly not buying anything?

Solution

First we make an observation that 100 and 101 are relatively prime. So suppose Johnny buys X apples and Y oranges and spends exactly Z amount of money. If he wants to spend EXACTLY Z amount of money with a different combination of fruits, he would have to decrease X by 101 and increase Y by 100, or increase X by 101 and decrease Y by 100.

For Johnny,

Consider case 1: If Johnny spends exactly 101 dollars. Clearly he can buy 101 apples or 100 oranges, but these are the only two cases.

Case 2: If Johnny spends less than 101 dollars. Now, pretend that the store only has 101 apples and 100 oranges (since Johnny can’t buy more apples or more oranges than these).

Consider all the combinations of apples and oranges that Johnny can buy, and consider what’s left at the store. The total amount of goods in the store are 1 dollar x 101 + 1.01 dollar x 100 = 202 dollars. So if Johnny spends less than 101 dollars, the total amount goods left in the store is greater than 101 dollars. We can’t reverse this situation, that is, Johnny can never spend more than 101 dollars so that the total amount left in the store is less than 101 dollars.

This means, in all the possible combinations of x apples (x is from 0 to 101 inclusive) and y oranges (from 0 to 100 inclusive), for each combination that Johnny can buy, there is precisely one combination that Johnny couldn’t buy. The combinations that Johnny couldn’t buy represent the amount that would be left in the store if Johnny had bought the “complement” combination instead.

The total number of combinations is 102 x 101 = 10302, (because we go from 0 apples to 101 inclusive, 0 oranges to 100 inclusive) but we have to subtract two combinations from case 1, so we have 10 300, split evenly between what Johnny could buy and couldn’t buy. So Johnny could buy 5150 combinations.

Together from Case 1 and Case 2, Johnny could buy fruits in 5152 ways.

For Sarah,

Case 1: She spends exactly 99 dollars. She can buy 99 apples. She couldn’t buy any oranges because if she wants to buy any oranges she’d have to increase it in increments of 100 and decrease the apples in increments of 101, again because 101 and 100 are relatively prime.

Now, consider the story of Johnny. Out of 5150 ways he could buy fruits, categorize them according to his spending:
Category 1: He spends 0 to 98.99
Category 2: He spends 99 exactly
Category 3: He spends 99.01 to 100.99
Category 4: He spends 101

Suppose he buys a certain number of apples and oranges. In order to keep the spending amount intact and changes the number of apples or oranges, as we’ve noted above, he would have to change the number of apples and oranges in increments of 101 and 100 respectively. The total amount of goods being changes (from apples to oranges or vice versa) is already 101 dollars. This is why in category 4 he has two ways of buying good. But this means, in category 1, 2, and 3, for each spending amount, there’s at most one (possibly zero) way to buy fruits with that spending amount.

Now, we show that 98.99 dollars spending amount is unattainable. Johnny could achieve that amount by buying 100 apples and –1 oranges, or –1 apples and 99 oranges. Neither one are reasonable.

Next, for each amount in category 1, we pair them up. We pair up X with 98.99 – X. For example, 0 and 98.99 is paired up. 0.01 and 98.98 is paired up, etc.

We claim that within each pair, at most one value is attainable, possibly zero. If both values are attainable, say if Johnny could buy A apples and B oranges with X dollars and C apples and D oranges with 98.99 – X dollars, then he could buy (A+C) apples and (B+D) oranges with 98.99 dollars, a contradiction since we’ve shown that 98.99 is unattainable. So since there are 9900 values, and thus 4950 pairs of values, so there are at most 4950 ways to buy fruits in category 1.

But then there is 1 way in category 2, and total of 5150 ways in category 1,2,3 altogether. So there are at least (5150 – 1 – 4950) = 199 ways to buy in category 3. But notice that there are exactly 199 values (amounts) in category 3, each of which can correspond to at most one way to buy fruits. Thus we must have that each value in category 3 is attainable by exactly one way of buying, and each pair of values in category 1 is attainable by exactly one way of buying.

So in total, when Sarah spends her money, she can spend it from category 1 or 2, and there are 4950 + 1 = 4951 ways of buying.

a,b,c fraction integer

Given positive integers $a,b,c$ such that
$$\frac{a}{b} + \frac{b}{c} + \frac{c}{a}$$
is also an integer, show that
$$\frac{a^2b^2}{c},\frac{b^2c^2}{a}, \frac{c^2a^2}{b}$$
are all cubic numbers.

Sequence modulo 2011

A sequence of integers $a_1, \dots, a_{2010}$ satisfy the following properties:

$a_1 - 1$ is divisible by 2011
$a_k a_{k-1} - k$ is divisible by 2011 for $k = 2, 3, \dots, 2010$

Show that $a_{2010} + 1$ is divisible by 2011.

Solution

First we prove the following assertion:

For $k$ odd, then $a_k.2.4.6. \cdots.(k-1) - 1.3.5.\cdots.k$ is divisible by 2011.
For $k$ even, then $a_k.1.3.5. \cdots .(k-1) - 2.4.6.\cdots.k$ is divisible by 2011.

Proof by induction. It can easily be seen for $k=1$ it's true. For $k=2$, we have $2011 | a_2a_1 - 2 = a_2(a_1-1) + (a_2-2)$ So $2011 | a_2 - 2$

Suppose it's true for $k-1$ odd, then for $k$ even:
$2011 | a_k a_{k-1} - k$ which means
$$2011 | 2.4.\cdots.(k-2) (a_k a_{k-1} - k) = 2.4.\cdots.(k-2)a_k a_{k-1} - 2.4.\cdots.(k-2).k$$
$$2011 | a_k (2.\cdots.(k-2)a_{k-1} - 1.3.\cdots.(k-1)) + (a_k.1.3.\cdots.(k-1) - 2.\cdots.(k-2).k)$$
And since 2011 divides the first term by induction hypothesis, then it also divides the second term, which completes the induction step. The proof for $k-1$ even and $k$ odd is similar.

Now, that means for $k=2010$, let $X = a_{2010}$ we have:
$$2011 | X.1.3. \cdots .2009 - 2.4.\cdots.2010$$

We now prove the following assertion for $i = 1,2,\dots,1005$
$$2011 | X.1.3. \cdots. (2011-2i) + (-1)^i (2i) (2i+2)\cdots.2010$$

For $i = 1$ it is true by definition. Now suppose it's true for $i-1$, then for $i > 1$:
$$2011 | X.1.3. \cdots. (2011 - 2i).(2011-2i+2) +(-1)^{i-1} (2i-2) (2i)\cdots.2010$$
if $2011 | a(2011+b) + c$ then $2011 | ab+c$
$$2011 | X.1.3. \cdots. (2011 - 2i).(-2i+2) + (-1)^{i-1} (2i-2) (2i)\cdots.2010$$
if $2011 | a$ then $2011 | -a$.
$$2011 | X.1.3. \cdots. (2011 - 2i).(2i-2) + (-1)^{i} (2i-2) (2i)\cdots.2010$$
$$2011 | 2(i-1)(X.1.3. \cdots. (2011 - 2i).+ (-1)^{i} (2i)\cdots.2010)$$
if $2011 | 2(i-1)a$ then $2011 | a$ since 2011 is prime and $i > 1$.

So the assertion holds for $i = 1,\dots, 1005$. Particularly, for $i = 1005$ we have:
$$2011 | X - 2010$$
$$2011 | X + 1 - 2011$$
$$2011 | X + 1$$

Supersum

For a natural number $n$, the supersum of $n$ is defined as the sum of possible combinations that we can obtain by deleting digits of $n$, calculated as modulo 9. For example, the supersum of 1234 is:

No deletions: 1234 +
Deleting 1 digit: 123 + 134 + 234 + 124
Deleting 2 digits: 12 + 13 + 14 + 23 + 24 + 34 +
Deleting 3 digits: 1 + 2 + 3 + 4

$ = 8 \mod 9$

If $n$ is a 2011-digit number, and $s$ is its supersum, show that $s-n$ is divisible by 9.

Circular Locker Problem

From a friend's brother:

There are 1000 lockers and 1000 students. The lockers are arranged in a circle, all closed. The 1st student opens all the lockers. The 2nd student closes every other locker. The 3rd student goes to every 3rd locker. If it’s open he closes it, if it’s closed, he opens it. When he gets to locker #999, he continues to locker #2 and continues until he reaches a locker that he has already touched. The 4th student goes to every 4th locker: again, if it’s closed, he opens it, if it’s open, he closes it. Every student after that does the same, until student #1000, who will obviously just open or close locker #1000. After they are all finished, which lockers will be open?

Solution


First, let's think about what happens when student $n$ does his turn.

If $n$ is relatively prime to 1000, that is, $n$ does not contain any factor of 2 or 5, then $n$ will touch all the lockers exactly once. For example, student #3 will go touching lockers 3,6,...,999,2,5,...,998,1,4,7,...,997,1000. In this case student $n$ behaves exactly like student #1.

If $n$ is a multiple of $2$ or $5$, then let $d = \gcd(1000,n)$ Student $n$ touches locker $m$ if and only if $d$ divides $m$. For example, if $n=16$, then $d = 8$. Student #16 will go touching lockers 16,32,...,992,8,24,...,1000, which are exactly all multiples of 8. In this case, student $n$ behaves exactly like student #8.

Now, how many students have numbers that are NOT relatively prime to 1000? Such students must have numbers in the form of $n = 2^a 5^b$ We can enumerate the possibilities:

If $b=0$, then the student numbers are: 2,4,8,16,32,64,128,256,512, for a total of 9 students. Remember that students #16,32,...,512 behave exactly like student #8,and there are 6 of them, so it's equivalent to student #8 going 6 extra times. Their effects cancel out pairwise. So we only need to consider the effects of students #2,4,8.

If $b=1$, then the student numbers are: 5,10,20,40,80,160,320,640, for a total of 8 students. Remember that students #80,...,640 behave exactly like student #40,and there are 4 of them, so their effects cancel out pairwise. So we only need to consider the effects of students #5,10,20,40.

If $b=2$, then the student numbers are: 25,50,100,200,400,800, for a total of 6 students. Remember that students #400,8000 behave exactly like student #200, so their effects cancel out. So we only need to consider the effects of students #25,50,100,200.

If $b=3$, then the student numbers are: 125,250,500,1000.

If $b=4$, then the student number is: 625, which behaves like student #125, and thus cancels the effect of student #125.

So in total, there are 9+8+6+4+1 = 28 numbers that are not relatively prime to 1000, so there are an even numbers of students that are relatively prime. Each of these students touches all lockers exactly once, so their effects again cancel out pairwise. Thus, the student numbers that we need to consider are: (grouped by their largest factor of 2):
5,25
2,10,50,250
4,20,100,500
8,40,200,1000

In order to determine if locker $n$ is closed or open, find all numbers above that divides $n$. If there are even such numbers, then the locker is close, otherwise it's open.

For example, 120 = 3 x 5 x 8, so 120 is divisible by 2,4,8, 5,10,20,40. That means locker #120 is open.

For a more explicit list of open lockers, the following are the open lockers:
1. Lockers with numbers (not divisible by 5 or divisible by 25), and (divisible by 2 but not by 4, or divisible by 8).
2. Lockers with numbers divisible by 5 but not 25, and (divisible by 4 but not by 8).

Floor And Ceiling

Show that there are positive integers $a,b,c,d$ with $b,d < 100$ such that:

$$\lfloor \frac{a}{b} k \rfloor = \lfloor \frac{73}{100} k \rfloor$$

and

$$\lceil \frac{c}{d} k \rceil = \lceil \frac{73}{100} k \rceil$$

For all $k = 1,2,\dots,99$

Note: $\lfloor x \rfloor$ denotes the floor function and $\lceil x \rceil$ denotes the ceiling function

Shuffling Card

A deck of 31 cards is being shuffled, where at each point, the shuffler may perform the following operation:

1. Cut the deck in half and interleave each half to perform a new deck. The cards at position 1,2,3,...,15 now occupy position 2,4,6,...,30, and the cards at position 16,..., 31 now occupy position 1,3,...,31.

2. Similar to operation one, but with different "cut." The cards at position 1,2,3,...,16 now occupy position 1,3,5,...,31, and the cards at position 17,...,31 now occupy position 2,4,6,...,30.

3. Take $m$ cards from the top and move them to the bottom of the deck (a standard cut).

Starting from the original configuration, how many different configurations can be achieved by repeating the three operations above?

Solution

There are $5.31 = 155$ different configurations.
First, it's clear that the deck can be "rotated" in any amount along one direction, so we only consider rotational configurations.
Step 1 moves cards from position $m$ to $2m \mod 31$
Step 2 moves cards from position $m$ to $2m-1 \mod 31$
Step 3 moves cards from position $m$ to $m+k \mod 31$ for some $k$.

Now, step 3 does not change the rotational configurations. Step 1 and 2 both can be consolidated into the move from $m$ to $2m \mod 31$ and followed by a suitable number of step 3.

Thus, the number of different rotational configurations are the smallest number $n$ such that $2^n \equiv 1 \mod 31$, and that means $n=5$.

So there are 5 rotational configurations and 31 configurations within each rotational configuration, for a total of 155.

Number of solutions to modular equation

Prove that there are infinitely many prime numbers $p$ such that there are exactly $p^2$ integer triples $(x,y,z)$ such that $0 \leq x,y,z < p$ and $x^2+y^2 - 2010z^3$ is divisible by $p$.

Solution

We will first show that any prime that has form $p = 6k-1$ and does not divide 2010 satisfies the given condition.

First, let $p$ be such prime. Suppose there are $a,b \in \{ 1, \dots, p-1 \}$ such that $a^3 \equiv b^3 \mod p$.

Since $b^{p-1} \equiv 1 \mod p$ then let $c \equiv ab^{p-2} \mod p$, so that we have $bc \equiv a \mod p$.

Then $b^3c^3 \equiv a^3 \equiv b^3 \mod p$ which means $b^3c^3 \equiv b^3 \mod p$ which then means $c^3 \equiv 1 \mod p$ (since $(b,p) = 1$).

Because $c^{p-1} = c^{6k-2} \equiv 1 \mod p$ and $c^{6k-3} = c^{3(2k-1)} \equiv 1 \mod p$, then we must have $c \equiv 1 \mod p$, which means $a \equiv b \mod p$.

In summary, we've shown that $a^3 \equiv b^3 \Rightarrow a \equiv b \mod p$. This means that the set $\{1^3, \dots, p^3 \} \mod p$ is the same as set $\{ 1, \dots, p \} \mod p$. So given any arbitrary $x$ and $y$, we can find exactly one $z$ such that $z^3 \equiv 2010^{-1} (x^2+y^2) \mod p$. Since there are $p^2$ possible pairs for $(x,y)$, then there are also $p^2$ possible triples for $(x,y,z)$.

Now we show that there are infinitely many primes of the form $6k-1$ which would mean that there must be infinitely many primes of the form $6k-1$ that do not divide 2010.

Note that any prime above 3 must have form $6k+1$ or $6k-1$. If there are only finite number of primes of the form $6k-1$, say $p_1, p_2, \dots, p_n$, consider the number $N = 6p_1p_2 \dots p_n - 1$.
For each $i$, $p_i$ does not divide $N$ because otherwise $p_i$ would also have to divide 1, a contradiction. So $N$ is not divisible by any of the $p_i$s, which means all prime factors of $N$ must be of the form $6k+1$. That means, $N \equiv 1 \mod 6$, a contradiction.

a,b,c integers and cubic number

Suppose $a,b,c$ are positive integers such that $\frac{a}{b} + \frac{b}{c} + \frac{c}{a}$ is an integer. Prove that $abc$ is a cubic number.

Solution

We have $ab^2 + bc^2 + ca^2 = kabc$ for some k.

Let $d = \gcd(a,b,c)$. We can replace $a,b,c$ by $a/d, b/d, c/d$ respectively and the problem does not change. Thus, without loss of generality, we may assume that $d = 1$.

Let $p$ be a prime that divides $abc$, which means $p$ divides at least one of $a,b,c$. We also know that $p$ cannot divide all three, since $d = 1$.

If $p$ divides exactly one of $a,b,c$, for example $a$, then $ab^2, ca^2, kabc$ are all divisible by $p$, but not $bc^2$. Impossible. Thus, $p$ must divide exactly two of $a,b,c$.

Suppose $p$ divides $a$ and $b$. Furthermore, let $x$ be the largest integer such that $p^x$ divides $a$. Likewise, let $y$ be the largest integer such that $p^y$ divides $b$.

Since $ab^2, bc^2, kabc$ are all divisible by $b$, then so is $ca^2$. Thus $y \leq 2x$.

Since $ab^2, ca^2, kabc$ are all divisible by $a$, then so is $bc^2$, Thus $y \geq x$, which means $x \leq y \leq 2x$.

Now, since $ab^2, ca^2, kabc$ are all divisible by $p^{2x}$, then so is $bc^2$, which means $y \geq 2x$.

Therefore, $y = 2x$, which means that the degree of $p$ in the factorization of $abc$ is $x+y = 3x$.

For each prime $p$ that divides $abc$, it must occur as a cubic number in its prime factorization. Thus $abc$ is a cubic number.

A non-trivial example is $a=1,b=2,c=4$.