Let $k>1$ be a positive integer. A set $S{}$ is called good if there exists a colouring of the positive integers with $k{}$ colours, such that no element from $S{}$ can be written as the sum of two distinct positive integers having the same colour. Find the greatest positive integer $t{}$ (in terms of $k{}$) for which the set \[S=\{a+1,a+2,\ldots,a+t\}\]is good, for any positive integer $a{}$.
Problem
Source:
Tags: combinatorics, Sets, Romanian TST, TST
16.05.2021 18:15
Let $a=2b$ and consider the following set \[M=\bigg\{b,b+1,...,b+\bigg\lfloor\frac{t+1}{2}\bigg\rfloor\bigg\}.\]Observe that for any $x,y\in M$ we have $a+1\leq x+y\leq a+t$. Therefore, for $S$ to be good there must exist a colouring of the positive integers for which no two elements of $M$ have the same colour. Therefore \[|M|=\bigg\lfloor\frac{t+1}{2}\bigg\rfloor+1\leq k\Longrightarrow t\leq 2k-2.\]We claim that $t=2k-2$ works. For the same of simplicity, let $C_i$ be the set of the numbers coloured with colour $i$. If $a=2b$ then \[C_1=\{1,2,...,b\}, \ C_2=\{b+1\}, \ C_3=\{b+2\},...,C_{k-1}=\{b+k-2\}, \ C_k=\{b+k-1,b+k,...\}.\]It is easy to observe that the above colouring works. Similarly, if $a=2b+1$ then \[C_1=\{1,2,...,b+1\}, \ C_2=\{b+2\}, \ C_3=\{b+3\},...,C_{k-1}=\{b+k-1\}, \ C_k=\{b+k,b+k+1,...\}.\]Therefore, $t=2k-2$ works and this is the maximal value.
20.08.2021 20:50
Wrong solution. Misinterpreted the problem.
20.08.2021 21:08
@above I am afraid you are wrong. You can access the official solution on the Romanian Mathematical Society website, over here. Unfortunately, it's in Romanian, but the first statement of P1's solution states "Aratam ca numarul cautat este $t = 2k - 2.$" which translates to "We prove that the number we are looking for is $t=2k-2.$"
07.11.2022 19:25
Very badly written solution, sorry for readers Since $k>1$, we know that $t\ge a+3$ i.e there are $x,y,z \in S$ such that $x+y=z$. Let $x\in S$ be random element and $s(x)\in S$ be the biggest number such that $x+s(x) \in S$. Then there are total $n_x=s(x)-x$ pairs of $(x,y_i)$ such that $x+y_i=z \in S$. Then $x,y_i$ must have different colors. Observe that the bigger $t$ is, the bigger $n_x$ is, forcing us to use more colors ( just wanted to say that,it is possible to color $y_i,y_j$ , since we are looking for max, we must maximizie $y_i,y_j$ that have same colors), hence we should have bound somehow, this is our first motivation. Notice that the bigger $a$ is, the least likely there are $x+y=z \in S$,hence if $a=1$ holds, then $a=a_0$ for arbitrarly bigger $a_0$ will more unlikely hold, hence it is enough to prove for the worst case, which is $a=1$. ( i.e, let $x=a+i,y=a+j$, then $z=2a+i+j$, it is easy to see that making $a$ big makes $z$ big, making unlikely that $z \in S, $) From above, we can assume $a=1$ ( $t \ge 4$). Then $S= \{ 2,3,4,...,t+1 \}$. Let $ N_i \ge i \ge 1$ , choose $x= 1+i$, then $s(x)=t-i>1+i $, $n_{1+i}=t-2i-1$. Then we need atleast $t-2i$ colors. Where $N_i$ is the biggest natural number such that $t-N_i > 1+N_i$ i.e number of possible pairs $x+y = z \in S$ where $x=1+i$, Note that if $N_i=0$, there are no such pairs ( which exists in our set) If $i=1$, we have $s(2)=t-1$ ( the biggest number such that $(2)+(t-1) \in S)$, $n_2=t-3$ ( number of possible pairs). Color all of these pairs with $2$ colors ( all $y_i$ has same color). Now let $i=2$. We have $n_3=t-5$ if $n_3 >0$, we must color $n_3$ different, which leaves us $3$ colors. Let $i=3$. We have $n_4=t-9$. if $n_4 >0$, we must use another color, which gives us $4$ colors. Overall, we can repeat this prosses. Notice that the bigger $t$ is, the more $n_k>0$ will have, which gives us a upper bound.Assume that the prosses goes on until $i=j$ ($i=j$ works but $j+1$ doesnt) Then these must hold: $$j \le k, t-2j-1 >0$$By definition of $j$ we choosed, $ t \le 2k-2$ ( if we choose $t > 2k-2$, say $2k-1$, we have $t-2j-1 > 2k-2-2j-1= k-j-1>0 \Leftrightarrow k> j+1$, contradiction). Hence $t=2k-2$ is the biggest integer possible. It is trivial to show a construction for $a=1$, for bigger $a$ it works automatically by the argument we made above. Hence we are done! Remark: I am not sure about my argument of $a=1$ being the worst case, it is a bit sketchy here, but hey at least I got the right answer duh
17.10.2023 14:14
oVlad wrote: @above I am afraid you are wrong. You can access the official solution on the Romanian Mathematical Society website, over here. Unfortunately, it's in Romanian, but the first statement of P1's solution states "Aratam ca numarul cautat este $t = 2k - 2.$" which translates to "We prove that the number we are looking for is $t=2k-2.$" Excuse me, how can I find solutions to other Romania TST from other years? still the same website? can you help me exactly where cause I don't know how to translate the language! Thanks a lot!
18.11.2023 13:59
Math03Math03 wrote: Excuse me, how can I find solutions to other Romania TST from other years? still the same website? can you help me exactly where cause I don't know how to translate the language! Thanks a lot! A few problems and solutions are on the website (ssmr.ro). If you want to navigate the website just use a browser extension to translate the page. If you want to find all the problems and solutions, your best chance is AoPS or maybe asking me.