Fdtxjr

Why one should not leave fingerprints on bulbs and plugs?

How to get the n-th line after a grepped one?

Fastest way to pop N items from a large dict

Did Ender ever learn that he killed Stilson and/or Bonzo?

How to plot polar formed complex numbers?

Simplify an interface for flexibly applying rules to periods of time

As a new Ubuntu desktop 18.04 LTS user, do I need to use ufw for a firewall or is iptables sufficient?

Bacteria contamination inside a thermos bottle

What is the relationship between relativity and the Doppler effect?

Why does a Star of David appear at a rally with Francisco Franco?

Are Roman Catholic priests ever addressed as pastor

Why is the President allowed to veto a cancellation of emergency powers?

Bach's Toccata and Fugue in D minor breaks the "no parallel octaves" rule?

et qui - how do you really understand that kind of phraseology?

What's the meaning of a knight fighting a snail in medieval book illustrations?

How are passwords stolen from companies if they only store hashes?

I got the following comment from a reputed math journal. What does it mean?

Are ETF trackers fundamentally better than individual stocks?

How to write cleanly even if my character uses expletive language?

Custom alignment for GeoMarkers

Is there a hypothetical scenario that would make Earth uninhabitable for humans, but not for (the majority of) other animals?

How should I state my peer review experience in the CV?

Do the common programs (for example: "ls", "cat") in Linux and BSD come from the same source code?

Different outputs for `w`, `who`, `whoami` and `id`

$n$ Tennis players took part in the one-round table tennis tournament $(n geq 3)$. We say that player $A$ is better than player $B$, if …

Ordered chain in a tournamentEveryone meets everyone else.Probability that the second-best player finishes second in a single-elimination tournament, given that better players always defeat weaker players?possible outcomes for round-robin tennis tournamentCombinatorics olympiad problemThe number of ways to pair 2n players in a tennis tournamentWhat is the distribution of the results of a round robin tournament? What is the distribution of the number of winners?Tournament puzzleNumber of game won in a round-robin tournamentThe tournament involves 2k tennis players they play the tournament, each played with each exactly once .What is the minimum number of rounds you

2

1

$begingroup$

$n$ Tennis players took part in the one-round table tennis tournament $(n geq 3)$. We say that player $A$ is better than player $B$, if $A$ won $B$ or there is such a player $C$, that $A$ won $C$, and $C$ won $B$. For what $n$ in the tournament could it be that each player is better than everyone else? There are no draws in tennis.

I proved that $n = 3k$ is suitable, I also learned how to make an example for $n = 5$, I assume that $n = 3k + 2$ is suitable, but I cannot prove it, it is also not clear what to do if $n = 3k + 1$.

combinatorics graph-theory

share|cite|improve this question

edited Mar 12 at 10:01

Gurjinder

552417

asked Mar 12 at 9:47

YaroslavYaroslav

1016

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  What is a "one-round tournament"? Perhaps if you show the $n=5$ example I can better understand the tournament format?
  $endgroup$
  – antkam
  Mar 12 at 13:20
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  one-round tournament is when everyone has played exactly one time with each
  $endgroup$
  – Yaroslav
  Mar 12 at 13:26
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Ah, thanks, what I usually call a "round-robin" tournament then. :)
  $endgroup$
  – antkam
  Mar 12 at 13:28
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  @MikeEarnest maybe I'm missing something obvious, but how does a Rock beat (directly or indirectly) another Rock? I can see this happening if, among the Rocks, you use something like my $n=odd$ solution, but then if each of the 3 groups (no need for equal size) are odd numbered, then the total number is odd and you could have just used my solution to begin with.
  $endgroup$
  – antkam
  Mar 12 at 18:00
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  @MikeEarnest - Your RPS idea does imply this: If some even $n$ is feasible, then any larger even $N > n$ is also feasible, because you can always divide $N-n$ into two odd groups and use my solution for each.
  $endgroup$
  – antkam
  Mar 12 at 20:01
  

  
  
  
  

 | 
show 7 more comments

2

1

$begingroup$

$n$ Tennis players took part in the one-round table tennis tournament $(n geq 3)$. We say that player $A$ is better than player $B$, if $A$ won $B$ or there is such a player $C$, that $A$ won $C$, and $C$ won $B$. For what $n$ in the tournament could it be that each player is better than everyone else? There are no draws in tennis.

I proved that $n = 3k$ is suitable, I also learned how to make an example for $n = 5$, I assume that $n = 3k + 2$ is suitable, but I cannot prove it, it is also not clear what to do if $n = 3k + 1$.

combinatorics graph-theory

share|cite|improve this question

edited Mar 12 at 10:01

Gurjinder

552417

asked Mar 12 at 9:47

YaroslavYaroslav

1016

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  What is a "one-round tournament"? Perhaps if you show the $n=5$ example I can better understand the tournament format?
  $endgroup$
  – antkam
  Mar 12 at 13:20
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  one-round tournament is when everyone has played exactly one time with each
  $endgroup$
  – Yaroslav
  Mar 12 at 13:26
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Ah, thanks, what I usually call a "round-robin" tournament then. :)
  $endgroup$
  – antkam
  Mar 12 at 13:28
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  @MikeEarnest maybe I'm missing something obvious, but how does a Rock beat (directly or indirectly) another Rock? I can see this happening if, among the Rocks, you use something like my $n=odd$ solution, but then if each of the 3 groups (no need for equal size) are odd numbered, then the total number is odd and you could have just used my solution to begin with.
  $endgroup$
  – antkam
  Mar 12 at 18:00
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  @MikeEarnest - Your RPS idea does imply this: If some even $n$ is feasible, then any larger even $N > n$ is also feasible, because you can always divide $N-n$ into two odd groups and use my solution for each.
  $endgroup$
  – antkam
  Mar 12 at 20:01
  

  
  
  
  

 | 
show 7 more comments

$begingroup$

$n$ Tennis players took part in the one-round table tennis tournament $(n geq 3)$. We say that player $A$ is better than player $B$, if $A$ won $B$ or there is such a player $C$, that $A$ won $C$, and $C$ won $B$. For what $n$ in the tournament could it be that each player is better than everyone else? There are no draws in tennis.

I proved that $n = 3k$ is suitable, I also learned how to make an example for $n = 5$, I assume that $n = 3k + 2$ is suitable, but I cannot prove it, it is also not clear what to do if $n = 3k + 1$.

combinatorics graph-theory

share|cite|improve this question

edited Mar 12 at 10:01

Gurjinder

552417

asked Mar 12 at 9:47

YaroslavYaroslav

1016

$endgroup$

share|cite|improve this question

edited Mar 12 at 10:01

Gurjinder

552417

asked Mar 12 at 9:47

YaroslavYaroslav

1016

share|cite|improve this question

edited Mar 12 at 10:01

Gurjinder

552417

asked Mar 12 at 9:47

YaroslavYaroslav

1016

edited Mar 12 at 10:01

Gurjinder

552417

edited Mar 12 at 10:01

Gurjinder

552417

asked Mar 12 at 9:47

YaroslavYaroslav

1016

asked Mar 12 at 9:47

YaroslavYaroslav

1016

1 Answer
1

active

oldest

votes

2

$begingroup$

Partial solution... specifically:

Claim A: Any odd $n$ is feasible.

Claim B: $n = 4$ is infeasible.

Proof of A: Arrange the players in a circle and number them $0, ..., n-1$, and let $i$ beat $i+1, i+3, ..., i+n-2$. All arithmetic is modulo $n$.

First of all, this assignment is consistent: For any $i neq j$, if $j = i + odd$ (i.e. $i$ beats $j$) then $i = j + even$ (i.e. $j$ does not beat $i$).

Next, clearly $i$ beats all the $i+odd$ directly, but since each $j$ beats $j+1$, $i$ also indirectly beats all the $i+odd+1$, i.e. all the $i+even$.

Proof of B: Among the $n=4$ players, clearly nobody can beat everyone or be beaten by everyone. Since each plays $3$ games, that means each must win only $1$ or $2$ games. Since there are $6$ games total, the only way to do this is if two players $W,X$ win twice each and two other players $Y,Z$ win once each. But consider the match between $Y,Z$ and without loss assume $Y$ beats $Z$. This is $Y$'s only win, and $Z$ beats only $1$ person (e.g. $W$), so $Y$ does not directly nor indirectly beat the other person (e.g. $X$).

share|cite|improve this answer

answered Mar 12 at 15:04

antkamantkam

2,142212

$endgroup$

add a comment | 

Your Answer

StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3144879%2fn-tennis-players-took-part-in-the-one-round-table-tennis-tournament-n-geq-3%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

2

$begingroup$

Partial solution... specifically:

Claim A: Any odd $n$ is feasible.

Claim B: $n = 4$ is infeasible.

Proof of A: Arrange the players in a circle and number them $0, ..., n-1$, and let $i$ beat $i+1, i+3, ..., i+n-2$. All arithmetic is modulo $n$.

First of all, this assignment is consistent: For any $i neq j$, if $j = i + odd$ (i.e. $i$ beats $j$) then $i = j + even$ (i.e. $j$ does not beat $i$).

Next, clearly $i$ beats all the $i+odd$ directly, but since each $j$ beats $j+1$, $i$ also indirectly beats all the $i+odd+1$, i.e. all the $i+even$.

Proof of B: Among the $n=4$ players, clearly nobody can beat everyone or be beaten by everyone. Since each plays $3$ games, that means each must win only $1$ or $2$ games. Since there are $6$ games total, the only way to do this is if two players $W,X$ win twice each and two other players $Y,Z$ win once each. But consider the match between $Y,Z$ and without loss assume $Y$ beats $Z$. This is $Y$'s only win, and $Z$ beats only $1$ person (e.g. $W$), so $Y$ does not directly nor indirectly beat the other person (e.g. $X$).

share|cite|improve this answer

answered Mar 12 at 15:04

antkamantkam

2,142212

$endgroup$

add a comment | 

2

$begingroup$

Partial solution... specifically:

Claim A: Any odd $n$ is feasible.

Claim B: $n = 4$ is infeasible.

Proof of A: Arrange the players in a circle and number them $0, ..., n-1$, and let $i$ beat $i+1, i+3, ..., i+n-2$. All arithmetic is modulo $n$.

First of all, this assignment is consistent: For any $i neq j$, if $j = i + odd$ (i.e. $i$ beats $j$) then $i = j + even$ (i.e. $j$ does not beat $i$).

Next, clearly $i$ beats all the $i+odd$ directly, but since each $j$ beats $j+1$, $i$ also indirectly beats all the $i+odd+1$, i.e. all the $i+even$.

Proof of B: Among the $n=4$ players, clearly nobody can beat everyone or be beaten by everyone. Since each plays $3$ games, that means each must win only $1$ or $2$ games. Since there are $6$ games total, the only way to do this is if two players $W,X$ win twice each and two other players $Y,Z$ win once each. But consider the match between $Y,Z$ and without loss assume $Y$ beats $Z$. This is $Y$'s only win, and $Z$ beats only $1$ person (e.g. $W$), so $Y$ does not directly nor indirectly beat the other person (e.g. $X$).

share|cite|improve this answer

answered Mar 12 at 15:04

antkamantkam

2,142212

$endgroup$

add a comment | 

$begingroup$

Partial solution... specifically:

Claim A: Any odd $n$ is feasible.

Claim B: $n = 4$ is infeasible.

Proof of A: Arrange the players in a circle and number them $0, ..., n-1$, and let $i$ beat $i+1, i+3, ..., i+n-2$. All arithmetic is modulo $n$.

First of all, this assignment is consistent: For any $i neq j$, if $j = i + odd$ (i.e. $i$ beats $j$) then $i = j + even$ (i.e. $j$ does not beat $i$).

Next, clearly $i$ beats all the $i+odd$ directly, but since each $j$ beats $j+1$, $i$ also indirectly beats all the $i+odd+1$, i.e. all the $i+even$.

Proof of B: Among the $n=4$ players, clearly nobody can beat everyone or be beaten by everyone. Since each plays $3$ games, that means each must win only $1$ or $2$ games. Since there are $6$ games total, the only way to do this is if two players $W,X$ win twice each and two other players $Y,Z$ win once each. But consider the match between $Y,Z$ and without loss assume $Y$ beats $Z$. This is $Y$'s only win, and $Z$ beats only $1$ person (e.g. $W$), so $Y$ does not directly nor indirectly beat the other person (e.g. $X$).

share|cite|improve this answer

answered Mar 12 at 15:04

antkamantkam

2,142212

$endgroup$

share|cite|improve this answer

answered Mar 12 at 15:04

antkamantkam

2,142212

answered Mar 12 at 15:04

antkamantkam

2,142212

answered Mar 12 at 15:04

antkamantkam

2,142212