Interesting Math Problem

Правка en1, от HereToDisappoint, 2017-11-02 11:30:48

Recently I encountered the following problem in the recruitment test for IBM research.

There is an array of size K with elements from 1 to N and an array of size N with elements from 1 to K. Prove that there exists a sub-array of the first array and a sub-array of the second array with the same sum.

I was thinking of applying pigeonhole principle using difference of prefix sums but could not get anything concrete. Any ideas about how to prove this ?

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский HereToDisappoint 2017-11-02 11:30:48 484 Initial revision (published)