Manzi has $n$ stamps and an album with $10$ pages. He distributes the $n$ stamps in the album such that each page has a distinct number of stamps. He finds that, no matter how he does this, there is always a set of $4$ pages such that the total number of stamps in these $4$ pages is at least $\frac{n}{2}$. Determine the maximum possible value of $n$.
Problem
Source: PAMO 2023 P4
Tags: combinatorics
23.05.2023 20:51
I’ll vent here to bump this. I did P5 in 10 minutes, then spent 3 effing hours on this cursed problem guessing bounds all of which turned out to be incorrect, didn’t even try P6 (or as I’ve learned some call Q6) which was way easier, and missed gold by 1 point. Talk about luck. After contest, I found out the what I was doing was close to the real thing. The answer is: $n=140$. Proving that it works is not hard. For $n$ greater than $140$, take pages with sizes: $i+c_0, i-1+c_1, \cdots, i-8+c_8,i-9$ where we choose $c_i=0,1$ such that $c_0\ge c_1\ge \cdots \ge c_8$ and $n=10i-45+\sum_{i=0}^8c_i$. It’s easy to show that this works.
07.06.2023 15:51
ZNatox wrote: I’ll vent here to bump this. I did P5 in 10 minutes, then spent 3 effing hours on this cursed problem guessing bounds all of which turned out to be incorrect, didn’t even try P6 (or as I’ve learned some call Q6) which was way easier, and missed gold by 1 point. Talk about luck. After contest, I found out the what I was doing was close to the real thing. The answer is: $n=140$. Proving that it works is not hard. For $n$ greater than $140$, take pages with sizes: $i+c_0, i-1+c_1, \cdots, i-8+c_8,i-9$ where we choose $c_i=0,1$ such that $c_0\ge c_1\ge \cdots \ge c_8$ and $n=10i-45+\sum_{i=0}^8c_i$. It’s easy to show that this works. Can you explain much more? What is "I" All thing your said is confused.
14.08.2024 11:14
this problem for sure not proposed to be p4 lol