If the average of the series is an integer, prove that there exists a number in the sequence that does not appear more than $n$ times.

Question

We consider a sequence of $6n+5$ numbers $(n \in \mathbb{N})$ all belonging to the set {$4, 5, 6, 7$}. If the average of this series is an integer, prove that there exists a number in the sequence that does not appear more than $n$ times.

I would like to point out that every number appears at least once, it is not stated in the English version of the problem, but it is in the Croatian version. I found this problem in the papers that I was given by a teacher when I was a member of the Croatian JBMO team, he gave us a combinatorics paper, and we were solving it together on the team preparations, but we didn't have enough time to get to this problem. The paper doesn't state the source of the problem, so I have no idea where it comes from. So far, I've tried something, and I don't think I found the right approach, but now I am a bit rusty, so I would like to share this problem with you, maybe someone will solve it with combinatorics (after all, it is a combinatorics problem). Like I said, so far I have tried to start by saying that $S_k$ is the number of times the number $k \in$ {$4,5,6,7$} appears in the sequence. Then, we would have
$S_4+S_5+S_6+S_7=6n+5$, and
$\frac{\displaystyle\sum_{k=4}^{7}kS_k}{6n+5}\in \mathbb{Z}$
The thing is that I think that I am approaching it like it is a number theory problem, not a combinatorics problem. I think it is better with combinatorics techniques, so I tried with something like invariants, but that led me nowhere.

Answer 1

Assume that it is, in fact, possible, and we can choose more than $n$ of each number in the set.

First, exactly what integers could the average be? Since there are some of each number, the only possibilities for the average are $5$ or $6$.

It's a bit easier to consider the equivalent problem of whether we can choose a total of $6n+5$ numbers belonging to the set $\left\{-3, -1, 1, 3\right\}$ whose average is $x=\pm1$.

Say we pick the values in the set $a+n$, $b+n$, $c+n$ and $d+n$ times respectively, where each of $a,b,c,d$ is a positive integer, and $a+b+c+d=2n+5$. Then $$-3a-3n-b-n+c+n+3d+3n=(6n+5)x$$ ie $$-3a-b+c+3d=(6n+5)x$$

As mentioned before, $x=\pm1$. If $x=1$, $$-3a-b+c+3d=6n+5$$

Also, $3(a+b+c+d)=6n+15$; combining these, $$10=6a+4b+2c$$

But this contradicts the fact that $a,b,c$ are positive integers.

The same argument works for the $x=-1$ case.

Answer 2

Proof by contradiction.

Assume that each number appears at least $~n+1~$ times.

This means that you have a subset of the terms, with this subset having $~4n+4~$ terms, and an average value of $~5.5.~$

So, you can say that the average value of this subset is off of the integers, by $~1/2~$ with a weight of $~4n+4.~$

The issue is whether the remaining terms can either bring the average up to as high as $~6,~$ or down to as low as $~5.$

Because of considerations of symmetry, without loss of generality, you can assume that the goal is to bring the average up to as high as $~6.~$

If this can not be done by making all of the rest of the terms equal to $~7,~$ then it is game over.

---

At this point, the math can be simplified by presuming that you have an average value of $~-1/2~$ with weight $~4n+4,~$ that $~7~$ represents $~+1~$ against the goal of $~6,~$ and that the most additional terms possible is $~(6n+5) - (4n+4) = 2n+1.~$

So, the contradiction is established, because

$$2 \times (2n+1) < 4n + 4.$$

This means that even though each $~7~$ is contributing $~+1~$ to the goal of bringing the overall average up to $~6,~$ since there are only to be $~(2n+1)~$ terms with the $~+1~$ value, it will not be enough to offset the $~-1/2~$ that has a weight of $~4n+4.$