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$
  • $\begingroup$ the box sign stands for smallest integer less than given number $\endgroup$ – praveen kr Jun 15 '17 at 14:31
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$
  • $\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$ – checkersquares Jun 15 '17 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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.