Making everyone content even with a brick wall in-between
Source: European Mathematical Cup, 2015, Senior, P4
December 30, 2016
combinatoricsgraph theoryDirected graphs
Problem Statement
A group of mathematicians is attending a conference. We say that a mathematician is content if he is in a room with at least people he admires or if he is admired by at least other people in the room. It is known that when all participants are in a same room then they are all at least -content. Prove that you can assign everyone into one of rooms in a way that everyone is at least -content in his room and neither room is empty. Admiration is not necessarily mutual and no one admires himself.Matija Bucić