Многоугольники
Добавлено: 04 май 2015, 16:40
Samorezishe
Помогите решить задачу: Рассмотрим правильный 8-угольник с вершинами, пронумерованными от 1 до 8. Будем случайным образом проводить в нём диагонали. Какое минимально количество диагоналей, которые надо провести, чтобы с вероятностью 1 после удаления сторон исходного многоугольника осталась связная конструкция?
Многоугольники
Добавлено: 05 май 2015, 05:14
Ian
Можно провести 15 диагоналей, не затрагивающих первую вершину (7*6/2-6).
А 16 диагоналей достаточно. Предположим есть 2 не связанных компоненты (про которые не утверждаем, что они сами связны), в одной k, в другой 8-k. Вычисляем, сколько максимум диагоналей и сколько минимум сторон там может быть внутри них проведено, получаем, что максимум диагоналей при k=1 или k=7 те самые 15