Агаханов Х.В. Окружной и финальный этапы
 Скачать 3 Mb.
|
|
520. Ответ. За пятьвопросов. Для нахождения искомого порядка a 1 , a 2 , . . . , расположения чисел в строке необходимо, чтобы каждая из пар (a i , a i+1 ) , i = 1, 2, . . . , 99, встречаласьхотя бы водном из наборов, о которых задают вопросы, в УЧЕБНЫЙ ГОД, 11 КЛАСС 319 противном случае для двух последовательностей a 1 , . . . , a i , a i+1 , . . . , и a 1 , . . . , a i+1 , a i , . . . , все ответы будут одинаковы. Докажем, что после любых двух заданных вопросов может возникнутьситуация, когда для охвата всех пар соседних чисел (еще не охваченных) потребуется задать еще не менее трех вопросов. Пусть k 1 , k 2 , . . . , k 50 — порядок расположения чисел, про которые задан первый вопрос, k 1 , k 2 , . . . , k 50 — порядок расположения чисел, про которые задан второй вопрос. Построим набор, a 2 , . . . , a 100 , для которого мы не сможем, задав еще два вопроса, однозначно установитьпорядок расположения в нем чисел. Рассмотрим ситуацию, когда все числа, названные как в первом, таки во втором вопросе, оказалисьв ответах на одних и тех же местах. В качестве искомого набора возьмем набору которого k i , k i ∈ ∈ {a 2i−1 , a 2i }, i = 1, 2, . . . , 50, и, кроме того, в каждой четверке, a 4m−2 , a 4m−1 , a 4m ) , m = 1, 2, . . . , 25, в первых двух вопросах не было сравнений соседних пар чисел из этой четверки. Покажем, что такой набор существует. Пусть X — множество чисел, не встречавшихся в первых двух вопросах. Возможны случаи 1) k 2m−1 = k 2m−1 , k 2m = k 2m , 2) k 2m−1 = k 2m−1 , k 2m = k 2m , 3) k 2m−1 = k 2m−1 , k 2m = k 2m , 4) k 2m−1 = = k 2m−1 , k 2m = Для этих случаев построим четверки (a 4m−3 , a 4m−2 , a 4m−1 , следующим образом 1) (k 2m−1 , ∗, ∗, k 2m ) , 2) (k 2m−1 , ∗, k 2m , k 2m ) , 3) (k 2m−1 , k 2m−1 , k 2m , k 2m ) , 4) (k 2m−1 , k 2m−1 , ∗, k 2m ) , где в качестве ∗ можно взятьлюбое из чисел множества X, не встречавшееся в вопросах и при построении предыдущих четверок. Тем самым показано, что после двух вопросов возможна (независимо от желания спрашивающего) ситуация, когда ни одна из пар (a i , при, не кратном 4, не охвачена. Каждое из 100 чисел входит при этом хотя бы в одну неохваченную пару, и, следовательно, должно фигурировать по крайней мере водном из последующих вопросов. Допустим, что в данной ситуации за два вопроса можно охватить все неохваченные пары тогда каждое из 100 чисел должно фигури- роватьровно водном из таких вопросов. Рассмотрев четверки вида, a 4i−2 , a 4i−1 , a 4i ) , i = 1, 2, . . . , 25, заметим, что если одно из чисел такой четверки будет фигурироватьв вопросе, то и остальные три тоже (иначе не все пары соседних чисел в этой четверке будут охвачены. Но тогда количество чисел в наборе, о котором задается вопрос, должно делиться на 4. Поскольку 50 не делится на 4, то имеем противоречие. Итак, за 4 вопроса наверняка определитьрасположение чисел 1, 2, . . . , 100 в строке нельзя. Покажем, как сделать это за 5 вопросов ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ Первый вопрос задаем про набор M 1 = {1, 2, . . . , 50}, второй — про набор M 2 = {51, 52, . . . , 100}. Набор будет состоятьиз 25 самых левых чисел набора и 25 самых левых чисел набора M 2 , а набор M 4 — из 25 самых правых чисел набора и 25 самых правых набора Ответ на вопрос о наборе определит, очевидно, числа a 1 , a 2 , . . . , а о наборе M 4 — числа a 76 , a 77 , . . . , a 100 . Пятым вопросом определяем расположение остальных 50 чисел в искомой строке г класс. Пусть P (x) = ax 2 +bx+c . Тогда (P (xy)) 2 −P (x 2 )P (y 2 ) = (ax 2 y 2 + + bxy + c) 2 − (ax 4 + bx 2 + c)(ay 4 + by 2 + c) = a 2 x 4 y 4 + b 2 x 2 y 2 + c 2 + + 2abx 3 y 3 + 2acx 2 y 2 + 2bcxy − a 2 x 4 y 4 − b 2 x 2 y 2 − c 2 − abx 2 y 2 (x 2 + y 2 ) − − ac(x 4 + y 4 ) − bc(x 2 + y 2 ) = abx 2 y 2 (2xy − x 2 − y 2 ) + ac(2x 2 y 2 − x 4 − − y 4 ) + bc(2xy − x 2 − y 2 ) = −abx 2 y 2 (x − y) 2 − ac(x 2 − y 2 ) 2 − bc(x − При a 0, b 0, c 0 все три слагаемых в последнем выражении неположительны, откуда и следует неравенство (P (xy)) 2 P (x 2 )P Замечание. Утверждение задачи остается справедливым для произвольного многочлена с неотрицательными коэффициентами. Пусть O — центр поворота, R — наибольшее из расстояний от точки до вершин многоугольника, A 1 — одна из вершин, такая, что OA 1 = = R . Если переходит при повороте в вершину A 2 , A 2 — в A 3 , A 3 — в, то, очевидно, A 1 A 2 A 3 A 4 — квадрат с центром в точке O; этот квадрат, очекидно, лежит в M. Отношение радиусов его вписанного и описанного кругов равно, при этом первый лежит в M, а второй содержит M по определению R, что и требовалось. Замечание. Справедливо следующее утверждение если выпуклый многоугольник M переходит в себя при повороте на угол α (α < то найдутся два круга с отношением радиусов, равным 2, один из которых содержит M, а другой содержится в M. Попробуйте доказатьего самостоятельно. Для удобства вместо боковой поверхности параллелепипеда a×b× ×c рассмотрим боковую поверхностьцилиндра высоты c и длиной окружности основания 2(a + b), разбитую на единичные квадраты линиями, параллельными окружностям оснований и образующими. (Для того чтобы превратить квадраты в квадраты, их следует разогнуть.) Проведем плоскостьчерез осьсимметрии цилиндра и через центры единичных квадратов в каком-нибудьстолбце S ширины 1 и высоты c на поверхности цилиндра. Докажем, что никакая оклейка прямоуголь- УЧЕБНЫЙ ГОД, 9 КЛАСС 321 никами, состоящими из четного числа единичных квадратов, удовлетворяющая условию задачи, несимметрична относительно этой плоскости. Действительно, в противном случае столбец S оказался бы покрыт прямоугольниками нечетной ширины. Площадь (а, значит, и высота) каждого из этих прямоугольников четна, что противоречит нечетности высоты столбца Итак, все способы оклейки можно разбитьна пары переходящих друг в друга оклеек (при симметрии относительно указанной плоскости, значит, их число четно. Ответ. Всем, кроме, бытьможет, одного. Ясно, что мудрец, стоящий в колонне последним, может спастись только случайно, ведь его колпака не видит никто из мудрецов. Но он может спасти всех остальных, сообщив им четность числа белых колпаков, надетых на них (по договоренности он скажет белый , если это число нечетно и черный в противном случае. Теперьмудрецы должны вы- числятьи называтьцвета своих колпаков по порядку от предпоследнего к первому сначала предпоследний, видя колпаки впереди стоящих и зная четностьчисла белых колпаков (среди колпаков впереди стоящих и своего, легко определит цвет своего колпака и назовет его затем мудрец, стоящий передним, зная цвета всех тех же колпаков, кроме своего (передние он видит, а про задний только что услышал, почетности может опреде- литьцвет своего колпака и назватьего. Остается продолжатьописанную процедуру до тех пор, пока первый мудрец не определит цвет своего колпака. Ответ. Нет. Допустим противное такие b и c нашлись. Тогда, если k и l — корни уравнения x 2 + bx + c = 0 , аи корни уравнения 2x 2 + (b + 1)x + + c + 1 = 0 , то по теореме Виета k + l = −b, (1) kl = c, (2) 2(m + n) = −b − 1, (3) 2mn = c + Из (4) видно, что c — целое нечетное число. Поэтому из (2) числа k и l оба нечетные, а сумма их (равная −b) — целое четное число. Но тогда число − 1) нечетно и равенство (3) невозможно. Противоречие. Объединим учеников в группы по фамилиями в группы по именам (возможны группы, состоящие из одного человека — например, ученик без однофамильцев. Каждый войдет в две группы — по фамилии и по имени. Из условия задачи следует, что в классе ровно одиннадцатьгрупп. ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ Действитель но, есть группы, состоящие из 1, 2, . . . , 11 человек, поэтому групп не меньше одиннадцати, ноте. мы уже сосчитали каждого ученика дважды, значит, больше групп нет. Рассмотрим группу из одиннадцати человек (скажем, однофамильцев). Остальных групп, ив частности групп тезок, не более десяти. Поэтому какие-то двое из одиннадцати входят в одну группу тезок, те. у них одинаковы и имя, и фамилия. A B C N M K E D H F Рис. 245 527. Пустьпрямые AD и пересекают прямую BC в точках и H соответственно (см. рис. 245). Достаточно доказать, что DE — средняя линия треугольника. Треугольник равнобедренный (BM = = BN ) и MN AH, поэтому N H — равнобедренная трапеция, те. Аналогично доказывается, что F N = = AK . Так как AK = AM, то из полученных равенств следует, что F N = NH, те середина F Тогда D — середина AF , а E — середина AH. 528. Ответ. Пример расстановки, для которой S = 106, приведен на рис. 246. 46 55 47 54 48 53 49 52 50 51 60 41 59 42 58 43 57 44 56 45 36 65 37 64 38 63 39 62 40 61 70 31 69 32 68 33 67 34 66 35 26 75 27 74 28 73 29 72 30 71 80 21 79 22 78 23 77 24 76 25 16 85 17 84 18 83 19 82 20 81 90 11 89 12 88 13 87 14 86 15 6 95 7 94 8 93 9 92 10 91 100 1 99 2 98 3 97 4 96 Рис. Докажем теперь, что S 106 для любой расстановки чисел в таблице. Нам понадобится следующая лемма. Лемма. Если в прямоугольнике 2 × 10 отмечено n 9 попарно несоседних клеток, то число (неотмеченных) клеток прямоугольника, соседних с отмеченными, больше n. УЧЕБНЫЙ ГОД, 10 КЛАСС 323 Д ока за тел ьс т во. В каждом из 10 прямоугольничков 1 × 2, длинные стороны которых параллельны коротким сторонам прямоугольника 10, отмечено не более одной клетки. Если одна клетка в таком прямо- угольничке отмечена, то другая — неотмеченная, соседняя с отмеченной. Тем самым уже имеем n таких клеток, а поскольку n 9, то (при n найдется, очевидно, и клетка, принадлежащая прямоугольничку 1 × 2 без отмеченных клеток, граничащая с отмеченной клеткой соседнего прямо- угольничка 1 × 2. Следовательно, общее число неотмеченных клеток, соседних с отмеченными, больше n. Лемма доказана. Допустим, что S 105 для некоторой расстановки чисел. Стерев все числа в таблице, будем вписыватьих на прежние места, начиная с числа в порядке убывания. Выделим в таблице пятьнеперекрывающихся горизонтальных полос 2 клетки и пятьнеперекрывающихся вертикальных полос 2 × 10 клеток. Зафиксируем число n 0 , после вписывания которого впервые либо в каждой горизонтальной, либо в каждой вертикальной полосе окажется не меньше одного вписанного числа соответствующий момент назовем критическим. Пустьуже вписаны 33 числа от 100 до 68, но естьпустые горизонтальная и вертикальная полосы. Те 64 клетки таблицы, которые не входят в эти полосы, можно разбитьна 32 прямоугольничка 1 × 2; хотя бы водном из них окажутся два вписанных числа с суммой, не меньшей, чем + 69 > 105 . Отсюда следует, что n 0 68, и все числа — несоседние. Заметим, что в критический момент в каждую из полос вписано меньше чисел (если бы нашлась, например, горизонтальная полоса, в которую вписано ровно 10 чисел, то перед вписыванием числа в ней было бы не меньше 9 чисел, в силу чего в каждой из вертикальных полос было бы минимум по одному числу, что противоречит определению числа Поэтому к полосам того направления, в которых в критический момент оказалосьхотя бы по одному числу, можно применитьлемму. Поскольку в критический момент в таблицу вписано 101 − чисел, из леммы следует, что у клеток, куда они вписаны, естьне менее (101 − n 0 ) + + 5 = 106 − пустых соседних. Нам предстоит, таким образом, вписать в таблицу число, которое не меньше, чем 106−n 0 , причем рядом с числом, которое не меньше, чем n 0 . Сумма этих двух чисел будет не меньше, чем n 0 + n 0 = 106 , что противоречит нашему предположению о том, что 105. 10 класс. Ответ. (±1; 0); (±4; 3); (±4; Правая часть неотрицательна, так как равна квадрату, следовательно 0, откуда левая частьне меньше (2y − 1) 2 , так как модульразности ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ОЛИМПИАДЫ. ОТВЕТЫ И РЕШЕНИЯ y 2 и любого квадрата целого числа (если y 0 и квадраты различны) не меньше |2y − 1|. Имеем (2y − 1) 2 1 + 16y, откуда y 5. Итак, правая частьможет приниматьзначения 1, 17, 33, 49, 65, 81, из них квадратами являются только 1, 49, Рассмотрим 3 случая = 0, (x 2 ) 2 = 1, откуда = ±1, y = 0. 2) % y = 3, (x 2 − 9) 2 = 49, откуда = 3, x 2 = 16, x 2 = те, откуда = 5, x 2 = 34, x 2 = те. Докажем утверждение от противного. Пустьестьраскраска, при которой отсутствует пара параллельных линий с одинаковым числом черных клеток. Будем называть весом линии количество черных клеток на ней. Пустьестьгоризонтальвеса n. Тогда n вертикалей и n диагоналей каждого направления должны иметь веса 1, 2, . . . , n, так как все они пересекают эту горизонталь. Тогда и n горизонталей имеют веса 1, 2, . . . , так как все они пересекают вертикальвеса Циклически переставим горизонтали и вертикали так, чтобы нижняя горизонтальи левая вертикальимели вес n свойства раскраски при этом не изменятся. Пронумеруем горизонтали снизу вверх от 0 до n − 1, а вертикали — от 0 до n − 1 слева направо. Каждая диагональпересекает по разу горизонтальи вертикальвеса поэтому диагонали веса 1 должны проходитьчерез клетку их пересечения клетку (0, 0). Итак, все клетки (i, i) и (n − i, i), i > 0, не закрашены. Если n нечетно, тов каждом столбце, кроме 0, получаем не менее двух незакрашенных клеток, и столбца веса n − 1 не найдется. Если n = 2m, то столбец m и строка m должны иметьвес n − 1 (в любой из остальных строки любом из остальных столбцов есть хотя бы две незакрашенные клетки. Тогда в них закрашены все клетки, кроме (m, и мы не сможем найти столбца веса Если с самого начала отсутствует горизонтальвеса n, то естьгоризон- тальвеса 0, и мы можем провести те же рассуждения, поменяв ролями закрашенные и незакрашенные клетки. Первое решение. Пусть N 1 — точка, симметричная точке относительно K см. рис. 247). Тогда KCN 1 = KDN, поэтому N и ∠N 1 CK = ∠NDK = π − ∠ABN. Заметим еще, что = π − ∠ABM. Складывая полученные равенства, находим, что УЧЕБНЫЙ ГОД, КЛАСС = ∠MBN. Кроме того, из условия следует, что CM = MB и = N те. и BN = CN 1 ). Значит, MCN 1 = MBN, откуда N 1 = M N . Отрезок MK — медиана в равнобедренном треугольнике N N 1 , поэтому ∠MKN = Рис. Второе решение. Это решение позволяет отказаться от дополнительного условия в задаче (о том, что точки C иле- жат по разные стороны от A), которое было задано лишьзатем, чтобы избежатьразбора различных случаев. Рассмотрим композицию поворотов R β M ◦R α N , где = ∠DNB, β = ∠BMC углы предполагаются ориентированными. Заметим, что α + β = ±180 ◦ , поэтому центральная симметрия относительно некоторой точки X. Но) = (R β M ◦ R α N )(D) = R β M (B) = поэтому X — середина отрезка CD, те. совпадает сточкой. Если Z K (N ) , тот. е. равнобедренный и ∠MKN = Замечание. Задача имеет много других решений. Например, можно воспользоваться подобием треугольников MEK и KF N, где E и F середины отрезков BC и BD соответственно. Эти треугольники имеют две пары взаимно перпендикулярных сторон EK и F N, ME и KF ; следовательно, перпендикулярны и их третьи стороны. Заметим, что количество сторон нашего многоугольника четно, так как его горизонтальные и вертикальные стороны чередуются. |