Problem

Source: Italy National Olympiad 2020 P6

Tags: combinatorics



In each cell of a table 8×8 lives a knight or a liar. By the tradition, the knights always say the truth and the liars always lie. All the inhabitants of the table say the following statement "The number of liars in my column is (strictly) greater than the number of liars in my row". Determine how many possible configurations are compatible with the statement.