3

A version of the pigeonhole principle is:

(1) If m objects are put in n boxes and n < m, then at least one box contains at least ceil(m/n) objects

An alternate (more generalized) version is:

(2) For a nonempty finite collection of integers (not necessarily distinct), the maximum value is at least the average value.

How do I prove (2) starting from (1)? Every description I have read leaves this as obvious but I can't seem to make the link so easily.

Neo
  • 133
  • 1
    IMO there is no need to be formalizing too much: we have $n$ integers whose sum is $m$, so we have "n" boxes containing "m" units/1's as a total. Then by (1) at least one box contains more than the average. – String Nov 01 '13 at 09:17
  • Once we have drawn the analogy of mapping each number to an equivalent number of units, it seems trivial. However, there is a small leap of logic to be made there and before I found the solution, it did not seem too obvious. – Neo Nov 01 '13 at 09:22
  • My comment was no so much about whether it seems trivial or not. It was just to point out that the idea in Tomas' answer can be communicated without defining additional notation -- to make it softer to read. – String Nov 01 '13 at 09:45

2 Answers2

4

Assume you have $n$ integers $a_1,\dots,a_n$. Assign them $n$ "boxes" $A_1,\dots,A_n$, such that for all $i$, $A_i$ is filled with $a_i$ "objects". The total number of objects will be $m:=a_1+\dots+a_n$. (1) applies and tells, that there is a box $A_i$ which contains at least $ceil(m/n)$ objects. Now $a_i$ is the number of objects of $A_i$, so: $$a_i\geq ceil(m/n)\geq m/n = \frac{a_1+\dots+a_n}{n}$$

Tomas
  • 4,534
  • Sir are you assuming the integers to be positive ? As negative integers as negative objects will make no sense? – Orion_Pax Apr 12 '22 at 10:42
1

I don't know how to prove (2) from (1), but (2) can be proved quite easily, can't it?

Let $a_1,\dots,a_n\in\mathbb R$ (not even necessarily in $\mathbb{Z}$). Suppose for contradiction that $$a_j< \frac 1n \sum_{i} a_i \quad\text{for all }j$$ If you add all these $n$ inequalities, you get $$\sum_j{a_j} < \sum_{i} a_i,$$ contradiction (since the name of the summation variable plays no role).

Do I miss something in your question?

yo'
  • 4,506
  • It is kind of intuitive and your proof states it well, but I wanted to derive it from version (1), in the sense that proving (2) will be one of the applications of (1). – Neo Nov 01 '13 at 08:55
  • Edited the question to improve version (1). – Neo Nov 01 '13 at 08:59