Выбрано 14 задач 
Убрать все задачи
Дана таблица n×n, столбцы которой пронумерованы числами от 1 до n. В клетки таблицы расставляются числа 1, ..., n так, что в каждой строке и в каждом столбце все числа различны. Назовём клетку хорошей, если число в ней больше номера столбца, в котором она находится. При каких n существует расстановка, в которой во всех строках одинаковое количество хороших клеток?
На окружности расположена тысяча непересекающихся дуг, и на каждой из них написаны два натуральных числа. Сумма чисел каждой дуги делится на произведение чисел дуги, следующей за ней по часовой стрелке. Каково наибольшее возможное значение наибольшего из написанных чисел?
На столе стоят 2004 коробочки, в каждой из которых лежит по одному шарику. Известно, что некоторые из шариков – белые, и их количество четно. Разрешается указать на любые две коробочки и спросить, есть ли в них хотя бы один белый шарик. За какое наименьшее количество вопросов можно гарантированно определить какую-нибудь коробочку, в которой лежит белый шарик?
Числа a, b, c таковы, что a²(b + c) = b²(a + c) = 2008 и a ≠ b. Найдите значение выражения c²(a + b).
Дан квадратный трёхчлен f(x) = x² + ax + b. Известно, что для любого вещественного x существует такое вещественное y, что f(y) = f(x) + y. Найдите наибольшее возможное значение a.
Участники шахматного турнира сыграли друг с другом по одной партии. Для каждого участника A было подсчитано число набранных им очков (за победу дается 1 очко, за ничью – ½ очка, за поражение – 0 очков) и
коэффициент силы по формуле: сумма очков тех участников, у кого A выиграл, минус сумма очков тех, кому он проиграл.
а) Могут ли коэффициенты силы всех участников быть больше 0?
б) Могут ли коэффициенты силы всех участников быть меньше 0?
На клетчатой бумаге нарисован прямоугольник 5x9. В левом нижнем углу стоит фишка. Коля и Серёжа по очереди передвигают ее на любое количество клеток либо вправо, либо вверх. Первым ходит Коля. Выигрывает тот, кто поставит фишку в правый верхний. Кто выигрывает при правильной игре?
Внутри параллелограмма ABCD выбрана точка O, причём ∠OAD = ∠OCD. Докажите, что ∠OBC = ∠ODC.
Докажите, что три выпуклых многоугольника на плоскости нельзя пересечь одной прямой тогда и только тогда, когда каждый многоугольник можно отделить от двух других прямой (т.е. существует прямая такая, что этот многоугольник и два остальных лежат по ее разные стороны).
Имеется 4 монеты, из которых 3 – настоящие, которые весят одинаково, и одна фальшивая, отличающаяся по весу от остальных. Чашечные весы без гирь таковы, что если положить на их чашки равные грузы, то любая из чашек может перевесить, если же грузы различны по массе, то обязательно перетягивает чашка с более тяжелым грузом. Как за три взвешивания наверняка определить фальшивую монету и установить, легче она или тяжелее остальных?
На шахматную доску поставлены 11 коней так, что никакие два не бьют друг друга.
Докажите, что на ту же доску можно поставить ещё одного коня с сохранением этого свойства.
В микросхеме 2000 контактов, первоначально любые два контакта соединены отдельным проводом. Хулиганы Вася и Петя по очереди перерезают провода, причем Вася (он начинает) за ход режет один провод, а Петя – либо два, либо три провода. Хулиган, отрезающий последний провод от какого-либо контакта, проигрывает. Кто из них выигрывает при правильной игре?
В кабинете президента стоят 2004 телефона, любые два из которых соединены проводом одного из четырёх цветов. Известно, что провода всех четырёх цветов присутствуют. Всегда ли можно выбрать несколько телефонов так, чтобы среди соединяющих их проводов встречались провода ровно трех цветов?
В нашем распоряжении имеются 32k неотличимых по виду монет, одна из которых фальшивая– она весит чуть легче настоящей. Кроме того, у нас есть трое двухчашечных весов. Известно, что двое весов исправны, а одни– сломаны (показываемый ими исход взвешивания никак не связан с весом положенных на них монет, т.е. может быть как верным, так и искаженным в любую сторону, причем на разных взвешиваниях– искаженным по-разному). При этом неизвестно, какие именно весы исправны, а какие сломаны. Как определить фальшивую монету за 3k + 1 взвешиваний?
|
|
 |
Условие
В нашем распоряжении имеются 32k неотличимых по виду монет, одна из которых фальшивая– она весит чуть легче настоящей. Кроме того, у нас есть трое двухчашечных весов. Известно, что двое весов исправны, а одни– сломаны (показываемый ими исход взвешивания никак не связан с весом положенных на них монет, т.е. может быть как верным, так и искаженным в любую сторону, причем на разных взвешиваниях– искаженным по-разному). При этом неизвестно, какие именно весы исправны, а какие сломаны. Как определить фальшивую монету за 3k + 1 взвешиваний?
Решение
Будем обозначать фальшивую монету ФМ.
Пусть ФМ находится среди 3d монет. Заметим, что если мы положим на чашки исправных весов по 3d–1 монет, то при любом исходе взвешивания число монет, которые могут оказаться фальшивыми, окажется равным 3d–1.
Лемма.
Из 32k монет за 3k взвешиваний можно либо найти фальшивую, либо найти три монеты, среди которых находится фальшивая, и при этом найти одни исправные весы.
Индукция по k.
База при k = 1. Расположим монеты в виде квадрата 3×3. Занумеруем его строки и столбцы цифрами от 1 до 3, а монеты – соответственно парами этих цифр; например, монета в первой строке и втором столбце получит номер 12.
Сравним монеты первой и второй строчек на первых весах; затем сравним монеты первого и второго столбца на вторых весах. Предположим, что первые и вторые весы исправны. Тогда в любом случае эти взвешивания позволяют однозначно определить ФМ. Можно считать, что это – монета 11.
Тогда, если сломаны первые весы, то ФМ находится в первом столбце, а если вторые – то в первой строке.
Третьим взвешиванием на последних весах сравним 12 + 13 с 21 + 31.
Если весы в равновесии, то ФМ может оказаться только 11; зато мы не знаем, какие весы сломаны. Пусть одна из чаш оказалась легче (например, 12 + 13). Это означает, что
показания третьих весов противоречат показаниям вторых, а тогда первые весы – исправные, и мы нашли три монеты (лежащие в первой строке), среди которых обязана быть ФМ.
Переход. Пусть k > 1, и у нас есть 3k монет. Объединим их в группы по 9 штук, назвав каждую новой монетой. По предположению индукции, мы можем за 3k – 3 выяснить либо фальшивую среди этих 32(k – 1) монет, либо найти исправные весы и три новых монеты, среди которых есть фальшивая.
В первом случае, пользуясь утверждением базы индукции для этих 9 монет (составляющих найденную новую монету), мы можем за 3 взвешивания сделать требуемое.
Во втором мы получили исправные весы и 27 кандидатов на фальшивую монету. Тогда за следующие 3 взвешивания на исправных весах мы уменьшим количество кандидатов до 9, до 3 и до 1, то есть найдем фальшивую. Переход, а вместе с ним и лемма, доказаны.
Теперь легко получить решение задачи. Сделаем 3k взвешиваний согласно лемме. Если мы уже нашли фальшивую монету, то мы совершили требуемое. Иначе мы нашли исправные весы и 3 монеты, среди которых есть фальшивая. Тогда за последнее взвешивание на этих весах мы из этих 3 монет найдем фальшивую.
Улучшив процедуру, можно добиться даже меньшего числа взвешиваний. Например, можно показать, что из 3n(n + 1) монет фальшивая находится за (n + 1)2 взвешиваний.
