What is the smallest number of integers needed, such that one is guaranteed to have a subset of three integers whose sum is divisible by three?

Since we are considering divisibility by 3, we need only consider the numbers modulo 3; thus, each integer is equivalent to 0, 1, or 2. Let us now consider the condition which we need for there to be no subset of three whose sum is divisible by three.

Note that if we have at least one of each type, then since 0+1+2=3, we have the desired subset. Thus, we must therefore have at most two of the types. Secondly, if we have three of the same type, then their sum is divisible by three. Thus, we must therefore have at most two of each of these types. This means a set of four integers is the largest that can lack the desired subset; considering the pigeonhole principle, the addition of a fifth integer will give us either three of one type, or one of each type, and thus the desired subset, so our answer is five.

For the general problem of guaranteeing the existence of a subset of *n* integers whose sum is divisible by *n*, one needs a set of at least 2*n*-1 integers (here, 2(3)-1=5).

[Apologies for the delay on this post; there was an issue with the post scheduling which I failed to catch]

### Like this:

Like Loading...

*Related*

Tags: Math, Modular Arithmetic, Monday Math, Pigeonhole Principle

This entry was posted on June 14, 2010 at 12:18 am and is filed under Math/Science. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

## Leave a Reply