• Non ci sono risultati.

Prove that there exists a player with at most⌊√q⌋ wins and a player with at most ⌊√q⌋ losses

N/A
N/A
Protected

Academic year: 2021

Condividi "Prove that there exists a player with at most⌊√q⌋ wins and a player with at most ⌊√q⌋ losses"

Copied!
1
0
0

Testo completo

(1)

Problem 12116

(American Mathematical Monthly, Vol.126, May 2019) Proposed by R. Thaper (USA).

In a round-robin tournament with n players, each player plays every other player exactly once, and each match results in a win for one player and a loss for the other. When player A defeats player B, we call B the victim of A. At the end of the tournament, each player computes the total number of losses incurred by the player’s victims. Let q be the average of this quantity over all players. Prove that there exists a player with at most⌊√q⌋ wins and a player with at most ⌊√q⌋ losses.

Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit`a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma, Italy.

Solution. We consider a directed graph G = (V, E) where the vertices represent the players and two vertices v and w are connected by an edge from v to w if player v won against player w. Let in(v) be the set of players which defeated v and let out(v) be the set of players that have been defeated by v. Then the average q is given by

q= 1

|V | X

v∈V

X

w∈out(v)

|in(w)| = 1

|V | X

w∈V

|in(w)| X

v∈in(w)

1 = 1

|V | X

w∈V

|in(w)|2.

1) Assume that all players have more than ⌊√q⌋ wins, that is |in(w)| >√qfor all w ∈ V , then

q= 1

|V | X

w∈V

|in(w)|2> 1

|V | X

w∈V

q= q

which is a contradiction. Hence there exists a player with at most ⌊√q⌋ wins.

2) Assume that all players have more than ⌊√q⌋ losses, that is |out(w)| >√q for all w ∈ V , then, sinceP

w∈V |in(w)| =P

w∈V |out(w)|, it follows by the Cauchy-Schwarz inequality that

|V | · |V |q = X

w∈V

12· X

w∈V

|in(w)|2≥ X

w∈V

1 · |in(w)|

!2

= X

w∈V

|out(w)|

!2

> X

w∈V

√q

!2

= |V |2q

which is a contradiction. Hence there exists player with at most ⌊√q⌋ losses. 

Riferimenti

Documenti correlati

L’elaborato vuole affiancare nozioni storiche a dati statistici che fotografino l’attuale punto di evoluzione dei due soggetti presi in considerazione nel testo, per

Restituire un senso alla vicenda dei secoli V­XV (chiedo venia per la cronologia frustra, convenzionale e       contestabile) è possibile se si proietta lo sguardo oltre

cellulose and lignin content measured by thermal analysis (mass loss related to EXO1 and EXO2) and wet chemical method for young and old forest litters and their

The most common site of pelvic avulsion (table ⇓ ) is the ischial tuberosity, followed by the anterior inferior iliac spine, and then the anterior superior iliac spine?. The table

 when “real” status (the correction) of the past is received from server.  compare it with corresponding

Client-side prediction + server correction, if game status not overly complex. or, slow

Dans la dernière partie de sa brève analyse (quatorze pages sur plus de trois cents), Le Cat passe de l’aspect physiologique du toucher à son aspect moral. Ce sens semblerait

La produzione dei dati permette di adottare un approccio DDDM Data Driven Decision Making (utilizzo di metriche e dati per guidare decisioni strategiche invece che