each deputy quarreled with exactly 3 other deputies
Source: II Soros Olympiad 1995-96 R1 10.10 https://artofproblemsolving.com/community/c2416727_soros_olympiad_in_mathematics
June 3, 2024
combinatorics
Problem Statement
Each deputy of the Academic Duma quarreled with exactly three other deputies. The President ordered the Speaker to divide the deputies into n factions so that agreement reigned within one faction. For what smallest is this always possible? (This means that there is such that deputies could always be divided into factions, but not always into factions.)