Fhyujk

Can I become debt free or should I file for bankruptcy? How do I manage my debt and finances?

Are there any modern advantages of a fire piston?

How to avoid being sexist when trying to employ someone to function in a very sexist environment?

If I sold a PS4 game I owned the disc for, can I reinstall it digitally?

Can you combine War Caster, whip, and Warlock Features to EB enemies with reach?

Why would the Pakistan airspace closure cancel flights not headed to Pakistan itself?

Broken patches on a road

Dilemma of explaining to interviewer that he is the reason for declining second interview

Avoiding morning and evening handshakes

Is there any differences between "Gucken" and "Schauen"?

Word or phrase for showing great skill at something without formal training in it

Does Windows 10's telemetry include sending *.doc files if Word crashed?

Using only 1s, make 29 with the minimum number of digits

How to deal with an incendiary email that was recalled

Solubility of a tribasic weak acid

Can an insurance company drop you after receiving a bill and refusing to pay?

Blindfold battle as a gladiatorial spectacle - what are the tactics and communication methods?

Why does lambda auto& parameter choose const overload?

What is the most triangles you can make from a capital "H" and 3 straight lines?

Why zero tolerance on nudity in space?

Caruana vs Carlsen game 10 (WCC) why not 18...Nxb6?

Why avoid shared user accounts?

How do I say "Brexit" in Latin?

How can I install sudo without using su?

Contest math problem about crossing out numbers in the table

Math contest proof equation problemContest math problem algebra proofmath contest ranking problem?Angle Manipulation Contest Math Problemfind minimum number of card which is needed to perform trickSolving a Chessboard problem using the Invariance principlemath contest geometry problemA contest math problemContest math problem proofSurface Area Problem Math Contest

6

$begingroup$

A table $ntimes n$ is filled with pairwise different natural numbers. Ann and Ben are playing the following game: Ann chooses the greatest number, then crosses out the row and the column containing it. She then chooses the greatest number from what is remained and repeats the whole process unless table is crossed out completely.

Ben takes exactly the same table, and repeats the same process, but choosing the least number on each step.

We need to show that the sum $A$ of numbers chosen by Ann is greater (or equal) to the sum $B$ of numbers chosen by Ben.

I think it should be done via presenting such $C$ that $Ageq Cgeq B$.
However, if $a_i$ and $b_i$ are the numbers chosen by Ann and Ben on $i$-th step respectively, the inequality $a_igeq b_{n-i+1}$ does not hold. So, I am stuck at this point.

combinatorics contest-math

share|cite|improve this question

edited 32 mins ago

darij grinberg

11k33167

asked 1 hour ago

Michael FreimannMichael Freimann

275112

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Nice question. Where does it come from?
  $endgroup$
  – saulspatz
  58 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @saulspatz saw it in a list of problems created by a Russian teacher. I think he is the author/
  $endgroup$
  – Michael Freimann
  53 mins ago
  
  
  

  
  
  
  

add a comment | 

6

$begingroup$

A table $ntimes n$ is filled with pairwise different natural numbers. Ann and Ben are playing the following game: Ann chooses the greatest number, then crosses out the row and the column containing it. She then chooses the greatest number from what is remained and repeats the whole process unless table is crossed out completely.

Ben takes exactly the same table, and repeats the same process, but choosing the least number on each step.

We need to show that the sum $A$ of numbers chosen by Ann is greater (or equal) to the sum $B$ of numbers chosen by Ben.

I think it should be done via presenting such $C$ that $Ageq Cgeq B$.
However, if $a_i$ and $b_i$ are the numbers chosen by Ann and Ben on $i$-th step respectively, the inequality $a_igeq b_{n-i+1}$ does not hold. So, I am stuck at this point.

combinatorics contest-math

share|cite|improve this question

edited 32 mins ago

darij grinberg

11k33167

asked 1 hour ago

Michael FreimannMichael Freimann

275112

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Nice question. Where does it come from?
  $endgroup$
  – saulspatz
  58 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @saulspatz saw it in a list of problems created by a Russian teacher. I think he is the author/
  $endgroup$
  – Michael Freimann
  53 mins ago
  
  
  

  
  
  
  

add a comment | 

$begingroup$

A table $ntimes n$ is filled with pairwise different natural numbers. Ann and Ben are playing the following game: Ann chooses the greatest number, then crosses out the row and the column containing it. She then chooses the greatest number from what is remained and repeats the whole process unless table is crossed out completely.

Ben takes exactly the same table, and repeats the same process, but choosing the least number on each step.

We need to show that the sum $A$ of numbers chosen by Ann is greater (or equal) to the sum $B$ of numbers chosen by Ben.

I think it should be done via presenting such $C$ that $Ageq Cgeq B$.
However, if $a_i$ and $b_i$ are the numbers chosen by Ann and Ben on $i$-th step respectively, the inequality $a_igeq b_{n-i+1}$ does not hold. So, I am stuck at this point.

combinatorics contest-math

share|cite|improve this question

edited 32 mins ago

darij grinberg

11k33167

asked 1 hour ago

Michael FreimannMichael Freimann

275112

$endgroup$

share|cite|improve this question

edited 32 mins ago

darij grinberg

11k33167

asked 1 hour ago

Michael FreimannMichael Freimann

275112

share|cite|improve this question

edited 32 mins ago

darij grinberg

11k33167

asked 1 hour ago

Michael FreimannMichael Freimann

275112

edited 32 mins ago

darij grinberg

11k33167

edited 32 mins ago

darij grinberg

11k33167

asked 1 hour ago

Michael FreimannMichael Freimann

275112

asked 1 hour ago

Michael FreimannMichael Freimann

275112

2 Answers
2

active

oldest

votes

5

$begingroup$

Let $a_1,a_2dots a_n$ be the numbers selected by Ann and $b_1,b_2,dots b_n$ be the numbers selected by Benjamin.

Lemma: $a_igeq b_{n+1-i}$ for all $1leq i leq n$.

Proof: Consider the set $A$ of all numbers that were eligible when we selected $a_i$ and the set $B$ of all the numbers eligible when we selected $b_{n+1-i}$. Notice that these two sets intersect (because $n-i+1$ rows are eligible in $A$ and $i$ rows are eligible in $B$, and the same happens with the columns) so the claim is true, since $a_i=max(A)$ and $b_i=min B$.

The problem follows from the lemma:

$sumlimits_{i=1}^n a_i geq sumlimits_{i=1}^n b_{n+1-i} = sumlimits_{i=1}^n b_i$

share|cite|improve this answer

edited 32 mins ago

darij grinberg

11k33167

answered 51 mins ago

Jorge Fernández HidalgoJorge Fernández Hidalgo

75.5k1191192

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  What, exactly, does it mean for a row or column to be "eligible" and how does this translate into a proof that $Acap Bnot=emptyset$?
  $endgroup$
  – Barry Cipra
  27 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @BarryCipra excellent question ! A row is eligible if no previous number has been selected in that row and the same definition applies for column! Now we can notice that if an element is in an eligible row and column, then it is eligible. I hope this help. Best regards.
  $endgroup$
  – Jorge Fernández Hidalgo
  8 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @BarryCipra let $k$ be an index such that both (a) no entry in row $k$ was picked by Ann in her first $i-1$ picks and (b) no entry in row $k$ was picked by Ben in his first $n-i$ picks. There indeed is such a $k$ because $n-i + (i-1) = n-1 < n$. Let $A_k$ denote the $i$-th row. We now show that of the $n$ entries in $A$ there is at least one not picked by Ann or Ben. But now let $l$ be an index such that both (a) no entry in column $l$ was picked by Ann in her first $i-1$ picks and (b) no entry in column $l$ was picked by Ben in his first $n-i$ picks. ...
  $endgroup$
  – Mike
  2 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  ... Then the entry $a_{kl}$ [the entry in the $k$-th row of $A$ and $l$-th column] is available to be picked by both Ann and Ben.
  $endgroup$
  – Mike
  2 mins ago
  
  
  

  
  
  
  

add a comment | 

1

$begingroup$

And in fact to add to @Jorge's answer strict inequality is not always possible: For any integer $n$ there are $n times n$ tables $A$ that will force Player A and Player B to have the same sum: Let $A$ be any $n times n$ table where the entries get larger as you head down a column, and to the right on a row: e.g., $A =[a_{ij}]$ where the $ij$-th entry is $i(n+1) + j$. [Note that all entries of $A$ are distinct.] Then both Player A and Player B will end up picking the diagonal elements of $A$.

share|cite|improve this answer

edited 1 min ago

answered 20 mins ago

MikeMike

4,216412

$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%2f3131640%2fcontest-math-problem-about-crossing-out-numbers-in-the-table%23new-answer', 'question_page');
}
);

Post as a guest

Name

Email

Required, but never shown

5

$begingroup$

Let $a_1,a_2dots a_n$ be the numbers selected by Ann and $b_1,b_2,dots b_n$ be the numbers selected by Benjamin.

Lemma: $a_igeq b_{n+1-i}$ for all $1leq i leq n$.

Proof: Consider the set $A$ of all numbers that were eligible when we selected $a_i$ and the set $B$ of all the numbers eligible when we selected $b_{n+1-i}$. Notice that these two sets intersect (because $n-i+1$ rows are eligible in $A$ and $i$ rows are eligible in $B$, and the same happens with the columns) so the claim is true, since $a_i=max(A)$ and $b_i=min B$.

The problem follows from the lemma:

$sumlimits_{i=1}^n a_i geq sumlimits_{i=1}^n b_{n+1-i} = sumlimits_{i=1}^n b_i$

share|cite|improve this answer

edited 32 mins ago

darij grinberg

11k33167

answered 51 mins ago

Jorge Fernández HidalgoJorge Fernández Hidalgo

75.5k1191192

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  What, exactly, does it mean for a row or column to be "eligible" and how does this translate into a proof that $Acap Bnot=emptyset$?
  $endgroup$
  – Barry Cipra
  27 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @BarryCipra excellent question ! A row is eligible if no previous number has been selected in that row and the same definition applies for column! Now we can notice that if an element is in an eligible row and column, then it is eligible. I hope this help. Best regards.
  $endgroup$
  – Jorge Fernández Hidalgo
  8 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @BarryCipra let $k$ be an index such that both (a) no entry in row $k$ was picked by Ann in her first $i-1$ picks and (b) no entry in row $k$ was picked by Ben in his first $n-i$ picks. There indeed is such a $k$ because $n-i + (i-1) = n-1 < n$. Let $A_k$ denote the $i$-th row. We now show that of the $n$ entries in $A$ there is at least one not picked by Ann or Ben. But now let $l$ be an index such that both (a) no entry in column $l$ was picked by Ann in her first $i-1$ picks and (b) no entry in column $l$ was picked by Ben in his first $n-i$ picks. ...
  $endgroup$
  – Mike
  2 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  ... Then the entry $a_{kl}$ [the entry in the $k$-th row of $A$ and $l$-th column] is available to be picked by both Ann and Ben.
  $endgroup$
  – Mike
  2 mins ago
  
  
  

  
  
  
  

add a comment | 

5

$begingroup$

Let $a_1,a_2dots a_n$ be the numbers selected by Ann and $b_1,b_2,dots b_n$ be the numbers selected by Benjamin.

Lemma: $a_igeq b_{n+1-i}$ for all $1leq i leq n$.

Proof: Consider the set $A$ of all numbers that were eligible when we selected $a_i$ and the set $B$ of all the numbers eligible when we selected $b_{n+1-i}$. Notice that these two sets intersect (because $n-i+1$ rows are eligible in $A$ and $i$ rows are eligible in $B$, and the same happens with the columns) so the claim is true, since $a_i=max(A)$ and $b_i=min B$.

The problem follows from the lemma:

$sumlimits_{i=1}^n a_i geq sumlimits_{i=1}^n b_{n+1-i} = sumlimits_{i=1}^n b_i$

share|cite|improve this answer

edited 32 mins ago

darij grinberg

11k33167

answered 51 mins ago

Jorge Fernández HidalgoJorge Fernández Hidalgo

75.5k1191192

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  What, exactly, does it mean for a row or column to be "eligible" and how does this translate into a proof that $Acap Bnot=emptyset$?
  $endgroup$
  – Barry Cipra
  27 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @BarryCipra excellent question ! A row is eligible if no previous number has been selected in that row and the same definition applies for column! Now we can notice that if an element is in an eligible row and column, then it is eligible. I hope this help. Best regards.
  $endgroup$
  – Jorge Fernández Hidalgo
  8 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @BarryCipra let $k$ be an index such that both (a) no entry in row $k$ was picked by Ann in her first $i-1$ picks and (b) no entry in row $k$ was picked by Ben in his first $n-i$ picks. There indeed is such a $k$ because $n-i + (i-1) = n-1 < n$. Let $A_k$ denote the $i$-th row. We now show that of the $n$ entries in $A$ there is at least one not picked by Ann or Ben. But now let $l$ be an index such that both (a) no entry in column $l$ was picked by Ann in her first $i-1$ picks and (b) no entry in column $l$ was picked by Ben in his first $n-i$ picks. ...
  $endgroup$
  – Mike
  2 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  ... Then the entry $a_{kl}$ [the entry in the $k$-th row of $A$ and $l$-th column] is available to be picked by both Ann and Ben.
  $endgroup$
  – Mike
  2 mins ago
  
  
  

  
  
  
  

add a comment | 

$begingroup$

Let $a_1,a_2dots a_n$ be the numbers selected by Ann and $b_1,b_2,dots b_n$ be the numbers selected by Benjamin.

Lemma: $a_igeq b_{n+1-i}$ for all $1leq i leq n$.

Proof: Consider the set $A$ of all numbers that were eligible when we selected $a_i$ and the set $B$ of all the numbers eligible when we selected $b_{n+1-i}$. Notice that these two sets intersect (because $n-i+1$ rows are eligible in $A$ and $i$ rows are eligible in $B$, and the same happens with the columns) so the claim is true, since $a_i=max(A)$ and $b_i=min B$.

The problem follows from the lemma:

$sumlimits_{i=1}^n a_i geq sumlimits_{i=1}^n b_{n+1-i} = sumlimits_{i=1}^n b_i$

share|cite|improve this answer

edited 32 mins ago

darij grinberg

11k33167

answered 51 mins ago

Jorge Fernández HidalgoJorge Fernández Hidalgo

75.5k1191192

$endgroup$

share|cite|improve this answer

edited 32 mins ago

darij grinberg

11k33167

answered 51 mins ago

Jorge Fernández HidalgoJorge Fernández Hidalgo

75.5k1191192

edited 32 mins ago

darij grinberg

11k33167

edited 32 mins ago

darij grinberg

11k33167

answered 51 mins ago

Jorge Fernández HidalgoJorge Fernández Hidalgo

75.5k1191192

answered 51 mins ago

Jorge Fernández HidalgoJorge Fernández Hidalgo

75.5k1191192

1

$begingroup$

And in fact to add to @Jorge's answer strict inequality is not always possible: For any integer $n$ there are $n times n$ tables $A$ that will force Player A and Player B to have the same sum: Let $A$ be any $n times n$ table where the entries get larger as you head down a column, and to the right on a row: e.g., $A =[a_{ij}]$ where the $ij$-th entry is $i(n+1) + j$. [Note that all entries of $A$ are distinct.] Then both Player A and Player B will end up picking the diagonal elements of $A$.

share|cite|improve this answer

edited 1 min ago

answered 20 mins ago

MikeMike

4,216412

$endgroup$

add a comment | 

1

$begingroup$

And in fact to add to @Jorge's answer strict inequality is not always possible: For any integer $n$ there are $n times n$ tables $A$ that will force Player A and Player B to have the same sum: Let $A$ be any $n times n$ table where the entries get larger as you head down a column, and to the right on a row: e.g., $A =[a_{ij}]$ where the $ij$-th entry is $i(n+1) + j$. [Note that all entries of $A$ are distinct.] Then both Player A and Player B will end up picking the diagonal elements of $A$.

share|cite|improve this answer

edited 1 min ago

answered 20 mins ago

MikeMike

4,216412

$endgroup$

add a comment | 

$begingroup$

And in fact to add to @Jorge's answer strict inequality is not always possible: For any integer $n$ there are $n times n$ tables $A$ that will force Player A and Player B to have the same sum: Let $A$ be any $n times n$ table where the entries get larger as you head down a column, and to the right on a row: e.g., $A =[a_{ij}]$ where the $ij$-th entry is $i(n+1) + j$. [Note that all entries of $A$ are distinct.] Then both Player A and Player B will end up picking the diagonal elements of $A$.

share|cite|improve this answer

edited 1 min ago

answered 20 mins ago

MikeMike

4,216412

$endgroup$

share|cite|improve this answer

edited 1 min ago

answered 20 mins ago

MikeMike

4,216412

answered 20 mins ago

MikeMike

4,216412

answered 20 mins ago

MikeMike

4,216412