о числах и вычетах (математическое)

Среди любых трех целых чисел найдутся два, сумма которых делится на 2 (четна). Это тривиально.

Среди любых пяти целых чисел найдутся три, сумма которых делится на 3. Это просто доказать - даже в уме - перебором остатков.

Верно ли, что среди любых 2n-1 целых чисел найдутся n, сумма которых делится на n? Это верно, и впервые доказано в статье Эрдеша, Гинзбурга и Зива в 1961-м году.

В этой статье Ноги Алона и Моше Дубинера (англ.) приводится пять разных простых доказательств этой теоремы. "Простых" здесь означает примерно на уровне второго курса университета, а не школьной математики. Рекомендую - красивые (и все краткие) доказательства.

Я перескажу здесь под катом одно из них.

( Read more... )

(via, of all places, Computational Complexity blog)

как бы слова

Интересно, что когда вся русская блогосфера смаковала преведы с креатиффами, четыре и три года назад, этого слова не было. А потом, когда, казалось бы, волна схлынула, оно появилось и стало набирать обороты.

Вот что находит Яндекс в блогах и комментариях и форумах:

2006: кагбэ - 7 / кагбе - 1
2007: кагбэ - 26 / кагбе - 11
2008: кагбэ - 9022 / кагбе - 9036
2009: кагбэ - 36749 / кагбе - 29827

2009 - первый год, в котором кагбэ (в обоих вариантах вместе) обогнала превед по популярности.

(по-хорошему надо взять числа по месяцам и нарисовать график, но мне лень)