Pigeonhole principle for dominoes.

Question

Suppose we have 13 dominoes, each with a red and blue integer number. Prove that there is a subset of 4 dominoes such that the sum of the 4 red numbers and the sum of the 4 blue numbers are both multiples of 4.

Answer 1

This is only an idea for now, not a solution:

let R denote the set of remainders when dividing a number by 4, R={0,1,2,3}. Out of any collection of 13 numbers, there must be at least 4 numbers with the same remainder by PHP. Then their sum will be divisible by four since we'll have 4r as the remainder. Now, that takes care of one of the sides(say the red side), but not necessarily the blue side. I think this may be the type of argument to use, but this needs tweaking to cover the blue case.

Answer 2

Idea: All numbers are $0, 1, 2, 3 \mod 4$. Ways we can add up to 4: $(0,0,0,0), (0,0,1,3),(0,0,2,2),(0,1,1,2),(0,3,3,2),(1,1,1,1),(1,1,3,3),(2,2,2,2),(3,3,3,3).$

6 dominoes is the most you can have without having a set from above, $(2,2,2,3,3,3)$. So we need to find at least 7 red number sets.

Because of the pigeon hole principle there has to be at least 3 sets of repeating numbers (like $(0,0,0,0)$) which add up to a multiple of 4. If you have 3 sets of 4 of one number and a number left over (like $(0,0,0,0,1,1,1,1,2,2,2,2,3)$) there must be at least 4 other sets because of the repeating numbers and the fact that you can make multiple sets with them.

If you choose 5 of one number, then there are 5 sets. At least two other sets are easy to find with the repeating numbers. If you choose 6, then you have at least 15 sets already.

Any way the 13 dominoes are numbered there must be at least 7 valid sets of red numbers that can add up to a multiple of 4, so that any selection of blue numbers on the same tiles also has to.

Answer 3

modular arithmetic: remainder mod 4 = 0 , 1 , 2 , 3 - so every integer is essentially one of these.

Notice every combination (with 13 elements) can be rearranged into an abstract form which is the analog of the following: (4 elements and lets say base 5) : {0,1,3,4,4} -> {0,0,4,4,4} .

The criterion for this transformation of the set is that the overall sum (disregarding the modulus) is conserved: i.e 0+1+3+4+4 = 0+0+4+4+4. Now a potential case of (for clarification) the transformed analog for 13 elements in mod 4 could be {0,0,0,0,0,0,0,2,3,3,3,3,3}.

Of importance here is that every combination of remainders can be transformed into such a form (where a set number of elements have been shifted to 0 and another set number to the maximum remainder, with 1 free to be anywhere on the possible remainder values (including 0)). If you don't believe me, try innovating a possible visual representation and notice how you can "push" all values to such ends.

Note: every combination of remainders can be transformed to such a unique set (try it) and the number of possible sets is demonstrably finite (in fact it corresponds to (nk - n + 1) where n is the number of elements in the set and k the number of possible remainders). From this, it follows that every remainder combination corresponds to such a form.

Crucially, it can easily be demonstrated that in such forms, there is always a way to pick four elements such that the remainder is 0. For our case, just pick 4 0s or 4 4s (one of two options will always exist).

Hence, if we can demonstrate that when one element from our set of 4 (with remainder 0) is shifted out, a way remains to recreate our desired 4-element remainder-0 set, by mathematical induction, we will have proved that when given 13 positive integers, there is always a way to pick 4 such that the remainder will be divisible by 4.

This step (I'll leave it to you / ask for more clues if you wan't some) can be found by assuming an abstract case where the desired set has already been found, and play around with what happens when you "shift out" one element from the remainder-0 subset.

Note, the question claims that (more abstractly) when you have 2 sets (in mod 4), both with 13 elements, bijected arbitrary, there is always a way of choosing 2 bijected subsets from the respective 2 sets such that both subsets satisfy the divisibility criterion.

The way to prove this would be to take your proof of the more basic 1 set / 1 sub set problem and demonstrate that the number of subsets satisfying the divisibility is sufficiently high that any arbitrary bijections to a similar set will at least leave behind 1 subset bisected to another subset, where both satisfy the desired criterion. I have to work out the details of how this part would work myself (but I should be able to help nevertheless).

Final note: I imagine there is a much simpler pigeon-hole method where you demonstrate an appropriate property of a smaller subset (lets say with 2 elements) and from that construct the case for 4 elements. But if you can manage the proof form I suggested, then you will be able to abstract the whole darn thing even further and expand the property you are trying to proof for your 13 dominoes into a property true for any n number of dominoes with a subset of k dominoes (divisible by k) (where I presume n is a function of k)!

Cheers!