Find the smallest integer $k \geq 2$ such that for every partition of the set $\{2, 3,\hdots, k\}$ into two parts, at least one of these parts contains (not necessarily distinct) numbers $a$, $b$ and $c$ with $ab = c$.
Problem
Source: 2019 Baltic Way P7
Tags: combinatorics
ubermensch
18.11.2019 14:10
The answer's 32. Assume to the contrary. Put 2 in, say, set A. 4 must be in set B. 16 must be in set A. If 8 is in set A, then $2 \cdot 8 =16 \implies$ Contradiction. If 8 is in set B, then $2 \cdot 16=8 \cdot 4 =32 \implies$ Contradiction. It's simple but a little tedious to find a set with $k=31$ that doesn't work- the trick's to put the primes (and 16) together. Here's one: $(2,3,5,7,11,13,16,17,23,24,29,31)$ and $(4,6,8,9,10,12,14,15,18,19,20,21,22,25,26,27,28,30)$. (Hopefully now it works, thanks to @below for pointing out the mistake in the partition)
benstein
18.11.2019 16:52
The sets you provided above work if you switch the positions of $21$ and $24$.
Letteer
18.11.2019 20:35
ubermensch wrote: The answer's 32. Assume to the contrary. Put 2 in, say, set A. 4 must be in set B. 16 must be in set A. If 8 is in set A, then $2 \cdot 8 =16 \implies$ Contradiction. If 8 is in set B, then $2 \cdot 16=8 \cdot 4 =32 \implies$ Contradiction. It's simple but a little tedious to find a set with $k=31$ that doesn't work- the trick's to put the primes (and 16) together. Here's one: $(2,3,5,7,11,13,16,17,21,23,29,31)$ and $(4,6,8,9,10,12,14,15,18,19,20,22,24,25,26,27,28,30)$. You switched $19 $ and $21$. Also, your example doesn't work since $4 \cdot 6=24$. Take $A=(2,3,5,16,24,28)$ and $B=(4,6,7,8,9,10,11,12,13,14,15,17,18,19,20,21,22,23,25,26,27,29,30,31)$. To convince yourself that this is good, notice that in $B$, $6 \cdot 6>31,4 \cdot 8>31$, so only $4 \dot 4=16$, $4 \cdot 6=24 $ and $4 \cdot 7=28$ can make problems, but they are in $A$. Similar argument works for $A$. Otherwise, I think your solution is perfectly well formalised.
I tried writing out a proof and the best I could come up with is as follows:-
$2^2=4$ and $4^2=16$ and so the set not containing $4$ must contain both $2$ and $16$. Then $8=\frac{16}{2}$ is in the same set as $4$. But now $32=2\times 16=4\times 8$ cannot be in either set.
In the second part you could perhaps say that for $k<31$ simply restrict any solution for $31$ to the smaller numbers.
A simple split is $A=\{2,3\}\cup\{x|x\ge16\}, B=\{x|4\le x<16\}$.
Th3Numb3rThr33
19.11.2019 07:50
See AIME II 2010/12.
Plops
16.03.2020 01:36
Label the two sets we divide $\{2, 3,\hdots, k\}$ into as $A$ and $B$ and consider dealing with powers of $2$. We want to find the minimum power of $2$ such that we are guaranteed to have some $2^i, 2^j, \text{and} 2^{i+j}$ in either $A$ or $B$. WLOG let $A$ contain $2$. Then $B$ must contain $2^2$. If $A$ contains $2^3, k=16$ satisfies the conditions, and if $B$ contains $2^3$, we must place $2^4$ in $A$, and $k=32$ satisfies the conditions (but $k=16$ need not). Optimality follows from CRT.
A-Thought-Of-God
10.11.2020 07:25
The trick is basically considering powers of 2. We claim that $k=32$. Assume opposite. Let $$2\in A\implies 4 \in B \implies 16\in A \implies 32\in B$$Now if $8\in A$ then $8\cdot 2=16,$ and if $8\in B$ then $8\cdot 4=32,$ Contradiction!
Here is a working partition for $k=31$.
Partion in the following way: $$A=\{2,3,5,7,11,13,16,18,23,24,28,29,30\}$$and $$B=\{4,6,8,9,10,12,14,15,17,19,20,21,22,25,26,27,31\}$$
bora_olmez
25.07.2021 19:29
Similar to the solutions above - posting for storage. We claim that the minimal $k$ is $32$. Let $A$ and $B$ denote the two sets. If $2 \in A$, then $4 \in B, 16 \in B$ and $32 \in A$, wherever we add $8$, we have either have $2,8,16$ or $4,8,32$ in the same set. If $k \leq 31$ take $A = \{2,3,5,7,11,13,16,17,18,19,23,24,29,31\}$ and $B = \{4,6,8,9,10,12,14,15,20,21,22,25,26,27,28,30\}$. $\blacksquare$