Московск математ олимпад ( олимпиада очень скоро , поэтому хочется прорешать побольше )
3. Каждый из 1994 депутатов парламента дал пощечину ровно одному своему коллеге. Докажите, что можно составить парламентскую комиссию из 665 человек, члены которой не выясняли отношений между собой указанным выше способом.
Элементы решения :
Назовем депутатов врагами, если один другого бил.
Индукцией по n (см. факт 24) докажем следующее утверждение: если в парламенте `M>3n - 2` депутатов, и каждый дал пощечину ровно одному коллеге, то можно составить парламентскую комиссию из n человек, в которой нет врагов. При `n=665` из этого будет следовать утверждение задачи, так как `1994 > 1993 = 3*665 - 2.`
Откуда они взяли это утверждение ?