An ode to generalise-ation

by p_square, Dec 19, 2018, 2:56 PM

Today's I'll attempt to discuss ~~ELMO 2018/2~~ the merits and demerits of attempting to generalise questions in order to prove their statements. Generlisation is a often very useful and perhaps counter-intuitively, many problems are actually harder to solve than a more general form of their statements.
Typical examples for this include induction style arguments and splitting one variable into 2. You'll get what this means in the example. A good example for this is the following problem.

*Note: I don't precisely remember the source, so anyone who does is requested to please comment below.

Unknown source; yagami1728 wrote:

There are $n^2$ lights of some $n$ colours (not necessarily $n$ of each colour). Prove that they can be arranged on $n$ christmas trees with $n$ lights per christmas tree, such that no tree has lights of three or more different types.

The more general version is this:

generalised yagami1728 wrote:

There are $nm$ lights of some $n$ colours. Prove they can be arranged on $n$ christmas trees such that each tree has $m$ lights and no tree has ornaments of three or more different colours.

For any fixed constant $m$ , this version can be solved via induction on $n$ .

The base case, ( $n=1$ ) is easy to see.
Now, assume it is possible for some $n$ .
Given any set of ornaments of $n+1$ colours, there is a colour which appears at most $m$ times (call such a colour sparse) and another colour which appears at least $m$ times (call such a colour abundant).
We can use all lights of a sparse colour on a tree and use lights of an abundant colour to fill in the incomplete spots, such that the tree finally has $m$ ornaments.
Observe that this reduces to the $n$ case and we're done by induction. $\blacksquare$

Here is another example of a problem (albeit ~~a little~~ much harder) in which a more general version is easier to solve.

ISL 2017 C6 wrote:

Let $n > 1$ be a given integer. An $n \times n \times n$ cube is composed of $n^3$ unit cubes. Each unit cube is painted with one colour. For each $n \times n \times 1$ box consisting of $n^2$ unit cubes (in any of the three possible orientations), we consider the multi-set of colours present in that box. This way, we get $3n$ sets of colours, split into three groups according to the orientation.

It happens that for every set in any group, the same set appears in both of the other groups. Determine, in terms of $n$ , the maximal possible number of colours that are present.

~~Since I'm too lazy to type the solution again~~ Here is the official solution from v_enhance's post which can be found here

The answer turns out to be $\dfrac{n(n+1)(2n+1)}{6}$
There does exist a messy solution which does not strengthen the problem statement in any way. However, much more is revealed about the problem by a different inductive, elegant solution which also explains the identity $\dfrac{n(n+1)(2n+1)}{6} = \sum_{i=1}^n i^2$ .

The following modifications on the original problem do not change the solution

we allow cubes to be invisible (i.e. to not have any color).
we still require every plate $S$ to be present in all three directions, unless $S = \varnothing$ .

The base case $n = 1$ is easy. For the inductive step, unless the entire cube is invisible (and hence has no colors at all), we can take an $S$ -plate ( $S \neq \varnothing$ ). Now suppose delete three $S$ -plates (one in each direction), then turn all those colours which appeared anywhere in $S$ invisible. This resulting $(n-1) \times (n-1) \times (n-1)$ cube that still satisfies the conditions! Since $S$ had at most $n^2$ distinct colors in it, it follows that $f(n) \le n^2 + f(n-1)$ and so $f(n) \le \frac16 n(n+1)(2n+1)$ as desired.

We can construct an example where $\frac16 n(n+1)(2n+1)$ colours are used as follows

We add $n$ colors, 1 for each point $(i,i,i)$ .
We then add $3 \binom n2$ . For any $1 \le i < j \le n$ , we have three colors; one on $(i,j,j)$ and $(j,j,i)$ ; one on $(i,j,i)$ and $(j,i,j)$ ; and one on $(j,i,i)$ and $(i,j,j)$ .
Lastly, we add $2 \binom n3$ colors. For any $1 \le i < j < k \le n$ , we have two colors: one on $(i,j,k)$ , $(j,k,i)$ , and $(k,i,j)$ ; and one on $(k,j,i)$ , $(i,k,j)$ , and $(j,i,k)$ .

Both of these question display the advantages of generalising questions but this art is a fickle friend. Many a time has an innocent person been lured by these gifts and overlooked the obvious. Here is an example of such an occurrence with an extremely overkill proof of ELMO 2018/2.

The original question statement is this

ELMO 2018/2 wrote:

Consider infinite sequences $a_1,a_2,\dots$ of positive integers satisfying $a_1=1$ and $a_n \mid a_k+a_{k+1}+\dots+a_{k+n-1}$ for all positive integers $k$ and $n.$ For a given positive integer $m,$ find the maximum possible value of $a_{2m}.$

There is a simple proof which can be easily found, but what follows is what I was able to come up with. If someone still wants to go through the simple proof, ~~get out of my blog~~, check here
Also, please if possible, go through my proof and tell me if there are any mistakes.

Some notation:
Call a natural number $n$ important if $a_n > 1$ and call $n$ esteemed if $a_n = \sum_{i=1}^{n-1} a_i$

We first demonstrate a few preliminaries about these sequences

Fact $1$ : $a_{k + n} \equiv a_k \pmod {a_n}$
Proof: For, the proof observe that we have $a_n|a_k + a_{k+1} + ..... + a_{n+k-1}$ On the other hand, we also know $a_n|a_{k+1} + ..... + a_{n+k}$ Subtracting, we obtain $a_n|a_{n+k} - a_k$

By induction $a_{k + mn} \equiv a_k \pmod {a_n}$ and more specifically every multiple of an important number is important. $a_m | a_{mn}$

Also, it's worth noting that $a_xa_{x+1} \mid (a_1+a_2 \cdots + a_x)$
Since $a_{x+1} \equiv 1 \pmod {a_x}$ , we know that $a_x,a_{x+1}$ are coprime.
By the condition on $a$ ,
$a_x \mid a_1 + a_2+ \cdots +a_x$ $a_{x+1} \mid a_1 + a_2+ \cdots +a_x + a_{x+1} - a_{x+1}$
The sum of two important numbers is important
Assume $i,j$ are important and WLOG $a_i \ge a_j$
Simply observe that $a_{i+j} \equiv a_j \pmod {a_i}$ which finishes the proof.
By induction, the sum of any finite multiset of important numbers is important

We will now deliberate over something we call the characteristic of the sequence

If $k$ is the largest number that divides every important number, call $k$ as the characteristic of the sequence $a$ .
Symbolically, $\mathbb{C}(a) := max(k)$ where $k$ varies over the set of numbers that divide all important numbers.
As an exception, define $\mathbb{C}(a) = 0$ , $\forall x, a_x = 1$

We first show that every sufficiently large multiple of $\mathbb{C}(a)$ is important.
From our assumption that there is no natural number greater than $\mathbb{C}(a)$ that divides all important numbers, we observe that there is a finite set $S$ of important numbers whose greatest common divisor is $\mathbb{C}(a)$ . ( Suppose you have checked all the important numbers upto $M$ and the gcd is something like $k\mathbb{C}(a)$ , where $k$ is some positive integer greater than $1$ (if not, then we are done!). But we know that the gcd of all important number is $\mathbb{C}(a)$ , thus there must exist some important number(maybe humongous) which is not divisible by $k\mathbb{C}(a)$ . Thus we include those numbers in our set $S$ and after adding finitely many numbers we are done!)
We are now done, since the sum of a finite multiset of important numbers was important.

Call a sequence $a$ primitive if $a_{\mathbb{C}(a)} = 1$

We will now attempt to use some bounding arguments to figure out what all the primitive sequences are.
We'll first show that $a_{r+\mathbb{C}(a)} > 2a_{r}$ for sufficiently large important $r$ .
Note that $a_{2\mathbb{C}(a)} | 2\mathbb{C}(a) - 1$ , so $a_{2\mathbb{C}(a)} \ne 2$
To prove the claim, consider the following congruences
$a_{r+\mathbb{C}(a)} \equiv a_{\mathbb{C}(a)} \equiv 1 \pmod {a_r}$ $a_r \equiv a_{\mathbb{C}(a)} \equiv 1 \pmod {a_{r-\mathbb{C}(a)}}$ $a_{r+\mathbb{C}(a)}\equiv a_{2\mathbb{C}(a)}\not\equiv 2\pmod {a_{r-\mathbb{C}(a)}}$
These together imply the result.

We now show that every sufficiently large multiple of $\mathbb{C}(a)$ is esteemed in a primitive sequence.

Proof: Observe that
$a_{r+\mathbb{C}(a)}-\sum_{i=1}^{r+1-\mathbb{C}(a)}a_i<a_r-\sum_{i=1}^{r-1}a_i+\mathbb{C}(a)$
We now show that $\mathbb{C}(a) \ne 1$ . That is not every natural number can be important.
Assume to the contrary.
Taking $x$ to be sufficiently large, we see that.
$a_xa_{x+1} \mid a_1 + a_2+ \cdots +a_x$ $a_xa_{x+1} \le a_1 + a_2+ \cdots +a_x = a_{x+1}~~~(because~~x+1 ~~is~~ esteemed)$ This is a contradiction to our assumption that $\mathbb{C}(a) = 1$ .

Now, we have developed enough machinery to determine all possible primitive sequences.

In any primitive sequences, since every sufficiently large multiple of $\mathbb{C}(a)$ is esteemed, if $r$ is sufficiently large $a_{r\mathbb{C}(a)} > \mathbb{C}(a)$
$a_{(r+1)\mathbb{C}(a)} = 2a_{r\mathbb{C}(a)} + \mathbb{C}(a) - 1$ $\mathbb{C}(a) - 1 \equiv 1 \pmod {a_{r\mathbb{C}(a)}}$ $\mathbb{C}(a) \equiv 2 \pmod {a_{r\mathbb{C}(a)}}$
Thus, $\mathbb{C}(a) = 2$
There is only 1 primitive sequence which is defined by
$a_x := \begin{cases} 1 & when~ x\equiv 1 \pmod 2\\ 2^{\frac{x}{2}} - 1 & when~x\equiv0\pmod2 \\ \end{cases}$ We know that $\exists$ $r, y$ ( $r$ is sufficiently large, $y = a_{2r}+1$ ) such that
$a_x := \begin{cases} 1& when~x=2m+1\\ y2^m-1&where~ x=2r+2m\\ \end{cases}$
Observe the bound $a_{2m} < 2^{2m}$ , which can be proved by induction.
${2} a_{2m} \equiv a_{2r+4m} \pmod {a_{2r+2m}}$ $a_{2m} \equiv y2^2m - 1 \equiv 2^{m}-1 \pmod {y2^m - 1}$
$a_{2r+2m} > a_{2m}$ yields $y = 1$ and $a_{2m} = 2^m - 1$ .

And now, we have enough machinery to figure out all possibilities for such sequences.
We will show that ll sequences fall into the following three types.
$a_x := 1$ $a_x := \begin{cases} k\mathbb{C}(a) & a_x = m\\ \text{else} & a_x = 1\\ \end{cases}$ where $m \mid \mathbb{C}(a) - 1$ , or
$a_x := \begin{cases} k\mathbb{C}(a) & a_x = (2^k-1)(\mathbb{C}(a)-1)\\ \text{else} & a_x = 1\\ \end{cases}$
We will prove this using infinite descent.
Consider a sequence $a$ not of this type with minimal characteristic $\mathbb{C}(a)$ . We'll find a sequence $b$ not of this type with smaller characteristic.
Clearly $y = a_{\mathbb{C}(a)} > 1$ , as the only primitive sequence was of this type.
Every term with an important index in $a$ is divisible by $y$ .
Also, clearly $y=a_{\mathbb{C}(a)}\mid \mathbb{C}(a)-1$
Define $b$ by
$b_x = \begin{cases} k\left(\frac{\mathbb{C}(a)-1}{y}+1\right) & b_x = a_{k\mathbb{C}(a)}\\ \text{else} & b_x = 1\\ \end{cases}$ It is easy to verify that $b$ also does not belong to the $3$ types and $\mathbb{C}(b) < \mathbb{C}(a)$

This post has been edited 6 times. Last edited by p_square, Jul 2, 2022, 12:52 PM

Comment

U VIEW ATTACHMENTS T PREVIEW J CLOSE PREVIEW rREFRESH

1 Comment

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

The source was Slovenia TST or something.

by Yagami1728, Dec 26, 2018, 7:39 PM

Report

Submit

thank you for teaching me the humpty point
by ihatemath123, Jun 27, 2024, 2:43 PM
ORZZZZZZZZZZ
by avisioner, Jun 19, 2024, 12:02 AM
He never had motivation to multiply out random polynomials
by the_mathmagician, Oct 25, 2023, 1:49 AM
Getting a part 3 is unlikely... anyways, if it ever gets released, it would be great if you listed some problems where this methods are useful!
by Alfombra12, Aug 13, 2023, 10:36 AM
still waiting for part 3
by kn07, Jun 14, 2023, 10:55 PM
Orz orz
by aansc1729, Mar 13, 2023, 1:13 PM
waiting for part 3 since 1 year
by anurag27826, Jul 18, 2022, 11:19 AM
pro kid moment
by the_mathmagician, Feb 15, 2022, 2:21 AM
Ded blog
by SPHS1234, Jan 31, 2022, 7:43 AM
orzity orz orz
by tigerzhang, Oct 15, 2021, 10:08 PM
congrats on IMO gold medal!
by mathlearner2357, Jul 25, 2021, 5:04 AM
orzorzorz
by PEKKA, Jul 21, 2021, 3:55 PM
Wow this is awesome!!

Waiting for part3
by lneis1, Jun 24, 2021, 5:42 PM
Part 3 hype
by NJOY, Jun 15, 2021, 9:29 AM
Ooh niceee! Waiting for part 3!
by L567, Jun 14, 2021, 4:43 AM
Something on FE's please
by Aryan-23, Feb 26, 2019, 5:33 PM
Post!!!!!!
by ELMOliveslong, Feb 22, 2019, 7:55 PM
Really amazing!! In fact you also have the skills of presenting things neatly!! waiting for more blog posts!!
by AlastorMoody, Jan 12, 2019, 7:40 AM
A good topic
by ahwawm, Dec 20, 2018, 3:22 PM
Nice post!
by Rmo, Dec 20, 2018, 2:17 PM
Great blog!!
by AhirGauss, Dec 19, 2018, 2:56 PM
@below He must have been busy these days. Have patience, boys. Legends are not made in ~~one day~~mere two months, after all.
by hansu, Dec 12, 2018, 6:52 PM
Nice blog! Please add NT
by Wizard_32, Nov 26, 2018, 12:47 PM
No.. this blog cannot die....
by enthusiast101, Nov 19, 2018, 1:14 PM
Nice blog!
by niyu, Nov 8, 2018, 5:02 AM
An "edge" was better
by anantmudgal09, Nov 1, 2018, 2:48 PM
@rajat1603_ Why do people want to know my "preparation story'??? In this blog most (all) of my posts will be mainly about math
by p_square, Aug 17, 2018, 5:10 AM
*PLEASE* let it be about your preparation story
by rajat1603_, Aug 17, 2018, 3:57 AM
I will post something during the weekend.
by p_square, Aug 16, 2018, 11:33 AM

63 shouts

A Vertex of Math

An ode to generalise-ation

by p_square, Dec 19, 2018, 2:56 PM

1 Comment