Can anyone come up with a full list of theorems and generalizations? How complete is the below list? I can only understand the first 2. Can anyone understand the rest of them containing "k" in the formulas?
Pigeonhole Principle (PP)
If n+1 objects are placed in n boxes, then one of the boxes must contain more than 1 object.
(PPb)
If n-1 objects are placed in n boxes, then one of the boxes must be empty.
Extended Pigeonhole Principle (EPP)
If nk+1 objects are placed in n boxes, then one of the boxes must contain at least k+1 objects.
(EPPb)
If nk-1 objects are placed in n boxes, then one of the boxes must contain at most k-1 objects.
Generalized Pigeonhole Principle (GPP)
If nk+s or more objects are placed in n boxes, then for each 0 ≤ m ≤ n there exist m boxes with a total of at least mk + min(s,m) objects
(GPPb)
If nk+s or fewer objects are placed in n boxes, then for each 0 ≤ m ≤ n there exist m boxes with a total of at most mk + max(0,s+m-n) objects
Pigeonhole Principle (PP)
If n+1 objects are placed in n boxes, then one of the boxes must contain more than 1 object.
In 4 spins 1 dozen has to repeat (excluding zero). Dozen have 3 boxes/pigeonholes. And in 4 spins we have 4 objects/pigeons.
(PPb)
If n-1 objects are placed in n boxes, then one of the boxes must be empty.
This could be the basis for the HG! If you can come up with a rule that puts less pigeons into more pigeonholes then we are guaranteed to never encounter a deadlock - a repeat will always happen before all uniques have shown.
Extended Pigeonhole Principle (EPP)
If nk+1 objects are placed in n boxes, then one of the boxes must contain at least k+1 objects.
I think this is related to multiple repeats? There will be 4 repeats (5 hits) of a dozen in 13 spins. Dozens have 3 boxes/pigeonholes (n). K = 4 = number of repeats. K +1 = 5, so 5 dozens/pigeons are placed in 1 pigeonhole:
D1
D1 D2 D3
D1 D2 D3
D1 D2 D3
D1 D2 D3
(EPPb)
If nk-1 objects are placed in n boxes, then one of the boxes must contain at most k-1 objects.
Related to the above, but need to think about this.
Generalized Pigeonhole Principle (GPP)
If nk+s or more objects are placed in n boxes, then for each 0 ≤ m ≤ n there exist m boxes with a total of at least mk + min(s,m) objects
(GPPb)
If nk+s or fewer objects are placed in n boxes, then for each 0 ≤ m ≤ n there exist m boxes with a total of at most mk + max(0,s+m-n) objects
I guess these last ones are based on the maximum pigeons being more than the average "For a non-empty, finite bag of numbers, the maximum value is at least the average value"?
Let's say we got 3 dozens and 3 pigeonholes to put them in. The maximum number of dozens/pigeons is 3, so the average is 2. The maximum is always greater than the average + 1?
Pigeons crap where they want, when they want. They don't care about your rules.
Quote from: Steve on Aug 23, 06:48 AM 2017
Pigeons crap where they want, when they want. They don't care about your rules.
Correct, Dick Dastardly never managed it
Lol i love mugsly's laugh