|
На недавней олимпиаде мы давали детям такую задачу: "Числитель и знаменатель дроби – натуральные числа, сумма которых не превосходит 101 , а сама дробь меньше 1/3. Какое наибольшее значение может иметь такая дробь?" Ответ нашли многие, но вот доказать, что он оптимальный смогли не все. Более того, участникам казалось, что оптимальность найденного ими решения очевидна. Предлагаю участникам форума
Дополнение. К п.2 предлагаю более парадоксальное сочетание констант, чем у @sunny. Пусть $%m+n\le 46, m/n<3/4$%, тогда наибольшей будет дробь 17/23, хотя сумма 17 + 23 равна только 40. "Угловое" решение (т.е. ближайшее к обеим прямым, задающим ограничения) есть 19/26, что является только 4 по величине из исследуемых дробей. задан 13 Апр '12 1:21 
DocentI |
|
25/76 Усложнение: например, сумма не превосходит 102 или 103. Или 100. Тогда очевидное становится неправильным (то есть нужная пара не равна заданному условию). Таких чисел каждое 3 из 4х для границы в 1/3. Решал (каюсь) перебором значений в Excel. отвечен 16 Апр '12 8:09 
sunny
(16 Апр '12 13:58)
DocentI
|
То, что 19/26 неоптимально, можно увидеть сразу: медианта дробей 19/26 и 3/4 равна 11/15, то есть получается не простым суммированием числителей и знаменателей, а еще и сокращением на 2. Ясно, что 11/15 ближе к 3/4, чем 19/26. А дальше, продолжая выполнять операцию "медианта", последовательно получаем 14/19, 17/23, 20/27 и т.д. - и выбираем наибольшую из таких, у которых числитель+знаменатель $%\le 46$%. В принципе, этот несложный алгоритм должен всегда давать правильный ответ, хотя доказательство, которое я знаю, использует цепные дроби и потому совсем неочевидно.