Restaurants
Source: Polish MO
February 25, 2017
combinatoricsgraph theoryPoland
Problem Statement
Gourmet Jan compared restaurants ( is a positive integer). Each pair of restaurants was compared in two categories: tastiness of food and quality of service. For some pairs Jan couldn't tell which restaurant was better in one category, but never in two categories. Moreover, if Jan thought restaurant was better than restaurant in one category and restaurant was better than restaurant in the same category, then is also better than in that category. Prove there exists a restaurant such that every other restaurant is worse than in at least one category.