Finite set $A$ has such property: every six its distinct elements’ sum isn’t divisible by $6$. Does there exist such set $A$ consisting of $11$ distinct natural numbers?
Problem
Source:
Tags: number theory proposed, number theory
20.04.2014 18:54
No, there is no such set $A$. This is a simple consequence of Erdos-Ginzburg-Zif Theorem: From any $2n-1$ integers, one can find exactly $n$ of them, such that their sum is divisible by $n$.
30.03.2016 18:23
I'm very sorry to revive this thread. I wonder if there is any elegant way to tackle this problem without using Erdos-Ginzburg-Zif Theorem, just considering this case with n=6 (suppose I haven't heard of the theorem before, but I still need to solve the problem during the contest)?
30.03.2016 23:54
It is easy to prove case $n=3$. Among 5 numbers always there are 3 numbers, such that their sum is divisible by 3. Get some 5 numbers from $A$. There are 3 numbers, such that their sum is divisible by 3. From another 8 numbers we can again get 5 numbers. There are again such 3 numbers. Now we have 5 numbers, we repeat operation. Now we have 3 sums of 3 distinct natural numbers,. every sum is divisible by 3. There are two sums with same remainder. So we can get these sums. These 6 numbers are all distinct and their sum is divisible by 6.