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 қызыл дөңгелегі бар ниндзя жолы болатындай ең үлкен k санын (n-ға байланысты) табыңыз.

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

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

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

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

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

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

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

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

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

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

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

Согл

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

Коммент:

Думал ответ [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 месяца 26 дней назад #

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

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

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