I'll call you a genius if you solve this problem?

Question

This is an interview question and I could not solve it after breaking my head over it.

Write any 3 numbers. It is always possible to find a subset (of size 1,2 or 3) of ADJACENT numbers among these 3 numbers that add up to a multiple of 3. Why is this so?
Generalizing, write any 'n' numbers. It is always possible to find a subset of adjacent numbers from among them that add up to a multiple of "n". Why is this so? Give proof.

davster I had tried along your lines; it doesn't explain why a subset of ADJACENT numbers have to add up to a multiple.

thomasoa, your answer correctly solves the problem. but I have got another problem now. I keep hitting my head on the wall shouting why I couldn't solve this problem while thomasoa could. Can you tell me how an idiot like me could have recognized this is a pigeonhole problem, and is there any other way of approaching the problem if the person had not studied the pigeonhole principle?

Answer 1

This is a classic pigeonhole principle problem. I might be a genius, but not for knowing this problem :-)

Let a1, a2, ..., an be your numbers.

Let x0 = 0, x1 = a1, x2 = a1+a2, x3=a1+a2+a3, ...
xn = a1+a2+...+an.

Dividing each of the xi by n and taking the remainder, there are only n possible remainders, and n+1 xi's, so two of the xi's have to have the same remainder. But then the difference of the two xi's has to be divisible by n, and that difference is a sum of consecutive members of the sequence.

---- added in response to question

I can't tell you how to know that this is a pigeonhole principle problem, because I happened to know the problem from the past. It is a fairly classic problem. For example, it appears in the book, "Proofs from the Book," which is meant to be a collection of extremely elegant proofs. I happened to be reading it recently, so I remembered it when posting here.

Many years ago, I was asked a problem like this in an interview - I think it was, given a sequence of values, a1, ..., an, of real numbers, write an efficient program to find the largest absolute of the sum of consecutive elements of the series.

Since I knew the pigeonhole problem, above, I realized the same reasoning would apply to this problem, and solved it quickly. Using the same xi, find the smallest and largest xi. Then the difference is the largest absolute value of the sum of consecutive elements of the ai.

Notice, the trick isn't really the pigeonhole principle, it is the idea that the set of values "the sum of consecutive ai's" can be instead represented as differences of xi. That trick is what makes it work.

One reason to consider the problem a pigeonhole principle is to consider that if we have n-1 number, we can't always find a subsequence which adds up to a multiple of n:

1,1,1,1,...,1 [(n-1) times]

does not have a sequence which adds up to a multiple of n. When we have a problem like this, where (n-1) isn't enough to ensure a property, it might be a pigeonhole problem.

Answer 2

Let the numbers be a,b,c . Then the adjacent sums are,

a,b,c,a+b,b+c, and a+b+c and we ask whether 3 divides

abc(a+b)(b+c)(a+b+c) after we assign the values mod3

in any way whatsoever to a,b,and c. These values are

0,1,and 2. Using the 0 works right away for example

c=0 means 3 divides c. If we use all 1's then 3| (a+b+c).

If we use just two ones then we have assignments

1,1,2 and 3| (b+c)

1,2,1 and 3| ((a+c),(b+c)

2,1,1 and 3|(a+b) etc

The easy way is to state: If all three are equal then 3
divides (a+b+c) and if not all three are equal then a 1 and
a 2 can be found adjacent and their sum will be divisible by 3

This looks like a classic and i'm surprised that i haven't
seen it before. Will look at generalising.

Answer 3

Call me genius:

Since the numbers cannot be divisible by 3 they can be represented as X + 1 or X + 2 where X is any number divisible by 3. Adding any two X+1 or X+2 will give an X + 3 which will be divisible by 3. If you use 3 X+2 numbers then all theree will total X + 6 which will be divisible by 3. Likewise if you use three X=! umbers (e.g. 4, 7, 10) then the sum of them will include some number of threes plus 3.

Let me try to restate it matthematically:

Every digit can be expressed as 3 * n + 1 or 3*m + 2 .
You options are
3n+1, 3m+1, 3r+1 = 3 (n+m+r) + 3 = divisible by three
e.g. 4,7,13

3n+2, 3m + 2, 3r + 1 take the last two elements 3m+2 + 3r + 1 = 3(m+r) + 3 = 3(m+r+1)
e.g. 5,8,4

3n+1,3m + 2, 3r + 1 = again first two or last two terms will add up to a multiple of 3 e.g. 4,8,13

3n+2,3m+1,3r+2 - again first or last two will add up to divisible by 3

Finally
3m+2,3n+2,3r+2, add all three to get 3(n+m+r+2) divisible by 3
e.g. 5,14,20

Answer 4

I answer this problem with what I understood the question. I may be wrong.

Let p be any number then three consecutive numbers are [p-1] p and [p+q].

Their sum is 3p. Hence three consecutive numbers when added up will be divisible by 3.


Now let us take n numbers and find their subsets, there will be n such sets each one adding to 3times of the number chosen. Now their sum is n x 3[of the number].

Naturally this is divisible by n.

Being so simple, I know this is not the correct answer.

Answer 5

The product of any three consecutive numbers is always divisible by 3. This can be proved by the method of induction.

Let the three consecutive numbers be "n", "n+1" and "n+2".

Then P(n)= n(n+1)(n+2).
Let us assume that P(n) is divisible by 3,
i.e. n((n+1)(n+2) is divisible by 3 for all values of n.

Now P(n+1) = (n+1)(n+2)(n+3) = n(n+1)(n+2) + 3(n+1)(n+2)
or P(n+1) = P(n) +3(n+1)(n+2) = P(n) + multiple of 3

So if P(n) is divisible by 3 then P(n+1) is also divisible by 3.

Now for n=1, P(n) = n(n+1)(n+2)= 1*2*3 is divisible by 3.
Thus P(n) is divisible by 3 for n=1.
So P(n) is also divisible by 3 for n=2, by induction proved above.
Since P(n) is divisible by 3 for n=2, it also divisible for n=3
and so on.
So P(n) is divisible by 3 for all values of n. Proved.
Now, for n=1

Answer 6

let these three no. are x-1, x, x+1
now add them x-1+x+x+1=3x ; which is multiple of 3. hence the sum of these no. is divisible by 3.

take another ex. of 5 adjacent no. say these are x-2, x-1, x, x+1, x+2.
sum it , it gives 5x, which is also ,multiple of 5.
hence we can generalise it for n numbers also.

Answer 7

Lishyank desires his hed sortin paintings, why not call it Yanklish as a substitute and byology on my own you grants your self a rubber to erase your condominable recommendations-set in the direction of the finer factors of psychological discourse. Hic! Sorry, you basically made me apologise for being excusive, in case you will pardon the pun.

Answer 8

Because you are using THREE numbers, so naturally right at the onset you are dealing with threes. It will always be based on threes.

Answer 9

i understand that you are looking for a genius.

but i think you should get out more often then posting this.

no offense, thought that i should tell ya that you are officially a nerd.

but i know someone will solve that math problem even though you know the answer.

Answer 10

Because you are using THREE numbers, so naturally right at the onset you are dealing with threes. It will always be based on threes.