Тема №9976 Задачи по математике "Степени вершин" 12
Поиск задачи:

Рассмотрим тему Задачи по математике "Степени вершин" 12 из предмета Математика и все вопросы которые связанны с ней. Из представленного текста вы познакомитесь с Задачи по математике "Степени вершин" 12, узнаете ключевые особенности и основные понятия.

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

Степени вершин
1. Каждая вершина графа имеет степень 3. Может ли в нём быть ровно 100
ребер?
2. В одном городе любая улица соединяет либо две различные площади, либо
площадь с тупиком, либо два тупика. С любой площади выходит ровно 5 улиц.
Всего в городе 49 улиц. Какое наименьшее количество тупиков может быть?
3. В математической стране Графляндии 2014 городов. Из любого города выходят ровно 200 дорог, причем от любого города можно добраться до любого. Из-за
ежегодного неожиданного наступления зимы, одна дорога пришла в негодность
— ее пришлось закрыть на ремонт. Верно ли, что, как раньше, от любого города
можно проехать к любому?
4. В лесу живут 20 гномов, каждый из которых дружит по крайней мере с 14
другими гномами. Обязательно ли найдутся 4 гнома, которые все дружат между
собой?
5. 17 ученых переписываются по трем дисциплинам. При этом любая пара ученых переписывается ровно по одной дисциплине. Докажите, что можно выбрать
троих ученых, которые переписываются по одной дисциплине.
6. Все ребра полного графа на 9 вершинах окрашены в белый либо зеленый
цвет. Докажите, что найдется зеленый K3 либо белый K4.
7. Дан правильный 45-угольник. Можно ли так расставить в его вершинах
цифры от 0 до 9 так, чтобы для любой пары различных цифр нашлась сторона,
концы которой занумерованы этими цифрами?
8. Турист, приехавший в Москву поездом, весь день ходил по городу пешком.
Очутившись на одной из площадей, он решил вернуться на вокзал, идя лишь теми
улицами, по которым он проходил нечетное число раз. Докажите, что он сможет
это сделать.
9. Рассеянный математик забыл трехзначный код своего замка. Замок открывается, если три цифры кода набраны подряд (даже если перед этим были набраны
другие цифры). Докажите, что математик сможет открыть замок за 1002 секунды,
если он набирает одну цифру в секунду.
10. Докажите, что если в графе степени всех вершин не превосходят n, то его
можно раскрасить в n + 1 цветов. Если к тому же есть хотя бы одна вершина
степени строго меньше n, то такой граф можно раскрасить даже в n цветов.
11. На шахматной доске расставлено несколько ладей. Какое наибольшее число
цветов может потребоваться для раскраски ладей так, чтобы ладьи одного цвета
не били друг друга?
12. В графе с n вершинами степень каждой вершины не превосходит 5. Докажите, что вершины можно раскрасить в 3 цвета так, что ребер с одноцветными
концами будет не более n/2.


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


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