Ответ:

Среди всех 3n учеников выберем такого ученика (точнее, одного из таких учеников), который имеет наибольшее число kk знакомых в одной из двух других школ. Пусть для определенности им оказался ученик А первой школы, который знает kk учеников, например, из второй школы. Тогда А знает n+1–kn+1–k учеников из третьей школы, причем n+1–k≥1n+1–k≥1, так как k≤nk≤n. Рассмотрим ученика В третьей школы, знакомого с А. Если В знает хотя бы одного ученика С из kk знакомых А во второй школе, то ученики A, В, С образуют искомую тройку. Если же В не знает никого из kk знакомых А во второй школе, то в этой школе он знаком не более чем с n–kn–k учениками, а значит, в первой школе он знаком не менее чем с n+1−(n−k)=k+1n+1−(n−k)=k+1 учениками, что противоречит выбору kk.