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

Комбинаторика на Иннополисе

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

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

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

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

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

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

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

Задача 1#119886

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

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

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

Подсказка 1

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

Подсказка 2

А если мы перейдем к какому-то подграфу? Какой длины у нас могут быть циклы, если всего вершин 10? Быть может, в некотором подграфе мы гарантированно сможем найти цикл нечетной длины?

Подсказка 3

Попробуйте рассмотреть граф К₆ и доказать, что в нем всегда найдется одноцветный цикл длины 3. Как это можно сделать?

Подсказка 4

Попробуйте рассмотреть "углы" (например, ребра v₁v₂ и v₁v₃ образуют "угол" v₂v₁v₃) и оценить среди них количество покрашенных в один цвет (оба ребра одного цвета).

Подсказка 5

Отлично, теперь давайте посмотрим на исходный граф. Достаточно ли доказанного факта для решения задачи?

Подсказка 6

Нет, у нас может получиться 2 цикла разных цветов, а они должны быть одноцветны. Давайте рассмотрим граф, который образуют эти 2 цикла, пусть в первом цикле были вершины v₁, v₂ и v₃, а во втором - v₄, v₅ и v₆. Возможно, благодаря новым ребрам мы сможем получить желаемое. Давайте без ограничения общности попробуем оценить количество синих ребер в новом графе.

Подсказка 7

Попробуйте доказать, что мы сможем найти один красный и один синий "угол" в этом графе, образованные ребрами между множествами вершин {v₁, v₂, v₃} и {v₄, v₅, v₆}. Какой вывод мы можем сделать из существования этих "углов"?

Подсказка 8

Так как мы строили граф на вершинах из циклов синего и красного цветов, мы получим два треугольника (граф К₃) таких же цветов, при том они будут иметь общую вершину. Можем взять вершины одного из этих треугольников в качестве первого цикла и попробовать найти еще один, который не пересекается с ним.

Подсказка 9

Пусть у нас нашлись треугольники v₁-v₂-v₃ и v₃-v₄-v₅. Рассмотрите граф К₁₀ \ {v₁, v₂, v₃, v₄, v₅}. Это будет граф К₅. Чем он может нам помочь?

Подсказка 10

Действительно, если в тем найдется одноцветный треугольник, то просто возьмем его в качестве второго цикла. А если нет? Нарисуйте граф К₅ и поищите в нем циклы нечетной циклы при условии, что у нас не нашелся одноцветный треугольник.

Подсказка 11

На самом деле, в графе К5 без одноцветного треугольника всегда найдутся 2 непересекающихся цикла одного цвета и длины 5, теперь надо доказать это в общем виде, и задача будет решена.

Подсказка 12

Посмотрите на какую-нибудь вершину и ребра, которые из нее выходят. Можно ли что-то сказать об их цветах?

Подсказка 13

Из условия о несуществовании треугольника получится, что из каждой вершины выходит ровно 2 красных и 2 синих ребра. Теперь рассмотрите подграф, состоящий (без ограничения общности) только из красных ребер, и доведите решение до конца.

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

Построим граф $(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 45$ — красный. Рассмотрим граф $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$ — в этом случае берем нужный из этих циклов в качетсве второго циклического маршрута. Доказательство утверждения задачи завершено.

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

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

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

Задача 2#126632

Множество всех целых положительных чисел разбили на два непересекающихся подмножества — $A$ и $B$ . Докажите, что для любого целого $n> 0$ найдутся такие целые $x >y >n,$ что ${x,y,x +y}⊆ A$ или ${x,y,x+ y}⊆ B.$

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

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

Подсказка 1

Рассмотрите случай, когда одно из множеств (например, А) конечно. Пусть m — наибольший элемент А. Какие числа гарантированно попадут в В и удовлетворят условию?) Возьмите х = m+1, y = m+2, х+у = 2m+3 — все они обязаны лежать в B.

Подсказка 2

Если оба множества бесконечны, предположите противное: для некоторого n > 0 нужных троек нет. Как выбрать числа а > b > с > n из А, чтобы получить противоречие? Число b-с не может лежать ни в А иначе (b, b-с, с) с В, ни в В иначе (a+b, c+a, b-c) с B

Подсказка 3

Почему тройка (a+b, b+с, с+а) обязана полностью принадлежать В? Как это приводит к тому, что число b-с не принадлежит ни А, ни В? Это нарушает условие разбиения N на два непересекающихся множества!

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

Без ограничения общности, пусть множество $A$ содержит конечное число элементов, наибольший из которых равен $m.$ Тогда ${m +1,m +2,2m +3}⊂ B,$ и условие задачи выполнено.

Теперь будем считать, что каждое из множеств $A,B$ содержит бесконечное число элементов. Препдположим, что существует такое целое $n> 0,$ что для любых целых $x> y > n$ множество ${x,y,x+ y}$ не содержится ни в $A,$ ни в $B.$ Выберем $a >b >c> n$ из множества $A$ с условием $b− c> n$ $($ по предположению, $(b− c) ∕∈ A,$ иначе ${b,b− c,c}⊂ B),$ что возможно, поскольку $A$ бесконечно. Тогда ${a+ b,b+ c,c+ a}⊂ B,$ иначе нарушается предположение, но тогда $(b− c) ∕∈B,$ иначе ${a+ b,c+ a,b − c}⊂ B.$ Получили, что число $(b− c)$ не содержится ни в $A,$ ни в $B,$ что противоречит условию. Таким образом, исходное утверждение доказано.

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

Задача 3#126634

За один ход разрешается одновременно заменять все члены последовательности $x ,x ,x ,...,x 1 2 3 n$ действительных чисел на $|a− x1|,|a − x2|,|a− x3|,...,|a− xn|,$ соответственно (число $a$ для разных ходов может быть разным). Докажите, что за конечное число ходов из любой начальной последовательности можно получить последовательность, состоящую только из нулей $(0,0,0,...,0),$ и найдите наименьшее число ходов, за которое гарантированно можно этого добиться для фиксированного $n.$

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

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

Подсказка 1

Давайте подберём для каждого хода какое-то удобное число a.

Подсказка 2

a можно выражать через соответствующие xᵢ для каждого хода. Помните, что мы хотим обратить все xᵢ в 0.

Подсказка 3

Сделаем все иксы равными, тогда на следующем ходе при a = x₁ получим последовательность нулей.

Подсказка 4

Пусть на первом шаге a = (x₁ + x₂)/2. Какими тогда будут x₁ и x₂?

Подсказка 5

Получится, что x₁ после первого шага и x₂ после k-ого шага будут равны |x₁ - x₂|/2. Попробуйте за n шагов обратить все xᵢ в 0.

Подсказка 6

Это утверждение доказывается по индукции, обратите внимание на минимальный и максимальный элемент последовательности на каждом шаге.

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

Покажем, что $n$ шагов достаточно для получения нулевой, т.е. состоящей только из нулей, последовательности. Будем обозначать $(k) (k) (k) x1 ,x2 ,...,xn$ последовательность после $k$ -го шага преобразований, и за $(k) a$ будем обозначать значения $a,$ выбранное на $k$ -ом шаге. Пусть

(1) x1+ x2 a = --2---,

тогда

1 x(11)= x(k2)= 2|x1− x2|

Далее пусть

a(2) = x(11)+-x(k3), 2

тогда

(2) (2) (2) 1|| (1) (1)|| x1 = x2 = x3 = 2|x1 − x3|

Продолжая аналогично, на $k$ -м шаге выберем:

a(k) = x(1k−1)+-x(kk+−11), 2

тогда:

(k) (k) (k) 1||(k−1) (k−1)|| x1 = x2 = ⋅⋅⋅= xk+1 = 2|x1 − xk+1 |

для $k< n.$ На $n$ -м шаге выберем $(n) (n−1) a = x1$ и получим последовательность из нулей.

Теперь покажем, что $n$ шагов необходимы для некоторых начальных последовательностей, например, $1!,2!,...,k!.$ Докажем это индукцией по $n.$

База. $n= 1$ тривиальна.

Индукционная гипотеза. Пусть утверждение верно для некоторого целого $k≥ 1,$ т.е. последовательность $1!,2!,...,k!$ невозможно свести к нулевой последовательности менее чем за $k$ шагов. Докажем аналогичное для $k+ 1.$

Отметим, что если $m$ — наименьшее число шагов, необходимое для “обнуления” последовательности $x1,x2,...,xn,$ то $m (k−1) ≤ a(k) < M(k−1)$ для $k= 1,2,...,m,$ где:

m (k−1) = min{x(1k−1),x(k2−1),...,x(kn−1)}

M (k−1) = max{x(k1−1),x(k2−1),...,x(nk−1)}

Действительно, для $a(k) < m(k−1)$ и всех $i$ имеем:

| | | | || | | | ( )| x(ik+1)= ||a(k+1)− x(ik)||= ||a(k+1)− ||a(k)− x(ik−1)||||=||x(ki−1)− a(k+1)− a(k)||= ||x(ik−1)− a

На $k$ -м шаге мы устанавливаем $a= a(k)+a(k+1)$ для экономии шагов, что противоречит минимальности $m.$

С другой стороны, для $a(k) > M (k−1)$ и всех $i$ имеем:

x(k+1)=|||a(k+1)− x(k)|||= |||a(k+1)− |||a(k)− x(k−1)||||||= |||−x(k−1)− a(k+1)+ a(k)|||= &#x0 i i i i i

На $k$ -м шаге мы устанавливаем $a= a(k)− a(k+1)$ для экономии шагов , что опять противоречит минимальности $m.$

Итак, $M (0) ≥ M (1) ≥ ⋅⋅⋅≥ M (m),$ откуда $a(k) ≤ M (0)$ для всех $k.$ При этом из $m(k) ≥0$ следует $a(k) ≥ 0$ для всех $k.$

Из предположения, что последовательность $1!,2!,...,k!,(k +1)!$ можно "обнулить"за не более чем $k$ шагов, следует, что последовательность $1!,2!,...,k!$ также обнулена этими шагами, причём для неё это количество шагов является минимальным (индукционная гипотеза). Из выше изложенного следует,что $0≤ a(i) ≤ k!$ для всех $i=1,2,...,k,$ но тогда:

(k) |||| || (1)|| (2)|| (k)|| ( (1) (2) (k)) xk+1 = ||⋅⋅⋅|(k+ 1)!− a |− a |− ⋅⋅⋅− a |= (k +1)!− a + a + ⋅⋅⋅+a ≥ (k+1)!− k⋅k!> 0,

что противоречит $(k) xk+1 = 0.$ Значит, последовательность $1!,2!,...,k!,(k+ 1)!$ невозможно обнулить $k$ шагами, и потребуется как минимум $k+1$ шаг, что завершает индукцию и решение задачи.

Ответ:

$n$

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

Задача 4#90003

Сколькими способами из множества ${1,2,3,...,2024}$ можно выбрать $n$ чисел так, чтобы сумма любых $m$ (произвольное натуральное число, меньшее $n$ ) из выбранных чисел не делилась на 3? Рассмотрите все возможные $n ≥ 2.$

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

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

Подсказка 1

Нужно рассмотреть все натуральные n>=2... как будто это очень много чисел.. Значит, нужно как-нибудь сузить круг поиска. Подумайте, может ли n быть больше трех?

Подсказка 2

Правда ли, что из любых трёх целых чисел найдётся несколько из них, сумма которых кратна трём?

Подсказка 3

Это действительно так! Получается n<=3, то есть нам нужно рассмотреть всего два варианта! Для подсчёта используйте число сочетаний и рассматривайте остатки при делении на 3.

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

Заметим, что из любых трёх целых чисел найдётся несколько из них, сумма которых кратна трём. (Ведь не может быть числа, кратного трём, и не могут быть одновременно числа с остатками $1$ и $2$ , а чисел одного остатка не более двух).

А значит, $n ≤3,$ при этом из условия нас интересуют $n≥ 2.$ В рассматриваемом множестве чисел по $675$ чисел, дающих остатки $1$ и $2$ при делении на $3.$

Тогда для $n= 3$ подходят любые три числа с одинаковыми остатками, их $3 2⋅C675.$ Для $n = 2$ любая пара чисел с ненулевыми остатками, то есть $2 2⋅C675$ пар чисел с одинаковыми остатками и $2 675$ с разными.

Итого $2 3 2 3 2 2 ⋅C 675+ 2⋅C675+ 675 =2 ⋅C 676+ 675 = 102971025$ чисел.

Ответ:

$2⋅C3 + 6752 = 102971025 676$

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

Задача 5#90012

В правильном $n$ -угольнике ( $n≥ 3$ ) Коля, аналитик платформы «AllCups», решил сопоставить отрезкам между вершинами (т.е. сторонам и диагоналям) их важности, т.е. натуральные числа, удовлетворяющие условиям:

1. для любого треугольника с вершинами в вершинах данного $n$ -угольника важности двух его сторон равны и превосходят важность третьей стороны;

2. важности всех отрезков должны образовывать отрезок натурального ряда, т.е. быть числами $1,2,3,...,k$ без пропусков, но с повторениями.

Найдите максимальное возможное $k$ .

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

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

Подсказка 1

Задача вида «оценка + пример», поэтому хочется понять ответ. Например, для n = 3 и n =4 какие ответы?

Подсказка 2

Для n = 3 ответ совсем просто проверяется, для n = 4 чуть сложнее. Но из них можно предположить, что для произвольного n значение k не превосходит n-1. Причем для k = n-1 нетрудно строиться пример(один из вариантов — пронумеровать вершины от 1 до n, а стороны между i и (i < j) сделать равными какому-то выражению от j). Значит, можно попробовать доказать эту оценку, но как?

Подсказка 3

С помощью индукции! База уже есть. Пусть для всех n от 1 до p предположение верно, докажем для n = p + 1.

Подсказка 4

Например, что не бывает треугольника с двумя отрезками важности 1. Рассмотрите произвольный отрезок АВ с важность 1 и две произвольные точки С и D, отличные от А и В. Что можно сказать о важности АС и ВС, а о паре АD и BD?

Подсказка 5

Они совпадают. Что если попробовать «склеить» А и В? Тогда как раз получится р точек и можно будет использовать предположение индукции. Нужно лишь проверить, что «склеивание» будет происходить корректно.

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

Перед нами задача вида “оценка $+$ пример”. Сперва докажем оценку. По индукции по $n$ будем доказывать, что наибольшее возможное значение $k$ не превосходит $n− 1$

База индукции: $n= 3.$ Если $k≥ 3,$ то стороны единственного треугольника обязаны быть $1,2,3,$ но это противоречит условию, о том, что в треугольнике есть две равные стороны.

Индукционное предположение: Пусть утверждение индукции выполняется для всех $n$ от $3$ до $p∈ ℕ.$ Рассмотрим произвольное распределение важностей для $n−$ угольника, где $n= p+ 1.$ Согласно условию, должен быть отрезок важности $1−$ рассмотрим произвольный треугольник на вершинах $n−$ угольника, для которого этот отрезок является стороной (далее будем называть такие треугольники подходящими). В треугольнике не может быть более одной стороны важности $1,$ ведь иначе оставшаяся сторона должна быть меньше $1.$

Обозначим вершины отрезка важности $1$ как $A$ и $B,$ за $C$ и $D$ обозначим произвольные вершины $n−$ угольника (такие найдутся, так как $p +1≥ 4$ ). Покажем, что важности сторон треугольника $ACD$ не поменяются при замене $A$ на $B.$ Действительно, при такой замене отрезок $AC$ будет заменён на $BC,$ а отрезок $AD$ на $BD.$ Но поскольку оба треугольника $ABC$ и $ABD$ содержат отрезок $AB$ важности $1,$ то, согласно доказанному выше, важности пар сторон каждого треугольника равны. Значит, важности $AC$ и $BC,$ как и важности $AD$ и $BD$ совпадают.

Проделаем следующую процедуру: для отрезка $AB$ с важностью $1,$ эти две вершины склеим в одну вершину $X,$ и для каждой вершины $C$ важностью $XC$ будем считать равной важности $AC.$ Докажем, что многоугольник удовлетворяет первому условию и “ослабленному” второму, т.e. важности всех его сторон и диагоналей образуют отрезок $1,2,3,...,k$ или $2,3,...,k$ натурального ряда без пропусков. Действительно, для любого подходящего треугольника $XY Z$ нового многоугольника, если ни одна из вершин $X,Y,Z$ не была склеена с другой, то требование на важности сторон не изменилось. Если же какая-то вершина (без ограничения общности, вершина $X$ ) была склеена из вершин $A$ и $B,$ то, как было показано ранее, распределение важностей в треугольнике $XY Z$ будет таким же, как в треугольниках $AYZ$ и $BYZ,$ в каждом из которых первое условие было выполнено, а значит, оно не нарушилось и после склейки. Второе, "ослабленное"условие также будет выполнено, т.к. после склейки из набора важностей будет удалено $1.$

Проделав такую склейку по очереди с каждым отрезком важности $1$ получим $m −$ угольник $(m < n)$ , для которого выполнено первое и второе "ослабленное условия задачи". Для него понизим все важности на $1,$ и получим выполняющиеся условия для $m −$ угольника, значит, $k− 1≤ m − 1,$ откуда $k≤ m ≤n − 1.$ Индукция доказана.

Пример: Занумеруем все вершины $n−$ угольника числами от $1$ до $n,$ и зададим отрезкам, соединяющим вершины с номерами $i$ и $j$ $(i< j),$ важность $j− 1.$ Легко проверить, что оба условия на важности выполняются, и максимальная важность равна $n − 1.$

Ответ:

$n − 1$

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

Задача 6#68525

Назовём клетчатый квадрат, каждая клетка которого покрашена в чёрный или в жёлтый цвет, гармоничным, если в нём количество чёрных клеток отличается от количества жёлтых клеток не более чем на единицу. Сколькими способами можно раскрасить клетки таблицы $100× 100$ в чёрный и жёлтый цвета так, чтобы любой квадрат в этой таблице был гармоничным?

Источники: Олимпиада Иннополис - 2023

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

Подсказка 1

Подумайте о том, сколько клеток каждого цвета должно быть в каждом квадрате 2х2. Попробуйте начать раскрашивать самую верхнюю строчку. Какие ограничения при этом накладываются на следующую строку?

Подсказка 2

Теперь попробуйте применить то же самое поведение на все последующие строчки. А при каких условиях раскраски первой строки она будет соответствовать условию? Что если найдётся подстрока, в которой разница цветных квадратов в которой больше 2?

Подсказка 3

Попробуйте обозначить количество подходящих раскрасок первой строки за x и выразить через него количество подходящих раскрасок для всей доски. И осталось только найти х!

Подсказка 4

Если всё ещё испытываете некое затруднение, попробуйте рассматривать в первой строке моменты, когда рядом идут две клетки одного цвета. Попробуйте разбить строку на блоки по 2 клетки и посчитать количество возможных вариантов.

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

Для начала заметим, что в каждом квадрате $2 ×2$ должно быть по две клетки каждого цвета. Рассмотрим раскраску самой верхней строки квадрата. Предположим, что в ней есть какие-то две соседние клетки одинакового цвета. Тогда, рассмотрев квадрат $2× 2,$ содержащий эти клетки, получим, что две клетки под ними должны быть противоположного цвета. Если теперь сдвинуть этот квадрат на одну клетку вправо, получим, что в левом столбце две клетки противоположного цвета, поэтому и в правом столбце клетки тоже должны быть противоположного цвета. Сдвигая этот квадрат аналогично вправо и влево, получим, что вторая строка должна быть противоположна (по цветам) первой.

$PIC$

Если теперь проделать такие же рассуждения со второй и третьей строкой, получим, что третья строка должна быть противоположна второй (т.к. во второй также найдутся две рядом стоящие клетки одного цвета). Аналогично далее строки будут чередоваться, и вся таблица заполняется однозначно. Теперь поймём, при каких условиях на первую строку раскраска будет подходящей. Предположим, что в первой строке найдётся подстрока, в которой клеток одного из цветов хотя бы на $k> 2$ больше, чем другого. Такую подстроку можно сократить до подстроки $A$ длины $m$ так, чтобы разница была ровно $3$ (т.к. при отбрасывании одной клетки разница меняется на 1). Рассмотрим квадрат $B$ размера $m × m,$ содержащий подстроку $A.$ Так как в $A$ разница между цветами равна $3,$ то $m$ нечётно. Значит, в квадрате $B$ тоже разница между цветами будет равна $3,$ т.к. все его строки, кроме первой, можно разбить на пары противоположных (понятно, что если в подстроке разница между цветами больше $1,$ то в ней найдутся две соседние клетки одного цвета).

Таким образом, в первой строке не должно найтись подстроки, в которой клеток какого-то цвета хотя бы на $3$ больше, чем другого. Предположим, что это условие выполнено, причём каждая строка, начиная со второй, противоположна предыдущей. Тогда в любом квадрате чётного размера цветов будет поровну, а в любом квадрате нечётного размера количество клеток разных цветов будет отличаться на $1,$ т.к. все строки в нём, кроме первой, разбиваются на пары, а в первой строке количество клеток разных цветов может отличаться только на $1.$

Обозначим количество подходящих раскрасок первой строки за $x.$ Тогда количество подходящих раскрасок всей доски будет равно $x − 2+ x= 2x− 2.$ Действительно, в первой строке будет либо чередование цветов ( $2$ варианта), либо где-то встретятся две клетки одинакового цвета. Во втором случае всё остальное определяется однозначно, а в первом всё определяется раскраской первого столбца (если и в первой строке, и в первом столбце не будет двух стоящих рядом клеток одного цвета, то с помощью последовательного рассмотрения квадратов $2 ×2$ мы получим, что раскраска должна быть шахматной).

Теперь осталось найти $x.$ Заметим, что трёх подряд идущих клеток одного цвета быть не может, т.к. эти три клетки уже дают подстроку с разницей $3.$ Найдём в строке первый момент, когда рядом встретились две клетки одного цвета. Найдём следующий момент, когда рядом встретятся две клетки одного цвета. Если это тот же самый цвет, то в минимальной подстроке, содержащей обе эти пары, разница цветов будет равна $3,$ чего быть не может. Значит, это должны быть клетки другого цвета. Таким образом, блоки из пар клеток одного цвета должны чередоваться, а ещё между этими блоками могут быть участки чётной длины из чередующихся клеток. Тогда для расположения блоков может быть два варианта: либо их первые клетки расположены на нечётных местах, либо на чётных.

В первом случае разобьём все клетки на пары подряд идущих. На месте каждой пары может быть либо блок из двух одинаковых клеток, либо пара разных клеток. По набору мест блоков и цвету самой левой клетки цвета всех остальных клеток определяются однозначно. Таким образом, вариантов в этом случае $50 51 2⋅2 =2 .$ В случае, когда первые клетки блоков располагаются на чётных позициях, есть всего $49$ мест для блоков, и цвета всех клеток также определяются наборами мест блоков и цветом самой левой клетки. В этом случае вариантов $49 50 2⋅2 = 2 .$ При этом те варианты, где блоков вообще нет, мы посчитали дважды. Таких вариантов $2$ (когда цвета чередуются). Значит, $51 50 x =2 + 2 − 2.$

Получаем ответ: $52 51 51 2x− 2= 2 +2 − 6= 3⋅2 − 6.$

Ответ:

$3⋅251− 6$

Курсы

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

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

Задача 7#68881

На плоскости нарисовано несколько окружностей, причем каждая пара окружностей пересекается ровно в двух точках, и никакие три окружности не имеют общей точки. Круглосторонник - это часть плоскости, со всех сторон ограниченная дугами этих окружностей, граница которой состоит из каких-то дуг этих окружностей, причем между любыми двумя внутренними точками круглосторонника можно пройти, не пересекая ни одной дуги данных окружностей. Например, ниже изображены две окружности, образующие 3 круглосторонника, обозначенные номерами 1, 2 и 3.

$PIC$

Смежные круглосторонники - это круглосторонники, имеющие общую дугу окружности в качестве границы, причем дуга должна быть невырожденной, то есть не сводящейся к одной точке. Например, на рисунке выше смежными являются круглосторонники 1 и 2, 2 и 3, но не 1 и 3. Для какого наименьшего $C ≥2023$ можно нарисовать окружности так, что выполнены условия, перечисленные выше, и эти окружности образовывали ровно $C$ круглосторонников?

Докажите, что для любого расположения нарисованных окружностей на плоскости, удовлетворяющих перечисленным условиям и образующих не менее 2023 круглосторонников, обязательно найдется круглосторонник, ограниченный менее чем 4-мя дугами.

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

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

Подсказка 1

Круглосторонники, окружности… Ну и ну. Хотя, вообще-то, вся это конструкция кое-что напоминает, если посмотреть на это под другим углом. У нас есть дуги, которые соединяют точки пересечения окружностей, у нас есть вот эти круглосторонники, которые отделены дугами , и внутри которых дуг нет. На что это похоже?

Подсказка 2

Верно, на плоский граф. Но, поскольку вершины этого графа, то есть точки пересечения пар окружностей, соединены дважды, то это плоский мультиграф. Интересно. А какую главную формулу мы знаем про плоские графы(и мультиграфы в том числе)?

Подсказка 3

Верно, формулу Эйлера для плоских графов. V - E + F = 2, где V - число вершин графа, E - число ребер, а F - число граней(здесь стоит сказать, что у нас вне этого плоского мультиграфа, тоже есть часть плоскости, которая отделена ребрами и внутри которой их нет - это часть плоскости вне графа, ее тоже стоит учитывать). Предположим, что окружностей у нас m, что тогда можно сказать про V? А как связать E и V?

Подсказка 4

Верно, так как окружностей m и каждая пара пересекается в двух точках, то всего точек пересечений, то есть вершин, 2*m(m-1)/2 = m(m-1)=V. Так как каждая вершина - точка пересечения ровно двух окружностей, то из нее исходит ровно 4 ребра. А значит E=4V/2=2V=2m(m-1). А значит F = 2 + E - V = m(m-1) + 2. Вспомним про рассуждения из предыдущего пункта, что число круглосторонников меньше числа граней на 1. Значит число круглосторонников равно m^2-m+1. Значит, нам надо решить неравенство m^2-m+1>=2023. Значит, m>=46. Но нужно привести пример. Подумайте как это можно сделать, использовав как-то правильный многоугольник и/или повороты на угол вокруг одной точки(что в общем-то, почти одно и тоже).

Подсказка 5

Теперь построим пример, для всех таких m от 1 до 46, когда никакие три окружности не пересекаются в одной точке. Возьмем окружность A_0 и точку О внутри нее, не совпадающую с ее центром. После чего построим, для всех i от 1 до m-1, окружности, которые получаются из А_0 поворотом на i*2pi/m против часовой стрелки, с центром в точке О. Почему этот пример подходит?

Подсказка 6

Верно, так как при такой картинке, «внешние» вершины соседних образуют правильный m-угольник, О - центр этого многоугольника. Тогда построим другую, неподходящую картинку, когда все окружности - есть описанные вокруг O и проходящие через свою сторону m - угольника. Тогда можно провести окружность(она не относится к нашим и нужна только для построения) с центром в точке О и посмотреть на пересечения этой окружностью серперов из точки О к сторонам нашего m-угольника. Тогда возьмем новые m штук окружностей, которые проходят через соответствующие стороны m-угольника и соответствующие точки пересечения серперов технической окружностью. Тогда, очевидно, они все перестанут пересекаться, так как мы на совсем чуть-чуть(пусть радиус технической окружности очень близок к нулю) сдвинули наши окружности(в силу непрерывности, доказали). Остался второй пункт задачи. Попробуйте доказать от противного.

Подсказка 7

Если предположить, что каждый круглосторонник ограничен как минимум 4 дугами, то общее число дуг, которые ограничивает круглосторонник не меньше чем 4*C=4(m^2-m+1). Пусть К - кол-во внешних граней мультиграфа, тогда K+4C<=E. Но тогда K+4+2m(m-1)<=0, что невозможно, так как K>=0, 4>0, 2m(m-1)>=0. Значит, предположение неверно, а значит, найдется круглосторонник, ограниченный не более чем 3 дугами.

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

Рассмотрим нарисованные окружности как плоский мультиграф (граф с кратными ребрами между вершинами): вершины – точки пересечений, ребра – дуги нарисованных окружностей, ограниченные точками пересечений. В такой интерпретации круглосторонники — это все грани этого графа, кроме «внешней» (т.е. части плоскости, лежащей вне всех окружностей).

Пусть нарисованы ровно $m$ окружностей. Согласно формуле Эйлера для плоских графов,

V − E +F = 2,

где $V$ — число вершин графа, $E$ — число ребер, а $F$ — – число граней (включая внешнюю).

Так как каждая пара окружностей пересекается ровно в двух своих уникальных точках, то число вершин

m-(m-−-1) V = 2⋅ 2 = m(m− 1)

Так как каждая вершина – это точка пересечения ровно двух окружностей, то наш граф является регулярным степени $4$ (то есть в каждую вершину входят ровно $4$ ребра). Поскольку каждое ребро соединяет две вершины, общее число ребер

4V E = -2-= 2V = 2m(m− 1)

Следовательно число граней нашего плоского мультиграфа должно быть равно

F = 2+ E− V =2+ 2m(m − 1)− m(m − 1)= 2+ m(m − 1)

Значит, число круглосторонников

C =F − 1⇒ C =1+ m (m − 1)

Найти наименьшее $m,$ такое, что $C ≥ 2023$ — значит найти наименьшее натуральное решение неравенства

2 m − m − 2022≥ 0

Решив, получаем, что наименьшее $m$ равно $46,$ соответственно $C =1 +46⋅45= 2071.$

Теперь заметим, что для любого $m ≥ 1$ (в том числе для $m = 46)$ можно расположить $m$ окружностей на плоскости так, что каждая пара пересекается ровно в двух своих уникальных точках. Действительно, нарисуем произвольную окружность $B$ на плоскости и выберем произвольную точку $O$ внутри нее (но не являющуюся ее центром), а потом рассмотрим $m$ окружностей $Bk,$ где $0≤ k≤ (m− 1),$ которые получаются в результате поворота окружности $B$ вокруг точки $O$ на угол $2πk m$ (окружность $B0$ совпадает с $B).$ На рисунке приведен пример для $m =4.$

$PIC$

Теперь докажем, что обязательно найдется круглосторонник, ограниченный менее чем $4-мя$ дугами. Предположим, что все круглосторонники ограничены не менее чем $4$ дугами. Тогда общее число «сторон» (дуг, ограничивающих круглосторонники) не меньше, чем $4C = 4(1+ m(m − 1)).$ Пусть $K$ — число границ внешней грани плоского мультиграфа, тогда

K + 4C = K +4+ 4m(m − 1)≤ 2m(m− 1)⇔ K +4 +2m (m − 2)≤ 0

Это невозможно, — следовательно, неверно предположение, что все круглосторонники ограничены не менее чем $4$ дугами. Поэтому обязательно найдется круглосторонник, ограниченный менее чем $4$ дугами, что и требовалось доказать.

Ответ: 2071

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

Задача 8#74912

Проводится шахматный турнир, в котором участвуют $n$ человек $(n> 2).$ Из-за эпидемической обстановки партии проходят в отдельных помещениях, причем в каждом помещении шахматист может играть только фигурами одного цвета.

Например, если Иван играл черными фигурами в помещении №1, то он уже не сможет сыграть белыми фигурами в этом помещении. Аналогично, если участник играл белыми фигурами в помещении №5, то в этом же помещении он уже не сможет играть черными фигурами. При этом он может снова играть белыми фигурами в помещении №5.

Известно, что каждый участник турнира должен сыграть с любым другим участником ровно одну партию. Организаторы хотят составить такое расписание, чтобы задействовать минимально возможное число помещений. Докажите, что это число равно $⌈log2n⌉.$

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

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

Подсказка 1

Давайте попробуем доказать, что нам понадобиться не менее, чем [log_2(n)] (под [x] подразумевается целочисленное x округление вверх) комнат и что именно [log_2(n)] достаточно. Для док-ва первого утверждения давайте для удобства заведём функцию f(n) - искомое кол-во помещений от кол-ва участников. И построим док-во по сильной индукции.

Подсказка 2

Рассмотрите какое-то помещение и разбейте множество игроков на тех, которые играли и не играли белыми фигурами. Что мы можем сказать про кол-во участников в одном из получившихся множеств?

Подсказка 3

В каком-то из множеств не более n/2 элементов, пусть в том, которые играли белыми фигурами, тогда не играли ими не менее n/2 элементов и им хватило на 1 помещение меньше, чем n игрокам, какую оценку мы тогда можем получить на f?

Подсказка 4

f(n) - 1 >= f([n/2]), применяя ПИ индукции получим f(n) - 1 >= [log_2([n/2])] <=> f(n) >= [log_2(n)], теперь осталось придумать пример рассадки.

Подсказка 5

Давайте попробуем переформулировать задачу в терминах ориентированного графа, пусть вершины - шахматисты, ориентируем ребро ij, если i > j (i играет белыми, а j - чёрными). Поставим каждому ребру число k - наибольшее такое число, что в двоичной записи числа i на k-м месте стоит 1, а у j - 0. Осталось только доказать, почему такой пример - верный.

Подсказка 6

Посмотрите, сколько всего может быть цифр в числах i, j и почему рёбрам ij, jl соответствуют разные номера, и задача решена!

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

Пусть $f(n)$ — искомое число помещении в зависимости от количества $n$ участников турнира. Сначала докажем индукцией по $⌈log n⌉ 2$ , что $f(n)≥ ⌈log2n⌉.$ База $($ для $n = 3$ и $n = 4)$ очевидна.

Зафиксируем помещение (например, №1) и обозначим через $U1$ множество шахматистов (вершин графа, каждое ребро которого соответствует определенной партии), которые играли в этом помещении белыми фигурами. Аналогично, обозначим за $U2$ множество шахматистов, которые не играли в этом помещении белыми фигурами. Множества $U1$ и $U2$ не пересекаются — значит, хотя бы одно из них $($ без ограничения общности будем считать, что это $U1)$ содержит не более $n∕2$ элементов, остальные шахматисты (их не менее $n∕2$ ) не играли белыми фигурами в помещении №1 — значит, им для этого хватило $f(n)− 1$ помещений:

f(n)− 1≥ f(⌈n∕2⌉)≥ ⌈log2(⌈n∕2⌉)⌉

f(n)≥⌈log2n⌉

Покажем, как сделать "правильное"(т.е. соответствующее условию задачи) расписание с $f(n)=$ $⌈log n⌉. 2$ Для этого занумеруем вершины графа (т.е. шахматистов) числами от $0$ до $n − 1$ и ориентируем ребра графа (т.е. партии) $ij,$ если $i> j$ (шахматист $i$ играет белыми, а $j$ — черными), а помещения занумеруем числами от $0$ до $⌈log2n⌉.$ Ребру $ij$ поставим в соответствие номер $k,$ который определяется как наибольшее $k,$ такое, что в двоичной записи числа $i$ на $k$ -м месте стоит 1, а у числа $j$ — $0.$ Такое $k$ существует, поскольку $i⁄= j.$ Кроме того, в двоичных разложениях $i,j$ не более $⌈log2n⌉$ цифр, откуда $k ≤⌈log2n⌉.$

Осталось проверить, что ребрам $ij$ и $jl$ соответствуют разные номера. Действительно, если бы им соответствовал общий номер $k,$ то у числа $j$ в $k$ -м разряде двоичной записи стояла бы и цифра $0$ $($ из-за ребра $ij),$ и цифра $1$ $($ из-за ребра $jl),$ что невозможно.

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

Задача 9#74913

Два игрока играют в игру: они по очереди вытаскивают камни из кучки, в которой изначально было $n$ камней. В свой первый ход первый игрок берет из кучи один или несколько камней, но не может забрать все камни. Каждым следующим ходом очередной игрок должен забрать из кучи количество камней, являющееся делителем числа камней, забранного противником на предыдущем ходу, и не превосходящее числа камней в куче. Выигрывает тот, кто заберет последний камень. Для каждого $n> 1$ определите, у кого из соперников есть выигрышная стратегия.

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

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

Подсказка 1

Попробуем как-то уменьшить перебор случаев. Давайте попробуем понять, а может ли выиграть первый игрок, если всегда будет брать, например, один камень из кучи?

Подсказка 2

Да, может, если количество камней в куче изначально нечётно! Для четных n похожую идею применить уже не получится. Тогда давайте посмотрим, что происходит при малых n, возможно увидим закономерность?

Подсказка 3

Верно, кажется, что при n, которые являются степенью двойки — выигрышная стратегия есть у второго игрока, а при остальных - у первого. Тогда, попробуем доказать по индукции, что для любого числа между соседними степенями двойки — есть выигрышная стратегия у первого игрока.

Подсказка 4

Да, мы поняли, что для n = 2 и n = 4, предположение выполняется(есть база), тогда давайте заметим, что первый игрок может взять количество камней в два раза больше, чем взял бы в игре с n/2 камнями, а этот случай уже попадает в индукционное предположение! Остаётся показать, что происходит, когда n является степенью двойки и соответственно есть выигрышная стратегия у второго игрока.

Подсказка 5

Попробуйте сделать ровно то же самое, но уже для второго игрока, то есть взять камней в 2 раза больше. И помните, что если на ходе какого-то игрока количество камней в куче нечетно, то он уже имеет выигрышную стратегию!

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

Заметим, что если в куче нечетное число камней, то первый игрок гарантирует себе победу, взяв на первом ходу 1 камень: тогда каждым следующим ходом игроки будут забирать по одному камню, и последний камень заберет первый игрок. Когда $n$ чётно, тот, кто первым сделает нечетный шаг, проиграет: такой шаг был сделан из четного числа — значит, он не будет последним, а противник заберет один камень, что и обеспечит ему победу.

Если $n= 2,$ то второй игрок, очевидно, побеждает. Если $n =3,$ то побеждает первый игрок, забирая первым ходом 1 камень. Если $n =4,$ то побеждает второй игрок: если первый берет 1 камень, то второй возьмет последний камень, а если первый игрок первым ходом берет 2 или 3 камня, то второй игрок первым своим ходом забирает остальные камни.

Докажем по индукции, что для всех четных $n$ от $k− 1 2 +1$ до $k 2 − 1$ (для натурального $k ≥2$ ) побеждает первый игрок, а для $k n =2$ — второй. База индукции $(k = 2)$ разобрана выше.

Пусть $2k−1+ 1≤ n≤ 2k− 1$ для натурального $k≥ 3.$ Тогда первый игрок сводит игру к таковой с $n∕2$ камнями (т.е. берет вдвое больше камней, чем взял бы в игре с $n∕2$ камнями), где у него есть победная стратегия согласно предположению индукции, поскольку $2k−2+ 1≤ n∕2 ≤2k−1− 1.$ Единственный способ помешать ему — взять нечетное число камней, но, как показано выше, тот, кто первым возьмет нечетное число камней, проигрывает.

Пусть теперь $n= 2k$ для $k ≥3.$ Тогда уже второй игрок применяет стратегию "половинчатой"игры, т.е. берет в 2 раза больше камней, чем взял бы в игре с $n∕2$ камнями. Согласно предположению индукции, это обеспечит ему победу.

Ответ:

При $n= 2k, k∈ ℕ,$ второй игрок может гарантировать себе победу. При прочих $n> 1$ выигрышная стратегия есть у первого игрока.

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

Задача 10#124048

Найдите максимальное целое число $n ≥0,$ для которого верно следующее утверждение: «Существует способ найти (определить) единственную фальшивую монету среди $n$ внешне одинаковых монет, взвешивая монеты на чашечных весах (без числовых делений) не более трех раз и одновременно определить ее относительный вес (то есть легче она или тяжелее настоящих)». (Замечание: предполагается, что все настоящие монеты имеют одинаковый вес, а фальшивая — другой вес, отличный от веса настоящих монет).

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

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

Подсказка 1

Сколько результатов можно получить за 3 взвешивания?

Подсказка 2

За одно взвешивание можно получить 3 результата, поэтому за 3 взвешивания получим 27. Теперь оцените n.

Подсказка 3

Количество вариантов фальшивой монеты и её относительного веса равно 2n, поэтому 2n ≤ 27 ⇒ n ≤ 13.

Подсказка 4

Будем перебирать n сверху. Пусть n = 13. Давайте предположим, что способ определить фальшивую монету существует, тогда либо приведем его, либо получим противоречие.

Подсказка 5

Заметим, что за 2 взвешивание можно получить только 9 результатов. Докажите, что в каждом взвешивании должно участвовать не менее 10 монет.

Подсказка 6

Докажите, что иначе в первом взвешивании участвует не более 8 монет.

Подсказка 7

Рассмотрите ситуации, когда в первом взвешивании участвует 10 монет, и сравните количества результатов с количествами вариантов.

Подсказка 8

Доказали, что n ≠ 13. Пусть n = 12. Попробуйте придумать алгоритм поиска фальшивой монеты. Сколько монет должно участвовать в первом взвешивании?

Подсказка 9

В первом взвешивании должно участвовать 8 монет, разберите ситуации, когда левая чаша тяжелее; правая чаша тяжелее; чаши уравновешены.

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

Сначала заметим, что за три взвешивания на чашечных весах можно получить только 27 результатов $(так как$ за каждое взвешивание на чашечных весах можно получить только 3 результата — левая чашка легче правой, чашки уравновешены, правая чашка $легче левой).$ Но так как количество вариантов фальшивой монеты $(из n)$ и ее относительного веса $(легче или тяжелее)$ равно $2n,$ то должно выполняться неравенство $2n≤ 27.$ Следовательно, $n ≤ 13.$

Пусть $n =13.$

Докажем методом от противного, что определить фальшивую монету и одновременно её относительный вес требуемым способом невозможно. Для этого предположим противное, то есть то, что есть такой способ.

Заметим, что так как за одно взвешивание на чашечных весах можно получить только 3 результата $(левая чаш ка$ легче правой, чашки уравновешены, правая чашка $легче левой),$ то за два взвешивания на чашечных весах можно получить только 9 результатов.

Теперь покажем, что в первом взвешивании должно участвовать не менее 10 монет $(∗)$ . Действительно, в противном случае в первом взвешивании участвует не более 8 монет $(число должно$ быть чётным, так как взвешивание происходит на чашечных весах, а на чашки весов надо класть равные $количества монет).$

Значит, если в результате первого взвешивания чашки весов уравновесятся, то фальшивая монета — одна из не менее, чем 5 монет, не участвовавших в первом взвешивании, она может быть как легче, так и тяжелее настоящих, и, следовательно, у нас возможно не менее 10 вариантов $(фальшивой монеты$ и её $относительного веса).$

А так как число результатов, которые можно получить за два взвешивания, меньше числа вариантов, то определение фальшивой монеты и её относительного веса невозможно.

В первом взвешивании участвует не менее 10 монет $(∗)$ — не менее 5 на каждой чаше весов. Если в результате первого взвешивания одна чашка $(с не менее,$ чем 5 $монетами),$ оказалась легче, а другая $(тоже с$ не менее, чем 5 $монетами)$ — тяжелее, то у нас возможно не менее 10 вариантов $(фальшивой монеты$ и ее $относительного веса).$ Вновь число результатов за 2 взвешивания будет меньше числа вариантов.

Таким образом, предположив существование способа с помощью чашечных весов определить фальшивую монету и одновременно её относительный вес, мы пришли к заключению, что способ не существует, то есть — к противоречию с предположением.

Пусть $n =12.$

В описании способа определения фальшивой монеты будем использовать следующие обозначения:

1.: Монеты будем обозначать $(1),(2),...,(14),$ а $гирьку$ — $(15).$
2.: Выражения вида $(p+q)?(r+ s)$ для взвешивания, в котором, в данном случае, пара монет $p$ и $q$ помещены на левую чашку весов, а пара других монет $r$ и $s$ (тоже из монет и гирьки) — на правую.
3.: У взвешивания $(p+ q)?(r +s)$ может быть три исхода: < $(если$ левая чашка $легче),$ = $(если$ чашки $уравновешены )$ и > $(если$ правая чашка $легче).$
4.: $case ((p + q)?(r + s)) of:$ означает «для такого выражения возможны следующие случаи» (и далее — случаи для =, > и <).

Теперь мы можем дать описание алгоритма, который получает 12 монет $(1),...,(12)$ , среди которых ровно одна фальшивая имеет вес, отличный от веса других настоящих монет равного веса, и определяет фальшивую монету и ее относительный вес за три взвешивания на чашечных весах. В круглых скобках находятся пояснения к каждому шагу.
$case ((1)+ ...+(4))?((5)+ ...+ (8)) of:$
(сначала мы кладем на левую чашу монеты с 1 по 4, а на вторую — с 5 по 8, остальные подобные выражения читаются аналогично)
$∙$ $=$ (получили равенство, тогда фальшивая среди $(9)...(12)$ , а все $(1)...(8)$ — настоящие):
$case ((1)+(9))?((10)+ (11)) of:$

$=$ (то есть фальшивая (12)):
$case ((1))?((12)) of:$
$■$ $<$ : фальшивая монета (12) и тяжелее;
$■$ $>$ : фальшивая монета (12) и легче;
$<$ (то есть фальшивая среди (9) и легче или среди (10) и (11) и тяжелее):
$case ((10))?((11)) of:$
$■$ $=$ (возможно только если (9) фальшивая и легче): фальшивая монета (9) и легче;
$■$ $<$ (возможно только если (11) фальшивая и тяжелее): фальшивая монета (11) и тяжелее;
$■$ $>$ (возможно только если (10) фальшивая и тяжелее): фальшивая монета (10) и тяжелее;
$>$ (то есть фальшивая среди (9) и тяжелее или среди (10) и (11) и легче):
$case ((10))?((11)) of:$
- $=$ (возможно только если (9) фальшивая и тяжелее): фальшивая монета (9) и тяжелее;
- $<$ (возможно только если (10) фальшивая и легче): фальшивая монета (10) и легче;
- $>$ (возможно только если (11) фальшивая и легче): фальшивая монета (11) и легче;

$∙$ $<$ (то есть фальшивая среди $(1)...(4)$ и легче, или среди $(5)...(8)$ и тяжелее, а все $(9)...(12)$ — настоящие):
$case ((1)+ (2)+ (5)+(6))?((3)+(9)+ (10)+ (11)) of:$

$=$ (то есть фальшивая среди (4) и легче, или (7) и (8) и тяжелее, а все остальные монеты — настоящие):
$case ((7))?((8)) of:$
$■$ $=$ (возможно только если фальшивая (4) и легче): фальшивая монета (4) и легче;
$■$ $<$ (возможна только если фальшивая (8) и тяжелее): фальшивая монета (8) и тяжелее;
$■$ $>$ (возможна только если фальшивая (7) и тяжелее): фальшивая монета (7) и тяжелее;
$<$ (возможно только если фальшивая среди (1) и (2) и легче):
$case ((1))?((2)) of:$
$■$ $<$ (возможна только если фальшивая (1) и легче): фальшивая монета (1) и легче;
$■$ $>$ (возможна только если фальшивая (2) и легче): фальшивая монета (2) и легче;
$>$ (возможно только если фальшивая среди (5) и (6) и тяжелее):
$case ((5))?((6)) of:$
$■$ $<$ (возможна только если фальшивая (6) и тяжелее): фальшивая монета (6) и тяжелее;
$■$ $>$ (возможна только если фальшивая (5) и тяжелее): фальшивая монета (5) и тяжелее;

$∙$ $>$ (то есть фальшивая среди $(1)...(4)$ и тяжелее, или среди $(5)...(8)$ и легче, а все $(9)...(12)$ — настоящие):
$case ((1)+(2)+(5)+(6))?((3)+ (9)+(10)+(11)) of:$

$=$ (то есть фальшивая среди (4) и тяжелее, или (7) и (8) и легче, а все остальные монеты — настоящие):
$case ((7))?((8)) of:$
$■$ $=$ (возможно только если фальшивая (4) и тяжелее): фальшивая монета (4) и тяжелее;
$■$ $<$ (возможна только если фальшивая (7) и легче): фальшивая монета (7) и легче;
$■$ $>$ (возможна только если фальшивая (8) и легче): фальшивая монета (8) и легче;
$<$ (возможно только если фальшивая среди (3) и тяжелее или (5) и (6) и легче):
$case ((5))?((6)) of:$
$■$ $=$ (возможно только если фальшивая (3) и тяжелее): фальшивая монета (3) и тяжелее;
$■$ $<$ (возможна только если фальшивая (5) и легче): фальшивая монета (5) и легче;
$■$ $>$ (возможна только если фальшивая (6) и легче): фальшивая монета (6) и легче;
$>$ (возможно только если фальшивая среди (1) и (2) и тяжелее):
$case ((1))?((2)) of:$
$■$ $<$ (возможна только если фальшивая (2) и тяжелее): фальшивая монета (2) и тяжелее;
$■$ $>$ (возможна только если фальшивая (1) и тяжелее): фальшивая монета (1) и тяжелее.

Итак, искомое $n= 12.$

Ответ:

$n =12$

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

Задача 11#90107

Какое наименьшее количество клеток доски $3×2016$ можно закрасить так, чтобы у каждой клетки была соседняя по стороне закрашенная клетка?

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

Для начала заметим, что если у нас есть какая-то закрашенная клетка, то сама по себе она не является соседней по стороне.Значит, одна из четырех (или меньшего количества) клеток тоже должна быть закрашена. Получается, у каждой клетки должна быть закрашена соседняя по стороне клетка, в том числе и у закрашенных.

Оценка. Давайте рассмотрим пары отмеченных клеток:

$PIC$

Заметим, что чтобы для каждой из пар клеток выполнялось условие, хотя бы две из пяти клеток (соседних 3 или сами 2 рассматриваемые клетки) должны быть закрашены. Причём области, где могут находиться закрашенные клетки с каждой из пар отмеченных клеток не пересекаются. Значит, наименьшее количество клеток, которые можно закрасить, чтобы выполнялось условие - 2016.

Пример. Закрасим центральную строку:

$PIC$

Тогда у каждой клетки найдётся соседняя по стороне закрашенная клетка.

Ответ: 2016