MathDB
Picking people from a group that know each other

Source: Poland Math Olympiad 1995 Round 1 #3

June 12, 2023

Problem Statement

In a group of knkn persons, each person knows more than (kāˆ’1)n(k-1)n others (k,nk,n are positive integers). Prove that one can choose k+1k+1 persons from this group so that each chosen person knows all the others chosen.
Note: If a person AA knows BB, then BB knows AA.