Тема Иннополис (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)

Подсказки к задаче

Подсказка 1

Давайте подумаем, какому условию должна удовлетворять стратегия Васи, иначе говоря, когда он ну точно не получит наибольшее вероятное количество фунтиков?

Подсказка 2

Если он 3 раза назовет число, большее N, то весь фонд уйдёт Пете. Можем сначала подобрать стратегию для Васи, а потом попробовать доказать, что она гарантирует наибольшее возможное количество фунтиков. Давайте рассматривать стратегии Васи с определёнными количествами "провалов" (когда Вася называет число k > N).

Подсказка 3

Давайте рассмотрим наименьшее число n, при котором n(n + 1)/2 ≥ M, и подумаем, какие шаги оптимально делать Васе до первого "провала".

Подсказка 4

Пусть Вася будет называть числа k₁ = n, k₂ = n + (n - 1), ... , kₘ₊₁ = n + (n - 1) + ... + (n - m), пока не угадает число N или не превзойдет его. Попробуйте придумать стратегию, при которой Вася будет совершать не более одного "провала".

Подсказка 5

Если Вася попадает в число N, то игра заканчивается. Иначе после провала он перейдет к угадыванию. Вася будет называть последовательные числа от kₘ₊₁ до N (в случае провала, N будет меньше kₘ₊₁). Сколько тогда фунтиков обеспечит себе Вася?

Подсказка 6

До kₘ₊₁ - (m + 1) раунд, до угадывания — не более (m +1) раунда, тогда Вася сыграет (m + 1) + (n - (m + 1)) раундов и получит (2M/3 - n) фунтиков. Надо теперь доказать, что эта стратегия оптимальна. Предположите для начала, что существует стратегия, при которой Вася может получить больше фунтиков.

Подсказка 7

Эта стратегия будет предписывать возрастающую последовательность чисел k₁ < k₂ < ... < kₜ, где t < n. Какое еще условие на k можно наложить через n? Попробуйте доказать через определение n, что такая стратегия не даст нам гарантированно больше фунтиков.

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

Очевидно, что Васе нужна стратегия, в которой он не более двух раз “проваливается”, то есть называет число, большее задуманного Петей $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#124050

Во время собеседования при приеме на работу в разных IT-компаниях любят задавать разные тестовые нестандартные задачи для проверки творческих способностей кандидата на работу. Одна из таких популярных тестовых задач следующая (см. рисунок):

$PIC$

Точки $A$ и $B$ двигаются на встречу друг-другу (обычно говорят о двух «путниках») со скоростями $a$ и $b$ соответственно, а между ними все время «летает» со скоростью $v (v >a$ и $v >b)$ еще одна точка (обычно говорят о «мухе», которая летает с носа одного путника на нос другого путника без задержек на носу ни одного из путников). Начальное расстояние между точками $A$ и $B$ равно $S.$ Вопрос: какое расстояние пролетит точка-муха от момента начала движения точек-путников до момента их встречи?

Так вот, в этой задаче вам сначала надо ответить на вопрос, сформулированный в тестовой задаче: какое расстояние пролетит точка-муха от момента начала движения точек-путников до момента их встречи? Далее, вам надо ответить на следующий вопрос (и доказать ответ!): конечное или бесконечное число полетов между точкам-путниками совершит точка-муха от момента начала движения до момента встречи точек-путников?

И, наконец, вам надо ответить на еще один вопрос. Пусть в начальный момент точка-муха находилась в точке $A.$ Какое суммарное расстояние пролетит точка-муха, когда движется от $A$ до $B?$ А какое суммарное расстояние пролетит точка-муха, когда движется от $B$ до $A?$

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

Подсказки к задаче

Вопрос 1, подсказка 1

Сначала можно вычислить время, которое будет летать точка-муха, а потом уже найти расстояние.

Вопрос 2, подсказка 1

Предположим, что точка-муха совершила конечное число полетов, тогда мы либо докажем это, либо получим противоречие.

Вопрос 2, подсказка 2

Попробуйте рассмотреть последний полет точки-мухи.

Вопрос 2, подсказка 3

Пусть последний полет был от точки А. Какие будут скорости у точки А и у точки-мухи?

Вопрос 2, подсказка 4

У точки-мухи будет скорость v, у точки А — a. Какая из этих точек прилетит раньше в точку встречи точек-путников?

Вопрос 2, подсказка 5

Сравните скорости a и v, опираясь на условие, и проведите аналогичные рассуждения в случае, если последний полет точки-мухи происходит от точки B.

Вопрос 3, подсказка 1

Давайте попробуем составить формулы расстояний перелетов в общем виде. Для этого можно посчитать расстояния в конкретных ситуациях.

Вопрос 3, подсказка 2

В некоторый момент времени точка-муха находится в точке А, пусть в этот момент расстояние между A и B равно p₀. Через какое время точка-муха окажется в точке B?

Вопрос 3, подсказка 3

t₁ = p₀ / (v + b). Какое расстояние при этом пролетит точка-муха?

Вопрос 3, подсказка 4

w₁ = t₁v = p₀v / (v + b). Чему будет равно расстояние между точками A и B после полета?

Вопрос 3, подсказка 5

p₁ = p₀ - t₁(a + b) = p₀ ⋅ (v - a) / (v + b). Через какое время точка-муха вновь окажется в точке А?

Вопрос 3, подсказка 6

t₂ = p₁ / (v + a) = p₀ ⋅ (v - a) / ((v + a)⋅(v + b)). Какое расстояние она пролетит от B к A?

Вопрос 3, подсказка 7

w₂ = t₂v = p₀ ⋅ (v - a) ⋅ v / ((v + a)⋅(v + b)). Какое расстояние между точками A и B после этого?

Вопрос 3, подсказка 8

p₂ = p₁ - t₂(a + b) = p₀ ⋅ (v - a)(v - b) / ((v + a)(v + b)). Посмотрите на полученные результаты и попробуйте записать в общем виде формулы для расстояний между точками A и B до и после k-го перелета.

Вопрос 3, подсказка 9

Теперь вспомним, что мы хотим найти. Запишите формулы для расстояний, которые будет пролетать точка-муха.

Вопрос 3, подсказка 10

Рассмотрим случай, когда точка-муха летит от A к B. Заметьте, что расстояния, которые будет пролетать точка-муха, образуют бесконечно убывающую геометрическую прогрессию.

Вопрос 3, подсказка 11

Ее суммой и будет суммарное расстоние, которое пролетит точка-муха от A до B. Чтобы найти суммарное расстояние, которое пролетит точка-муха от B к A, для начала посчитайте общее расстояние, которое пролетит точка-муха.

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

Первый вопрос.

Общее время движения точек-путников

S t= a+-b,

поэтому расстояние, которое пролетит точка-муха за это время

l= vt= aS+vb

Второй вопрос.

Давайте предположим, что точка-муха совершит некоторое конечное число полетов между точками-путниками. Тогда либо мы докажем это, либо прийдем к противоречию и получим, что полетов было бесконечное количество.

Рассмотрим последний полет точки-мухи между точками-путниками. Если это был полет от точки $A,$ движущейся направо со скоростью $a,$ то, так как это был последний полет, точка-муха тоже летит направо со скоростью $v$ и прилетает в точку встречи точек-путников не раньше точки $A,$ то есть скорость точки-мухи $v,$ которая не больше скорости $a.$

Получаем противоречие с тем, что $v > a.$ Аналогично получаем противоречие в случае, если последний полет точки-мухи происходит от точки $B.$ Следовательно, предположение о конечном числе полетов неверно.

Третий вопрос.

Пусть в некоторый момент времени точка-муха находится в точке $A$ и в это время расстояние между точками $A$ и $B$ равно $p0 >0.$ Тогда точка-муха окажется в точке $B$ спустя время

-p0- t1 = v+ b,

при этом точка-муха пролетит расстояние

w1 =t1v = p0v v+ b

в направлении от $A$ к $B,$ а расстояние между точками $A$ и $B$ после полета будет равно

p1 = p0− t1(a+b)= p0− p0(a+-b)= p0(v−-a)= p0⋅ v−-a v+ b v +b v+ b

Точка-муха вновь окажется в точке $A$ спустя время

-p1- -p0(v-− a)- t2 = v+ a = (v+ a)(v+ b)

Она пролетит в направлении от $B$ к $A$

w2 =t2v =-p0(v−-a)v- (v +a)(v +b)

После этого расстояние между точками $A$ и $B$ будет равно

p0(v−-a) p0(v−-a)(a+-b)- p0(v−-a)(v−-b)- (v−-a)(v−-b) p2 =p1− t2(a+ b)= v+ b − (v+ a)(v+ b) = (v+ a)(v+ b) =p0⋅(v+ a)(v+ b)

Следовательно, для любого $k≥ 1$ мы имеем: расстояние между точками $A$ и $B$ после $k- ого$ перелета

от $A$ до $B$ равно
$( ) S ⋅ v− a-⋅ (v−-a)(v− b) k−1 v+b (v+ a)(v+b)$
от $B$ до $A$ равно
$( ) S⋅ (v−-a)(v−-b) k (v+ a)(v+ b)$

Теперь заметим, что для любого $k ≥ 1$ расстояние между точками перед $k-ым$ перелетом

от $A$ до $B$ равно
$((v− a)(v− b))k−1 S⋅ (v+-a)(v+-b)$
от $B$ до $A$ равно
$v− a ((v−-a)(v− b))k−1 S ⋅v− b ⋅ (v+ a)(v+b)$

Тогда для любого $k≥ 1$ расстояние, которое пролетит точка-муха в $k-ый$ раз,

от $A$ до $B$ равно
$( )k− 1 W2k−1 = S⋅-v-⋅ (v−-a)(v−-b) v+ b (v+ a)(v+ b)$
от $B$ до $A$ равно
$( )k−1 W2k = S ⋅-v-⋅ v−-a⋅ (v−-a)(v−-b) v+b v+ a (v+ a)(v+ b)$