2
$\begingroup$

While reading about hash collisions I landed on this problem in Wikipedia Article on the Pigeonhole Principle.

While I think I understand the Pigeonhole principle, I am not sure what to make of this example and what the author tries to explain with it.

  • The author uses 7 Players, where I think 5 would have been enough to make the Point
  • In the mathematical formula the author drops the remaining 0.5 from the 6/4 without explanation
  • After dropping 0.5 author uses an equal sign, which to me, signals equality of both sides.

Is this an acceptable equation? Why does the author use 7 Players instead of the 5 it would need to make the example? Is this not violating what the equal sign stands for?


I do not have enough faith in my opinion to edit a Wikipedia article, which is why I am asking here.

$\endgroup$
1
  • $\begingroup$ the box sign stands for smallest integer less than given number $\endgroup$
    – praveen kr
    Jun 15, 2017 at 14:31

2 Answers 2

1
$\begingroup$

Although your intuition is correct in suggesting that $5$ players would have been the fewest number possible to apply the pigeonhole principle, the example is still correct as stated. The important fact here is that $7>4$.

The $0.5$ has been absorbed by the floor function: see here

$\lfloor\frac{6}{4}\rfloor=\lfloor1.5\rfloor=1$.

The answer concludes, based on the formula given in the introduction, that at least one team will contain $2$ of the players. It is possible, since there are $7$ players, that more than one team will contain $2$ of the players. It is also possible that one team will contain more than $2$ players. The pigeon-hole principle is the assertion that

at least one team will contain $2$ of the players

which is always true, given that there are $7$ players and $4$ teams.

$\endgroup$
1
  • $\begingroup$ Ohhh ok. I'm not overly famliar with Mathematical Notation and didn't realize that this was a floor function and not just brackets. Well, I feel stupid now, especially since I use Math.Floor() often enough... $\endgroup$ Jun 15, 2017 at 14:38
0
$\begingroup$

You're correct that the author only needed to use $5$ players to come to the same conclusion ($5$ is the smallest number to come to the conclusion that at least one team has at least $2$ players). There doesn't seem to be a specific reason the author used $n=7$, just the number he used.

The reason the author dropped the $0.5$ when he divided $6/4$ is because he is applying the flooring function. He is essentially dropping to the greatest integer value preceding the value you are calculating. Since the greatest integer value preceding $6/4$ is $1$, when you apply the flooring function, you get

$\lfloor\frac{6}{4}\rfloor=1$.

Based on the equation $\left\lfloor \frac{n-1}{m} \right\rfloor + 1$, where $n$ is equal to the number to softball players (ie. $n = 7$) and $m$ is the number of softball teams (ie. $m = 4$), you can see that we get $\left\lfloor \frac{n-1}{m} \right\rfloor + 1 = \left\lfloor \frac64 \right\rfloor + 1 = 1 + 1 = 2$. This conclusion is stating that, no matter how you order the players on the $4$ teams, there will always be at least one team that has two players, which is a clear case of the pigeon hole principle.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .