Monday Math 123

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 2n-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]

Advertisements

Tags: , , ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: