There are infinitely many boxes - initially one of them contains $n$ balls and all others are empty. On a single move we take some balls from a non-empty box and put them into an empty box and on a sheet of paper we write down the product of the resulting amount of balls in the two boxes. After some moves, the sum of all numbers on the sheet of paper became $2023$. What is the smallest possible value of $n$?
Problem
Source: Bulgaria JBMO TST 2023, Day 2, Problem 3
Tags: combinatorics, invariant
starchan
17.06.2023 21:54
Solved with AdhityaMV, Siddharth03, p_square
We treat the operations as moves on an initially complete graph $K_n$. When we split a number $m$ into number $a, b$ we split the vertices of the component we are in (the $K_m$) into two smaller components of sizes $a, b$ and delete all edges between the two. This implies that if some $n$ achieves $2023$, we must have ${n \choose 2} \geqslant 2023$, which implies that $n \geq 65$. Now we need only show that if $n = 65$ we can come up with a sequence of deletions which deletes exactly $2023$ edges. This is the same as leaving ${65 \choose 2} - 2023 = 57$ edges in the final graph. As the final graph can be anything, as long as each component is a clique, we may force it to become the union of a $K_{11}$ and two $K_2$'s and a bunch of $K_1$'s. Since $11 + 2 + 2 \leq 65$ this is valid and we're done. The minimum value of $n$ is $65$.
egxa
17.06.2023 23:36
Answer:$65$. Solved with binsherlo, PuzzlingCane. We will define $f(n)$ as the maximum possible value of the sum that can be obtained with $n$ balls. We will prove that $f(n)=\frac{n(n-1)}{2}$ by induction. We can easily see $f(1)=0, f(2)=1,f(3)=3,f(4)=6$ Firstly, let's take $b$ balls from the nonempty box which has $a+b$ balls in the beggining. We have $f(a+b)=f(a)+f(b)+ab$ $f(a+b)=\frac{a^2-a}{2}+\frac{b^2-b}{2}+ab=\frac{a^2+b^2-a-b+2ab}{2}=\frac{(a+b)(a+b-1)}{2}$ So $f(n)=\frac{n(n-1)}{2}$ $f(64)=2016<2023$ and we have an example for $65$.