Let k be a positive integer. At the European Chess Cup every pair of players played a game in which somebody won (there were no draws). For any k players there was a player against whom they all lost, and the number of players was the least possible for such k. Is it possible that at the Closing Ceremony all the participants were seated at the round table in such a way that every participant was seated next to both a person he won against and a person he lost against. Proposed by Matija Bucić.
Problem
Source: European Mathematical Cup 2012, Junior Division, Problem 4
Tags: induction, strong induction, combinatorics proposed, combinatorics, Tournament graphs, Hamiltonian path
03.12.2014 20:27
A nice problem,but fairly standard.Let n be the number of such people for k.First,it is reasonable to guess the answer is yes(Try small values,k=1,2) and in first look there is no way to prove that it is impossible.Ok,now we have to build such an arragemnt.Well,now the only way that is logic and that has sense is to pick some of them and put them on the table and than build a larger one,or maximal principle(if we arrange them arbirtaly and swithing them doesn't seem too look and nothing that has any sence has bumped to me).Ok,now assume that the size of that group is less than n.Now,by maximality it is obvious that every guy that is not in the group(arrangment) will win againts all the guys int the maximal group or he will lose againts all the guys in the group.Now,using minimality of k,it is easy to prove that will have guys that win againts and lose againts all so we just need to prove that all the guys that won can't win all guys that lost from every guy from the maximal arrangment,cause then that group will satisfay the statement if it is bigger than k and if it is less than k just pick up them with some other guys that are not in the group and again we get a contradiction,so we add a guy that won againts all the guys in the maximal arrangmnet and the guy who lost againts all and won the previos guy(if the group is n−1,we already proved that the guy can't won or lose againts all the guys,so just add him),so we are finished. Well,I explanied in detail and give some motivation cause it is junior section,but I still think they are obvios and the problem is nice but standard.
03.12.2014 21:57
That thing above is quite hard to read and/or understand. The problem immediately succumbs to this well-known Lemma for tournaments (complete digraphs). In effect, this has been proposed by Poland in an ugly algebraic form in the 1989 IMO LongList. Lemma. Let G be a tournament. Then either it contains a Hamiltonian circuit, or else it partitions into two smaller non-empty tournaments G1 and G2, such that all G1−G2 edges are directioned from G1 towards G2. Proof. If G has a source vertex α, take G1=α and G2=G−α. If G has a sink vertex ω, take G1=G−ω and G2=ω. Otherwise G always contains a circuit. Let γ be a largest circuit in G. If it is Hamiltonian, we won. Otherwise it is easy to show that for any vertex v∈G−γ all v−γ edges are directioned the same. Denote by A the subset of G−γ such that all A−γ edges are directioned from A towards γ, and denote by B the subset of G−γ such that all B−γ edges are directioned from γ towards B. If A=∅ then B≠∅ and we can take G1=γ and G2=B. If B=∅ then A≠∅ and we can take G1=A and G2=γ. If both A≠∅ and B≠∅, it also follows that all A−B edges are directioned from A towards B, and we can take G1=A and G2=B∪γ or G1=A∪γ and G2=B. By this we proved that one or the other of the situations occurs. ◻ Now the problem immediately follows. Assuming no Hamiltonian circuit in G, if |G1|≤k then a group of k players including G1 cannot have another player against whom they all lost, while if |G1|>k then |G| was not minimal.
03.12.2014 22:26
Here's another solution I heard from a friend: Introduce the notation V1→V2, meaning "every edge of the tournament between the disjoint sets of vertices V1 and V2 goes from V1 to V2". Call a partition of G into two smaller non-empty tournaments G1 and G2 'evil' if V(G1)→V(G2). We prove the Lemma by strong induction on n=|V(G)|. To start, it is trivial when G has 1,2,3 vertices. Pick a graph G with no evil partitions and a vertex v∈V(G), and consider the tournament formed by the remaining vertices. If this tournament has no evil partitions, leave it as is, else consider an evil partition and the two parts. Now if one of the two parts has an evil partition, divide it again into two and so on. This way, the vertices of G are partitioned into v, and sets V1→V2→⋯→Vk. Because of the induction hypothesis, there is a Hamiltonian circuit within the subtournament in Vi for i=1,2,…,k. Also, there is an edge from v to V1 and an edge from Vk to v, or else the partition of vertices V1−V(G)∖V1 or Vk−V(G)∖Vk would be evil. To find a Hamiltonian circuit in G, we simply need to travel from v to V1, almost around the circuit, to V2, around the circuit, ..., around Vk and back to v.
15.12.2019 19:50
Let's take the largest number of participants whom we can seat around the table as desired. If we have seated all the participants we are done. Otherwise there is a person not seated at the table. As well there is at least one person seated at the table so let's name it a. WLOG we can assume that for each person seated at the table to his right there is a person he won against and to his left a person he lost against. Denote by W the set of people who won against person a, and are not seated at the table. Similarly, let L denote the set of all people who lost against a and are not seated at the table. Let's consider any person p from W. If person p lost against the left neighbour of a, then we could seat p in between a and his (former) left neighbour, which is a contradiction with the assumption that we have seated the maximal possible number of people. So p won against the left neighbour of a. Using similar deduction we conclude that p won against the next left neighbour as well etc. So p must have won against everybody seated at the table. In the same way if we consider any person q from L and consider the right neighbour of a, we can conclude that q lost against every person seated at the table. If some person r from W lost against some person s in L, then instead of seating a we can seat s and r respectively by which we would reach a contradiction to the number of people seated being maximal. So we conclude that all the people in W won against all people not in W and all the people in L lost against all people not in L. As there is a someone who is not seated either W or L is non-empty. If W is non-empty, we can consider the set W as an independent chess cup. It is a cup with smaller number of participants but still satisfying problem conditions which would be the contradiction with the fact that our starting cup is the smallest such cup. As well if L is non-empty, the smaller cup made by people seated at the table and people in W also satises the problem conditions and gives us a contradiction. So the only possibility is that both W and L are empty so indeed it is possible to seat everyone at such table.