Тема №5915 Ответы к задачам по математике Дрозина (Часть 3)
Поиск задачи:

Рассмотрим тему Ответы к задачам по математике Дрозина (Часть 3) из предмета Математика и все вопросы которые связанны с ней. Из представленного текста вы познакомитесь с Ответы к задачам по математике Дрозина (Часть 3), узнаете ключевые особенности и основные понятия.

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

Ответы в самом низу встроенного документа

561. Поезду, в котором находится М пассажиров, предстоит
сделать N остановок.
а) Сколькими способами могут выйти пассажиры на этих
остановках?
б) Решите эту же задачу, если учитывается лишь количество
пассажиров, вышедших на каждой остановке. [7]
562. В кошельке лежит по 20 монет достоинством в 10, 15
и 20 копеек. Сколькими способами можно из этих 60 монет
выбрать 20? [7]
156 5. Систематизация нестандартных задач
563. Сколькими способами можно расположить в 9 лузах
7 белых и 2 черных шара? Часть луз может быть пустой, а лузы
считаются различными. [7]
ГРАФЫ
Четность
564. В некоторой стране из столицы выходит 89 дорог, из
города Дальний —1 дорога, из остальных 1988 городов —по
20 дорог. Доказать, что из столицы можно проехать в Дальний. [9]
565. В графе из любой вершины выходит по 3 ребра. Может
ли в нем быть 1990 ребер? [9]
566. Доказать, что число штатов США с нечетным числом
соседей четно.
567. Существует ли ломаная, пересекающая все ребра кар­
тинки Ь-ЧЧ по одному разу? [9]
568. Можно ли составить решетку, изображенную на рис. 13:
а) из 5 ломаных длины 8? б) из 8 ломаных длины 5? (Длина
стороны клетки равна 1.) [7]
569. На плоскости дано 100 окружностей, состав­
ляющих связную (т. е. не распадающуюся на части)
фигуру. Докажите, что эту фигуру можно нарисовать,
не отрывая карандаша от бумаги и не проводя дважды
одну и ту же линию. [7]
570. На ребрах связного графа стрелки расставле­
ны так, что для каждой вершины числа входящих и
выходящих ребер равны. Докажите, что, двигаясь по стрелкам,
можно добраться от любой вершины до любой другой. [7]
Рис. 13
Формула Эйлера
571. В стране Озерная 7 озер, соединенных между собой
10 каналами, причем от любого озера можно доплыть до любого
другого. Сколько в этой стране островов? [7]
235 572*. В квадрате отметили 20 точек и соединили их непере-
секающимися отрезками друг с другом и с вершинами квадрата
так, что квадрат разбился на треугольники. Сколько получилось
треугольников? [7]
573. Грани некоторого многогранника раскрашены в два цвета
так, что соседние грани имеют разные цвета. Известно, что все грани,
кроме одной, имеют число ребер, делящееся на 3. Доказать, что
и эта одна грань имеет делящееся на 3 число ребер. [9]
Восьмой класс 157
Связные графы
574. В стране любые два города соединены или железной доро­
гой, или авиалинией. Доказать, что один из видов транспорта
позволяет добраться из любого города в любой (т. е. если объ­
единение двух графов — полный граф, то один из них связен). [9]
575. 20 школьников решали 20 задач. Каждый решил ровно
две задачи, и каждую задачу решили ровно двое. Доказать, что
можно устроить разбор задач так, чтобы каждый рассказал одну
решенную им задачу. [9]
576. Из полного 100-вершинного графа выкинули 98 ребер.
Доказать, что он остался связным. [9]
577. В графе каждая вершина — синяя или зеленая. При этом
каждая синяя вершина связана с 5 синими и 10 зелеными, а
каждая зеленая —с 9 синими и 6 зелеными. Каких вершин
больше — синих или зеленых? [9]
578. В графе 100 вершин, причем степень любой из них не
меньше 50. Доказать, что граф связан. [9]
579. Есть 20 карточек, у каждой из которых на двух сторонах
написано по числу. При этом все числа от 1 до 20 написаны по
два раза. Доказать, что карточки можно разложить так, чтобы
все числа сверху были различны. [9]
580. В классе больше 30, но меньше 40 человек. Любой
мальчик дружит с тремя девочками, а любая девочка — с пятью
мальчиками. Сколько человек в классе? [9]
Ориентированные графы
581. В некотором государстве каждый город соединен с каж­
дым дорогой. Сумасшедший король хочет ввести на дорогах
одностороннее движение так, чтобы, выехав из любого города,
в него нельзя было вернуться. Можно ли так сделать? [7]
582. Докажите, что на ребрах связного графа можно так
расставить стрелки, чтобы из некоторой вершины можно было
добраться по стрелкам до любой другой. [7]
583. В связном графе степени всех вершин четны. Докажите,
что на ребрах этого графа можно расставить стрелки так, что­
бы выполнялись следующие условия: а) двигаясь по стрелкам,
можно добраться от любой вершины до любой другой; б) для
каждой вершины числа входящих и выходящих ребер равны. [7]
584. На ребрах связного графа стрелки расставлены так, что
для каждой вершины числа входящих и выходящих ребер рав-
158 5. Систематизация нестандартных задач
ны. Докажите, что, двигаясь по стрелкам, можно добраться от
любой вершины до любой другой. [7]
КОМБИНАТОРНАЯ ГЕОМЕТРИЯ
585. Доказать, что из девяти выпуклых шестиугольников
нельзя составить выпуклый 39-угольник. [1]
586. Существует ли на плоскости множество, состоящее из
1978 различных точек, таких, что для любых двух из них най­
дется третья, образующая с ними вершины равнобедренного
треугольника? [1]
587. Доказать, что 17-угольник нельзя разрезать на 12 таких
четырехугольников, что их вершины либо совпадают с верши­
нами 17-угольника, либо лежат внутри него, причем ни одна из
вершин какого-либо четырехугольника не может быть внутрен­
ней точкой стороны другого четырехугольника. [1]
588. Дана точка. Нарисуйте а) вокруг нее, б) вне ее много­
угольник так, чтобы ни одна его сторона не была видна из этой
точки полностью. [13]
589. Все клетки шахматной доски выкрашены в белый цвет.
По ней начинает гулять маляр, который, переходя в соседнюю
клетку (с общей стороной), перекрашивает ее (из белого —в
черный, а из черного —в белый). Может ли он гулять так,
чтобы покрасить клетки в шахматном порядке? [13]
ДЕВЯТЫЙ КЛАСС
АРИФМЕТИКА
Десятичная запись и признаки делимости
590. Найдите наименьшее натуральное число, делящееся на
36, в записи которого встречаются все 10 цифр. [7] ___ __
591. а) Дано шестизначное число abcdef, причем def — abc
делится на 7. Докажите, что и само число делится на 7. б) Сфор­
мулируйте и докажите признак делимости шестизначных чисел
на 7. в) Сформулируйте и докажите признак делимости шести­
значных чисел на 13. [7]
592. Может ли сумма нескольких первых натуральных чисел
оканчиваться на 1989? [7]
593. А — шестизначное число, в записи которого по одному
разу встречаются цифры 1, 2, 3, 4, 5, 6. Докажите, что А не
делится на 11. [7]
Девятый класс 159
594. Докажите, что разность числа, имеющего нечетное ко­
личество цифр, и числа, записанного теми же цифрами, но в
обратном порядке, делится на 99. [7]
595. Можно ли составить из цифр 2, 3, 4, 9 (каждую цифру
можно использовать сколько угодно раз) два числа, одно из
которых в 19 раз больше другого? [7]
596. Сумма двух цифр А и В делится на 7. Докажите, что
число АВА также делится на 7. [7]
597. Существует ли такое трехзначное число АВС, что
АВС - СВА является квадратом натурального числа? [7]
598. К числу справа приписывают тройки. Докажите, что
когда-нибудь получится составное число. [7]
Делимость и остатки. Остатки квадратов и кубов
599*. Докажите, что ни одно из чисел вида 103n+1 нельзя 194
представить в виде суммы двух кубов натуральных чисел. [7]
600. Из трехзначного числа вычли сумму его цифр. С по­
лученным числом проделали то же самое и так далее, 100 раз.
Докажите, что в результате получится нуль. [7]
601. Пусть А — сумма цифр числа 44444Ш, а В — сумма цифр
числа А. Найдите сумму цифр числа В. [7]
Периодические дроби
я 1000 993 602. Докажите, что дроби ^ и ^ имеют одинаковую
длину периодов. [13]
603. Найдите все шестизначные числа, которые увеличивают­
ся в целое число раз при перенесении последней цифры в начало.
Разложение на простые множители
604. Имеются 4 гири и двухчашечные весы без стрелки.
Сколько всего различных по весу грузов можно точно взвесить
этими гирями, если их можно класть только на одну чашку
весов; гири можно класть на обе чашки весов?
605. Вы имеете право сделать 4 гири любого веса. Какие
это должны быть гири, чтобы на весах из предыдущей задачи
можно было взвесить грузы от 1 до 40 кг?
606. Имеются две веревки. Если любую из них поджечь с од­
ного конца, то она сгорит за час. Веревки горят неравномерно.
Например, нельзя гарантировать, что половина веревки сгорает
за 30 минут. Как, имея две такие веревки, отмерить промежу-
160 5. Систематизация нестандартных задач
ток времени в 15 минут? Сколько промежутков времени (считая
нулевой) можно отмерить, имея три такие веревки?
607. С числом разрешается производить две операции: «уве­
личить в два раза» и «увеличить на 1». За какое наименьшее число
операций можно из числа 0 получить а) число 1 0 0 ; б) число и?
Алгоритм Евклида вычисления НОД
608. Решите уравнение 2х + Зу + 5г = 11 в целых числах. [7]
609. Фишка стоит на одном из полей бесконечной в обе
стороны клетчатой полоски бумаги. Она может сдвигаться на
т полей вправо или на п полей влево. При каких т и п
она сможет переместиться в соседнюю справа клетку? За какое
наименьшее число ходов она сможет это сделать? [7]
610. Можно ли сократить дробь при каком-нибудь
целом п, и если да, то на какое число? [13]
Решение уравнений в целых и натуральных числах
1) метод перебора и разложение на множители
_ 611. (2х+у)(5х + 3у) = 7. [7]
196 612*. ху=х+у+3. [7]
613. х2 = 14+у2. [7]
614. х2+у2=х+ у + 2. [7]
2) сравнения по модулю
196 615*. х 2 + У 2 = 4 z - I. [7]
196 616*. х3 + 21у2 + 5 = 0. [7]
617. 15х2-7 у 2 = 9. [7]
618. x2+y2 + z2 = 8t - 1. [7]
3) замена неизвестной
196 619*. Ът + 7 = 2". [7]
197 620*. 3-2т + 1 = л 2. [7]
4) неравенства и оценки
621. — + -j- + — = 1 . [7]
а Ь с
622. х2 - у 2 = 1988. [7]
Метод полной индукции
623. Докажите, что всякий (не обязательно выпуклый) мно­
гоугольник можно разделить на треугольники непересекающи-
мися диагоналями. [7]
Девятый класс 161
Указание. Индукция по числу сторон. Переход основан
на лемме о наличии у всякого многоугольника целиком лежа­
щей в нем диагонали. Такая диагональ делит многоугольник на
два с меньшим числом сторон.
624*. Известно, что X + — целое число. Докажите, что 204
л
при любом натуральном N число XN + тоже целое. [7]
625. Докажите, что правильный треугольник можно разре­
зать на N правильных треугольников для любого N, начиная с
шести. [7]
626. Докажите:
— !— + ____ I_____ + + _______ !_______ = — ~—
а{а + Ь) (а + Ь){а + 2Ь) (а + ( п - l)b)(a + nb) a{a + nb) '
где а и b — произвольные числа. [7]
627. Докажите:
от! (от+1)! (от + и)! _ (от + я+1)!
0! 1! “ и! я! (от +1) ’
где т, и = 0, 1, 2, ... [7]
«28. Докажите: = 2 !±L. ,7 ,
629. Докажите, что модуль суммы любого числа слагаемых
не превосходит суммы модулей этих слагаемых. [7]
630. Доказать неравенство (1 +х)" > 1 + пх, где х > — 1, 0 и
л = 2, 3, ... [7]
631. Доказать неравенство 1 ^ ^ , где 2>4-о-...-2л у2л+1
л —любое натуральное число. [7]
632. Докажите, что из любых 2Л+1 натуральных чисел можно
выбрать ровно 2” чисел, сумма которых делится на 2”. [7]
633. На окружности взяли N точек и соединили их все­
возможными отрезками. Оказалось, что никакие три из этих
отрезков не пересекаются в одной точке. На сколько частей
они делят круг? [7]
634. Даны несколько квадратов. Докажите, что их можно
разрезать на такие части, из которых удастся сложить один
квадрат. [7]
635. На какое наибольшее число частей могут разбивать
плоскость N окружностей? N треугольников? [7]
636. На плоскости нарисовано несколько окружностей. В
каждой из них проведено по хорде. Докажите, что получив-
162 5. Систематизация нестандартных задач
шуюся «карту» можно раскрасить тремя красками так, чтобы
любые две соседние области были покрашены разными цвета­
ми. [7]
Рациональные и иррациональные числа
637. Найдите первые 17 знаков в десятичной записи у чисел:
V2 +pL+ ; A /|40V2-57|-V40VlT57.
лб + д/2 + лб л/2-д/2-лб л б -з Я З л V v
638. Вычислите:
а) ^/20 + л/3 9 5 + ^2 0 -л/392; б) ^5^+7-^5^5-7;
в) -\Jx + 6^x- 9 + л]х-бл/х- 9 (9<х< 18).
639. Избавьтесь от иррациональности в знаменателе:
1 1
л/а + Л® + л/с ’ ^ + V o i + V5'
640. Представьте следующие числа в виде обычных и в виде деся­
тичных дробей: а) 0,(12)+ 0,(122); б) 0,(3)-0,(4); в) 0,(9)-0,(85).
641. Докажите, что число рационально тогда и только тогда,
когда оно представляется конечной или периодической деся­
тичной дробью.
642. Для каких натуральных п число — представляется ко- П
нечной десятичной дробью?
643. Пусть число а задается десятичной дробью:
« = 0,101001000100001000001...;
а = 0,123456789101112131415...
Будет ли это число рациональным?
644. Докажите, что в любой бесконечной десятичной дроби
можно так переставить цифры, что полученная дробь станет
рациональным числом.
645. Докажите иррациональность следующих чисел: a) fyl7;
б) л/2 + л/З.
ГЕОМЕТРИЯ
Неравенство треугольника. Против большего угла большая
сторона
646. В выпуклом многоугольнике одна из сторон равна 1,
а длины всех диагоналей — целые. Доказать, что число сторон
этого многоугольника меньше шести. [ 1]
Девятый класс 163
647. Через вершины А и С прямоугольника ABCD проведена
дуга окружности, целиком лежащая внутри прямоугольника.
Провести прямую, параллельную АВ, пересекающую ВС в точке
Р, AD в точке Q, а дугу АС в точке R так, чтобы сумма площадей
фигур AQR и CRP была минимальной. [1]
648. На сторонах АВ и CD параллелограмма ABCD найти
такие точки К и М, чтобы площадь четырехугольника, полу­
ченного при пересечении треугольников AM В и CKD, была
наибольшей. [1 ]
ЛОГИКА
Примут Дирихле
1) доказательство от противного
649. На квадратном столе лежат 100 механических часов.
Докажите, что в некоторый момент времени сумма расстояний
от центра стола до центров часов будет меньше, чем сумма
расстояний от центра стола до концов минутных стрелок. [4]
2) с дополнительными ограничениями
650. На конференции присутствуют 50 ученых, каждый из
которых знаком по крайне мере с 25 участниками конференции.
Докажите, что найдутся четверо из них, которых можно усадить
за круглый стол так, чтобы каждый сидел рядом со знакомыми
ему людьми. [7]
651. Каждый из 102 учеников одной школы знаком не ме­
нее, чем с 6 8 другими. Докажите, что среди них найдутся
четверо, имеющие одинаковое число знакомых. [7]
3) в связи с делимостью и остатками
652. Доказать, что для всякого простого р, не равного 2
или 5, существует такое к, что рк записывается в десятичной
системе одними единицами. [1]
653. Шахматист играет не менее одной партии в день и не
более 12 за календарную неделю. Докажите, что в течение года
найдутся несколько идущих подряд дней, за которые он сыграл
ровно 20 партий. [4]
654*. Докажите, что среди чисел, записываемых только еди- 209
ницами, есть число, которое делится на 1993. [12]
4) разбиение на ячейки (например, на шахматной доске)
655. Клетчатый лист бумаги размером 10 х 10 покрыт 55 квад­
ратиками, состоящими из 4 клеток. Докажите, что один из них
164 5. Систематизация нестандартных задач
можно убрать так, что оставшиеся будут по-прежнему покры­
вать всю доску. [4]
5) в геометрии
656. В квадрат со стороной 1 см поместили 1979 многоуголь­
ников, сумма площадей которых равна 1978,5 см2. Доказать, что
все многоугольники имеют общую точку. [1]
657. Внутри единичного квадрата расположена 51 точка. До­
казать, что среди них найдутся три, умещающиеся в круге
радиуса 1/7. [1]
658. На отрезке длины 10 несколько меньших непересека-
ющихся отрезков покрашены в красный цвет, причем никакие
две красные точки не находятся на расстоянии 1. Докажите,
что сумма длин закрашенных отрезков не превосходит 5. [4]
659. В квадрат 1x1 поместили несколько кругов, сумма ра­
диусов которых равна 3/5. Докажите, что есть прямая, парал­
лельная стороне квадрата, которая пересекает не менее двух
кругов. [4]
660. В окружности радиуса 1 проведено несколько хорд так,
что любой диаметр пересекает не более четырех из них. Дока­
жите, что сумма длин хорд не превосходит 13. [4]
Раскраски
1) шахматная раскраска
661. На шахматной доске стоят 8 ладей так, что они не
бьют друг друга. Докажите, что число ладей, стоящих на черных
полях, четно. [13]
2) замощения
662. При каких п квадрат пхп можно разбить на фигурки
вида: а) d b б) □£]? [9]
663. Доказать, что прямоугольник со сторонами, большими
1 0 0 и площадью, делящейся на 3, можно разбить на уголки.
664. Дно прямоугольной коробки вымощено плитками 1 х 4
и 2x2. Плитки высыпали из коробки, и одна плитка 2x 2
потерялась. Ее заменили плиткой 1 х 4. Докажите, что теперь
^_ дно коробки вымостить не удастся. [7]
211 665*. Можно ли доску размерами 4 х « обойти ходом ко­
ня, побывав на каждом поле ровно один раз, и вернуться на
исходное поле?
Девятый класс 165
6 6 6 . Доска 8 x 8 раскрашена в 4 цвета. При этом в любом
квадратике 2 x 2 встречаются все 4 цвета. Докажите, что угловые
клетки раскрашены в 4 различных цвета. [13]
3) виды раскрасок
667. Коробка имеет форму куба с ребром 6 см. Какое
наибольшее число прямоугольных параллелепипедов размером
1 х 4 х 4 см можно поместить в эту коробку так, чтобы их грани
были параллельны граням куба? [1 ]
4) четность
6 6 8 . Докажите, что не существует многогранника, у которого
число граней нечетно, и каждая грань имеет нечетное число
вершин. [1 ]
Инварианты
1) делимость
669. На столе лежит куча из 1001 камня. Ход состоит в
том, что из какой-либо кучи, содержащей более одного камня,
выкидывают камень, а затем одну из куч делят на две. Мож­
но ли через несколько ходов оставить на столе только кучки,
состоящие из трех камней? [7]
2) сумма или другая функция переменных
670*. На доске написаны числа 1, 2, 3, ..., 19, 20. Разре- 215
шается стереть любые два числа А и В и вместо них написать
число А + В - 1. Какое число может остаться на доске после
19 таких операций? [7]
671. На доске выписаны числа 1, 2, ..., 20. Разрешается сте­
реть любые два числа А и В и заменить их на число АВ+А + В.
Какое число может остаться на доске после 19 таких опера­
ций? [7]
3) правило крайнего
672. Докажите, что треугольник, все стороны которого мень­
ше 1 , можно поместить в квадрат со стороной 1 . [1 ]
673. В вершинах 100-угольника числа расставлены так, что
каждое равно среднему арифметическому своих соседей. Дока­
жите, что все они равны. [13]
4) полуинвариант
674. В клетках таблицы /ихи вписаны некоторые числа.
Разрешается одновременно менять знак у всех чисел одного
166 5. Систематизация нестандартных задач
столбца или одной строки. Докажите, что несколькими такими
операциями можно добиться того, чтобы суммы чисел в каждой
строке и в каждом столбце были неотрицательными. [13]
АНАЛИЗ
Метод разложения на разность
675. Докажите, что
1 - 1 I 3 I 5
п < vr+V2 + V2+V5 + V5+vm+ "-
...+ ■ г---- <п. [1] Л/(и— 1)2 + 1 + л/и2 + 1
676. Докажите, что 1-11 + 2-2! + . . . + w-/t! = (/i+ 1)1-1. [13]
ТЕОРИЯ МНОЖЕСТВ
Соответствие
677. На окружности даны 1987 точек. Рассмотрим всевоз­
можные выпуклые многоугольники с вершинами в этих точках.
Каких многоугольников больше: тех, которые содержат первую
точку, или тех, которые ее не содержат? [13]
КОМБИНАТОРИКА
Правило произведения. Выборки с повторениями и без
678. Сколькими способами можно выбрать из полной коло­
ды, содержащей 52 карты, 6 карт так, чтобы среди них были
представители всех четырех мастей? [7]
Размещения и сочетания. Свойства сочетаний
679. Ладья стоит на левом поле клетчатой полоски 1 х 30 и
за ход может сдвинуться на любое количество клеток вправо.
а) Сколькими способами она может добраться до крайнего
правого поля?
б) Сколькими способами она может добраться до крайнего
правого поля ровно за 7 ходов? [7]
680. На каждом борту лодки должно сидеть по 4 человека.
Сколькими способами можно выбрать команду для этой лодки,
Девятый класс 167
если есть 31 кандидат, причем 1 0 человек хотят сидеть на левом
борту лодки, 1 2 —на правом, а девяти безразлично, где си­
деть? [7}
681. Имеется куб размером 10 х 10 х 10, состоящий из ма­
леньких единичных кубиков. В центре О одного из угловых
кубиков сидит кузнечик. Он может прыгать в центр кубика,
имеющего общую грань с тем, в котором кузнечик находится в
данный момент, причем так, чтобы расстояние до точки О уве­
личивалось. Сколькими способами кузнечик может допрыгать
до кубика, противоположного исходному? [7]
Метод <*•перегородок» (сочетания с повторениями)
682. Сколькими способами 3 человека могут разделить меж­
ду собой 6 одинаковых яблок, один апельсин, одну сливу и
один мандарин? [7]
683. Сколькими способами 4 черных щара, 4 белых щара и
4 синих шара можно разложить в 5 различных ящиков? [7]
684. Общество из N членов выбирает из своего состава од­
ного представителя.
а) Сколькими способами может произойти открытое голосо­
вание, если каждый голосует за одного человека (быть может,
и за себя)?
б) Решите ту же задачу, если голосование тайное, т. е. учи­
тывается лишь число голосов, поданных за каждого кандидата,
и не учитывается, кто за кого голосовал персонально. [7]
685. Сколькими способами можно выложить в ряд 5 крас­
ных, 5 синих и 5 зеленых шаров так, чтобы никакие два синих
шара не лежали рядом? [7]
6 8 6 . Сколькими способами можно представить число
1 0 0 0 0 0 0 в виде произведения трех множителей, если произ­
ведения, отличающиеся порядком множителей, считаются раз­
личными? [7]
687. На полке стоит 12 книг. Сколькими способами мож­
но выбрать из них 5 книг, никакие две из которых не стоят
рядом? [7]
6 8 8 . Сколькими способами можно разложить 3 рублевых ку­
пюры и 10 полтинников в 4 различных пакета? [7]
Бином Ньютона и треугольник Паскаля
689. Докажите, что из п предметов четное число предметов
можно выбрать 2"~1 способами. [7]
168 5. Систематизация нестандартных задач
690. Докажите, что CJJ - С{п + С% -... + (-1 )"С" = 0. [7]
691. Докажите, что каждое число п в треугольнике Паска­
ля, уменьшенное на 1 , равно сумме всех чисел, заполняющих
параллелограмм, ограниченный теми правой и левой диагоналя­
ми, на пересечении которых стоит число и (сами эти диагонали
в рассматриваемый параллелограмм не включаются). [7]
ГРАФЫ
Эйлеровы графы
692. Докажите, что связный граф с 2п нечетными верши­
нами можно нарисовать, оторвав карандаш от бумаги ровно
п - 1 раз и не проводя никакое ребро дважды. [7]
693. Доказать, что связный граф можно обойти, проходя по
каждому ребру дважды. [9]
694. а) Из какого минимального числа кусков проволоки
можно спаять каркас куба?
б) Какой максимальной длины кусок проволоки можно вы­
резать из этого каркаса? [9]
Формула Эйлера
695. В стране любые два города соединены дорогой с одно­
сторонним движением. Доказать, что можно проехать по всем
городам, побывав в каждом по одному разу (т. е. что в полном
ориентированном графе есть гамильтонов путь). [9 ]
696. Докажите, что для плоского графа справедливо нера-
венство 2Р^ЗК. [7]
236 697*. Докажите, что для плоского связного графа справед­
ливо неравенство Р<32?-6. [7]
698. Докажите, что для любого плоского графа (в том числе
и несвязного) справедливо неравенство Р<32?-6. [7]
699. Можно ли построить три дома, вырыть три колодца и
соединить тропинками каждый дом с каждым колодцем так,
чтобы тропинки не пересекались? [7]
Связные графы
700. На конференции присутствуют 50 ученых, каждый из
которых знаком по крайне мере с 25 участниками конференции.
Докажите, что найдутся четверо из них, которых можно усадить
Девятый класс 169
за круглый стол так, чтобы каждый сидел рядом со знакомыми
ему людьми. [7]
701. Каждый из 102 учеников одной школы знаком не менее
чем с 6 8 другими. Докажите, что среди них найдутся четверо,
имеющие одинаковое число знакомых. [7]
Деревья
702. В графе все вершины имеют степень 3. Докажите, что
в нем есть цикл. [7]
703. Докажите, что при удалении любого ребра из дерева
оно превращается в несвязный граф. [7]
704*. В стране Древляндия 101 город и некоторые из них 233
соединены дорогами. При этом любые два города соединяет
ровно один путь. Сколько в этой стране дорог? [7]
705. Докажите, что связный граф, у которого число ребер
на единицу меньше числа вершин, является деревом. [7]
706*. Волейбольная сетка имеет вид прямоугольника разме- 233
ром 50 х 600 клеток. Какое наибольшее число веревочек можно
перерезать так, чтобы сетка не распалась на куски? [7]
707. В некоторой стране 30 городов, причем каждый соеди­
нен с каждым дорогой. Какое наибольшее число дорог можно
закрыть на ремонт так, чтобы из каждого города можно было
проехать в каждый? [7]
708. В стране 100 городов, некоторые из них соединены
авиалиниями. Известно, что от любого города можно доле­
теть до любого другого (возможно с пересадками). Докажите,
что можно побывать в каждом городе, совершив не более:
а) 198 перелетов; б) 196 перелетов. [7]
709. Дима нарисовал на доске 7 графов, каждый из которых
является деревом с 6 вершинами. Докажите, что среди них есть
два изоморфных. [7]
Теорема Рамсея о попарно знакомых
710. Собрались 18 человек. Доказать, что среди них найдется
либо 4 попарно знакомых, либо 4 попарно незнакомых (каждые
двое либо знакомы, либо незнакомы). [1 ]
711. В некоторой группе людей каждые два человека, име­
ющие поровну знакомых (в этой группе), не имеют общих
знакомых. Доказать, что либо в этой группе никто ни с кем не
знаком, либо кто-нибудь имеет одного знакомого. [1 ]
170 5. Систематизация нестандартных задач
712. Каждое из ребер полного графа с 6 вершинами покра­
шено в один из двух цветов. Докажите, что есть три вершины,
все ребра между которыми одного цвета. [7]
713. Каждое из ребер полного графа с 17 вершинами покра­
шено в один из трех цветов. Докажите, что есть три вершины,
все ребра между которыми одного цвета. [7]
714. В некоторой стране любые два города соединены либо
авиалинией, либо железной дорогой. Докажите, что:
а) можно выбрать вид транспорта так, чтобы от любого
города можно было добраться до любого другого, пользуясь
только этим видом транспорта;
б) из некоторого города, выбрав один из видов транспорта,
можно добраться до любого другого города не более, чем с од­
ной пересадкой (пользоваться можно только выбранным видом
транспорта);
в) каждый город обладает свойством из пункта б);
г) можно выбрать вид транспорта так, чтобы, пользуясь толь­
ко им, можно было добраться из любого города до любого
другого не более, чем с двумя пересадками. [7]
715. Ребра полного 6 -вершинного графа раскрашены в два
цвета. Доказать, что найдется одноцветный треугольник. [9]
716. Ребра полного 17-вершинного графа раскрашены в три
цвета. Доказать, что найдется одноцветный треугольник. [9]
Ориентированные графы
235 717*. В некоторой стране каждый город соединен с каждым
дорогой с односторонним движением. Докажите, что найдется
город, из которого можно добраться в любой другой. [7]
718. В некотором государстве каждые два города соедине­
ны дорогой. На каждой дороге разрешено движение только в
одном направлении. Доказать, что найдется город, выехав из
которого, можно объехать все государство, побывав в каждом
городе только один раз. [1 ]
719. Несколько команд сыграли между собой круговой тур­
нир по волейболу. Будем говорить, что команда А сильнее ко­
манды В, если либо А выиграла у В, либо существует команда
С такая, что А выиграла у С, a С — у В.
а) Докажите, что есть команда, которая сильнее всех.
б) Докажите, что команда, выигравшая турнир, сильнее всех. [7]
720. В одном государстве 100 городов и каждый соединен с
каждым дорогой с односторонним движением. Докажите, что можно
Десятый класс 171
поменять направление движения на одной дороге так, чтобы
из любого города можно было доехать до любого другого. [7]
721. 20 команд сыграли круговой турнир по волейболу. До­
кажите, что команды можно пронумеровать числами от 1 до 2 0
так, что 1 -я команда выиграла у 2 -й, 2 -я —у 3-й, ..., 19-я —
у 20-й. [7]
КОМБИНАТОРНАЯ ГЕОМЕТРИЯ
722. На плоскости даны два непересекающихся круга. Су­
ществует ли такая точка, лежащая вне обоих кругов, что любая
прямая, проходящая через нее, пересекает хотя бы один круг? [1 ]
723. Из шахматной доски 8 x 8 вырезана клетка Ь8 . Доказать,
что полученную фигуру нельзя разбить на 17 равновеликих
треугольников. [1 ]
724. Параллелограмм разбит прямыми, параллельными его
сторонам, на несколько частей, причем одна его сторона раз­
бита на т частей, а другая на п частей. На какое наибольшее
число частей можно разбить параллелограмм, если провести
еще одну прямую? [1 ]
725. Существует ли правильный многоугольник, одна диаго­
наль которого равна сумме двух других? [1 ]
ДЕСЯТЫЙ КЛАСС
АРИФМЕТИКА
Малая теорема Ферма
Теорема Ферма. Пустьр — простое число, а не делится
на р. Тогда
ар~х - 1 (mod р).
726. Найдите остаток от деления 2100 на 101. [7] _
727*. Найдите остаток от деления З102 на 101. 19
728. Докажите, что ЗОО3000 — 1 делится на 1001. [7]
729. Найдите остаток от деления 8 900 на 29. [7] _
730*. Докажите, что 7120- 1 делится на 143. 19
731. Докажите, что число З0239 + 2393° составное. [7]
Рациональные и иррациональные числа
732. Докажите иррациональность следующих чисел:
a) cos 1 0 °; б) tg 1 0 °; в) sin Г; г) log2 3.
172 5. Систематизация нестандартных задач
ЛОГИКА
Принцип Дирихле в геометрии
733. В круге радиуса 3 произвольным образом помещено
несколько кругов, сумма радиусов которых равна 25. Доказать,
что найдется прямая, которая пересекает не менее 9 из этих
кругов. [1 ]
734. Доказать, что в выпуклом многограннике есть две грани
с одинаковым числом сторон. [1 ]
Раскраски, замощения
735. Какое максимальное количество брусков 1x1x4 мож­
но вырезать из куба 6 x 6 x 6 ? [9]
АЛГЕБРА
Разложение многочленов на множители
736. Разложите на множители с действительными коэффи­
циентами следующие многочлены:
х4 +у4; х8 +х4 + 1 ; х1 0+х5 + 1 ;
(х + 1)(х + 3)(х + 5)(х + 7) + 15; а 3 + Ь3 + с8 — ЪаЬс,
(a + b + с)3 — а3 — Ь3 — с3; а8 + а6Ь2 + а4Ь4 + a2b6 + А8.
Алгоритм Евклида для многочленов и теорема Безу
737. При каких а и b многочлен
Р(х) = (а + b)x5 + abx2 + 1
делится на х2 - х + 2 ?
738. Найдите остаток R(x) от деления многочлена х?+х + 2
на х2 - 1 .
739. Один из корней уравнения
х3 - 6 х2 + ах— 6 = 0
равен 3. Решите уравнение.
740. При каких значениях параметра а многочлен
Р(х)=хп + ахп~2 (п >2)
делится на х - 2 ?
Десятый класс 173
741. При каких я многочлен
Р(х) — я3х5 + (1 — а)х4 + (1 + я3)х2 + (1 — я3)х — я3
делится на х - 1?
742. Найдите все многочлены, которые удовлетворяют тож­
деству х • Р(х - 1) = (х - 26) • Р(х).
Квадратный трехчлен
743. Рассмотрите графики функций у = х 2 +px + q, которые
пересекают оси координат в трех различных точках. Докажите,
что все окружности, описанные около треугольников с верши­
нами в этих точках, имеют общую точку.
744. Укажите все точки плоскости (х; у), через которые не
проходит ни одна из кривых семейства у = р 2 + ( 4 - 2р)х - х2.
745. Укажите все точки плоскости (х;у), через которые не
проходит хотя бы одна кривая семейства у = р 2 + (2р - 1 )х + 2х2.
746. Изобразите ту часть плоскости (х; у), которая накрыва­
ется всевозможными кругами вида (х - я)2 + (у - я)2 < 2 + а2.
747. Докажите, что корни уравнений
(х - я)(х- Ь) + (х-Ь)(х-с) + (х - я)(х- с) = 0;
с(х - я)(х -Ь) + я(х—Ь)(х-с) + Ь(х - я)(х - с) = 0
всегда вещественные.
748. При каких значениях параметра я уравнение
(я - 1)х2 - 2(я + 1)х + 2(я + 1) = 0
имеет только одно неотрицательное решение?
749. Найдите все значения х, удовлетворяющие неравенству
(2 - я)х3 + (1 - 2я)х2 - 6х+ 5 + 4я - я2 < 0
хотя бы при одном значении е е [-1; 2].
ГРАФЫ
Формула Эйлера
750. Докажите, что для любого плоского графа (в том числе
и несвязного) справедливо неравенство Р^ЗВ-6. [7]
751. Докажите, что в плоском графе есть вершина, степень
которой не превосходит 5. [7]
174 5. Систематизация нестандартных задач
752. Каждое ребро полного графа с 11 вершинами покраше­
но в один из двух цветов: красный или синий. Докажите, что
либо красный, либо синий граф не является плоским. [7]
753. Семиугольник разбит на выпуклые пяти- и шестиуголь­
ники, причем так, что каждая его вершина является вершиной
по крайне мере двух многоугольников разбиения. Докажите,
что число пятиугольников разбиения не меньше 13. [7]
Связные графы
754. Каждое из ребер полного графа с 9 вершинами по­
крашено в синий или красный цвет. Докажите, что либо есть
четыре вершины, все ребра между которыми синие, либо есть
три вершины, все ребра между которыми красные. [7]
755. Каждое из ребер полного графа с 18 вершинами по­
крашено в один из двух цветов. Докажите, что есть четыре
вершины, все ребра между которыми одного цвета. [7]
Ориентированные графы
756. В некотором государстве 2п + 1 городов. Из каждого го­
рода в каждый можно попасть без пересадки водным, железно­
дорожным или воздушным транспортом. Доказать, что можно
выбрать п +1 городов и выбрать вид транспорта так, чтобы
из каждого выбранного города можно было попасть в каждый
другой выбранный город указанным видом транспорта (может
быть, с пересадками). [1]
757. Какие-то две команды набрали в круговом волейболь­
ном турнире одинаковое число очков. Докажите, что найдутся
команды А, В и С такие, что А выиграла у В, В выиграла у С,
а С выиграла у А. [7]
758. В некотором государстве 101 город.
а) Каждый город соединен с каждым дорогой с односто­
ронним движением, причем в каждый город входит 50 дорог и
из каждого города выходит 50 дорог. Докажите, что из любого
города можно доехать в любой другой, проехав не более, чем
по двум дорогам.
б) Некоторые города соединены дорогами с односторонним
движением, причем в каждый город входит 40 дорог и из каж­
дого города выходит 40 дорог. Докажите, что из любого города
можно добраться до любого другого, проехав не более, чем по
трем дорогам. [7]
Десятый класс 175
759. В стране Ориентация на всех дорогах введено односто­
роннее движение, причем из любого города в любой другой
можно добраться, проехав не более, чем по двум дорогам. Одну
дорогу закрыли на ремонт так, что из каждого города по-преж­
нему можно добраться до каждого. Докажите, что для любых
двух городов это можно сделать, проехав не более, чем по трем
дорогам. [7]
КОМБИНАТОРНАЯ ГЕОМЕТРИЯ
760. Доказать, что в круг радиуса 1 нельзя поместить без
наложений 3 треугольника площади 1 каждый. [1]
761. В единичной квадратной решетке берется единичный
квадрат. Доказать, что одно из расстояний от произвольного
узла решетки до вершин этого квадрата иррационально. [1]
762. Существует ли 11-гранник, каждая грань которого име­
ет четное число ребер? [1]
 


Категория: Математика | Добавил: Админ (04.04.2016)
Просмотров: | Теги: Дрозина | Рейтинг: 0.0/0


Другие задачи:
Всего комментариев: 0
avatar