Mixing
Prove that there exists a row or a column of the chessboard which contains at least √n distinct numbers.
Clash Royale CLAN TAG#URR8PPP
up vote
5
down vote
favorite
On each cell of an $n times n$ chessboard, we write a number from $1, 2, 3, .
. . , n$ in such a way that each number appears exactly $n$ times. Prove
that there exists a row or a column of the chessboard which contains
at least $sqrtn$ distinct numbers.
This question is dying for a proof by contradiction, but I can't seem to show how. When I searched through the Internet, there is the following hint:
Assume each row and each column has less than $sqrtn$ distinct numbers in
it. For each row or column, consider the number of distinct numbers in
it.
I feel like double counting is involved in the process, but what to count in two different ways? Also I can prove the statement with the probabilistic method but I would really like to learn the double counting approach.
combinatorics
edited 3 hours ago
greedoid
31.2k94287
asked 5 hours ago
user2694307
163210
add a comment |Â
up vote
5
down vote
favorite
On each cell of an $n times n$ chessboard, we write a number from $1, 2, 3, .
. . , n$ in such a way that each number appears exactly $n$ times. Prove
that there exists a row or a column of the chessboard which contains
at least $sqrtn$ distinct numbers.
This question is dying for a proof by contradiction, but I can't seem to show how. When I searched through the Internet, there is the following hint:
Assume each row and each column has less than $sqrtn$ distinct numbers in
it. For each row or column, consider the number of distinct numbers in
it.
I feel like double counting is involved in the process, but what to count in two different ways? Also I can prove the statement with the probabilistic method but I would really like to learn the double counting approach.
combinatorics
edited 3 hours ago
greedoid
31.2k94287
asked 5 hours ago
user2694307
163210
For reference, and to help others, could you post your probability-based proof, either as part of your question, or perhaps as an answer? I would very much like to see it. Thanks.
– quasi
2 hours ago
@quasi I am posting it now
– user2694307
8 mins ago
add a comment |Â
up vote
5
down vote
favorite
up vote
5
down vote
favorite
On each cell of an $n times n$ chessboard, we write a number from $1, 2, 3, .
. . , n$ in such a way that each number appears exactly $n$ times. Prove
that there exists a row or a column of the chessboard which contains
at least $sqrtn$ distinct numbers.
This question is dying for a proof by contradiction, but I can't seem to show how. When I searched through the Internet, there is the following hint:
Assume each row and each column has less than $sqrtn$ distinct numbers in
it. For each row or column, consider the number of distinct numbers in
it.
I feel like double counting is involved in the process, but what to count in two different ways? Also I can prove the statement with the probabilistic method but I would really like to learn the double counting approach.
combinatorics
edited 3 hours ago
greedoid
31.2k94287
asked 5 hours ago
user2694307
163210
On each cell of an $n times n$ chessboard, we write a number from $1, 2, 3, .
. . , n$ in such a way that each number appears exactly $n$ times. Prove
that there exists a row or a column of the chessboard which contains
at least $sqrtn$ distinct numbers.
This question is dying for a proof by contradiction, but I can't seem to show how. When I searched through the Internet, there is the following hint:
Assume each row and each column has less than $sqrtn$ distinct numbers in
it. For each row or column, consider the number of distinct numbers in
it.
I feel like double counting is involved in the process, but what to count in two different ways? Also I can prove the statement with the probabilistic method but I would really like to learn the double counting approach.
combinatorics
combinatorics
edited 3 hours ago
greedoid
31.2k94287
asked 5 hours ago
user2694307
163210
edited 3 hours ago
greedoid
31.2k94287
asked 5 hours ago
user2694307
163210
edited 3 hours ago
greedoid
31.2k94287
edited 3 hours ago
greedoid
31.2k94287
edited 3 hours ago
greedoid
31.2k94287
31.2k94287
asked 5 hours ago
user2694307
163210
asked 5 hours ago
user2694307
163210
asked 5 hours ago
user2694307
163210
163210
For reference, and to help others, could you post your probability-based proof, either as part of your question, or perhaps as an answer? I would very much like to see it. Thanks.
– quasi
2 hours ago
@quasi I am posting it now
– user2694307
8 mins ago
add a comment |Â
For reference, and to help others, could you post your probability-based proof, either as part of your question, or perhaps as an answer? I would very much like to see it. Thanks.
– quasi
2 hours ago
@quasi I am posting it now
– user2694307
8 mins ago
For reference, and to help others, could you post your probability-based proof, either as part of your question, or perhaps as an answer? I would very much like to see it. Thanks.
– quasi
2 hours ago
For reference, and to help others, could you post your probability-based proof, either as part of your question, or perhaps as an answer? I would very much like to see it. Thanks.
– quasi
2 hours ago
@quasi I am posting it now
– user2694307
8 mins ago
@quasi I am posting it now
– user2694307
8 mins ago
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
5
down vote
accepted
So we have $C_1,...C_n$ columns and $R_1,...,R_n$ rows. Each of these we call a line. So we have $2n$ lines $L_1,L_2,...,L_2n$ and suppose that each line has less than $sqrtn$ different numbers ($d(L_i)<sqrtn$).
Suppose number $kin1,2,...,n$ appears in $c_k$ columns and $r_k$ rows. Then we see that $$r_k+c_k geq 2sqrtn$$
(Imagine a square $sqrtntimes sqrtn$ filled with the same number. ''Clearly'' at this configuration is the minimum for $r_k+c_k$).
So we have: $$2ncdot sqrtn>sum _i=1^2n d(L_i) = sum_k=1^n (r_k+c_k)geq ncdot (2sqrtn)$$
A contradiction.
edited 1 hour ago
Avraham
2,4771131
answered 4 hours ago
greedoid
31.2k94287
Can you explain the claim $r_k+c_kge 2sqrtn$?
– quasi
3 hours ago
Imagine a square $sqrtntimes sqrtn$ filed with the same number. ''Clearly'' at this configuration is the minimum for $r_k+c_k$
– greedoid
3 hours ago
1
Yes, I see. I think that mini-argument should be included in the proof.
– quasi
3 hours ago
1
Nice proof! (+1).
– quasi
3 hours ago
I actually made use of the mini square argument in the probabilistic proof. Seeing that it also works here is great. Thanks a lot.
– user2694307
2 hours ago
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
5
down vote
accepted
So we have $C_1,...C_n$ columns and $R_1,...,R_n$ rows. Each of these we call a line. So we have $2n$ lines $L_1,L_2,...,L_2n$ and suppose that each line has less than $sqrtn$ different numbers ($d(L_i)<sqrtn$).
Suppose number $kin1,2,...,n$ appears in $c_k$ columns and $r_k$ rows. Then we see that $$r_k+c_k geq 2sqrtn$$
(Imagine a square $sqrtntimes sqrtn$ filled with the same number. ''Clearly'' at this configuration is the minimum for $r_k+c_k$).
So we have: $$2ncdot sqrtn>sum _i=1^2n d(L_i) = sum_k=1^n (r_k+c_k)geq ncdot (2sqrtn)$$
A contradiction.
edited 1 hour ago
Avraham
2,4771131
answered 4 hours ago
greedoid
31.2k94287
Can you explain the claim $r_k+c_kge 2sqrtn$?
– quasi
3 hours ago
Imagine a square $sqrtntimes sqrtn$ filed with the same number. ''Clearly'' at this configuration is the minimum for $r_k+c_k$
– greedoid
3 hours ago
1
Yes, I see. I think that mini-argument should be included in the proof.
– quasi
3 hours ago
1
Nice proof! (+1).
– quasi
3 hours ago
I actually made use of the mini square argument in the probabilistic proof. Seeing that it also works here is great. Thanks a lot.
– user2694307
2 hours ago
add a comment |Â
up vote
5
down vote
accepted
So we have $C_1,...C_n$ columns and $R_1,...,R_n$ rows. Each of these we call a line. So we have $2n$ lines $L_1,L_2,...,L_2n$ and suppose that each line has less than $sqrtn$ different numbers ($d(L_i)<sqrtn$).
Suppose number $kin1,2,...,n$ appears in $c_k$ columns and $r_k$ rows. Then we see that $$r_k+c_k geq 2sqrtn$$
(Imagine a square $sqrtntimes sqrtn$ filled with the same number. ''Clearly'' at this configuration is the minimum for $r_k+c_k$).
So we have: $$2ncdot sqrtn>sum _i=1^2n d(L_i) = sum_k=1^n (r_k+c_k)geq ncdot (2sqrtn)$$
A contradiction.
edited 1 hour ago
Avraham
2,4771131
answered 4 hours ago
greedoid
31.2k94287
Can you explain the claim $r_k+c_kge 2sqrtn$?
– quasi
3 hours ago
Imagine a square $sqrtntimes sqrtn$ filed with the same number. ''Clearly'' at this configuration is the minimum for $r_k+c_k$
– greedoid
3 hours ago
1
Yes, I see. I think that mini-argument should be included in the proof.
– quasi
3 hours ago
1
Nice proof! (+1).
– quasi
3 hours ago
I actually made use of the mini square argument in the probabilistic proof. Seeing that it also works here is great. Thanks a lot.
– user2694307
2 hours ago
add a comment |Â
up vote
5
down vote
accepted
up vote
5
down vote
accepted
So we have $C_1,...C_n$ columns and $R_1,...,R_n$ rows. Each of these we call a line. So we have $2n$ lines $L_1,L_2,...,L_2n$ and suppose that each line has less than $sqrtn$ different numbers ($d(L_i)<sqrtn$).
Suppose number $kin1,2,...,n$ appears in $c_k$ columns and $r_k$ rows. Then we see that $$r_k+c_k geq 2sqrtn$$
(Imagine a square $sqrtntimes sqrtn$ filled with the same number. ''Clearly'' at this configuration is the minimum for $r_k+c_k$).
So we have: $$2ncdot sqrtn>sum _i=1^2n d(L_i) = sum_k=1^n (r_k+c_k)geq ncdot (2sqrtn)$$
A contradiction.
edited 1 hour ago
Avraham
2,4771131
answered 4 hours ago
greedoid
31.2k94287
So we have $C_1,...C_n$ columns and $R_1,...,R_n$ rows. Each of these we call a line. So we have $2n$ lines $L_1,L_2,...,L_2n$ and suppose that each line has less than $sqrtn$ different numbers ($d(L_i)<sqrtn$).
Suppose number $kin1,2,...,n$ appears in $c_k$ columns and $r_k$ rows. Then we see that $$r_k+c_k geq 2sqrtn$$
(Imagine a square $sqrtntimes sqrtn$ filled with the same number. ''Clearly'' at this configuration is the minimum for $r_k+c_k$).
So we have: $$2ncdot sqrtn>sum _i=1^2n d(L_i) = sum_k=1^n (r_k+c_k)geq ncdot (2sqrtn)$$
A contradiction.
edited 1 hour ago
Avraham
2,4771131
answered 4 hours ago
greedoid
31.2k94287
edited 1 hour ago
Avraham
2,4771131
edited 1 hour ago
Avraham
2,4771131
edited 1 hour ago
Avraham
2,4771131
2,4771131
answered 4 hours ago
greedoid
31.2k94287
answered 4 hours ago
greedoid
31.2k94287
answered 4 hours ago
greedoid
31.2k94287
31.2k94287
Can you explain the claim $r_k+c_kge 2sqrtn$?
– quasi
3 hours ago
Imagine a square $sqrtntimes sqrtn$ filed with the same number. ''Clearly'' at this configuration is the minimum for $r_k+c_k$
– greedoid
3 hours ago
1
Yes, I see. I think that mini-argument should be included in the proof.
– quasi
3 hours ago
1
Nice proof! (+1).
– quasi
3 hours ago
I actually made use of the mini square argument in the probabilistic proof. Seeing that it also works here is great. Thanks a lot.
– user2694307
2 hours ago
add a comment |Â
Can you explain the claim $r_k+c_kge 2sqrtn$?
– quasi
3 hours ago
Imagine a square $sqrtntimes sqrtn$ filed with the same number. ''Clearly'' at this configuration is the minimum for $r_k+c_k$
– greedoid
3 hours ago
1
Yes, I see. I think that mini-argument should be included in the proof.
– quasi
3 hours ago
1
Nice proof! (+1).
– quasi
3 hours ago
I actually made use of the mini square argument in the probabilistic proof. Seeing that it also works here is great. Thanks a lot.
– user2694307
2 hours ago
Can you explain the claim $r_k+c_kge 2sqrtn$?
– quasi
3 hours ago
Can you explain the claim $r_k+c_kge 2sqrtn$?
– quasi
3 hours ago
Imagine a square $sqrtntimes sqrtn$ filed with the same number. ''Clearly'' at this configuration is the minimum for $r_k+c_k$
– greedoid
3 hours ago
Imagine a square $sqrtntimes sqrtn$ filed with the same number. ''Clearly'' at this configuration is the minimum for $r_k+c_k$
– greedoid
3 hours ago
1
1
Yes, I see. I think that mini-argument should be included in the proof.
– quasi
3 hours ago
Yes, I see. I think that mini-argument should be included in the proof.
– quasi
3 hours ago
1
1
Nice proof! (+1).
– quasi
3 hours ago
Nice proof! (+1).
– quasi
3 hours ago
I actually made use of the mini square argument in the probabilistic proof. Seeing that it also works here is great. Thanks a lot.
– user2694307
2 hours ago
I actually made use of the mini square argument in the probabilistic proof. Seeing that it also works here is great. Thanks a lot.
– user2694307
2 hours ago
add a comment |Â
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2950325%2fprove-that-there-exists-a-row-or-a-column-of-the-chessboard-which-contains-at-le%23new-answer', 'question_page');
);
Post as a guest
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
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
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
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
For reference, and to help others, could you post your probability-based proof, either as part of your question, or perhaps as an answer? I would very much like to see it. Thanks.
– quasi
2 hours ago
@quasi I am posting it now
– user2694307
8 mins ago