Loading [MathJax]/jax/output/SVG/jax.js

Международная олимпиада 2023, Чиба, Япония, 2023 год


Пусть n1 натуральное число. Японский треугольник состоит из 1+2++n одинаковых кругов, выложенных в форме равностороннего треугольника так, что для каждого i=1,2,,n ряд с номером i состоит ровно из i кругов, в точности один из которых покрашен в красный цвет. Путем ниндзя в японском треугольнике называется последовательность из n кругов, построенная следующим образом: начинаем с круга в ряде 1 в затем поочередно спускаемся вниз, переходя от круга к одному из двух кругов непосредственно под ним, пока не дойдем до ряда n. Ниже приведен пример японского треугольника для n=6, а также пути ниндзя, содержащего два красных круга. Найдите наибольшее число k (зависящее от n) такое, что в любом японском треугольнике существует путь ниндзя, содержащий хотя бы k красных кругов.

посмотреть в олимпиаде

Комментарий/решение:

пред. Правка 3   10
11 месяца 19 дней назад #

  0
1 года 3 месяца назад #

Красивое решение

  0
1 года 4 месяца назад #

Уважаемый бекжан

Ваши утверждение полностью неверны и не обоснованны

Например не факт что в любом японсеом триугольнике найдется красный круг под номер лог2 n+1

И вы утверждаете что аналогично можно построить нужный нам японский триугольник хотя это не так. Ваша идея не как не влияет на построение

  0
1 года 3 месяца назад #

Согл

  1
5 месяца 3 дней назад #

Коммент:

Думал ответ [n+12]- но он не правильный, вот и заблудился. Правильный ответ [log2(n)+1]. Нужно было внимательнее оценить n=1,2,...,10, оттуда у меня выходят две идеи помогающие решить задачу.

Решение:

К каждому кругу С отметим число - наибольшее количество красных кругов из всех путей ниндзя проходящие вершину и С. (!) Тогда любое число не меньше предыдущих чисел в любом пути. Пример японского треугольника с числами:

1

21

222

2223

(!!) Докажем что для n=2t1 можем покрасить треугольник так что числа в крайнем нижнем ряду равны t. Базовый пример для n=1, 3, очевидны. n=7:

1

12

222

2223

22333

233333

3333333

Если верно для n=2t1, докажем для n=2t+11.

Выделим треугольник со стороной 2t1 из вершины, его можно покрасить чтобы ряд 2t1 чисел равен 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, сумма чисел в крайнем нижнем ряду не меньше t2t+1. Базовый пример n=1,2 дают 1,3.

Докажем для n=2t+1:

slsmsr

...

SlslSm1sm...Sm2t+1smSrsr

Отметим наибольшее число smt+1 в ряду из 2t чисел, а sl и sr- суммы подряд идущих чисел слева и справа в том же ряду. Временно стерем красные круги и оценим сумму крайнего нижнего ряда.

В ряду из 2t+1 чисел существует ровно 2t+1 подряд идущих чисел для которых проходит путь ниндзя проходящий sm. Отметим их как Sm, а Sl и Sr- суммы подряд идущих чисел слева и справа в том же ряду. (sl,Sl) и (sr,Sr) можно разбить на лево и право наклоняющеся пути ниндзя соответственно. По (!), Smsm, Slsl, Srsr. Сумма чисел крайнего ряда тогда не меньше:

Sl+Sm1+...+Sm2t+1+Sr(sl+sm+sr)+2tsm(t2t+1)+2t(t+1)=t2t+1+2t+1

Теперь оценим как красные круги влиют на сумму чисел крайнего ряда. Разобьем нижние 2t рядов на лево наклоняющеся диагоналей. Если в диагонале m красных кругов то к сумме крайних нижних чисел добавляется m. Так как всего красных кругов в этих диагоналях 2tб то сумма крайних нижних чисел хотя бы:

(t2t+1+2t+1)+2t=(t+1)2t+1+1

Получаем из (!!),(!!!) что для n=2t,...,2t+11:

t+1kt+1

Из чего k=[log2(n)]+1.

  0
1 месяца 28 дней назад #

Ну по моему это легкая задача которую можно решит с одим взглядом и заполучить халявных баллов чтобы вознаграждатся на олимпиаде.

Ответ:нельзя

Решение:разложим 2024 на простые делители.выйдет 2*2*2*11*23.у нас в общем 6 столбцов и строка вместе.каждая клетка является множителем для 2 строк и столбов(1строка и 1 столб).Значит у нас три числа которые делятся на 23.если взять их минимальными то выйдут числа 23;46,92.но при этом в строке или столбце где стоит число 92 будет число делящеесе на 11 а это хотя бы 11.96+11=107.А это уже больше чем 100.