MathDB

12

Part of 1999 Ukraine Team Selection Test

Problems(1)

number of persons having no signal <= [n+3 -\frac{18m}{n}]

Source: Ukrainian TST 1999 p12

2/13/2020
In a group of n≥4n \ge 4 persons, every three who know each other have a common signal. Assume that these signals are not repeated and that there are m≥1m \ge 1 signals in total. For any set of four persons in which there are three having a common signal, the fourth person has a common signal with at most one of them. Show that there three persons who have a common signal, such that the number of persons having no signal with anyone of them does not exceed [n+3−18mn]\left[n+3 -\frac{18m}{n}\right]
combinatorics