liars and truth-lovers All-Russian MO 1994 Regional (R4) 9.4
Source:
August 26, 2024
combinatorics
Problem Statement
On the world conference of parties of liars and truth-lovers there were participants which were sitting in four rows with chairs each. During a break each participant claimed that among his neighbors (by row or column) there are members of both parties. It is known that liars always lie, whereas truth-lovers always tell truth. What is the smallest number of liars at the conference for which this situation is possible?