Тема Иннополис (Innopolis Open)

Алгебраические текстовые задачи на Иннополисе

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела иннополис (innopolis open)

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#90011

Петя и Вася разыгрывают призовой фонд, содержащий перед началом игры натуральное число $M$ фунтиков. (Мы не знаем, что такое фунтики, но фунтики бесконечно делимы, например можно «отмерить» $√ - 1∕ 2$ фунтиков). Петя знает секретное (целое) число фунтиков $N$ (из диапазона $0≤ N ≤M$ ), которое ему нужно для поездки в Иннополис, а Вася должен угадать это число $N$ .

Игра состоит из раундов «Васина догадка - Петин ответ», которые продолжаются, пока Вася не назовет число $N$ или пока не опустеет призовой фонд. В каждом раунде Вася называет целое число $k$ (из диапазона $0≤ k≤ M$ ) и

- если $k <N$ , то Петя говорит об этом Васе, после чего игроки просто переходят к следующему раунду;

- если $k >N$ , то Петя говорит об этом Васе, забирает из фонда $M ∕3$ фунтиков, и если в фонде еще остались фунтики, то игроки переходят к следующему раунду;

- если $k =N$ , то Петя говорит об этом Васе, затем Вася получает из фонда $(x− n)$ фунтиков, где $x$ - количество фунтиков в фонде на данный момент, а $n$ - количество сыгранных раундов. Если $x ≤n$ , то Вася получит 0 фунтиков.

Какое наибольшее число фунтиков может гарантировать себе Вася?

Источники: Иннополис - 2024 (см. dovuz.innopolis.university)

Показать ответ и решение

Очевидно, что Васе нужна стратегия, в которой он не более двух раз “проваливается”, то есть называет число, большее задуманного Петей $N$ (так как после третьего "провала"весь фонд уходит Пете). Сначала предложим стратегию, позволяющую Васе гарантированно получить указанное количество фунтиков, а потом докажем, что это максимальное количество, которое он может гарантировать.

Стратегия Васи с одним “провалом”: пусть $y(y+1) n= {y| 2 ≥M }$ (т.е. наименьшее натуральное $n$ , при котором $n(n+1) 2 ≥ M$ ). Шаги до “провала”: Вася называет числа $k1 =n,k2 = n+ (n − 1),k3 =n +(n− 1)+(n− 2),...,$ пока Петя не скажет, что для очередного $km +1 =n +(n− 1)+...+(n− m)> N$ (первый "провал") или что угадано число $N.$ Сумма арифметической прогрессии $n(n+1) --2-- ≥M ≥N,$ а значит, такой момент обязательно наступит. Если это в момент первого "провала то в этот момент Петя получает из фонда $M -3$ фунтиков, в фонде остаётся $2M 3--$ фунтиков, а Вася приступает к выполнению шагов до "угадал".

Шаги до “угадал”: Вася называет (не более чем $(m − 1)$ последовательные числа от $(km +1)$ до $N$ (которое меньше $km + 1$ ) до тех пор, пока Петя не скажет, что задуманное число угадано, а Вася, сыграв $n= (m + 1)+ (n− (m − 1))$ раундов, получает из фонда $(2M3-− n)$ фунтиков.

Докажем, что такая стратегия оптимальна. Пусть существует стратегия для Васи, позволяющая гарантированно получить больше фунтиков. Эта стратегия предписывает возрастающую последовательность чисел $k1 <k2 < ...<kt,$ где $t<n$ и $ki+ 1< ki+(n− i)$ для любого $1≤ i< t.$ Но так как $n= min{y|y(y2+1) ≥M },$ то $kt < M,$ а значит, остались непроверенные числа от $(kt+ 1)$ до $M,$ и такая стратегия не может гарантированно улучшить результат.

Ответ:

$2M-− min{y|y(y+1)≥ M } 3 2$

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 2#94952

Дан клетчатый прямоугольник $2m ×2n$ , разбитый произвольным образом на доминошки $2× 1$ .

Если две доминошки образуют квадрат $2× 2$ , разрешается повернуть их обе на $∘ 90$ (сделать флип). Наша цель — последовательностью флипов сделать все доминошки горизонтальными (кирпичная кладка) за как можно меньшее количество операций.

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

Пусть нам дано некоторое замощение прямоугольника доминошками, которое мы обозначим через T. Сопоставим замощению его функцию высоты — это будет функция на вершинах клеток нашего прямоугольника, которую мы будем обозначать $HT (v)$ .

Определим её следующим образом. Выберем левую нижнюю вершину $v0$ прямоугольника и положим ее высоту равной нулю; далее, каждую вершину $v$ соединим с $v0$ путем, который проходит по линиям сетки и не пересекает доминошек. Этот путь состоит из стрелок, каждая из которых проходится либо в попутном направлении (т. е. сонаправлена с путем), либо в противоположном. Положим высоту $HT(v)$ равной разности числа попутных и противоположно направленных стрелок.

Назовем кирпичной кладкой разбиение $Tmin$ , в котором все доминошки горизонтальны. Назовем приведенной высотой разбиения $T$ величину

| | hT(v)= |HT(v)− HTmin(v)|. 4

Назовём рангом замощения $T$ число $r(T)=∑v hT(v)$ . Докажите, что любое замощение $T$ можно превратить в кирпичную кладку за $r(T)$ флипов, причём за меньшее количество флипов это сделать невозможно.

Источники: Иннополис - 2021, 11.3 (см. dovuz.innopolis.university)

Показать доказательство

Утверждение. Функция высоты $H T$ задаёт разбиение единственным образом.

_________________________________________________________________________________________________________________________________________________________________________________

Доказательство. Покажем, что для любых соседних вершин $u$ и $v,$ ребро между которыми направлено от $u$ к $v,$ либо $HT (v)= HT(v)+1,$ либо $HT (v)= HT(u)− 3$ . Действительно, первый случай реализуется, когда стрелка от от $u$ к $v$ — это стрелка на границе доминошки, а второй случай сотвествует тому, что это стрелка, которая разделяет доминошку на две половинки.

Рассмотрим те рёбра, разность функций высоты на концах которых равна $1$ . Эти рёбра будут образовывать границы доминошек нашего разбиения; напротив, те ребра, разность функций высоты на концах которых равна $− 3$ , будут «закрыты» доминошками. Далее рассмотрим какую-нибудь клетку. Все стрелки на её границе направлены в одном направлении: либо по часовой стрелке, либо против. Поскольку сумма приращений функции высоты при обходе этой клетки равна нулю, это значит, что существует ровно три ребра из четырех, для которых разность значений функции высоты на их концах равна единице, и одно ребро, для которого эта разность равна минус трём; оно и будет закрыто доминошкой. То же самое можно будет сказать и про клетку, смежную с данной по этому ребру. Тем самым все клетки окажутся разбитыми на пары, то есть в итоге из функции высоты действительно однозначно получится замощение нашего прямоугольника.

_________________________________________________________________________________________________________________________________________________________________________________

Будем вести индукцию по величине $r(T)$ .

Если $r(T)= 0$ , доказывать нечего, т.к. тогда $HT = HTmin$ , и, согласно утверждению выше, $T = Tmin$ . В противном случае рассмотрим в замощении $T$ функцию $|HT |$ , пусть $v1$ — вершина, в которой эта функция достигает глобального максимума (если таких вершин несколько, выберем любую из них). Заметим, что в этой вершине можно сделать флип. Действительно, рассмотрим квадрат $2× 2$ , центром которого является вершина $v1$ . Тогда или горизонтальные, или вертикальные ребра, выходящее из $v1$ , должны быть закрыты доминошками разбиения $T$ (если из вершины $v1$ выходит и горизонтальное, и вертикальное ребра, то, сдвинувшись по одному из них, можно увеличить значение $|HT (v1)|$ , что невозможно, т.к. $v1$ — точка максимума). Значит, квадрат $2× 2$ действительно разбит на две доминошки, и флип возможен.

Сделаем флип с центром в этой точке. Данный флип уменьшит приведеную высоту вершины $v1$ на $1,$ а высоты остальных вершин оставит без изменений. Так мы получим новое замощение $T′$ , для которого $r(T′) =r(T)− 1$ . Применяя предположение индукции, получаем требуемое.

Курсы

Всё необходимое для достижения цели

Интенсивы

Глубокий разбор тем, требующих дополнительного внимания

Предыдущий раздел

Следующий раздел