Федотов Валерий Павлович (matholimp) wrote,
Федотов Валерий Павлович
matholimp

Categories:

Решения задач 1 тура олимпиады "Третье тысячелетие" для 11-12 классов

Условия – на http://matholimp.livejournal.com/1412408.html .



1. Каждый из трех землекопов, работая в одиночку, может вырыть траншею за целое число дней. А если ту же траншею они будут рыть все втроем, на это у них уйдет соответственно на 2, 5 и 10 дней меньше, чем при рытье вдвоем (т.е. без первого, второго и третьего соответственно). За сколько дней может выкопать яму самый медленный из них?
Решение.
Обозначим время, за которое все трое суммарно выкопают траншею, за t (дней). Тогда их суммарная производительность равна 1/t. Производительность пар, согласно условию, равна 1/(t+2), 1/(t+5) и 1/(t+10). Если сложить производительность пар, то получится удвоенная общая производительность (как если бы копали два первых, два вторых и два третьих землекопа): 1/(t+2) + 1/(t+5) + 1/(t+10) = 2/t.
Отсюда t/(t+2) + t/(t+5) + t/(t+10)=2;
вычитая 1 из каждой дроби, получаем равносильное уравнение
1/(t+2) + 1/(t+5) + 1/(t+10)=1.
Угадываем один из корней этого уравнения: t=10. Других положительных корней уравнение иметь не может, поскольку каждая дробь при положительном t убывает.
Таким образом, все трое выроют траншею за 10 дней. Суммарная производительность троих равна 1/10 траншеи в день, а суммарная производительность двух самых быстрых – 1/12 траншеи в день. Производительность самого медленного равна 1/10-1/12=1/60 траншеи в день.
Ответ: за 60 дней. (А два других — за 20 и 30 дней)
Примечание. Условие о целочисленности не используется, но наводит на мысль о подборе корней.

2. Андрей перемножил два последовательных натуральных числа и получил в некоторой системе счисления двузначное число, записываемое двумя последовательными цифрами, не превосходящими 9. Найдите эти цифры.
Решение. Пусть d – основание системы счисления, а р и р+1 − искомые числа. Прежде всего, заметим, что р≤d , иначе запись р(р+1) в этой системе счисления имела бы не менее трёх цифр.
Пусть с и с+1 − искомые цифры. Тогда р(р+1)=сd+с+1 , откуда р2+р−1=с(d+1) .
Сразу напрашивается вариант с=1 с d= р2+р−2. Подходящее d можно подобрать для любого целого р>1 , но р(р+1) всегда будет записываться как 12.
Постараемся найти с>1 . Прежде всего, так как р(р+1) чётно, то р2+р−1 нечётно. Поэтому с не может быть чётным.
Если р(р+1) делится на 3, то р2+р−1 не делится на 3. В противном случае р даёт при делении на 3 остаток 1, а р+1 даёт при делении на 3 остаток 2. В этом случае р(р+1) даёт при делении на 3 остаток 2. Значит, р2+р−1 не делится на 3 ни при каком целом р. Поэтому с тоже не может делиться на 3.
Аналогично можно показать, что с не может делиться на 7.
Из цифр от 0 до 9 остаётся только 5. Она подходит. Кроме 7∙8=56, есть примеры и в других системах счисления. Например, 17∙18=306 записывается как 56 в системе счисления с основанием 60.
Ответ: 12 или 56.


3. Костя выписал на доску 30 последовательных членов арифметической прогрессии с разностью 2061. Докажите, что в ней содержится не более 20 точных квадратов.
Решение. Смотрим на последнюю цифру. На каждом шаге она увеличивается на 1, но в случае точных квадратов она не может быть равна 2, 3, 7 и 8. Значит, 4 из каждых 10 последовательных членов арифметической прогрессии с разностью 2061 заведомо не являются точными квадратами. Следовательно, точных квадратов заведомо не может быть больше 18.

4. Вещественные числа x и y таковы, что x4y2+x2+2x3y+6x2y+8≤0 . Докажите, что x≥−1/6.
Решение. Если x≤-1/6, то дискриминант этого квадратного трехчлена относительно y отрицателен. Следовательно, трехчлен принимает только положительные значения.


5. Маша красит клетки белой доски 10х10. Она может покрасить любой вертикальный ряд клеток синей краской или любой горизонтальный ряд красной краской (каждый ряд красят не более одного раза). Если синяя краска ложится поверх красной, получается синяя клетка, а если красная поверх синей, то краски вступают в реакцию и обесцвечиваются, получается белая клетка. Может ли на доске оказаться 33 красных клетки?
Решение. Достаточно заметить, что в любой момент можно так переставить строки и столбцы на доске, чтобы красные клетки образовали прямоугольник. Его площадь была бы равна 33 только в случаях 1х33 или 3х11. Но ни тот, ни другой не помещаются внутри квадрата 10х10.
Ответ: Нет.

6. Можно ли утверждать, что log√a (a+1)+ loga+1(√a) ≥√6 при a>1 ?
Решение. Прежде всего, нужно заметить, что слагаемые – взаимно обратные величины. Поэтому чем дальше они от 1, тем больше их сумма. Если в первом слагаемом заменить а+1 на а, то оно станет равно 2. Следовательно, сумма не может быть меньше, чем 2+0.5, что больше √6 .
Ответ: Да, неравенство верно.

7. Докажите, что количество способов разрезать прямоугольник 200х3 на домино (прямоугольники 1х2) делится на 3.
Решение. Рассмотрим какое-либо разбиение прямоугольника 2Кх3 на доминошки 1х2. Направим по сторонам прямоугольника оси координат. Координатами доминошки считаем координаты её левого нижнего угла. Занумеруем доминошки в порядке возрастания их абсцисс, а при равных абсциссах − в порядке возрастания их ординат.
Составим шифр разбиения в виде числа из 3К цифр, соответствующих доминошкам в порядке их нумерации. Если доминошка повёрнута в направлении оси абсцисс, то в соответствующем ей разряде запишем 1, а в противном случае – 2. Например, при К=1 возможны разбиения с шифрами 111, 122 и 212.
Будем говорить, что разбиение имеет разрез, если прямоугольник распадается на два меньших по целым доминошкам. Разрезы могут быть горизонтальными (в направлении оси абсцисс) или вертикальными. Если разбиение имеет горизонтальный разрез, но не имеет вертикальных, то его шифр имеет вид 1211…112 или 2111…112 (где вместо многоточия стоят только единицы).
Вертикальный разрез появляется после группы цифр любого из этих двух видов, либо после 111 (третий вид). Шифр разбиения распадается на такие группы цифр, отвечающие фрагментам разбиения между разрезами. Поэтому двойки в составе шифра можно сгруппировать в пары, отвечающие фрагментам разбиения между разрезами. Вторая из них («замыкающая» фрагмент) всегда стоит в разряде, номер которого делится на 3. А первая («открывающая» фрагмент) имеет меньший номер, не делящийся на 3.
Итак, задача свелась к подсчёту числа 300-значных шифров нужного вида. Чтобы получить приемлемый шифр, нужно сначала выбрать некоторое множество «замыкающих» разрядов, номера которых делятся на 3, а затем на каждом промежутке между двумя соседними «замыкающими» разрядами выбрать по одному «открывающему», номер которого не делится на 3.
Прежде всего, заметим, что заведомо делится на 3 количество разбиений, в составе которых имеется хотя бы один «короткий» фрагмент, занимающий 3 разряда. Действительно, выберем из коротких фрагментов самый первый; вне зависимости от заполнения остальных фрагментов, для него возможны 3 варианта: 111, 122 и 212.
Также заведомо делится на 3 количество разбиений, в составе которых нет коротких фрагментов, но при этом имеется не менее трёх фрагментов, не все одинаковой длины. Переставляя эти фрагменты, такие разбиения можно сгруппировать в группы, причём количество разбиений в каждой группе будет делиться на три (например, для трёх фрагментов — три или шесть разбиений в каждой группе).
Остались неучтёнными:
* 2 разбиения без вертикальных разрезов;
* 97 способов выбрать один вертикальный разрез на 2 фрагмента, для каждого из которых возможны 2 варианта заполнения; всего их 97∙4=388;
* случай фрагментов равной длины. Длина должна быть кратным 3 делителем 300, не меньше 6 и не больше 100. Так как для каждого фрагмента возможны 2 варианта заполнения, то число таких разбиений складывается из степеней двойки, показатели которых равны числу фрагментов, т.е. служат (некратными 3) дополнительными делителями 300. Легко проверить, что два из них нечётны (значит, нужные степени дадут остаток 2 при делении на 3), а ещё пять чётны (степени дадут остаток 1).
Суммирование последних чисел приводит к нужному выводу.


8. Случайным образом выбираются 3 числа от 1 до N и располагаются в порядке возрастания. С какой вероятностью они образуют арифметическую прогрессию?
Решение. Обозначим (с учётом очерёдности выбора!) первое число через X, второе – через Y, а третье – через Z. Всего имеется N3 равновероятных вариантов (X, Y, Z). Геометрически им соответствуют целочисленные точки куба 1≤ X, Y, Z ≤ N .
Чтобы эти числа образовали арифметическую прогрессию, среднее по величине должно быть равно полусумме двух оставшихся. Рассмотрим, как плоскость X+Y=2Z (отвечающая случаю, когда средним по величине является Z) пересекается с кубом 1≤ X, Y, Z ≤ N . Сечением служит ромб с вершинами (1, 1, 1), (0, N, N/2), (N, N, N) и (0, N/2, N). Если (X, Y, Z) – какая-то точка в этом сечении, то (X, Y, 0) – её проекция на плоскость Z=0 . Поэтому вместо подсчёта точек сечения, все три координаты которых целые числа, достаточно найти число точек квадрата 1≤ X, Y≤ N , для которых X+Y чётно. Это одна точка с X+Y=2, три точки с X+Y=4, пять с X+Y=6 и т.д. Никуда не уйти от рассмотрения двух случаев разной чётности N.
Если N=2K – чётно, то последними перед главной диагональю будут К точек с X+Y=2К (=N), после чего все варианты повторятся в обратном порядке. Суммарное число точек 2К2 .
Если N=2K+1 – нечётно, то к предыдущей сумме добавляются N точек главной диагонали. Суммарное число точек 2К2 +2K+1.
Найденное значение нужно сначала утроить (так как средним по величине может оказаться любое из трёх чисел), а затем из полученного вычесть 2N (так как точки главной диагонали куба X=Y=Z были учтены трижды). Получим 6К2−4К для N=2K и 6К2+2К+1 для N=2K+1. Если использовать квадратные скобки для обозначения целой части числа, то оба случая можно объединить одной формулой [3N2/2]−4[N/2] .

Ответ: вероятность равна ([3N2/2]−4[N/2])/ N3 .


9. Треугольники АВС и А1В1С1 таковы, что sin A = cos A1 , sin B = cos B1 , sin C=cosC1 . Найдите наибольший из шести углов.
Решение. Начнём с того, что синусы всегда положительны. Косинусы же положительны только для острых углов. Поэтому треугольник А1В1С1 остроугольный. Если треугольник АВС тупоугольный, то наибольшим окажется какой-то из его углов. Не теряя общности считаем, что тупой угол – А. Тогда условие сводится к соотношениям: A= 90°+A1, В= 90°−В1, С= 90°−С1. Вычитаем из первого равенства два других, выделяем в итоговом соотношении суммы углов каждого треугольника и заменяем их на 180°. После упрощений находим А=135° .
Если же оба треугольника остроугольные, то A= 90°−A1 , В= 90°−В1 , С= 90°−С1 , в результате общая сумма шести углов равна 270°, что невозможно.
Ответ: 135° .


10. Пусть d(k) – число делителей натурального числа k, а квадратные скобки означают целую часть вещественного числа. Докажите, что числа и имеют одинаковую чётность.
Решение. Ключевая идея: нечётное число делителей имеют все точные квадраты и только они (если число не является точным квадратом, то его делители естественным образом разбиваются на пары, тогда как у √n нет пары). Поэтому по мере добавления новых слагаемых перемена чётности суммы будет происходить в те же самые моменты, когда целая часть корня увеличится на 1.
Tags: олимпиада
Subscribe

promo matholimp november 26, 17:30 55
Buy for 10 tokens
Дистанционное обучение внезапно оказалось в тренде. Поэтому пишут о нём сейчас все, кому не лень, вплоть до вездесущего Онищенко. В итоге громкое большинство минимум в 99% составляют публикации несведущих профанов. А 9 из 10 написанных педагогами статей о дистанционном обучении явно свидетельствуют…
  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 0 comments