Sum of 4 integers divisible by 4.

[caffeinemachine]

1) Given $n$ integers. What is the minimum value of $n$ so that one can always choose $4$ integers from these $n$ integers such that the summation of the chosen $4$ integers is divisible by $4$.

Using the Pigeon hole principle I was able to prove that $n \leq 9$. Then by computation (mostly) I arrived at the result that $n=7$.
The only counter examples I could find for $n=6$ are: $\{2,2,2,3,3,3 \}$, $\{0,0,0,1,1,1\}$, $\{0,0,0,3,3,3\}$, $\{1,1,1,2,2,2\}$. (I have taken integers mod $4$). I am pretty sure these are the only counter examples for $n=6$

2) DEFINITION: An element $(a,b) \in \mathbb{Z} \times \mathbb{Z}$ is said to be divisible by $4$ if $4|a$ and $4|b$. Summation of two elements $(a_1,b_1), (a_2,b_2) \in \mathbb{Z} \times \mathbb{Z}$ is simply $(a_1+b_1,a_2+b_2)$.
QUESTION: Given $n$ elements from $\mathbb{Z} \times \mathbb{Z}$. What is the minimum value of $n$ such that one can always choose $4$ elements from these $n$ elements such that summation of then chosen $4$ elements is divisible by $4$.

Using the result from (1) and using the pigeon hole principle we easily get 25 as an upper bound on the value of $n$. I am pretty sure this is not the minimum value of $n$. Can someone bring down the upper bound or find the minimum value of $n$ (that would be great).

 

[PaulRS]

My idea for the first part is pretty brute-forcish too, we try to consturct a set of 7 such that the assertion fails:

First we note that since we have 7 elements and 4 remainders, some module must appear twice, but then:

• Having $\{0,0\}$ or $\{2,2\}$ implies we can't have 1 and 3 at the same time.
• Having $\{1,1\}$ or $\{3,3\}$ implies we can't have 0 and 2 at the same time.

In any case, we end up using up to 3 remainders, and so there must be one that appears at least 3 times. Suppose we had $\{a,a,a\}$ , the of course we can't choose $a$ again, and in fact $\{a,a\}$ sums up to either 0 or 2. (all sums will be in module 4)

• If $a+a = 2$ (i.e. $a = 1 \text{ or }3$) then we can't choose both $0$ and $2$ at the same time (that'd lead to $\{0,2,a,a\}$ which sums 0). This implies that the rest is made up of 0's and $(4-a)$ ' s or 2's and $(4-a)$ ' s . In the former case, since no number can appear 4 times (we can't fill the remaining 4 entries with all 0's or all (4-a)'s ), we must contain $\{0,0,a,4-a\}$ or $\{a,a,4-a,4-a\}$ , both sum 0. Similarly in the latter case $\{2,2,a,4-a\}$ and $\{a,a,4-a,4-a\}$ both sum 0.
• If $a+a = 0$ (i.e. $ a = 0 \text{ or } 2$) then we can't choose both $1$ and $3$ at the same time. This implies that the rest is made up of either 1's and $(a+2)$ ' s or 3's and $(a+2)$ 's. In the former case we look at $\{a,1,1,a+2\}$ or $\{a, a,a+2,a+2 \}$ (depending on which appears twice), and in the latter $\{a,3,3,a+2\}$ or $\{a,a,a+2,a+2\}$.

As for the second question... it looks quite messy (Wondering), I will see if I can come back to it later.

UPDATE: Counter-example for $N = 12$ : $\{( 0 , 0 ), ( 0 , 0 ), ( 0 , 0 ), ( 1 , 2 ), ( 1 , 2 ), ( 1 , 2 ), ( 2 , 3 ), ( 2 , 3 ), ( 2 , 3 ), ( 3 , 3 ), ( 3 , 3 ), ( 3 , 3 )\}$. Currently I suspect that the minimum value is $N = 13$ .

 

[caffeinemachine]

My idea for the first part is pretty brute-forcish too, we try to consturct a set of 7 such that the assertion fails:

First we note that since we have 7 elements and 4 remainders, some module must appear twice, but then:

• Having $\{0,0\}$ or $\{2,2\}$ implies we can't have 1 and 3 at the same time.
• Having $\{1,1\}$ or $\{3,3\}$ implies we can't have 0 and 2 at the same time.

In any case, we end up using up to 3 remainders, and so there must be one that appears at least 3 times. Suppose we had $\{a,a,a\}$ , the of course we can't choose $a$ again, and in fact $\{a,a\}$ sums up to either 0 or 2. (all sums will be in module 4)

• If $a+a = 2$ (i.e. $a = 1 \text{ or }3$) then we can't choose both $0$ and $2$ at the same time (that'd lead to $\{0,2,a,a\}$ which sums 0). This implies that the rest is made up of 0's and $(4-a)$ ' s or 2's and $(4-a)$ ' s . In the former case, since no number can appear 4 times (we can't fill the remaining 4 entries with all 0's or all (4-a)'s ), we must contain $\{0,0,a,4-a\}$ or $\{a,a,4-a,4-a\}$ , both sum 0. Similarly in the latter case $\{2,2,a,4-a\}$ and $\{a,a,4-a,4-a\}$ both sum 0.
• If $a+a = 0$ (i.e. $ a = 0 \text{ or } 2$) then we can't choose both $1$ and $3$ at the same time. This implies that the rest is made up of either 1's and $(a+2)$ ' s or 3's and $(a+2)$ 's. In the former case we look at $\{a,1,1,a+2\}$ or $\{a, a,a+2,a+2 \}$ (depending on which appears twice), and in the latter $\{a,3,3,a+2\}$ or $\{a,a,a+2,a+2\}$.

As for the second question... it looks quite messy (Wondering), I will see if I can come back to it later.

I also did pretty much the same thing you have done. Thanks for taking interest in this. The result of the second one (rather the technique to arrive at it) is kinda important to me. I will post it if I make any progress.

 

[caffeinemachine]

My idea for the first part is pretty brute-forcish too, we try to consturct a set of 7 such that the assertion fails:

First we note that since we have 7 elements and 4 remainders, some module must appear twice, but then:

• Having $\{0,0\}$ or $\{2,2\}$ implies we can't have 1 and 3 at the same time.
• Having $\{1,1\}$ or $\{3,3\}$ implies we can't have 0 and 2 at the same time.

In any case, we end up using up to 3 remainders, and so there must be one that appears at least 3 times. Suppose we had $\{a,a,a\}$ , the of course we can't choose $a$ again, and in fact $\{a,a\}$ sums up to either 0 or 2. (all sums will be in module 4)

• If $a+a = 2$ (i.e. $a = 1 \text{ or }3$) then we can't choose both $0$ and $2$ at the same time (that'd lead to $\{0,2,a,a\}$ which sums 0). This implies that the rest is made up of 0's and $(4-a)$ ' s or 2's and $(4-a)$ ' s . In the former case, since no number can appear 4 times (we can't fill the remaining 4 entries with all 0's or all (4-a)'s ), we must contain $\{0,0,a,4-a\}$ or $\{a,a,4-a,4-a\}$ , both sum 0. Similarly in the latter case $\{2,2,a,4-a\}$ and $\{a,a,4-a,4-a\}$ both sum 0.
• If $a+a = 0$ (i.e. $ a = 0 \text{ or } 2$) then we can't choose both $1$ and $3$ at the same time. This implies that the rest is made up of either 1's and $(a+2)$ ' s or 3's and $(a+2)$ 's. In the former case we look at $\{a,1,1,a+2\}$ or $\{a, a,a+2,a+2 \}$ (depending on which appears twice), and in the latter $\{a,3,3,a+2\}$ or $\{a,a,a+2,a+2\}$.

As for the second question... it looks quite messy (Wondering), I will see if I can come back to it later.

UPDATE: Counter-example for $N = 12$ : $\{( 0 , 0 ), ( 0 , 0 ), ( 0 , 0 ), ( 1 , 2 ), ( 1 , 2 ), ( 1 , 2 ), ( 2 , 3 ), ( 2 , 3 ), ( 2 , 3 ), ( 3 , 3 ), ( 3 , 3 ), ( 3 , 3 )\}$. Currently I suspect that the minimum value is $N = 13$ .

Thank you Paul. I will try to counter N=13. today I have 8 class hours. Plenty of time to work on this ;)

 

[caffeinemachine]

Progress:

Out of 23 elements from $\mathbb{Z}_4 \times \mathbb{Z}_4$ one can always choose $4$ elements such that their sum is divisible by $4$. I will post the proof in a few hours. Its kinda difficult to explain here.
So as of now the best upper bound we have is $22$.

 

[caffeinemachine]

UPDATE:

One can always choose 4 elements out of 13 DISTINCT elements from $\mathbb{Z}_4 \times \mathbb{Z}_4$ such that the sum of these 4 elements is divisible by 4.

Proof: There are 16 elements in $\mathbb{Z}_4 \times \mathbb{Z}_4$. Group them into 4 groups as:
$ \{ (0,0),(0,2),(2,0),(2,2) \}, \{ (0,1),(0,3),(1,1),(3,3) \}, \{ (1,2),(3,2),(1,3),(3,1) \} , \{ (2,1),(2,3),(1,0),(3,0) \}$.
Note that each group has 4 elements and sum of elements in each group is divisible by 4

Choosing 13 distict elements from $\mathbb{Z}_4 \times \mathbb{Z}_4$ is as good as kicking out 3 elements. Since there are 4 groups and one is kicking out 3 elements, there will be one group all of whose elements will be selected. The sum of these 4 will be divisible by 4.

So this suggests that the required answer is 13 or not too far away from 13.

 

[Opalg]

Let $S$ be a collection of 13 elements from $\mathbb{Z}_4 \times \mathbb{Z}_4$ such that no subset of four elements has sum $(0,0)$ (all addition being mod 4). caffeinemachine has shown that the elements of $S$ cannot all be distinct. So $S$ must contain some element, $(a,b)$ say, at least twice. Let $S' = \{(x-a,y-b): (x,y)\in S\}$. Then the sum of any four elements of $S'$ is the same (mod 4) as the sum of the four corresponding elements of $S$. Replacing $S$ by $S'$, we may therefore assume that the element $(0,0)$ occurs at least twice in $S$.

Arrange the elements of $\mathbb{Z}_4 \times \mathbb{Z}_4$ in a table like this:
$$\begin{array}{cccc}(0,0)&\color{red}{(0,2)} & \color{blue}{(2,0)} & \color{green}{(2,2)} \\ &\color{red}{(0,1)\ (0,3)} & \color{blue}{(1,0)\ (3,0)} & \color{green}{(1,1)\ (3,3)} \\ &\color{red}{(2,1)\ (2,3)} & \color{blue}{(1,2)\ (3,2)} & \color{green}{(1,3)\ (3,1)} \end{array}$$

Notice that each element in the middle and bottom rows of the table, when added to itself, gives the element of the same colour on the top row.

In $S$, the black element (0,0) occurs at least twice, but not more than three times (because the sum of four copies of it would add up to (0,0)). So there must be at least ten coloured elements in $S$. By the pigeonhole principle, at least four of them must be the same colour, say red. Therefore (pigeonhole again) some row of the table must contain at least two red elements of $S$. The element (0,2) cannot occur twice in $S$ (because (0,2)+(0,2)+(0,0)+(0,0) = (0,0)). Also, $S$ cannot contain both of the distinct red elements in the same row. If for example it contained (0,1) and (0,3), then we would have (0,1)+(0,3)+(0,0)+(0,0) = (0,0). So it must contain some red element at least twice. But then it cannot contain (0,2) at all. (If, for example, it contained (0,1) twice, and also (0,2), then we would have (0,1)+(0,1)+(0,2)+(0,0)=(0,0).)

Next, $S$ cannot contain two copies of a red element from the middle row of the table and also two copies of a red element from the bottom row of the table (the sum of those four elements would be (0,0)). So the only way for $S$ to contain four red elements is for it to contain three copies of an element from one of the bottom two rows, and one copy of an element from the other of those rows. The sum of those two distinct elements is then an element of another colour. For example, if $S$ contains three copies of (0,1) and one copy of (2,3) then we would have (0,1)+(2,3)=(2,0). That means that we cannot have any other pair of elements of $S$ whose sum is the blue element (2,0). This puts a very severe limit on the number of blue elements that $S$ can contain. In fact, the only way that $S$ can contain more than one blue element is if it contains one blue element from the middle row and one blue element from the bottom row. But the sum of those two elements is either (0,0) or the green element (2,2). That in turn limits the number of green elements that are possible, making it impossible for there to be as many as 10 coloured elements altogether.

It's hard to give a concise watertight argument for this, but the conclusion is that $S$ cannot contain four elements of the same colour. Thus the largest set $S$ satisfying the condition that no four of its elements should sum to (0,0) will consist of 12 elements (three copies each of an element of each of the four colours black, red, blue, green).

 

[caffeinemachine]

Let $S$ be a collection of 13 elements from $\mathbb{Z}_4 \times \mathbb{Z}_4$ such that no subset of four elements has sum $(0,0)$ (all addition being mod 4). caffeinemachine has shown that the elements of $S$ cannot all be distinct. So $S$ must contain some element, $(a,b)$ say, at least twice. Let $S' = \{(x-a,y-b): (x,y)\in S\}$. Then the sum of any four elements of $S'$ is the same (mod 4) as the sum of the four corresponding elements of $S$. Replacing $S$ by $S'$, we may therefore assume that the element $(0,0)$ occurs at least twice in $S$.

Arrange the elements of $\mathbb{Z}_4 \times \mathbb{Z}_4$ in a table like this:
$$\begin{array}{cccc}(0,0)&\color{red}{(0,2)} & \color{blue}{(2,0)} & \color{green}{(2,2)} \\ &\color{red}{(0,1)\ (0,3)} & \color{blue}{(1,0)\ (3,0)} & \color{green}{(1,1)\ (3,3)} \\ &\color{red}{(2,1)\ (2,3)} & \color{blue}{(1,2)\ (3,2)} & \color{green}{(1,3)\ (3,1)} \end{array}$$

Notice that each element in the middle and bottom rows of the table, when added to itself, gives the element of the same colour on the top row.

In $S$, the black element (0,0) occurs at least twice, but not more than three times (because the sum of four copies of it would add up to (0,0)). So there must be at least ten coloured elements in $S$. By the pigeonhole principle, at least four of them must be the same colour, say red. Therefore (pigeonhole again) some row of the table must contain at least two red elements of $S$. The element (0,2) cannot occur twice in $S$ (because (0,2)+(0,2)+(0,0)+(0,0) = (0,0)). Also, $S$ cannot contain both of the distinct red elements in the same row. If for example it contained (0,1) and (0,3), then we would have (0,1)+(0,3)+(0,0)+(0,0) = (0,0). So it must contain some red element at least twice. But then it cannot contain (0,2) at all. (If, for example, it contained (0,1) twice, and also (0,2), then we would have (0,1)+(0,1)+(0,2)+(0,0)=(0,0).)

Next, $S$ cannot contain two copies of a red element from the middle row of the table and also two copies of a red element from the bottom row of the table (the sum of those four elements would be (0,0)). So the only way for $S$ to contain four red elements is for it to contain three copies of an element from one of the bottom two rows, and one copy of an element from the other of those rows. The sum of those two distinct elements is then an element of another colour. For example, if $S$ contains three copies of (0,1) and one copy of (2,3) then we would have (0,1)+(2,3)=(2,0). That means that we cannot have any other pair of elements of $S$ whose sum is the blue element (2,0). This puts a very severe limit on the number of blue elements that $S$ can contain. In fact, the only way that $S$ can contain more than one blue element is if it contains one blue element from the middle row and one blue element from the bottom row. But the sum of those two elements is either (0,0) or the green element (2,2). That in turn limits the number of green elements that are possible, making it impossible for there to be as many as 10 coloured elements altogether.

It's hard to give a concise watertight argument for this, but the conclusion is that $S$ cannot contain four elements of the same colour. Thus the largest set $S$ satisfying the condition that no four of its elements should sum to (0,0) will consist of 12 elements (three copies each of an element of each of the four colours black, red, blue, green).

Thank you Opalg. I have been trying to solve this for more than two weeks and it seems there is no way to arrive at a general result. My goal was to do what we are doing for $\mathbb{Z}_4 \times \mathbb{Z}_4 \times \mathbb{Z}_4 \times \mathbb{Z}_4 $. I was actually trying to solve a version of 1985 IMO problem. But it gets so cumbersome even for $\mathbb{Z}_4 \times \mathbb{Z}_4$. Seems like a research problem in itself.

 

[Opalg]

My goal was to do what we are doing for $\mathbb{Z}_4 \times \mathbb{Z}_4 \times \mathbb{Z}_4 \times \mathbb{Z}_4 $.

So the problem now is:

QUESTION: Given $n$ elements from $\mathbb{Z} \times \mathbb{Z} \times \mathbb{Z} \times \mathbb{Z}$. What is the minimum value of $n$ such that one can always choose $4$ elements from these $n$ elements such that the sum of the chosen $4$ elements is divisible by $4$?

It seems clear from the results for $\mathbb{Z}$ and $\mathbb{Z} \times \mathbb{Z}$ that the answer should be $n=49$. A counterexample for $n=48$ would be to take three copies of each of the sixteen elements $(x_1,x_2,x_3,x_4)$, where each $x_i$ can be 0 or 1. If you are going to find a proof for that, then I guess you would first need to find a simpler and more conceptual way to prove the result for $\mathbb{Z} \times \mathbb{Z}$.

 

[caffeinemachine]

So the problem now is:

QUESTION: Given $n$ elements from $\mathbb{Z} \times \mathbb{Z} \times \mathbb{Z} \times \mathbb{Z}$. What is the minimum value of $n$ such that one can always choose $4$ elements from these $n$ elements such that the sum of the chosen $4$ elements is divisible by $4$?

It seems clear from the results for $\mathbb{Z}$ and $\mathbb{Z} \times \mathbb{Z}$ that the answer should be $n=49$. A counterexample for $n=48$ would be to take three copies of each of the sixteen elements $(x_1,x_2,x_3,x_4)$, where each $x_i$ can be 0 or 1. If you are going to find a proof for that, then I guess you would first need to find a simpler and more conceptual way to prove the result for $\mathbb{Z} \times \mathbb{Z}$.

The original question was:
Given 100 integers. None of these 100 integers has a prime factor greater than 7. Prove that there are 4 integers among these such that their product is a fourth power.

Isn't this equivalent to:
Given $n$ elements from $ \mathbb{Z} \times \mathbb{Z} \times \mathbb{Z} \times \mathbb{Z}$. Let $k$ be the minimum value of $n$ such that one can always choose $4$ elements from these $n$ elements such that the sum of these $4$ elements is divisible by $4$ . Prove that $ k \leq 100 $.

Since the question gives us 100 elements to choose from I don't think 49 is the minimum value, although it may very well be.​