another math problem (help!)

GuestGuest Member
edited July 2011 in Thought Required
This was in my hw the other day and I was wondering if anyone could help...

I need to write a proof, and idk how to even start :(

4. Let x_1, x_2, . . . , x_19 be positive integers each of which is less than or equal to 93. Let y_1, y_2, . . . , y_93 be positive integers each of which is less than or equal to 19. Prove that there exists a (nonempty) sum of some x_i’s equal to a sum of some y_j’s.

Comments

  • PatashuPatashu Simfiler
    edited July 2011
    I suspect the answer has something to do with modulus arithmetic but beyond that I don't have a clue. It seems as if trying to generate a counterexample (e.g. all xs 93, all ys 19, adjust 93s until no multiple of 19 adds up to any of them) leads you into a trap whereby adding them in order won't work but out of order there's always some way to do it, some residue that is forced to be assembled
Sign In or Register to comment.