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

Иннополис - задания по годам → .11 Иннополис 2025

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

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

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

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

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

Разделы подтемы Иннополис - задания по годам

Иннополис 2015 и ранее

Иннополис 2016

Иннополис 2017

Иннополис 2018

Иннополис 2019

Иннополис 2020

Иннополис 2021

Иннополис 2022

Иннополис 2023

Иннополис 2024

Иннополис 2025

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

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

Задача 1#119884

Пусть $D$ — некоторое фиксированное непустое множество, а $f(x,y)$ — функция двух переменных, принимающих значения из $D.$ Известно, что

1.: $f(x,f(y,z))= f(f(x,z),y)$ для любых $x,y,z ∈ D,$
2.: для любых значений $x,z ∈ D$ существует такое $y ∈ D,$ что $f(x,y)=z.$

Докажите, что существует такое $t∈D,$ что $f(t,x) =x$ для всех $x∈D.$

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

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

Сначала докажем, что $f(x,y)=f(y,x)$ при любых $x,y ∈ D.$ Согласно свойству $2,$ для $x$ и $y$ существует такое $d,$ что $f(x,d) =y;$ тогда с помощью свойства $1$ получаем $f(x,y) =f(x,f(x,d))= f(f(x,d),x)= f(y,x).$

Далее, пусть $p$ — произвольный элемент $D;$ согласно свойству $2,$ существует такое $t∈ D,$ что $f(p,t)= p.$ Для этого $t$ и произвольного $x∈D$ имеем $f(t,x)= f(t,f(p,c)),$ где $c$ таково, что $f(p,c)= x$ (см. свойство $2).$ Тогда, используя доказанное выше, свойство $1$ и равенство $f(p,c)=x$ получаем

f(t,x)= f(t,f(p,c)) =f(t,f(c,p))=f(f(t,p),c)=f(f(p,t),c)= f(p,c),

что и требовалось доказать.

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

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

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

Задача 2#119885

Пусть $b ,b ,...,b 1 2 2025$ — неотрицательные числа, и

2025 2024 (x+ b1)(x+b2)⋅⋅⋅(x+b2025)= a2025x +a2024x + ⋅⋅⋅+ a1x +a0

Докажите, что $a2≥ ai−1ai+1 i$ для любого $i= 1,2,3,...,2024.$

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

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

Докажем индукцией более общее утверждение:

Для любого целого $n ≥2,$ если $b1,...,bn$ неотрицательны и

n n−1 anx + an−1x + ⋅⋅⋅+ a1x +a0 = (x+ b1)⋅⋅⋅(x+ bn)

то $a2≥ a a i i−1 i+1$ для любого $i=1,2,...,n − 1.$

База индукции $(n= 2):$ в таком случае $a = 1,a = b +b 2 1 1 2$ и $a = bb , 0 1 2$ а значит, $a2= b2+2b b +b2≥ bb = a a 1 1 12 2 12 02$ — доказано.

Индукционное предположение: пусть для некоторого $n≥ 2$ и любых неотрицательных $b,...,b, 1 n$ если

n n−1 anx + an−1x + ⋅⋅⋅+ a1x +a0 = (x+ b1)⋅⋅⋅(x+ bn)

то $a2≥ ai−1ai+1 i$ для любого $i=1,2,...,n − 1.$

Шаг индукции: рассмотрим многочлен $(x+ b1)⋅⋅⋅(x+ bn)(x+b),$ где $b≥ 0.$ Имеем

n n−1 (x+ b1)⋅⋅⋅(x +bn)(x+ b)=(anx + an−1x + ⋅⋅⋅+ a1x+ a0)(x +b)=

= a xn+1+(a b+ a )xn+ (a b+ a )xn−1+⋅⋅⋅+(a b+a )x2+(a b+a )x+a b n n n−1 n−1 n−2 2 1 1 0 0

Для завершения индукционного шага достаточно рассмотреть (доказать) три неравенства:

1.: $(anb+an−1)2 ≥ an(an−1b+an−2);$
2.: $(a1b+a0)2 ≥a0b(a2b+ a1);$
3.: $(aib+ ai− 1)2 ≥ (ai+1b+ai)(ai−1b+ ai− 2)$ для всех i = $2,...,n− 1.$

Рассмотрим их по порядку:

1.

Раскроем скобки и оценим выражение, откинув неотрицательные слагаемые,

2 22 2 2 (anb+ an−1) = anb+ 2anan− 1b+ an−1 ≥ anan−1b+ an−1

Теперь, применяя предположение индукции, получаем то, что нужно

2 anan−1b+an−1 ≥ anan−1b+anan−2 = an(an−1b+ an−2)

2.

Применяя базу, получаем то, что нужно

(a1b+a0)2 =a21b2+ 2a1a0b+a20 ≥ a2a0b2+ a1a0b= a0b(a2b+a1)

3.

Пусть теперь $i∈{2,...,n − 1}$ — произвольное целое число. Раскроем скобки в левой части неравенства:

(aib +ai−1)2 = a2b2+ 2aiai−1b+a2 i i−1

Раскроем скобки в правой части неравенства:

(ai+1b+ai)(ai−1b +ai−2)= ai+1ai−1b2 +(ai+1ai−2 +aiai−1)b+aiai−2

По предположению индукции первое слагаемое из левой части неравенства не меньше первого слагаемого из правой части неравенства: $a2ib2 ≥ai+1ai−1b2.$ Аналогично, последнее слагаемое из левой части неравенства не меньше последнего слагаемого из правой части неравенства: $a2i−1 ≥ aiai−2.$

Теперь сравним средние слагаемые в левой и правой частях неравенства: очевидно, что для этого достаточно сравнить $a a a a . i i−1 i+1 i−2$ Для этого умножим обе величины на $aa ii−1$ и применим индукционное предположение:

(aiai−1)2 = a2ia2i−1 ≥ (ai+1ai−1)(aiai−2)= (ai+1ai−2)(aiai−1)

Следовательно, $aiai−1 ≥ai+1ai−2,$ что завершает доказательство.

Шаг индукции доказан, а вместе с ним и утверждение, обобщающее утверждение задачи.

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

Задача 3#119886

В стране $N$ есть 10 городов, каждая пара которых соединена двусторонним авиамаршрутом, который обеспечивается одной из двух авиакомпаний. Докажите, что одна из этих авиакомпаний может предложить своим пассажирам два циклических маршрута, каждый из которых проходит по нечетному числу городов, причем ни один город не является частью обоих маршрутов.

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

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

Построим граф $(K ), 10$ вершины которого — города, а ребра — авиамаршруты между городами. Будем красить ребра в красный и синий цвета в зависимости от того, какой авиакомпании принадлежит соответствующий маршрут. Требуется доказать, что в построенном графе существуют два непересекающихся нечетных цикла одного цвета.

_________________________________________________________________________________________________________________________________________________________________________________

Лемма 1. Если каждое ребро полного графа $K6$ (граф с $6$ -ю вершинами, каждая пара из которых соединена ребром) покрасить в один из двух цветов, то найдется треугольник (цикла длины $3),$ все стороны (ребра) которого имеют один цвет.

Доказательство. Пусть $v1,...,v6$ — вершины графа. Если ребра $vivj$ и $vivk$ окрашены в один цвет, то будем считать, что в этот цвет покрашен угол $vjvivk.$ Пусть $ri,bi$ — количества соответственно красных и синих ребер, выходящих из вершины $vi.$ Тогда $ri+ bi = 5$ (для всех $i$ ) и общее число окрашенных углов

6 6 ∑ (C2r+ C2b)≥ ∑ (C22 + C23)= 24 i=1 i i i=1

С другой стороны, в каждом «одноцветном» треугольнике все три угла должны быть окрашены в один цвет, а в каждом «неодноцветном» треугольнике есть только один окрашенный угол. Всего есть $3 C6 = 20$ треугольников и пусть $m$ из них одноцветны, тогда $3m+ (20 − m )≥24,$ откуда $m ≥2 >1,$ что завершает доказательство леммы 1.

___________________________________________________________________________________________________________________________________________________________________

Лемма 2. Если каждое ребро полного графа $K5$ (граф с $5$ -ю вершинами, каждая пара из которых соединена ребром) покрасить в один из двух цветов, и в этом графе нет одноцветного треугольника (цикла длины $3,$ все ребра которого окрашены в один цвет), то в этом графе есть два непересекающихся (не имеющих общих ребер) цикла, каждый из которых окрашен в один цвет и имеет длину $5.$

Доказательство. Пусть $v1,v2,...,v5$ — вершины графа. Рассмотрим ребра $v1v2,v1v3,v1v4,v1v5$ — если три из них имеют один и тот же цвет, то найдется одноцветный треугольник, что противоречит условию: действительно, пусть $v1v2,v1v3,v1v4$ — красные, тогда все ребра $v2v3,v3v4,v4v2$ должны быть синими (иначе получим красный треугольник), но тогда мы имеем синий треугольник. Итак, из каждой вершины выходят по два красных и два синих ребра.

Рассмотрим граф, состоящий из $5$ вершин и только красных ребер — в таком графе степень каждой вершины равна $2,$ а значит, он либо является циклом длины $5,$ либо разбивается на меньшие циклы. Если разбить граф на $5$ вершинах степени $2$ на меньшие циклы, то либо получим цикл из $1$ вершины (в наших условиях это невозможно), либо одноцветный треугольник, что также исключено (см. выше). Итак, граф на красных ребрах — цикл длины $5,$ аналогичный вывод делаем для графа на синих ребрах. Лемма 2 доказана.

_________________________________________________________________________________________________________________________________________________________________________________

Вернемся к задаче: пусть $v1,v2,...,v10$ — вершины графа $K10$ и пусть $v1v2v3$ — одноцветный треугольник в нем (его существование следует из леммы $1).$ В графе $K10∖{v1,v2,v3}$ также есть одноцветный треугольник, т.к. количество его вершин не меньше $6$ (даже $7)$ — пусть это треугольник $v4v5v6.$ Если эти треугольники окрашены в один цвет, то решение завершено. Если же нет (допустим, $v1v2v3$ — синий, а $v4v5v6$ — красный), то рассмотрим ребра $vivj$ для $i=1,2,3,$ $j = 4,5,6$ — всего $9$ ребер и, согласно принципу Дирихле, среди них найдутся $5$ ребер одного цвета (без ограничения общности будем считать, что синего). Тогда для некоторого $k∈ {4,5,6}$ найдутся два синих ребра из тройки $v1vk,v2vk,v3vk,$ т.е. меем один синий и один красный треугольники с общей вершиной $vk.$

Итак, “угол” $v v v 1 23$ — синий, а “угол” $vv v 3 4 5$ — красный. Рассмотрим граф $K ∖{v ,v v,v ,v }= K . 10 1 2 3 4 5 5$ Если в нем есть одноцветный треугольник, то решение завершено: берем его и соответствующий ему по цвету $v vv 12 3$ или $vv v . 34 5$ Если в $K 5$ нет одноцветного треугольника, то, согласно лемме $2,$ в ней найдутся два разноцветных цикла длины $5$ — в этом случае берем нужный из этих циклов в качетсве второго циклического маршрута. Доказательство утверждения задачи завершено.

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

Задача 4#119891

Даны целое $a> 0,$ не являющееся целой степенью числа $10,$ и целое $b> 0.$ Верно ли, что существует такое целое $n >0,$ что в десятичной записи числа $n a$ встречается десятичная запись числа $b?$ Например, для $a= 2$ и $b= 19$ можно выбрать $n =13,$ т.к. $13 2 = 8192,$ в записи которого есть $19.$

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

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

Докажем, что для любого целого $a≥ 2$ ( $a⁄= 1= 100)$ и любого целого $b> 0$ найдется целое $n> 0,$ для которого десятичная запись числа $n a$ начинается с последовательно записанных цифр числа $b$ — иными словами, найдутся такие целые положительные $m,n,$ что

m n m 10 ⋅b< a < 10 ⋅(b+ 1)

Прологарифмируем последнее двойное неравенство с основанием $10:$

m + lgb <n ⋅lga< m +lg(b+ 1)

lgb< n⋅lga − m < lg(b+1)

Докажем, что $lga$ иррационально: если это не так, то $lga= pq$ для некоторых целых положительных взаимно простых $p,q,$ тогда $10p = aq,$ что невозможно. Итак, $lga$ иррационально.

Для завершения решения задачи можно доказать, что для любого иррационального $x> 0$ и любого выбранного интервала $(u,v)$ $(0< u< v)$ найдутся такие целые положительные $m,n,$ что

u< nx− m <v

Заметим, что для любого целого $n >0$ можно выбрать такое целое $mn > 0,$ что $0< nx− mn < 1.$ Пусть $k= ⌈v1−u⌉,$ т.е. отрезок $[0,1]$ можно разбить на $k$ равных отрезков, длина каждого из которых будет меньше длины интервала $(u,v).$ Рассмотрим бесконечный набор чисел $x− m1,$ $2x− m2,$ $3x− m3,...$ и выберем из него два числа попадающие в один и тот же из упомянутых $k$ отрезков — пусть это числа $ix− mi$ и $jx− mj$ (без ограничения общности будем считать, что первое меньше второго). Тогда

jx− m − (ix− m )= t∈(0;1∕k) j i

Для найденного $t$ рассмотрим числа $t,2t,3t,...$ — ввиду $t< 1∕k$ среди них найдется число, лежащее на интервале $(u,v),$ что и требовалось доказать.

Осталось заметить, что в условиях нашей задачи $x= lg a$ — иррациональное положительное число; $(u,v)=(lgb,lg(b+ 1))$ — положительный интервал (если $b= 1⇒ lgb= 0,$ то в качестве $u$ можно выбрать любое число из интервала $(0;lg(b+1))).$ Итак, найдутся такие целые положительные $m,n,$ что $lgb< n⋅lga− m < lg(b+ 1),$ т.е. десятичная запись числа $an$ будет начинаться с цифр числа $b.$

Ответ:

Да, верно

Предыдущая подтема