Log In

Divisible by 100

Posted on: July 29th, 2013 by
1

Given any 100 integers, show that one can find a subset of these 100 integers whose sum is divisible by 100.

- via Moscow Math Olympiad


One Response to Divisible by 100

  1. Dinesh had this to say about that:

    Let S_1 = a_1, S_2 = a_1 + a_2 and so on be the partial sums of the numbers given. If all S_i, i=1,\dots,100 leave distinct reminders modulo 100, we are done since 0 should be in there somewhere. If not, there should be two indices i,j such that S_i \equiv S_j mod 100 which means that the subset a_{i+1},\dots,a_j has sum divisible by 100.


{"result":"error", "message":"You can't access this resource as it requires an 'view' access for the website id = 1."}