Главное меню

Новости:

SMF - Just Installed!

Как решить задачу: В ряд стоят 35 школьников?

Автор Jinovad, Март 14, 2024, 14:11

« назад - далее »

Jinovad

В ряд стоят 35 школьников (все они смотрят в одну сторону). Каждый из них посчитал сумму количества мальчиков слева от него и количество девочек справа от него. Среди получившихся 35 чисел ровно 5 встретились нечётное число раз. Найдите сумму этих 5 чисел.

Aril

Решим данную задачу графически.
Рассмотрим сначала ряд школьников. И посмотрим как могут меняться суммы при переходе от одного к другому. Для упорядоченности будем двигаться слева на право.
Итак берем произвольного школьника. У него слева будет m - мальчиков, а справа d - девочек. В сумме получим (m+d). А теперь посмотрим, как меняется сумма при переходе к следующему ученику. Возможны всего 4 варианта расположения рядом (M; M); (M; Д); (Д; М); (Д; Д)
Два мальчика подряд (М; М) (Сумма увеличится на 1)
Для мальчика слева сумма (m+d), а для следующего мальчика справа количество девочек не поменялась - осталась d, а количество мальчиков увеличилось на 1. Для мальчика справа сумма будет (m+1+d). То есть вся сумма увеличилась на 1
Аналогично можно понять, что мальчик и девочка (М; Д) суммы будут одинаковы.
Так как количество девочек справа уменьшится на 1, а количество мальчиков слева увеличится и сумма станет (m+1 + d-1) = (m+d)
Так же для девочка -> мальчик (Д; М) сумма не изменится. В этом случае количество девочек справа и количество мальчиков слева не меняется.
А в случае Девочка -> Девочка (Д; Д) Сумма уменьшится на 1, Так как девочек станет (d-1), а слева мальчиков не изменится m
Рассмотрим теперь зависимость (функцию) суммы от значения последовательности детей и исследуем её.
Когда пол школьника не меняется, то функция суммы возрастает (при мальчиках) или убывает (при девочках)
При смене пола рядом стоящих детей значение функции не меняется.
Для наглядности нарисуем произвольный график.
И сделаем следующие заключения.
1) Рассмотрим сначала только значения Сумм на участках возрастания и убывания функции. Если таких участков чётное количество, то и этих сумм будет четное количество.
При этом заметим, что в этом случае возрастание было, когда аргумент Мальчик, а убывание, когда аргумент Девочка. То есть в этих случаях при чётных суммах количество Мальчиков и Девочек одинаково.
2) Теперь рассмотрим значения сумм на участках где оно не меняется. Количество сумм будет чётным, когда аргументов будет чётно, а с условием чередования мальчиков и девочек так же получим равное количество мальчиков и девочек.
3) Теперь рассмотрим комбинацию из нечетного количества точек значений сумм идущих подряд. Значит этот ряд начинается и заканчивается одним и тем же полом ребенка. Например, если стационарные суммы начались с девочки, то до этого функция убывала и закончится девочкой, значит продолжит убывать. И чтоб получить чётное число сумм, функция снова должна возрастать в это значение, а это возможно в точке мальчик. Снова получаем, что при чётном количестве мальчиков и девочек поровну. Аналогично, если стационарный участок начнется с мальчика и закончится мальчиком.
Таким образом при всех возможных случаях четных количеств сумм - мальчиков и девочек будет поровну.
Теперь рассмотрим нечётное количество. Если оно не равно 1, то разложим его на чётное и 1. Чётное количество даст равенство мальчиков и девочек, а одна уникальная сумма означает, что там функция возрастает или убывает.
Причем заметим, что при следующей нечётной сумме функция должна продолжить возрастать, если она возрастала на предыдущей сумме или убывать если убывала на предыдущей сумме.
Таким образом 5 нечётных сум означают, что есть пять участков, где функция строго возрастает 5 раз или строго убывает 5 раз, а остальные значения чётное количество и дают равенство девочек и мальчиков.
Возрастание 5 уникальных раз даёт на 5 больше мальчиков чем девочек, то есть 20 мальчиков и 15 девочек
Аналогично: убывание даст 20 девочек и 15 мальчиков.
Рассмотрим решение с возрастанием.
Пусть ряд начинается с мальчика, как рассмотрели выше функция суммы может сколь угодно гулять, но в конечном итоге от этого значения она пойдет в возрастание, то есть в ряду этих значений сумм будет нечётно.
Тогда считаем его. У этого мальчика справа 15 девочек, а слева никого. Сумма 15
Следующие 4 суммы будут на 1 больше. Получим 15 + 16 + 17 + 18 + 19 = 85
Если ряд начнется с девочки, то функция уйдет в возрастание после мальчика. А это означает, что значение этих сумм будет чётно и её учитывать не надо. значение этой суммы  : 14 девочек справа и слева никого, равно 14. Тогда нужны следующие 5 сумм с разницей в 1.
Снова 15 + 16 + 17 + 18 + 19 = 85
Для убывания с девочками аьсолютно симметрично и аналогично
Ответ: 85