Выбрано 10 задач 
Убрать все задачи
Дан треугольник ABC и прямая l, пересекающая прямые BC, AC, AB в точках La, Lb, Lc. Перпендикуляр, восставленный из точки La к BC, пересекает AB и AC в точках Ab и Ac соответственно. Точка Oa – центр описанной окружности треугольника AAbAc. Аналогично определим Ob и Oc. Докажите, что Oa, Ob и Oc лежат на одной прямой.
Доказать, что (2n – 1)n – 3 делится на 2n – 3 при любом n.
Доказать, что при чётном n 20n + 16n – 3n – 1 делится на 323.
Через произвольную точку P стороны AC треугольника ABC параллельно его медианам AK и CL проведены прямые, пересекающие стороны BC и AB в точках E и F соответственно. Докажите, что медианы AK и CL делят отрезок EF на три равные части.
12 шахматистов сыграли турнир в один круг. Потом каждый из них написал 12 списков. В первом только он, в (k+1)-м – те, кто были в k-м и те, у кого они выиграли. Оказалось, что у каждого шахматиста 12-й список отличается от 11-го. Сколько было ничьих?
По кругу расставлены 2005 натуральных чисел.
Доказать, что найдутся два соседних числа, после выкидывания которых оставшиеся числа нельзя разбить на две группы с равной суммой.
Имеются две одинаковых шестеренки по 14 зубьев на общей оси. Их совместили и выбили четыре пары зубьев.
Доказать, что шестеренки можно повернуть так, что они образуют полноценную шестеренку (без дырок).
На стороне AB квадрата ABCD взята точка E, а на стороне CD – точка F, причём AE : EB = 1 : 2, а CF = FD.
Будут ли голубой и зелёный треугольники (см. рис.) подобны?
Квадрат раскрашен в два цвета. Можно любой прямоугольник
перекрашивать в преобладающий в нем цвет. Доказать, что
такими операциями можно сделать весь квадрат одноцветным.
В лаборатории на полке стоят 120 внешне неразличимых пробирок, в 118 из которых находится нейтральное вещество, в одной – яд и в одной – противоядие. Пробирки случайно перемешались, и нужно найти пробирку с ядом и пробирку с противоядием. Для этого можно воспользоваться услугами внешней тестирующей лаборатории, в которую одновременно отправляют несколько смесей жидкостей из любого числа пробирок (по одной капле из пробирки), и для каждой смеси лаборатория сообщит результат: $+1$, если в смеси есть яд и нет противоядия; $-1$, если в смеси есть противоядие, но нет яда; 0 в остальных случаях. Можно ли, подготовив 19 таких смесей и послав их в лабораторию единой посылкой, по сообщенным результатам гарантированно определить, в какой пробирке яд, а в какой противоядие?
|
|
 |
Условие
В лаборатории на полке стоят 120 внешне неразличимых пробирок, в 118 из которых находится нейтральное вещество, в одной – яд и в одной – противоядие. Пробирки случайно перемешались, и нужно найти пробирку с ядом и пробирку с противоядием. Для этого можно воспользоваться услугами внешней тестирующей лаборатории, в которую одновременно отправляют несколько смесей жидкостей из любого числа пробирок (по одной капле из пробирки), и для каждой смеси лаборатория сообщит результат: $+1$, если в смеси есть яд и нет противоядия; $-1$, если в смеси есть противоядие, но нет яда; 0 в остальных случаях.
Можно ли, подготовив 19 таких смесей и послав их в лабораторию единой посылкой, по сообщенным результатам гарантированно определить, в какой пробирке яд, а в какой противоядие?
Решение
Для описания отправляемых в лабораторию смесей составим таблицу, состоящую из 120 строк и 19 столбцов. Каждый столбец таблицы – это описание состава смеси, отправляемой в лабораторию. На пересечении $i$-й строки и $j$-го столбца стоит единица, если $j$-я смесь содержит жидкость из $i$-й пробирки, и ноль в противном случае.
Сначала попробуем найти пару пробирок с ядом и противоядием, не устанавливая, где в этой паре яд, а где противоядие. Для этого огрубим результат лаборатории, убрав из него знак (то есть будем считать, что для каждой смеси лаборатория сообщает результат $+1$, если в смеси есть яд без противоядия или противоядие без яда, и ноль иначе). Рассмотрим две строки, соответствующие пробиркам с ядом и противоядием. Их покоординатная сумма, взятая по модулю 2, совпадает со строкой результатов, присланных лабораторией. Следовательно, если все суммы пар строк таблицы, взятые по модулю 2, будут попарно различны, то в результате тестирования мы сможем определить номера строк, соответствующих яду и противоядию.
Такую таблицу можно построить следующим образом. Первую ее строку заполним произвольно. Вторую строку заполняем так, чтобы она не совпадала с первой. Третья и все последующие строки должны удовлетворять двум условиям:
1) новая строка не должна совпадать с уже заполненными;
2) новая строка должна быть такой, чтобы суммы всех возможных пар построенных строк, взятые по модулю 2, были различны.
Покажем, что построение возможно. Покоординатную сумму строк $a$ и $b$, взятую по модулю 2, будем обозначать как $a\oplus b$. Рассмотрим строчки $s_1, s_2, s_3$ и $s_4$. Предположим, что $s_1\oplus s_2=s_3\oplus s_4$, тогда $s_1\oplus s_2\oplus s_3 = s_3\oplus s_3\oplus s_4=s_4$. Следовательно, правила построения таблицы можно переформулировать следующим образом:
1) новая строка не должна совпадать с уже заполненными;
2) новая строка должна быть такой, чтобы она была отлична от всех возможных сумм троек уже построенных строк.
Число строк длины 19, составленных из нулей и единиц, равно $2^{19} = 2^{10} \cdot 2^9 > 1000 \cdot 500 = 500 000$. Запретов, даже после заполнения всех 120 строк, будет не более чем $C^3_{120} + 120 = \frac{120\cdot119\cdot118}{6} + 120 < 20\cdot 120 \cdot 120 + 120 = 288 120 < 300 000$. Следовательно, такую таблицу можно построить.
Чтобы определить пару пробирок с ядом и противоядием, найдем все попарные суммы строк таблицы, взятые по модулю 2. Найдем такие строки $s_1$ и $s_2$, что $s_1\oplus s_2$ совпадает с огрубленным результатом лаборатории. Пробирки, соответствующие строкам $s_1$ и $s_2$, содержат яд и противоядие. Далее, рассматривая уже настоящий результат лаборатории, мы сможем точно сказать, в какой пробирке яд, а в какой противоядие. Действительно, обязательно найдется хотя бы одна смесь, содержащая либо только яд, либо только противоядие, иначе строки таблицы, соответствующие пробирке с ядом и пробирке с противоядием, будут одинаковыми, что запрещено построением. Тогда по знаку результата для этой смеси мы сможем определить, был в ней яд или противоядие.
Ответ
Да, можно.
