HereToDisappoint's blog

Interesting Math Problem
By HereToDisappoint, history, 6 years ago, In English

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 ?

  • Vote: I like it
  • +39
  • Vote: I do not like it

»
6 years ago, # |
← Rev. 2   Vote: I like it -38 Vote: I do not like it

both of them have a sub-array of sum 1

EDIT: just removed an annoyingly large image

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    There isn't every element presented neccesarily. If N=2, K=5, then arrays can be e.g. {2,2,2,2,2} and {3,5}.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      oh

      in my defense it wasn't very clearly stated... though I should've figured :face_palm:

      → Reply
»
6 years ago, # |
  Vote: I like it +37 Vote: I do not like it

Nice problem. It is quite not straightforward, so no shame if you can't solve it. Not going to burn the IBM interview question though, because it is hard to find nice problems like this. Usually interviewers give hints for such hard problems or don't expect the candidate to fully solve it, looking at approaches the candidate tries to use.

→ Reply
»
6 years ago, # |
  Vote: I like it +15 Vote: I do not like it

http://codeforces.com/contest/618/problem/F

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you. Such clever uses of the pigeonhole principle never fail to amaze me.

    → Reply