Дано 2007 целых чисел. Докажите, что из них можно выбрать два, разность которых делится на 2000
Answers & Comments
Удачник66
Из 2007 чисел можно составить 2007*2006/2=2013021 пар. При делении разности на 2000 можно получить 2000 разных остатков, от 0 до 1999. Если мы получили остаток 0, то задача решена - разность двух чисел делится на 2000. Если мы получили две пары (a1;b1) и (a2;b2) с одинаковыми остатками, то можно составить перекрестные пары (a1;a2); (a1;b2); (a2;b1); (a2;b2). Скорее всего, одна из них даст остаток 0. Если ни одна не даст, можно попробовать другие две пары. Пар в 1000 раз больше, чем различных остатков, наверняка где-то получится.
1 votes Thanks 4
Удачник66
Слегка ошибся с парами. Должно быть так: (a1;a2); (a1;b2); (b1;a2); (b1;b2)
Answers & Comments
При делении разности на 2000 можно получить 2000 разных остатков, от 0 до 1999.
Если мы получили остаток 0, то задача решена - разность двух чисел делится на 2000.
Если мы получили две пары (a1;b1) и (a2;b2) с одинаковыми остатками, то можно составить перекрестные пары (a1;a2); (a1;b2); (a2;b1); (a2;b2).
Скорее всего, одна из них даст остаток 0.
Если ни одна не даст, можно попробовать другие две пары.
Пар в 1000 раз больше, чем различных остатков, наверняка где-то получится.