Пусть в школе всего N детей. Будем пред­став­лять детей в виде вер­шин графа, а факт друж­бы между детьми в виде ребра, со­еди­ня­ю­щие вер­ши­ны, со­от­вет­ству­ю­щие дру­зьям. Если то сумма сте­пе­ней вер­шин не мень­ше чем

Сумма сте­пе­ней вер­шин чет­ная, то она равна как ми­ни­мум 2N, а тогда ребер хотя бы N, из чего сле­ду­ет, что най­дет­ся цикл, а зна­чит при n  =  9 за­ве­до­мо найдётся не­сколь­ко детей, ко­то­рых можно по­са­дить за круг­лый стол так, чтобы каж­дый знал обоих своих со­се­дей (оче­вид­но, что дру­зья знают друг друга).

Если же n  =  8, то можно по­стро­ить при­мер, когда цикла не будет и, сле­до­ва­тель­но, ука­зан­ная рас­сад­ка не воз­мож­на. На­при­мер, возь­мем 10 вер­шин, со­еди­ним их путем (9 ребер) и затем ко всем вер­ши­нам, кроме кон­цов до­ба­вим «ви­ся­чую» вер­ши­ну, как по­ка­за­но на ри­сун­ке ниже.

Ответ: 9.