Подскажите решение задачи

[ragdoll]

С коллегами решали школьную задачу, не решили
Может быть, кто-то подскажет правильное решение?

Условие такое:
По кругу в случайном порядке расставляют целые числа от 1 до 13.
При любой случайной комбинации чисел всегда найдутся три стоящих рядом числа, сумма которых в данной комбинации минимальна.
Найти максимально возможную минимальную сумму таких чисел.

[Финик]

исправлюсь

[ragdoll]

1: Финик пишет:
> шесть

внимательно читаем последнюю строчку условия.

[Финик]

исправился)

[vwb3]

16?

[ragdoll]

4: vwb3 пишет:
> 16?

я не знаю.

[Fat]

15=1+2+12 ?

[kodin]

1) Поскольку среднее в ряду от 1 до 13 будет 7, то среднее значение сумм соседних трех чисел будет 7*3=21. Следовательно, максимальное из минимальных сумм не может превышать 21.
2) Можно разбить численный ряд на три сектора: [1,2,3,4], [5,6,7,8,9], [10,11,12,13]. Искомым будет ряд, где суммы трех соседних чисел будут примерно равны. Поэтому необходимо ставить рядом числа в следующем примерном порядке: с левого края ряда, из центра ряда, с правого края ряда. Например, 1, 7, 13, 2, 8, 12... При этом нужно следить, чтобы сумма соседних трех чисел была бы максимально приближена к 21. Легко убедиться, что подобных вариантов будет немного.
3) Перебрав подобные варианты, можно показать, что 21 и 20 добиться нельзя. Во всяком случае у меня не получилось. А вот 19 уже получается из такой цепочки: 1,6,12,2,7,11,3,8,9,4,10,5,13.
Можно ли "в лоб" решить такую задачу - не знаю.

[TJ]

Стандартная задача на поиск минимаксных и максиминных значений. Но хоть убейте, не вспомню, как это решать Наверное это будет так: Ищем все возможные варианты. Максимсальное значение - 11+12+13=36. Его отбрасываем, как максимальное, и получится что это - 11+12+13-1=35 - максимальное из минимальных...

[ragdoll]

7: kodin пишет:
> 1) Поскольку среднее в ряду от 1 до 13 будет 7, то среднее значение сумм соседних трех чисел будет 7*3=21. Следовательно,
> максимальное из минимальных сумм не может превышать 21.
> 2) Можно разбить численный ряд на три сектора: [1,2,3,4], [5,6,7,8,9], [10,11,12,13]. Искомым будет ряд, где суммы трех соседних чисел
> будут примерно равны. Поэтому необходимо ставить рядом числа в следующем примерном порядке: с левого края ряда,
> из центра ряда, с правого края ряда. Например, 1, 7, 13, 2, 8, 12... При этом нужно следить, чтобы сумма соседних трех чисел
> была бы максимально приближена к 21. Легко убедиться, что подобных вариантов будет немного.

До этого места понятно.

> 3) Перебрав подобные варианты, можно показать, что 21 и 20 добиться нельзя.

Почему же нельзя, ведь первые же три числа из приведенного вами ряда дают 21...

> А вот 19 уже получается из такой цепочки: 1,6,12,2,7,11,3,8,9,4,10,5,13.
> Можно ли "в лоб" решить такую задачу - не знаю.

P.S. спасибо за ответ в личку.

[BadBlock]

8: TJ:

Ну и при каком же варианте 35 будет минимальной суммой на круге?

[GT3]

Эта задачка из математической олимпиады для 5 класса, сегодня итоги будут подведены.

[kodin]

9: ragdoll пишет:

>> 3) Перебрав подобные варианты, можно показать, что 21 и 20 добиться нельзя.
>
> Почему же нельзя, ведь первые же три числа из приведенного вами ряда дают 21...
А дальше-то? Там все время оказываются рядом 4, 5, 6 - никак их не разобьешь. "Большие" числа уже заканчиваются до этого.

[kodin]

11: pilon пишет:
> Эта задачка из математической олимпиады для 5 класса, сегодня итоги будут подведены.
Для 5 класса круто, конечно. Это какого уровня? Областная, городская?
Вообще на многих олимпиадных задачах метод перебора так или иначе присутствует. Важно его свести к минимуму.

[GT3]

13: kodin пишет:
> 11: pilon пишет:
>> Эта задачка из математической олимпиады для 5 класса, сегодня итоги будут подведены.
> Для 5 класса круто, конечно. Это какого уровня? Областная, городская?
> Вообще на многих олимпиадных задачах метод перебора так или иначе присутствует. Важно его свести к минимуму.
У меня сын в 5 классе учится в 15 школе, им задали поучаствовать. Олимпиаду проводит ФизТех из г. Долгопрудный. Первые 3 места "яблопланшеты". И поверьте эта задача не самая трудная.

[ragdoll]

> А дальше-то? Там все время оказываются рядом 4, 5, 6 - никак их не разобьешь. "Большие" числа уже заканчиваются
> до этого.

Кажется, начинаю понимать.
Итак, мы выяснили, что максимальная минимальная сумма не может превышать 21.
Далее делаем предположение, что сумма может равняться 21, и доказываем, что это предположение неверно, т.к. при любом раскладе найдется сумма других трех чисел, которая меньше 21.
Иными словами, 21 - не минимальная сумма при любом раскладе.
Далее то же самое делаем с суммой, равной 20.
А минимальная сумма, равная 19, уже возможна.

Таким должен быть ход решения?

[kodin]

15: ragdoll пишет:
> Таким должен быть ход решения?
Да.

[kodin]

14: pilon пишет:
> 13: kodin пишет:
>> 11: pilon пишет:
>>> Эта задачка из математической олимпиады для 5 класса, сегодня итоги будут подведены.
>> Для 5 класса круто, конечно. Это какого уровня? Областная, городская?
>> Вообще на многих олимпиадных задачах метод перебора так или иначе присутствует. Важно его свести к минимуму.
> У меня сын в 5 классе учится в 15 школе, им задали поучаствовать. Олимпиаду проводит ФизТех из г. Долгопрудный. Первые
> 3 места "яблопланшеты". И поверьте эта задача не самая трудная.
Если олимпиада удаленная - то нормально. А вот если по времени - то она, конечно, решаемая, но много времени потребуется.

[Bender Rodriguez]

Я вот тут тоже наткнулся на какой-то анекдот-задачку и немного залип. Решение так и не нашёл (правда не особо и старался )

Задачка от Блондинки:
Я у тебя взяла 100 рублей. Пошла в магазин и потеряла их.
Встретила подругу. Взяла у нее 50 рублей. Купила 2 шоколадки по 10.
У меня осталось 30 рублей. Я их отдала тебе. И осталась должна 70. И подруге 50. Итого 120. Плюс у меня 2 шоколадки.
Итого 140!
Где 10 рублей???

[kodin]

18: Bender Rodriguez пишет:
> Я вот тут тоже наткнулся на какой-то анекдот-задачку и немного залип. Решение так и не нашёл (правда не особо и
> старался )
>
> Задачка от Блондинки:
> Я у тебя взяла 100 рублей. Пошла в магазин и потеряла их.
> Встретила подругу. Взяла у нее 50 рублей. Купила 2 шоколадки по 10.
> У меня осталось 30 рублей. Я их отдала тебе. И осталась должна 70. И подруге 50. Итого 120. Плюс у меня 2 шоколадки.
> Итого 140!
> Где 10 рублей???
Популярная задача в интернете. Суммирование проводится неправильно. Где-то тоже встречал пояснение, что это типичная ошибка начинающих бухгалтеров, как-то так
По факту: долг 70+50 = 120. И 30 уже отдала. Итого: 150.
Потратила: 100 потеряла и на 20 купила шоколадки. Осталось 30, которые и вернула.
А в рассуждениях блондинки долг и траты смешаны между собой.

[SladkaYA_N]

если из круга исключить 13, то получится четыре тройки чисел, сумма чисел в каждой из которых не меньше минимальной, обозначим ее за x. следовательно, сумма всех чисел не меньше 4x + 13. с другой стороны, она составляет 1+2+3+...+13=13*14/2=13*7
следовательно 4x <= 13*6
x <= 39/2 = 19.5. Поскольку x - целое число, то x<=19
Всё. Никакие переборы не нужны

[ragdoll]

20: SladkaYA_N пишет:
> если из круга исключить 13, то получится четыре тройки чисел, сумма чисел в каждой из которых не меньше минимальной,
> обозначим ее за x. следовательно, сумма всех чисел не меньше 4x + 13. с другой стороны, она составляет 1+2+3+...+13=13*14/2=13*7
>
> следовательно 4x <= 13*6
> x <= 39/2 = 19.5. Поскольку x - целое число, то x<=19
> Всё. Никакие переборы не нужны

Как-то не очевидно. Если ничего не исключать, а просто нарисовать задачу на бумаге, то легко можно убедиться, что троек совсем не 4, а 13. Каждое число участвует в трех разных тройках одновременно.
Тогда, следуя Вашей логике, принимая за х минимальную сумму, получаем:
13х<3*(1+2+...+13), х<21, следовательно искомое значение 20.

[kodin]

20: SladkaYA_N пишет:
> если из круга исключить 13, то получится четыре тройки чисел, сумма чисел в каждой из которых не меньше минимальной,
> обозначим ее за x. следовательно, сумма всех чисел не меньше 4x + 13. с другой стороны, она составляет 1+2+3+...+13=13*14/2=13*7
>
> следовательно 4x <= 13*6
> x <= 39/2 = 19.5. Поскольку x - целое число, то x<=19
> Всё. Никакие переборы не нужны
Я тоже сначала пошел по подобному пути. Но смутило, что чисел 13, а не 12 и на тройки просто так не разобьешь. Почему 13 в данном решении исключается просто так - непонятно.
Кроме того, х здесь всего-навсего среднее арифметическое среди чисел от 1 до 12. Дальше надо еще доказать, что именно 19 максимальное из минимальных для троек от 1 до 12. И мы приходим к алгоритму, который я опять описал.

[SladkaYA_N]

21: ragdoll пишет:
> Как-то не очевидно. Если ничего не исключать, а просто нарисовать задачу на бумаге, то легко можно убедиться, что
> троек совсем не 4, а 13. Каждое число участвует в трех разных тройках одновременно.
> Тогда, следуя Вашей логике, принимая за х минимальную сумму, получаем:
> 13х<3*(1+2+...+13), х<21, следовательно искомое значение 20.


Непересекающихся троек

[SladkaYA_N]

Ваше решение сложнее. 13 исключается. Остальные числа разбиваются на непересекающиеся тройки.
22: kodin пишет:
> 20: SladkaYA_N пишет:
>> если из круга исключить 13, то получится четыре тройки чисел, сумма чисел в каждой из которых не меньше минимальной,
>> обозначим ее за x. следовательно, сумма всех чисел не меньше 4x + 13. с другой стороны, она составляет 1+2+3+...+13=13*14/2=13*7
>>
>> следовательно 4x <= 13*6
>> x <= 39/2 = 19.5. Поскольку x - целое число, то x<=19
>> Всё. Никакие переборы не нужны
> Я тоже сначала пошел по подобному пути. Но смутило, что чисел 13, а не 12 и на тройки просто так не разобьешь. Почему
> 13 в данном решении исключается просто так - непонятно.
> Кроме того, х здесь всего-навсего среднее арифметическое среди чисел от 1 до 12. Дальше надо еще доказать, что именно
> 19 максимальное из минимальных для троек от 1 до 12. И мы приходим к алгоритму, который я опять описал.

[ragdoll]

24: SladkaYA_N пишет:
> Ваше решение сложнее. 13 исключается. Остальные числа разбиваются на непересекающиеся тройки.

Я очень благодарен Вам за то, что поучаствовали в решении задачи, но без пояснений Ваше решение принять за правильное не могу. Представьте, что я пятиклассник, и не понимаю:
1. Почему вы исключили именно число 13? Исключите 1, и ответ будет другой.
2. Почему тройки у Вас не пересекаются, вопреки условию?

[Tpaktop]

25: ragdoll пишет:
> 24: SladkaYA_N пишет:
>> Ваше решение сложнее. 13 исключается. Остальные числа разбиваются на непересекающиеся тройки.
>
> Я очень благодарен Вам за то, что поучаствовали в решении задачи, но без пояснений Ваше решение принять за правильное
> не могу. Представьте, что я пятиклассник, и не понимаю:
> 1. Почему вы исключили именно число 13? Исключите 1, и ответ будет другой.
> 2. Почему тройки у Вас не пересекаются, вопреки условию?

это называется метод от противного. рассуждения такие
1) пусть минимальная сумма любой тройки больше либо равна 20
2) исключим самое большое число - 13, а остальные числа разобьём на не пересекающиеся тройки. получится 4 тройки
3) по предположению сумма чисел в каждой такой тройке больше либо равна 20, а общая сумма больше либо равна 4*20+13=93
4) но сумма 1+2+3+...+13=13*7=91, что меньше, чем 93
5) получили противоречие, значит минимальная сумма любой тройки не может быть больше 19
6) 19 получается перебором

[BadBlock]

26: Tpaktop:

Тройки-то почему не пересекаются?

[ragdoll]

> это называется метод от противного. рассуждения такие

Ну с некоторой натяжкой можно считать что да, метод от противного используется. Проехали.

> 1) пусть минимальная сумма любой тройки больше либо равна 20

Пока всё понятно.

> 2) исключим самое большое число - 13, а остальные числа разобьём на не пересекающиеся тройки. получится 4 тройки

А вот здесь уже ничего не понятно. Почему Вы исключаете самое большое число, для чего? Что при этом пролисходит? Поймите, мы решаем не конкретную задачу, а пытаемся понять, как решаются такие задачи вообще. Если бы в условии были числа от 1 до 12, какое бы число вы убрали? Никакое? Потому что 12 на тройки и так прекрасно разбивается? А елсли бы было от 1 до 14, вы бы убрали не одно число, а два?

И почему бы не убрать самое маленькое число? И будет у вас 4*20+1=81.
Или среднее 7, тогда 4*20+7=87

Про тройки. Почему они не пересекаются - так и нет ответа.

P.S. Пусть максимальная минимальная сумма меньше 20. Уберем все числа кроме 1, 8, 10. Тогда 1+8+10=19. Ура.
Ну, вы поняли.

[.yepp59.]

предложу свой вариант.
пусть у нас есть 5 групп чисел: 4 "ячейки" по 3 числа и 1 "ячейка" - 1 число.
к примеру, {4}{1,11,6}{7,8,9}{2,13,10}{12,3,5}, на самом деле без разницы какие числа в этих самых "ячейках", важна сумма каждой ячейки.
сумма ряда 1..13 = 91.
разделим ее на 5 ячеек = 91/5=18,2
получаем следующую картину относительно сумм ячеек: {18,2}{18,2}{18,2}{18,2}{18,2}
в одной из ячеек у нас всего одна цифра, т.е. сумма этой ячейки не может превышать наибольшего числа из ряда.
Тут два варианта: {1} и {13}, когда в качестве обособленного числа будут крайние числа ряда.
1) {13}. Если в ячейке с один числом будет 13, то, чтобы "уравновесить" общую (неизменную ни при каких условиях) сумму всего ряда,вычтем из полученной средней суммы ячеек 18,2 сумму ячейки с одним числом и поделим поровну между остальными 4мя.
То есть, 18,2-13=5,2
5,2/4=1,3
18,2+1,3=19,5
Получаем вот такую картину (это по суммам ячеек): {13}{19,5}{19,5}{19,5}{19,5}
чтобы сумма в ячейке была минимальной среди подобных в данном случае, округляем вниз.
получаем в первом случае 19.
2) {1}. аналогично рассмотрим случай, когда в ячейке с один числом будет число 1.
18,2-1=17,2
17,2/4=4,3
18,2+4,3=22,5
получаем в ячейках по суммам: {1}{22,5}{22,5}{22,5}{22,5}
округляем и получаем минимальную из троек сумму в данном случае - 22.
Из 19 и 22 максимальное - 22.
как то так