Задача к ЕГЭ по информатике на тему «Линейные программы и ветвление» №6

Просмотров 10 Комментарии 0

Докажите при помощи математической индукции, что в n-угольнике ровно $2 n-−23n$ диагоналей (n > 3). В качестве ответа запишите 0.

Докажем, для n = 4: $2 4-−32∗4= 2$ . Это верно.

Примем, что для n = k: $k2−23k-$ верно.

Теперь докажем, для n = k+1: $(k+1)2−3(k+1) = k2+2k+1−3k−3-= k2−-k−-2= k2−3k+ (k − 1) 2 2 2 2$ .

При добавлении новой вершины в n-угольник мы получаем одну дополнительную диагональ (если поставить её между веришами $A$ и $B$ , то бывшее ребро $AB$ станет диагональю) и $k − 2$ диагоналей (соединяя новую вершину со всеми остальными кроме соседних). Тогда у нас добавляется $1+ k − 2 = k − 1$ диагональ. Что и соответствует равенству выше.

Ответ: 0