Сейчас была на очень интересном семинаре. Докладчик (Димитрис Христофидис) для разминки в начале показывал разные трюки с вероятностными доказательствами "невероятностных" теорем. В наших классических курсах ТВ такое обычно иллюстрируют теоремой Вейерштрасса о равномерном приближении непрерывных функций многочленами. От Христофидиса сегодня узнала и про элегантное вероятностное доказательство теоремы Рамсея про "раскраску" вершин полного графа. ИМХО, в чем-то даже более эффектно, чем теорема Вейерштрасса. А вишенкой на торте была классическая олимпиадная задача (1967г), которую мы с ребенком буквально на прошлой неделе по индукции с трудом решили: В комнате стоят весы с двумя чашами, на которых лежат гири. На каждой гире написано имя одного из присутствующих в классе учеников (на гире может быть написано имя только одного ученика, но имен может быть несколько на разных гирях). Известно, что в какой бы последовательности ученики ни заходили в комнату, каждый из них может переложить все гири со своим именем на другую чашу весов так, что после каждого такого действия состояние равновесия весов меняется на противоположное (положение равновесия считается невозможным). Докажите, что весы изначально находились в равновесии (этот пункт варьируется: в классической версии 1967 года спрашивалось, возможно ли такое положение, если изначально весы были не в равновесии). Вероятностный способ — красивый и короткий: Представим, что каждый ученик независимо друг от друга с вероятностью решает: перекладывать свои гири или оставить их на месте. Пусть W — начальная разность весов на чашах. Пусть w_i — суммарный вес всех гирь с именем i-го ученика. Если он совершает действие, разность меняется на -2w_i (если гири на левой чаше) или +2w_i (если на правой). Условие задачи означает, что для любой последовательности заходов итоговый знак разности определяется четностью количества действий. Если рассмотреть математическое ожидание знака разности, выясняется, что оно может быть согласовано с условием только в том случае, если исходный вес равен нулю.