I am looking for a generalized method to solve simple to advanced pigeonhole principle questions (that are PURELY pigeon-hole ie not in combination with any other topics like probability)
The definition:
Suppose that $n$ pigeons fly into $d$ pigeonholes. Performing the division, let $n = qd + r$, where the remainder is $r = 0, 1, 2, . . . , d − 1.$
If $r = 0$, there must be at least one pigeonhole with $q$ pigeons.
If $r > 0$, there must be at least one pigeonhole with $q + 1$ pigeons.
The least number of pigeons that will guarantee that there is at least one pigeonhole with at least $q + 1$ pigeons is $qd + 1$
Normally I don't use the above definition because I dont really understand it but I can solve wuestion anyway by intuition. So I am asking: If $r=0$, why is $n = q$ and not $qp$? If $r > 0$, why is the remainder $q+1$? Since the remainder can be up to $d-1$, I don't understand where the $q+1$ comes from. And From the third statement, I have realised that I am probably interpreting the law incorrectly: it seems that I should be ignoring $d$ for some reason or maybe I am just supposed to set it equal to $1$?
My second question is: will considering the "worst case scenario" work for every question? This method has not failed me yet but if I search online, there is hardly any information on it (and on the PHP in general).
Typical questions involve something along the lines of "how many socks/ties/hats would I have to pick to ensure two of the same color" and I just consider the worst case scenario where I delay the desired outcome until the very end. Then I just add one to force the ceiling function to go to the next positive integer, which basically ensures the "same color" pair. HOWEVER, when the "worst case scenario" gets more abstract eg $$\text{Prove by using PHP that there are two powers of $2$ that differ by a multiple of 8479}$$
I cannot identify the worst case scenario. Basically,should I be able to use it in all PHP questions?
I have a statement which I think is what I need to prove:
RTP $2^a - 2^b = 8479k$, where $a,b,k$ are integers.
But I'm not sure how to proceed from here USING MY METHOD. I know there is another method that consists of considering a set of powers of $2$ and dividing by $8480$ to produce $8479$ remainders. But in this case, is there a "worst case scenario"?
The version of pigeonhole principle that you cited is ridiculous. Not because it is wrong, but because it is NOT the right way to learn at all. In fact, it is completely pointless to learn the name "pigeonhole principle". Instead, just think as follows:
If you have $d$ groups, each having at most $k$ objects, then in total you have at most $d·k$ objects. That is it. Now think what this implies for the applications you want.
No need for your vague intuition about 'worst-case scenario' either. If every power of two is different modulo $m$, then obviously there are at most $m$ powers of two.......