Форум умных людей

Пусть у нас есть N иррациональных чисел. Какое максимальное количество рациональных чисел может быть среди их попарных сумм?

Michael, верно. Что любопытно, оставшиеся два ответа я тоже давал, а затем отверг, как ошибочные.

Хорошая задачка, спасибо.

вопрос:
при каком N формулы моя и michael'а дают разные значения?

при N = 3.5  )))

moonlight, пардон, мне показалось, что у тебя [n/2]²

 Сорри, я тоже не заметил что ответы совпадают. :(

вот что бывает, когда пытаешься соригинальничать, а тебя не понимают )))

Решение в студию!

числа - вершины графа
рёбра проводим там, где суммы рациональны
очевидно, что если есть цикл нечётной длины, то все числа цикла - рациональны
чуть менее очевидно, что если циклов нечётной длины нет, то граф двудольный, и существует такой набор иррациональных чисел, а именно: одна доля из чисел равных пи, другая доля - из минус пи
вопрос свёлся к подсчёту максимального количества ребёр в двудольном графе, т.е., на поиск максимума у параболы, которая повёрнута жопой кверху, простите мой французский

Через классы эквивалентности проще, мне кажется.

это как?

хотя забудьте. всё равно всё сведётся к графам

третья доля часть  из чисел равных  корень из 2, четвёртая доля часть из чисел равных  минус корень из 2,
пятая доля часть из чисел равных  корень из 5, шестая доля часть из чисел равных  минус корень из 5
и т.д...
Потом можно показать что если частей две(пи и минус пи), то ребёр(а следовательно рациональных сумм) будет больше.

планировал в скором времени выложить "Рациональное и иррациональное (2)"
но с обобщением как-то туго...

Michael, доля - это не множество вершин из одинаковых чисел
что такое двудольный граф (http://ru.wikipedia.org/wiki/%D0%94%D0%B2%D1%83%D0%B4%D0%BE%D0%BB%D1%8C%D0%BD%D1%8B%D0%B9_%D0%B3%D1%80%D0%B0%D1%84)

В общем, я имел в виду что не обязательно доля состоит из однотипных чисел типа пи, могут быть два и больше типов. Хотя один, конечно, лучше.

   корень из 2           корень из 3            -------------- доля 1
 . . . . . . . . . .        . . . . . . . . . . . .
|||||||||||||||||       ||||||||||||||||||||
 . . . . . . . . . .        . . . . . . . . . . . .
минус корень из 2   минус  корень из 3    -------------- доля 2

Граф на рисунке двудольный, но сказать что


нельзя.
Я не придираюсь к словам как может показаться, просто для моего рисунка получится другой ответ. Доказать что два типа лучше чем четыре легко, но, всё-таки, надо.

этот факт не нуждается в доказательстве
очевидно, что полный двудольный граф содержит больше рёбер, чем неполный

вот более подробное решение
граф - это вершины и рёбра, без чисел на вершинах.
идея: поставим в соответствие нашим иррациональным числам и попарным суммам графы
пусть
А(N) - максимальное количество рациональных попарных сумм
B(N) - максимальное количество рёбер в двудольном графе
доказано:
1) что получатся только двудольные графы, следовательно, А(N) <= B(N)
2) что для произвольного двудольного графа можно подобрать такие иррациональные числа на его вершинах, что соответствующий рациональным попарным суммам граф будет содержать не меньше рёбер, следовательно А(N) >= B(N)
дальше ищем B(N) вместо А(N)

Вообще-то, да.