a hard problem

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

a hard problem

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: bdmo higher secondary 2017

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

823 posts

#1 h Mar 15, 2018, 1:38 PM • 2 Y

Y by Adventure10, Mango247

a tournament is playing between n persons. Everybody plays with everybody one time. There is no draw here. A number $k$ is called $n$ good if there is any tournament such that in that tournament they have any player in the tournament that has lost all of $k$ 's.
prove that
1. $n$ is greater than or equal to $2^{k+1}-1$
2.Find all $n$ such that $2$ is a n-good

This post has been edited 2 times. Last edited by thegreatp.d, Apr 20, 2021, 5:10 PM
Reason: Typo

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

823 posts

#2 h Mar 15, 2018, 1:40 PM • 1 Y

Y by Adventure10

,........

This post has been edited 1 time. Last edited by thegreatp.d, Apr 20, 2021, 5:09 PM
Reason: Typo

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

823 posts

#3 h Mar 16, 2018, 3:43 AM • 2 Y

Y by Adventure10, Mango247

..........

This post has been edited 1 time. Last edited by thegreatp.d, Dec 19, 2021, 5:58 PM
Reason: Typo

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

823 posts

#4 h Mar 16, 2018, 5:06 AM • 2 Y

Y by Adventure10, Mango247

.........

This post has been edited 1 time. Last edited by thegreatp.d, Jul 27, 2024, 7:10 PM
Reason: Typo

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3465 posts

#5 h Mar 16, 2018, 5:28 AM • 1 Y

Y by Adventure10

Please don't post again and again like this. It's a kind of spamming.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

823 posts

#6 h Mar 16, 2018, 5:33 AM • 1 Y

Y by Adventure10

I think u are not enough smart to solve the problem so u r saying these kind of rambling

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

7546 posts

#7 h Mar 16, 2018, 5:34 AM • 2 Y

Y by Adventure10, Mango247

jrc1729 wrote:

Please don't post again and again like this. It's a kind of spamming.

I have to agree with jrc1729. Why the urgency?

thegreatp.d wrote:

they have any player in the tournament that has lost all of $k$ 's.

English is my native (first) language, and I cannot understand this statement. Can you post the question exactly how it was written?

This post has been edited 1 time. Last edited by scrabbler94, Mar 16, 2018, 5:34 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

823 posts

#8 h Mar 16, 2018, 5:38 AM • 2 Y

Y by Adventure10, Mango247

............

This post has been edited 1 time. Last edited by thegreatp.d, Jul 27, 2024, 7:11 PM
Reason: .....

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

7546 posts

#9 h Mar 16, 2018, 6:10 AM • 2 Y

Y by Adventure10, Mango247

Okay - I was wondering because last time you posted a link to a forum where the BDMO problems were written in English.

Do you mean to say that $k \le n$ is $n$ -good if there exists a tournament such that for any $k$ players, there exists a player who has beaten the remaining players?

(This would be my best guess, but it doesn't make much sense for $k=2$ since any tournament would be $2$ -good under this definition).

Mathematics requires precise language, especially on quantifiers like "any/every", "exists", etc. so I cannot answer the question currently. Either you or someone can help me interpret (which would be appreciated) or post a link to the problems.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

823 posts

#10 h Mar 16, 2018, 6:23 AM • 2 Y

Y by Adventure10, Mango247

..........

This post has been edited 1 time. Last edited by thegreatp.d, Jul 27, 2024, 7:11 PM
Reason: .....

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2541 posts

#11 h Mar 31, 2018, 5:51 PM • 5 Y

Y by Ankoganit, thegreatp.d, anonman, Adventure10, Mango247

Based on my (very) limited grasp of Bengali, and with the help of Google Translate, I'm reading:

ahmedittihad wrote:

A tournament is played between $n$ people. Everyone plays with everyone else, and no game ends in a draw. A number $k$ is said to be $n$ -good if there exists such a tournament in which there is, for every $k$ people, a player who has lost to all of them.
a) Prove that $n\geq 2^{k+1}-1$
b) Give all $n$ for which $2$ is $n$ -good.

The result appeared originally in an an article by Paul Erdős. The following is a replication of his argument:

For part a) we will proceed by induction; the base case of $k=1$ is trivial. Assume that the statement holds for $k=m-1$ , we will show that this implies the corresponding claim for $k=m$ . Suppose, for the sake of contradiction, the opposite—that there exists such a tournament with $n\leq 2^{m+1}-2$ . Observe that there necessarily exists a player in this tournament (call her Ruba) who has won at most $\left\lfloor\tfrac{1}{2}(n-1)\right\rfloor=2^m-2$ matches. There are two cases: either (i) Ruba has won at least $m-1$ matches, or (ii) she has won strictly fewer than $m-1$ .

In the former case, consider the set $L$ of $\l$ (by definition at least $m-1$ at at most $2^m-2$ ) players whom Ruba has defeated. For any group of $m-1$ players in $L$ , we know that there exists some other player (call him Munna) in the tournament who has lost to each of these $m-1$ and to Ruba. Furthermore, and again by definition, Munna is a member of $L$ . It follows that $\l$ is $m-1$ -good, and thus that $\l\geq 2^m-1$ , a contradiction.

Alternatively, suppose that $\l<m-1$ . Choose some $m-1-\l$ players not Ruba or members of $L$ and add them to $L$ to form a set $L'$ of $m-1$ players. By hypothesis, there is some player in the tournament (say, Topu) who has lost to all of the members of $L'$ as well as to Ruba. Topu is clearly a member of $L$ , but $L\subset L'$ (and he has surely not lost to himself!), again a contradiction $\Box$

As for part b), we claim that $n\geq 7$ is necessary and sufficient. The former half is immediate from the inequality from a). Consider first the $n=7$ case. Label the $7$ players $p_0,p_1,\dots,p_6$ , and say $p_i\to p_j$ if player $i$ loses to player $j$ . Observe that the tournament whose game's results are:
$p_0\to p_1\to p_2\to p_3\to p_4\to p_5\to p_6\to p_0$ $p_0\to p_2\to p_4\to p_6\to p_1\to p_3\to p_5\to p_0$ $p_0\to p_4\to p_1\to p_5\to p_2\to p_6\to p_3\to p_0$ Has the desired property (that for every two players there is a third who has lost to both). This is motivated by the fact that $\{1,2,4\}-\{1,2,4\}$ is the complete set of residues modulo $7$ . To obtain a construction for $n>7$ , simply add $n-7$ players $q_7,q_8,\dots, q_{n-1}$ so that each game between a $q$ and a $p$ is won by the $q$ . (The games between the $q$ s can be assigned arbitrarily—they don't really matter). It is again fairly easy to check that this satisfies the problem statement, as desired $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Olympus_mountaineer

414 posts

Olympus_mountaineer

#12 h Feb 16, 2019, 3:26 PM • 2 Y

Y by Adventure10, Mango247

Correct question is posted here.
http://matholympiad.org.bd/forum/viewtopic.php?f=13&t=4237&p=20754#p20754

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a