Understand the problem

In a badminton singles tournament, each player played against all the others
exactly once and each game had a winner. After all the games, each player
listed the names of all the players she defeated as well as the names of all the
players defeated by the players defeated by her. For instance, if A defeats B
and B defeats C, then in the list of A both B and C are included. Prove that
at least one player listed the names of all other players.

Source of the problem

I.S.I. (Indian Statistical Institute) B.Stat/B.Math Entrance Examination 2013. Subjective Problem no. 4.

Topic
combinatorics

Difficulty Level

7.5 out of 10

Suggested Book

Problem Solving Strategies by Engel

 

Start with hints

Do you really need a hint? Try it first!

Do you know what is Well-ordering principle ? it says that Every nonempty set A of nonnegative integers has a minimal element and a maximal element , which need not to be unique . now some time this simple property help us to get very nice solution to a problem , can you some how apply this property .      

Use the method of contradiction , first of all assume that there is no player which have the given property . Now try to use the property of hint 1 .  

If there is no such list , A’s list has the maximum no. of players Now , if A does not have the certain property then there exist another another player B , who has won against A . Now B’s list contain the name of A [ by the 1st condition ] and all the names of the players defeated by A [ by the 2nd condition]  

Now , can you find out some contradiction , yes exactly ….. B’s list contain more number of element than A So, A’s list must have the certain property .      

Connected Program at Cheenta

I.S.I. & C.M.I. Entrance Program

Indian Statistical Institute and Chennai Mathematical Institute offer challenging bachelor’s program for gifted students. These courses are B.Stat and B.Math program in I.S.I., B.Sc. Math in C.M.I.

The entrances to these programs are far more challenging than usual engineering entrances. Cheenta offers an intense, problem-driven program for these two entrances.

Similar Problem

Does there exist a Magic Rectangle?

Magic Squares are infamous; so famous that even the number of letters on its Wikipedia Page is more than that of Mathematics itself. People hardly talk about Magic Rectangles. Ya, Magic Rectangles! Have you heard of it? No, right? Not me either! So, I set off to...

A trigonometric relation and its implication

Understand the problemProve that a triangle is right-angled if and only ifVietnam National Mathematical Olympiad 1981TrigonometryMediumChallenge and Thrill of Pre-college MathematicsStart with hintsDo you really need a hint? Try it first!Familiarity with the...

I.S.I Entrance-2013 problem 2

This is the solution of ISI-2013 undergraduate entrance

A function on squares

Understand the problem Let be a real-valued function on the plane such that for every square in the plane, Does it follow that for all points in the plane?Putnam 2009 A1 Geometry Easy Mathematical Olympiad Challenges by Titu Andreescu Start with hintsDo you...

Extremal Principle : I.S.I Entrance 2013 problem 4

This is a nice problem based on Well-ordering principle , from ISI entrance 2013

Lattice point inside a triangle

Geometry problem from Iran math Olympiad .

An isosceles triangle, ISI Entrance 2016, Solution to Subjective problem no. 6

Understand the problemLet \(a,b,c\) be the sides of a triangle and \(A,B,C\) be the angles opposite to those sides respectively. If \( \sin (A-B)=\frac{a}{a+b}\sin A\cos B-\frac{b}{a+b} \cos A \sin B\), then prove that the triangle is isosceles. I.S.I. (Indian...

Research Track – Cocompact action and isotropy subgroups

Suppose a group $latex \Gamma $ is acting properly and cocompactly on a metric space X, by isometries. (Understand: proper, cocompact, isometric action) Claim There are only finitely many conjugacy classes of the isotropy subgroups in $latex \Gamma $ Sketch Since the...

I.S.I 2016 SUBJECTIVE PROBLEM – 1

Understand the problemSuppose that in a sports tournament featuring n players, each pairplays one game and there is always a winner and a loser (no draws).Show that the players can be arranged in an order P1, P2, . . . , Pn suchthat player Pi has beaten Pi+1 for all i...

ISI 2019 : Problem #7

Understand the problem Let be a polynomial with integer coefficients. Define and for .If there exists a natural number such that , then prove that either or .   I.S.I. (Indian Statistical Institute) B.Stat/B.Math Entrance Examination 2019. Subjective Problem...