Ggthjy

Why did the villain in the first Men in Black movie care about Earth's Cockroaches?

What's the most convenient time of year to end the world?

Citing paywalled articles accessed via illegal web sharing

Slow moving projectiles from a hand-held weapon - how do they reach the target?

What is this metal M-shaped device for?

Can a dragon be stuck looking like a human?

Grade 10 Analytic Geometry Question 23- Incredibly hard

How can animals be objects of ethics without being subjects as well?

Would a National Army of mercenaries be a feasible idea?

Jumping Numbers

How would an AI self awareness kill switch work?

What kind of hardware implements Fourier transform?

Chess tournament winning streaks

Why zero tolerance on nudity in space?

Placing an adverb between a verb and an object?

Why did other German political parties disband so fast when Hitler was appointed chancellor?

If I delete my router's history can my ISP still provide it to my parents?

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

Why avoid shared user accounts?

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

Why is "points exist" not an axiom in geometry?

What does Cypher mean when he says Neo is "gonna pop"?

Disable the ">" operator in Rstudio linux terminal

Am I a Rude Number?

Contest math problem about crossing out numbers in the table

math contest ranking problem?Game of cards and GCDFour numbers are chosen from 1 to 20. If $1leq k leq 17$, in how many ways is the difference between the smallest and the largest number equal to k?A question on choosing 6 numbers out of a population of 45, given restrictions.Maximum Seating Chart Confusion: Students with Same Name ending up in Same GroupsContest math problem proofFind the smallest possible sum of all numbers in the first row.Comparing sums of numbers in tableProve that the last number remaining is greater then $frac{1}{n}$Ratio of maximum sums in table

10

1

$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 12 hours ago

darij grinberg

11k33167

asked 13 hours ago

Michael FreimannMichael Freimann

295113

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Nice question. Where does it come from?
  $endgroup$
  – saulspatz
  13 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

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

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  "pairwise different" that phrase doesn't make sense.
  $endgroup$
  – Acccumulation
  7 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @Acccumulation : It literally means, "for all pairs of numbers in the table, $(x,y)$, the members of the pair are different, $x neq y$". I.e., each natural number appears zero or one times in the table.
  $endgroup$
  – Eric Towers
  7 hours ago
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  @Accumulation : The correct question to follow being told "... filled with different natural numbers ... " is "Different from what?" I'm fine with "distinct" in that usage. And there is no such thing as a unique natural number.
  $endgroup$
  – Eric Towers
  7 hours ago
  

  
  
  
  

 | 
show 1 more comment

10

1

$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 12 hours ago

darij grinberg

11k33167

asked 13 hours ago

Michael FreimannMichael Freimann

295113

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Nice question. Where does it come from?
  $endgroup$
  – saulspatz
  13 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

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

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  "pairwise different" that phrase doesn't make sense.
  $endgroup$
  – Acccumulation
  7 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @Acccumulation : It literally means, "for all pairs of numbers in the table, $(x,y)$, the members of the pair are different, $x neq y$". I.e., each natural number appears zero or one times in the table.
  $endgroup$
  – Eric Towers
  7 hours ago
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  @Accumulation : The correct question to follow being told "... filled with different natural numbers ... " is "Different from what?" I'm fine with "distinct" in that usage. And there is no such thing as a unique natural number.
  $endgroup$
  – Eric Towers
  7 hours ago
  

  
  
  
  

 | 
show 1 more 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 12 hours ago

darij grinberg

11k33167

asked 13 hours ago

Michael FreimannMichael Freimann

295113

$endgroup$

share|cite|improve this question

edited 12 hours ago

darij grinberg

11k33167

asked 13 hours ago

Michael FreimannMichael Freimann

295113

share|cite|improve this question

edited 12 hours ago

darij grinberg

11k33167

asked 13 hours ago

Michael FreimannMichael Freimann

295113

edited 12 hours ago

darij grinberg

11k33167

edited 12 hours ago

darij grinberg

11k33167

asked 13 hours ago

Michael FreimannMichael Freimann

295113

asked 13 hours ago

Michael FreimannMichael Freimann

295113

2 Answers
2

active

oldest

votes

14

$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 12 hours ago

darij grinberg

11k33167

answered 13 hours ago

Jorge Fernández HidalgoJorge Fernández Hidalgo

75.6k1192193

$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
  12 hours 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
  12 hours 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
  12 hours 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 for her $i$-th pick and Ben's $n-i+1$-th pick. So what Ann picks then will be no larger than $a_{kl}$ and what Ben picks no larger.
  $endgroup$
  – Mike
  12 hours ago
  
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  I like how this proof generalizes, pretty much word-for-word, to the $k$-dimensional version of the problem. (+1)
  $endgroup$
  – Micah
  11 hours ago
  

  
  
  
  

 | 
show 2 more comments

6

$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$: Player A will end up picking the diagonals southeast to northwest when Player B northwest to southeast.

share|cite|improve this answer

edited 12 hours ago

answered 12 hours ago

MikeMike

4,266412

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Good point! It makes it interesting as it raises the question as to why the numbers must be distinct. I guess it is so that the choosing number algorithm is easier to explain.
  $endgroup$
  – Jorge Fernández Hidalgo
  11 hours ago
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  $begingroup$
  @JorgeFernándezHidalgo - in fact it is clear from your very nice proof that even if the original matrix contains repeats, and even if a player can choose any of the multiple maxima (or minima), the claim is still true.
  $endgroup$
  – antkam
  10 hours ago
  

  
  
  
  

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

14

$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 12 hours ago

darij grinberg

11k33167

answered 13 hours ago

Jorge Fernández HidalgoJorge Fernández Hidalgo

75.6k1192193

$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
  12 hours 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
  12 hours 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
  12 hours 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 for her $i$-th pick and Ben's $n-i+1$-th pick. So what Ann picks then will be no larger than $a_{kl}$ and what Ben picks no larger.
  $endgroup$
  – Mike
  12 hours ago
  
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  I like how this proof generalizes, pretty much word-for-word, to the $k$-dimensional version of the problem. (+1)
  $endgroup$
  – Micah
  11 hours ago
  

  
  
  
  

 | 
show 2 more comments

14

$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 12 hours ago

darij grinberg

11k33167

answered 13 hours ago

Jorge Fernández HidalgoJorge Fernández Hidalgo

75.6k1192193

$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
  12 hours 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
  12 hours 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
  12 hours 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 for her $i$-th pick and Ben's $n-i+1$-th pick. So what Ann picks then will be no larger than $a_{kl}$ and what Ben picks no larger.
  $endgroup$
  – Mike
  12 hours ago
  
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  I like how this proof generalizes, pretty much word-for-word, to the $k$-dimensional version of the problem. (+1)
  $endgroup$
  – Micah
  11 hours ago
  

  
  
  
  

 | 
show 2 more comments

$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 12 hours ago

darij grinberg

11k33167

answered 13 hours ago

Jorge Fernández HidalgoJorge Fernández Hidalgo

75.6k1192193

$endgroup$

share|cite|improve this answer

edited 12 hours ago

darij grinberg

11k33167

answered 13 hours ago

Jorge Fernández HidalgoJorge Fernández Hidalgo

75.6k1192193

edited 12 hours ago

darij grinberg

11k33167

edited 12 hours ago

darij grinberg

11k33167

answered 13 hours ago

Jorge Fernández HidalgoJorge Fernández Hidalgo

75.6k1192193

answered 13 hours ago

Jorge Fernández HidalgoJorge Fernández Hidalgo

75.6k1192193

6

$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$: Player A will end up picking the diagonals southeast to northwest when Player B northwest to southeast.

share|cite|improve this answer

edited 12 hours ago

answered 12 hours ago

MikeMike

4,266412

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Good point! It makes it interesting as it raises the question as to why the numbers must be distinct. I guess it is so that the choosing number algorithm is easier to explain.
  $endgroup$
  – Jorge Fernández Hidalgo
  11 hours ago
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  $begingroup$
  @JorgeFernándezHidalgo - in fact it is clear from your very nice proof that even if the original matrix contains repeats, and even if a player can choose any of the multiple maxima (or minima), the claim is still true.
  $endgroup$
  – antkam
  10 hours ago
  

  
  
  
  

add a comment | 

6

$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$: Player A will end up picking the diagonals southeast to northwest when Player B northwest to southeast.

share|cite|improve this answer

edited 12 hours ago

answered 12 hours ago

MikeMike

4,266412

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Good point! It makes it interesting as it raises the question as to why the numbers must be distinct. I guess it is so that the choosing number algorithm is easier to explain.
  $endgroup$
  – Jorge Fernández Hidalgo
  11 hours ago
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  $begingroup$
  @JorgeFernándezHidalgo - in fact it is clear from your very nice proof that even if the original matrix contains repeats, and even if a player can choose any of the multiple maxima (or minima), the claim is still true.
  $endgroup$
  – antkam
  10 hours ago
  

  
  
  
  

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$: Player A will end up picking the diagonals southeast to northwest when Player B northwest to southeast.

share|cite|improve this answer

edited 12 hours ago

answered 12 hours ago

MikeMike

4,266412

$endgroup$

share|cite|improve this answer

edited 12 hours ago

answered 12 hours ago

MikeMike

4,266412

answered 12 hours ago

MikeMike

4,266412

answered 12 hours ago

MikeMike

4,266412