На недавней олимпиаде мы давали детям такую задачу: "Числитель и знаменатель дроби – натуральные числа, сумма которых не превосходит 101 , а сама дробь меньше 1/3. Какое наибольшее значение может иметь такая дробь?"

Ответ нашли многие, но вот доказать, что он оптимальный смогли не все. Более того, участникам казалось, что оптимальность найденного ими решения очевидна.

Предлагаю участникам форума

  1. Решить эту задачу.
  2. Предложить такую ее модификацию, при которой "очевидное" решение будет неверным (по аналогии с парадоксами целочисленного линейного программирования).

Дополнение. К п.2 предлагаю более парадоксальное сочетание констант, чем у @sunny. Пусть $%m+n\le 46, m/n<3/4$%, тогда наибольшей будет дробь 17/23, хотя сумма 17 + 23 равна только 40. "Угловое" решение (т.е. ближайшее к обеим прямым, задающим ограничения) есть 19/26, что является только 4 по величине из исследуемых дробей.

задан 13 Апр '12 1:21

изменен 16 Апр '12 22:15

То, что 19/26 неоптимально, можно увидеть сразу: медианта дробей 19/26 и 3/4 равна 11/15, то есть получается не простым суммированием числителей и знаменателей, а еще и сокращением на 2. Ясно, что 11/15 ближе к 3/4, чем 19/26. А дальше, продолжая выполнять операцию "медианта", последовательно получаем 14/19, 17/23, 20/27 и т.д. - и выбираем наибольшую из таких, у которых числитель+знаменатель $%\le 46$%. В принципе, этот несложный алгоритм должен всегда давать правильный ответ, хотя доказательство, которое я знаю, использует цепные дроби и потому совсем неочевидно.

(13 Июл '15 13:39) knop
10|600 символов нужно символов осталось
0

25/76

Усложнение: например, сумма не превосходит 102 или 103. Или 100. Тогда очевидное становится неправильным (то есть нужная пара не равна заданному условию). Таких чисел каждое 3 из 4х для границы в 1/3.

Решал (каюсь) перебором значений в Excel.

ссылка

отвечен 16 Апр '12 8:09

  1. Ответ верный. Доказать можно, сравнив эту дробь в произвольной m/n. Главная идея - если целое число больше 0, то он не меньше 1. Это дает значительное усиление неравенства.
  2. Неплохо, но ответ в этом случае тот же? Хотелось бы найти совсем неожиданный ответ. Пожалуй, воспользуюсь-ка и я Excel.
(16 Апр '12 13:58) DocentI
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×756
×103

задан
13 Апр '12 1:21

показан
829 раз

обновлен
13 Июл '15 13:39

Отслеживать вопрос

по почте:

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

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru