Международная олимпиада 2023, Чиба, Япония, 2023 год
Комментарий/решение:
Уважаемый бекжан
Ваши утверждение полностью неверны и не обоснованны
Например не факт что в любом японсеом триугольнике найдется красный круг под номер лог2 n+1
И вы утверждаете что аналогично можно построить нужный нам японский триугольник хотя это не так. Ваша идея не как не влияет на построение
Коммент:
Думал ответ [n+12]- но он не правильный, вот и заблудился. Правильный ответ [log2(n)+1]. Нужно было внимательнее оценить n=1,2,...,10, оттуда у меня выходят две идеи помогающие решить задачу.
Решение:
К каждому кругу С отметим число - наибольшее количество красных кругов из всех путей ниндзя проходящие вершину и С. (!) Тогда любое число не меньше предыдущих чисел в любом пути. Пример японского треугольника с числами:
1
21
222
2223
(!!) Докажем что для n=2t−1 можем покрасить треугольник так что числа в крайнем нижнем ряду равны t. Базовый пример для n=1, 3, очевидны. n=7:
1
12
222
2223
22333
233333
3333333
Если верно для n=2t−1, докажем для n=2t+1−1.
Выделим треугольник со стороной 2t−1 из вершины, его можно покрасить чтобы ряд 2t−1 чисел равен t. Для i-ого ряда снизу красим i-ый круг слева в красный. Эти красные круги попарно не имеют общий путь ниндзя, а любой путь проходит через ряд из чисел t и множество красных кругов ниже ровно один раз, из чего крайние нижние числа равны t+1.
t...t
t...tt+1
t...t+1t+1t+1
t...t+1t+1t+1t+1t+1
t+1t+1t+1...t+1t+1t+1
(!!!) Докажем что для n=2t, сумма чисел в крайнем нижнем ряду не меньше t⋅2t+1. Базовый пример n=1,2 дают 1,3.
Докажем для n=2t+1:
slsmsr
...
Sl≥slSm1≥sm...Sm2t+1≥smSr≥sr
Отметим наибольшее число sm≥t+1 в ряду из 2t чисел, а sl и sr- суммы подряд идущих чисел слева и справа в том же ряду. Временно стерем красные круги и оценим сумму крайнего нижнего ряда.
В ряду из 2t+1 чисел существует ровно 2t+1 подряд идущих чисел для которых проходит путь ниндзя проходящий sm. Отметим их как Sm, а Sl и Sr- суммы подряд идущих чисел слева и справа в том же ряду. (sl,Sl) и (sr,Sr) можно разбить на лево и право наклоняющеся пути ниндзя соответственно. По (!), Sm≥sm, Sl≥sl, Sr≥sr. Сумма чисел крайнего ряда тогда не меньше:
Sl+Sm1+...+Sm2t+1+Sr≥(sl+sm+sr)+2t⋅sm≥(t⋅2t+1)+2t⋅(t+1)=t⋅2t+1+2t+1
Теперь оценим как красные круги влиют на сумму чисел крайнего ряда. Разобьем нижние 2t рядов на лево наклоняющеся диагоналей. Если в диагонале m красных кругов то к сумме крайних нижних чисел добавляется m. Так как всего красных кругов в этих диагоналях 2tб то сумма крайних нижних чисел хотя бы:
(t⋅2t+1+2t+1)+2t=(t+1)⋅2t+1+1
Получаем из (!!),(!!!) что для n=2t,...,2t+1−1:
t+1≤k≤t+1
Из чего k=[log2(n)]+1.
Ну по моему это легкая задача которую можно решит с одим взглядом и заполучить халявных баллов чтобы вознаграждатся на олимпиаде.
Ответ:нельзя
Решение:разложим 2024 на простые делители.выйдет 2*2*2*11*23.у нас в общем 6 столбцов и строка вместе.каждая клетка является множителем для 2 строк и столбов(1строка и 1 столб).Значит у нас три числа которые делятся на 23.если взять их минимальными то выйдут числа 23;46,92.но при этом в строке или столбце где стоит число 92 будет число делящеесе на 11 а это хотя бы 11.96+11=107.А это уже больше чем 100.
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.