7 класс Группа "профи"("Ш")
Для самостоятельного решения
жүктеу/скачать 471 Kb.
|
- Бұл бет үшін навигация:
- Двудольные графы
- Максимальное число ребер
- Обходы
- Правильная раскраска в два цвета. Нечетные циклы.
- Для самостоятельного решения
- Самостоятельная-блиц на ГМТ
- Геометрическое место точек (ГМТ)
Для самостоятельного решенияЗад8. Перекроите квадрат в правильный шестиугольник, разрезав его не более чем на а) 8 частей; б)* 5 частей. Зад9. Перекроите квадрат в 3 равных квадрата, разрезав его не более чем на а) 10 частей; б) 7 частей. Зад10. Перекроите квадрат в правильный треугольник, разрезав его не более, чем на а) 10 частей; б)* 5 частей. Зад11. Пусть  . Перекроите квадрат со стороной c в два квадрата со сторонами a и b, разрезав его не более, чем на 5 частей (число частей не должно зависеть от a и b).
Двудольные графыПодсчет ребер двумя способамиЗад1. В классе каждый мальчик дружит с тремя девочками, а каждая девочка – с пятью мальчиками. 17 из них любят играть в матбой, и в классе 15 парт. Сколько всего ребят в классе? Зад2. В прошлом учебном году в городе прошли такие мат.олимпиады: городская, областная, и турнир городов. В каждой из них участвовало нечетное число учеников маткласса, причем участник участвовал в нечетном числе олимпиад. Всего в матклассе 20 учеников. Докажите, что кое-кто из них не был ни на одной олимпиаде. Определения. Граф – двудольный, если его вершины можно раскрасить в два цвета так, что не будет ребер с концами одинакового цвета. Упр3. В двудольном графе сумма степеней вершин каждого цвета равны между собой. Упр4. Если в двудольном графе степени всех вершин одинаковы, то вершин каждого цвета поровну. Максимальное число реберУпр5. Какое наибольшее число ребер может быть в двудольном графе с b белыми и r черными вершинами? Зад6. Какое наибольшее число ребер может быть в двудольном графе а) с 2n вершинами; б) с 2n+1 вершиной? Зад7. В строку выписано 11 целых чисел. Для любой группы подряд идущих чисел подсчитана ее сумма (группы из одного числа тоже учитывались). Какое наибольшее количество сумм могло оказаться нечетными? ОбходыУпр8. Может ли конь обойти шахматную доску 77 так, чтобы побывать на каждом поле ровно по одному разу и вернуться последним ходом на исходное поле? Упр9. Докажите, что в двудольном графе нет нечетных циклов. Зад10. У куба отмечены вершины и центры граней, а также проведены диагонали всех граней. Можно ли по отрезкам этих диагоналей обойти все отмеченные точки, побывав в каждой из них ровно по одному разу? Лемма 11. Пусть Г – двудольный граф с черными и белыми вершинами. а) Если в Г есть замкнутый цикл, проходящий через каждую вершину ровно по одному разу, то вершин каждого цвета – поровну. б) Если в Г есть путь, проходящий через каждую вершину ровно по одному разу, то что число белых вершин отличается от числа черных вершин не более чем на 1. Зад12. Замок в форме треугольника со стороной 50 метров разбит на 100 треугольных залов со сторонами 5 м. В каждой стенке между залами есть дверь. Какое наибольшее число залов сможет обойти турист, не заходя ни в какой зал дважды? Правильная раскраска в два цвета. Нечетные циклы.Зад13. Несколько равносторонних треугольников на плоскости не перекрываются. Всегда ли можно раскрасить их в два цвета так, чтобы треугольники с общим отрезком границы были разного цвета? Лемма 14. Дерево – двудольный граф. Теорема 15. (критерий двудольного графа) Граф – двудольный в графе нет нечетных циклов. Зад16. При каких n можно в вершинах n-угольника расставить натуральные числа так, чтобы на каждой стороне одно число делилось на другое, а для всех остальных пар чисел такого не было? Для самостоятельного решенияЗад17. а) В клетки доски 8x8 записали числа 1,2,...,64 в неизвестном порядке. Разрешается узнать сумму чисел в любой паре клеток с общей стороной. Всегда ли можно узнать расположение всех чисел? б) То же для доски 9x9. Зад18. Можно ли в клетки шахматной доски расставить натуральные числа так, чтобы для любых клеток с общей стороной одно из чисел делилось на другое, а для всех остальных пар клеток такого не было. б) Тот же вопрос для пар клеток с общей стороной или вершиной. Зад19. Гриша записал в клетки шахматной доски числа 1,2,...,64 в неизвестном порядке. Он сообщил Леше сумму чисел в каждом прямоугольнике из двух клеток и добавил, что 1 и 64 лежат на одной диагонали. Докажите, что по этой информации Леша может точно определить, где какое число записано. Зад20. Вершины конечного графа как-то пронумеровали от 1 до n, затем на каждом ребре записали сумму номеров в его концах, а номера в вершинах стерли. Докажите, что а) Если граф не двудольный, то нумерация однозначно восстанавливается. б) Если нумерация однозначно не восстанавливается, то этот граф двудольный с равным количеством вершин обоих цветов. Самостоятельная-блиц на ГМТИзобразите следующие ГМТ: С1. ГМТ, равноудаленных от двух данных пересекающихся прямых. С2. ГМТ, удаленных от данной прямой больше чем на R. С3. ГМТ, удаленных от точки A дальше, чем от точки B. С4. АМ + МВ = АВ, где A и B – заданные точки. С5. все точки M для которых AM<AB<BM, где A и B – заданные точки. С6. ГМТ середин отрезков длины R с концами на двух данных перпендикулярных прямых (один конец на первой, другой – на второй прямой). Геометрическое место точек (ГМТ)Упр1. Найдите геометрическое место центров всевозможных окружностей, проходящих через две данные точки А и В. Упр2. Пусть А, В и С – точки, не лежащие на одной прямой. Найдите ГМТ М таких, что ближайшей к М точкой среди точек А, В и С является А. Зад3. Даны две параллельные прямые. Найдите ГМТ, для которых расстояние до первой вдвое больше, чем до второй. Зад4. На плоскости изображена окружность радиуса 2000. Найдите ГМТ М, для каждой из которых расстояние до ближайшей к М точки окружности равно 1. Зад5. Даны точки А и В. Найдите ГМТ М таких, что точки А, В и М являются вершинами равнобедренного треугольника. Зад6. Найти геометрическое место четвертых вершин квадратов таких, что остальные три вершины лежат на двух данных перпендикулярных прямых. Зад7. Найти ГМТ, равноудаленных от трех данных прямых. Зад8. Пусть А, В и С – точки, не лежащие на одной прямой. Найдите ГМТ М таких, что: 8.1. прямая СМ пересекает отрезок АВ; 8.2. луч СМ пересекает отрезок АВ; 8.3. отрезок СМ пересекает отрезок АВ; Зад9. Найдите ГМТ, равноудаленных от сторон данного угла. Зад10. Найдите геометрическое место центров всевозможных окружностей, которые пересекают данный отрезок ровно в двух точках. Зад11. Если в треугольнике отметить точку P и соединить ее с вершинами, то треугольник разобьется на три меньших треугольника. Найдите ГМТ Р, для которых сумма площадей двух из этих треугольников будет равна площади третьего. жүктеу/скачать 471 Kb. Достарыңызбен бөлісу:
|