Challenge Math Challenge - June 2020

[PhysicsBoi1908]

Question 15

Spoiler

Define $$s_i=a_1 + a_2 + a_3 + \cdots + a_i$$ where $i\in\{1, 2, \cdots, n\}$

Note that any element of the subset $\{a_{j1}, \cdots, a_{jm}\}$ can be represented as a difference of $s_i$ and $s_{i-1}$ using suitable i.
Let $b_i$ be the remainder when $s_i$ is divided by $n$. $b_i$ can assume n values from $0$ to $n-1$.
Then $$s_i \equiv b_i~(mod~n)~\cdots~(1)$$
If $b_i$ becomes $0$ then the set $\{a_1, a_2, \cdots, a_i\}$ satisfies the required condition so now we need to consider only those cases where $b_i$ assumes values from $1$ to $n-1$.

We have $n$ possible sums of the form $s_i$ but only $n-1$ remainders.
So using the Pigeon Hole principle, At least one remainder must have occurred twice.

Say $b_m = b_n$ such that $m>n$.
Then using $(1)$ we get $$s_m - s_n \equiv 0~ (mod~n)$$
Which means that the required set is $\{a_{n+1}, \cdots, a_m\}$ which will always exist.
And we are done.

 

[PhysicsBoi1908]

Question 13

Spoiler

Rearragne the equation to get $$3a^3 = n - b^3~\cdots(1)$$

When $n$ is a multiple of $3$:
Assuming $3|n$, we obtain that $3|b^3$ but that means $3$ is a prime factor of $b$. Hence, we conclude that $3|b \Rightarrow 27|b^3$.
Let $n=3k$ (note that $k \in N_0)$, then using $(1)$:
$$\begin{align} 2&7|3k-3a^3 \\\Rightarrow~&9|k-a^3\\\Rightarrow~& 9p=k-a^3 \end{align}$$
Set $a=-c$ (note that $c$ will be an integer) and rearrange the above equation to get:
$$9p-k=c^3$$
The cube of any integer can only be of the form $9q, 9q-1, 9q-8~\cdots (2)$ (Proof given below).
Thus we conclude that the equation will have solutions only if $k \equiv i(mod~9)$ where $i \in \{0, 1, 8\}$
Hence, we have found all possible $n$ such that it is a multiple of $3$ and satisfies $(1)$.
Minimum value of $k$ such that the equation has no solutions will be $2$. Thus $n=6$ represents the smallest multiple of $3$ such that $(1)$ does not hold.
It is easy to check that there exist solutions to $(1)$ when $n=1,2,4,5$.
Thus $6$ is the smallest value of $n$ such that $(1)$ has no solution.

Proof of $(2)$:
There are $3$ possibilities:
$$\begin{align}&c\equiv 0(mod~3) \Rightarrow c=3p\\&c\equiv1(mod~3)\Rightarrow c=3p+1\\ \text{and }&c\equiv 2 (mod~3) \Rightarrow c=3p+2 \end{align}$$
Cubing $c$ in each case and expanding gives the required result.

 

[PhysicsBoi1908]

I tried generalizing when the equation in question 13 will have a solution such that $n$ is not divisible by $3$, just like I did for the case when $3|n$, but I have no idea how to proceed, can anyone give a hint?

 

[fresh_42]

I tried generalizing when the equation in question 13 will have a solution such that $n$ is not divisible by $3$, just like I did for the case when $3|n$, but I have no idea how to proceed, can anyone give a hint?

This is one of the entry points to algebraic geometry, where the vanishing sets of polynomials $(3X^3+Y^3-Z)$ are investigated by means of ring theory $\mathbb{Q}[X,Y,Z]$. There are in general no easy solutions.

 

[PhysicsBoi1908]

Would it be in reach for me (a senior high school student). If yes, can you recommend any book?

 

[fresh_42]

Would it be in reach for me (a senior high school student). If yes, can you recommend any book?

Everything is in reach. It's only a matter of patience and effort. I guess one should first read a book about commutative algebra to get used to the concept of ideals and rings. However, this does not mean that this heavy machinery is necessary for the above question. Special cases are often easier than general ones.

But if I remember how long it took to deal with $X^n+Y^n-Z^n$ then things can quickly become complicated.

There is also an approach like the one you have chosen by considering remainders modulo suited numbers, primes preferred. This leads to concepts like the Legendre-, Jacobi-, and Kronecker-symbols. You can look those up on Wikipedia. There are also some theorems from Euler, Fermat and others which might help.

The question was only to show that $n=6$ is impossible. To show that a certain problem has no solutions is normally a lot harder than to find one. I don't want to rule out that the given problem has some nice and easy generalizations, so go ahead and find out.

Here are two serious sources for many kind of books which can be downloaded as pdf files. Another possibility is to search for lecture notes. Many professors publish them, so there is no real limit anymore to learn something. Just an advice: If you start to get annoyed by e.g. complexity of the stuff, stop reading and try something else. It would be a pity if you lost interest, just because you tackled a book too early. There are so many interesting things out there. It usually takes a while to find out what one's favorite topics are.

https://link.springer.com/search?facet-content-type="Book"&package=mat-covid19_textbooks&facet-sub-discipline="Number+Theory"&facet-language="En"&sortOrder=newestFirst&facet-discipline="Mathematics"&showAll=true

https://www.ams.org/open-math-notes...u0edm5--TilnXy0jH25azg4T63LiOjRPWzefguHc4DH_0

 

[benorin]

@wrobel I’be got a snowball’s chance in hell of solving problem #9 but thought it’d be good for me to try since I’ve not attempted this material in 20+ yrs. I just wanted to ask if I need to use Papa Rudin on this one as a source or if I can get by with a lesser text? I thought the Topology text was giving me workout... but Papa Rudin make me hurt right in the math muscle.