Croatia team selection test for IMO 2012 (combinatorics)












8












$begingroup$


There is an island and 20 houses at the beach around the island, each house with 20 wrestlers. Each wrestler fights with all wrestlers from other houses. There is no two wrestlers with the same power and the stronger wrestler always win. We say that house $A$ is stronger than house $B$ if there is $k$ fights in which fighters from house $A$ wins. What is a maximum $k$ if we know that each house is stronger than the neighboring house in the direction of the clock movement?



I was trying to solve this was but in the end I gave up and I read an official solution. I was very unsatisfied how it was solved. Perhaps someone will have a diferent aproach here.



Here is an offical solution: http://natjecanja.math.hr/wp-content/uploads/2015/02/2012_izborno-rjesenja.pdf






combinatorics discrete-mathematics contest-math alternative-proof extremal-combinatorics







share|cite|improve this question











$endgroup$








  • 4




    $begingroup$
    It looks like a nice generalization of the concept of non-transitive dice - en.wikipedia.org/wiki/Nontransitive_dice
    $endgroup$
    – Jack D'Aurizio
    Aug 15 '17 at 20:58






  • 1




    $begingroup$
    I suppose you meant "We say that house $A$ is stronger than house $B$ if there are $k$ fights in which fighters from house $A$ win against fighters from house $B$". Is that correct?
    $endgroup$
    – Fimpellizieri
    Aug 15 '17 at 21:03






  • 1




    $begingroup$
    If $kleq 200$ then it is possible for $A$ to be stronger than $B$ and at the same time $B$ to be stronger than $A$. This means that for any of those lower values of $k$, we can create the clockwise arrangement by simply having every house be stronger than both of its neighbors. Therefore the maximum $k$ is greater than $200$. If $k=400$ then "stronger than" is transitive and it is certainly impossible.
    $endgroup$
    – Zubin Mukerjee
    Aug 15 '17 at 21:25


















8












$begingroup$


There is an island and 20 houses at the beach around the island, each house with 20 wrestlers. Each wrestler fights with all wrestlers from other houses. There is no two wrestlers with the same power and the stronger wrestler always win. We say that house $A$ is stronger than house $B$ if there is $k$ fights in which fighters from house $A$ wins. What is a maximum $k$ if we know that each house is stronger than the neighboring house in the direction of the clock movement?



I was trying to solve this was but in the end I gave up and I read an official solution. I was very unsatisfied how it was solved. Perhaps someone will have a diferent aproach here.



Here is an offical solution: http://natjecanja.math.hr/wp-content/uploads/2015/02/2012_izborno-rjesenja.pdf






combinatorics discrete-mathematics contest-math alternative-proof extremal-combinatorics







share|cite|improve this question











$endgroup$








  • 4




    $begingroup$
    It looks like a nice generalization of the concept of non-transitive dice - en.wikipedia.org/wiki/Nontransitive_dice
    $endgroup$
    – Jack D'Aurizio
    Aug 15 '17 at 20:58






  • 1




    $begingroup$
    I suppose you meant "We say that house $A$ is stronger than house $B$ if there are $k$ fights in which fighters from house $A$ win against fighters from house $B$". Is that correct?
    $endgroup$
    – Fimpellizieri
    Aug 15 '17 at 21:03






  • 1




    $begingroup$
    If $kleq 200$ then it is possible for $A$ to be stronger than $B$ and at the same time $B$ to be stronger than $A$. This means that for any of those lower values of $k$, we can create the clockwise arrangement by simply having every house be stronger than both of its neighbors. Therefore the maximum $k$ is greater than $200$. If $k=400$ then "stronger than" is transitive and it is certainly impossible.
    $endgroup$
    – Zubin Mukerjee
    Aug 15 '17 at 21:25
















8












8








8


4



$begingroup$


There is an island and 20 houses at the beach around the island, each house with 20 wrestlers. Each wrestler fights with all wrestlers from other houses. There is no two wrestlers with the same power and the stronger wrestler always win. We say that house $A$ is stronger than house $B$ if there is $k$ fights in which fighters from house $A$ wins. What is a maximum $k$ if we know that each house is stronger than the neighboring house in the direction of the clock movement?



I was trying to solve this was but in the end I gave up and I read an official solution. I was very unsatisfied how it was solved. Perhaps someone will have a diferent aproach here.



Here is an offical solution: http://natjecanja.math.hr/wp-content/uploads/2015/02/2012_izborno-rjesenja.pdf






combinatorics discrete-mathematics contest-math alternative-proof extremal-combinatorics







share|cite|improve this question











$endgroup$




There is an island and 20 houses at the beach around the island, each house with 20 wrestlers. Each wrestler fights with all wrestlers from other houses. There is no two wrestlers with the same power and the stronger wrestler always win. We say that house $A$ is stronger than house $B$ if there is $k$ fights in which fighters from house $A$ wins. What is a maximum $k$ if we know that each house is stronger than the neighboring house in the direction of the clock movement?



I was trying to solve this was but in the end I gave up and I read an official solution. I was very unsatisfied how it was solved. Perhaps someone will have a diferent aproach here.



Here is an offical solution: http://natjecanja.math.hr/wp-content/uploads/2015/02/2012_izborno-rjesenja.pdf






combinatorics discrete-mathematics contest-math alternative-proof extremal-combinatorics




combinatorics discrete-mathematics contest-math alternative-proof extremal-combinatorics






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Dec 10 '18 at 10:52









Batominovski

1




1










asked Aug 15 '17 at 20:55









greedoidgreedoid

40.7k1149100




40.7k1149100








  • 4




    $begingroup$
    It looks like a nice generalization of the concept of non-transitive dice - en.wikipedia.org/wiki/Nontransitive_dice
    $endgroup$
    – Jack D'Aurizio
    Aug 15 '17 at 20:58






  • 1




    $begingroup$
    I suppose you meant "We say that house $A$ is stronger than house $B$ if there are $k$ fights in which fighters from house $A$ win against fighters from house $B$". Is that correct?
    $endgroup$
    – Fimpellizieri
    Aug 15 '17 at 21:03






  • 1




    $begingroup$
    If $kleq 200$ then it is possible for $A$ to be stronger than $B$ and at the same time $B$ to be stronger than $A$. This means that for any of those lower values of $k$, we can create the clockwise arrangement by simply having every house be stronger than both of its neighbors. Therefore the maximum $k$ is greater than $200$. If $k=400$ then "stronger than" is transitive and it is certainly impossible.
    $endgroup$
    – Zubin Mukerjee
    Aug 15 '17 at 21:25
















  • 4




    $begingroup$
    It looks like a nice generalization of the concept of non-transitive dice - en.wikipedia.org/wiki/Nontransitive_dice
    $endgroup$
    – Jack D'Aurizio
    Aug 15 '17 at 20:58






  • 1




    $begingroup$
    I suppose you meant "We say that house $A$ is stronger than house $B$ if there are $k$ fights in which fighters from house $A$ win against fighters from house $B$". Is that correct?
    $endgroup$
    – Fimpellizieri
    Aug 15 '17 at 21:03






  • 1




    $begingroup$
    If $kleq 200$ then it is possible for $A$ to be stronger than $B$ and at the same time $B$ to be stronger than $A$. This means that for any of those lower values of $k$, we can create the clockwise arrangement by simply having every house be stronger than both of its neighbors. Therefore the maximum $k$ is greater than $200$. If $k=400$ then "stronger than" is transitive and it is certainly impossible.
    $endgroup$
    – Zubin Mukerjee
    Aug 15 '17 at 21:25










4




4




$begingroup$
It looks like a nice generalization of the concept of non-transitive dice - en.wikipedia.org/wiki/Nontransitive_dice
$endgroup$
– Jack D'Aurizio
Aug 15 '17 at 20:58




$begingroup$
It looks like a nice generalization of the concept of non-transitive dice - en.wikipedia.org/wiki/Nontransitive_dice
$endgroup$
– Jack D'Aurizio
Aug 15 '17 at 20:58




1




1




$begingroup$
I suppose you meant "We say that house $A$ is stronger than house $B$ if there are $k$ fights in which fighters from house $A$ win against fighters from house $B$". Is that correct?
$endgroup$
– Fimpellizieri
Aug 15 '17 at 21:03




$begingroup$
I suppose you meant "We say that house $A$ is stronger than house $B$ if there are $k$ fights in which fighters from house $A$ win against fighters from house $B$". Is that correct?
$endgroup$
– Fimpellizieri
Aug 15 '17 at 21:03




1




1




$begingroup$
If $kleq 200$ then it is possible for $A$ to be stronger than $B$ and at the same time $B$ to be stronger than $A$. This means that for any of those lower values of $k$, we can create the clockwise arrangement by simply having every house be stronger than both of its neighbors. Therefore the maximum $k$ is greater than $200$. If $k=400$ then "stronger than" is transitive and it is certainly impossible.
$endgroup$
– Zubin Mukerjee
Aug 15 '17 at 21:25






$begingroup$
If $kleq 200$ then it is possible for $A$ to be stronger than $B$ and at the same time $B$ to be stronger than $A$. This means that for any of those lower values of $k$, we can create the clockwise arrangement by simply having every house be stronger than both of its neighbors. Therefore the maximum $k$ is greater than $200$. If $k=400$ then "stronger than" is transitive and it is certainly impossible.
$endgroup$
– Zubin Mukerjee
Aug 15 '17 at 21:25












1 Answer
1






active

oldest

votes


















3





+50







$begingroup$

Too long for a comment.



I don’t understand why you are unsatisfied with the official solution. I am for a quarter of a century in math competitions and may assure you that this is a typical solution of (such) a competition problem. It is short, simple and clear. Also it is correct. I provide its English translation for not easy reading Slavic languages people.




The required number is $k = 290$. Let's first show that $k>290$ is impossible. In every house
we rank the wrestlers with respect to their strength (from $1$ to $20$) and choose a wrestler who is tenth by strength in each house. Let the weakest among the chosen wrestlers live in the house $A$. Then in
every other house $B$ (and, in particular, in the house neighbor to house $A$) there are at least $10$ wrestlers
(from 1st to 10th strength rank) who beat at least $11$ wrestlers (from 10th to 20th strength rank)
from $A$. So the number of fights in which the wrestlers from $A$ beat wrestlers from its neighbor house is at most $20cdot 20 – 10cdot 11 = 290$, which is a contradiction with the assumption that house $A$ is stronger than its neighbor.



An example that shows that for $k = 290$ the cyclic house strength order is possible can be constructed as
follows. Rank all $400$ wrestlers from the weakest to the strongest, and we mark
$210$ weaker (for $1$ to $210$) and $190$ stronger wrestlers (from $211$ to $400$). For each $i = 1, dots, 20$, let's
in the house $A_i$ live $i$ weaker and $20-i$ and stronger wrestlers. More precisely, in $A_1$ live wrestlers with ranks $1$ and from $211$ to $229$, in $A_2$ live wrestlers with ranks $2$, $3$ and form $230$ to $247$ etc.



Let us show that the house $A_i$ is stronger than the house $A_{i-1}$ for each $i = 2,dots 20$. All the weaker wrestlers from $A_i$ beat the weaker wrestlers from $A_{i-1}$, and all the stronger wrestlers from $A_i$ beat all wrestlers from $A_{i-1}$. The number the fights in which the wrestlers from the house $A_i$ win is $i(i-1) + (20-i)20 = i^2-21i + 400$. This number is the smallest when $i = 10$ or $i = 11$ and then it is exactly 290. In addition, $19$ stronger wrestlers from the house $A_1$ beat all the wrestlers from the house $A_{20}$, so there were $20cdot 19 = 380>290$ victories and the house $A_1$ is stronger than the house $A_{20}$, which proves the claim.







share|cite|improve this answer











$endgroup$









  • 1




    $begingroup$
    Well there is not explained how did they get this 290. They just prove that 290 is OK but there is no methodological way to find this number. So, my question is how would someone find this 290.
    $endgroup$
    – greedoid
    Oct 19 '17 at 13:24










  • $begingroup$
    @JohnWatson I also don’t see a clear way to this number. I guess that both participants and jury of IMO selection have a common belief that the first should be sufficiently smart to find lower and upper bounds which are good up to coincidence. :-)
    $endgroup$
    – Alex Ravsky
    Oct 19 '17 at 14:11










  • $begingroup$
    Even when you were writing this comment I have encountered the same problem with an other contest math bounty question, about which OP have told “I have heard my country's there are no people who solved this problem”. :-) Let’s wait what other MSE members will say.
    $endgroup$
    – Alex Ravsky
    Oct 19 '17 at 14:12








  • 3




    $begingroup$
    @JohnWatson I do agree with you, this expectation of coming up with solutions by "divine inspiration" is one of the things that turned me off math contests in school in favour of physics. But this one's not that bad. I started looking at 3 houses, 3 wrestlers each, and that gave me the idea of how to construct the example which shows some $k$ works. I think you could get to 290 then by seeing how far you can push that construction. For me it turned out trickier to prove that 291 can't be done some other way - now that I read this solution, I'm embarrassed by the simplicity of that part.
    $endgroup$
    – Nick Pavlov
    Oct 22 '17 at 14:55











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


















StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2394824%2fcroatia-team-selection-test-for-imo-2012-combinatorics%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown

























1 Answer
1






active

oldest

votes








1 Answer
1






active

oldest

votes









active

oldest

votes






active

oldest

votes









3





+50







$begingroup$

Too long for a comment.



I don’t understand why you are unsatisfied with the official solution. I am for a quarter of a century in math competitions and may assure you that this is a typical solution of (such) a competition problem. It is short, simple and clear. Also it is correct. I provide its English translation for not easy reading Slavic languages people.




The required number is $k = 290$. Let's first show that $k>290$ is impossible. In every house
we rank the wrestlers with respect to their strength (from $1$ to $20$) and choose a wrestler who is tenth by strength in each house. Let the weakest among the chosen wrestlers live in the house $A$. Then in
every other house $B$ (and, in particular, in the house neighbor to house $A$) there are at least $10$ wrestlers
(from 1st to 10th strength rank) who beat at least $11$ wrestlers (from 10th to 20th strength rank)
from $A$. So the number of fights in which the wrestlers from $A$ beat wrestlers from its neighbor house is at most $20cdot 20 – 10cdot 11 = 290$, which is a contradiction with the assumption that house $A$ is stronger than its neighbor.



An example that shows that for $k = 290$ the cyclic house strength order is possible can be constructed as
follows. Rank all $400$ wrestlers from the weakest to the strongest, and we mark
$210$ weaker (for $1$ to $210$) and $190$ stronger wrestlers (from $211$ to $400$). For each $i = 1, dots, 20$, let's
in the house $A_i$ live $i$ weaker and $20-i$ and stronger wrestlers. More precisely, in $A_1$ live wrestlers with ranks $1$ and from $211$ to $229$, in $A_2$ live wrestlers with ranks $2$, $3$ and form $230$ to $247$ etc.



Let us show that the house $A_i$ is stronger than the house $A_{i-1}$ for each $i = 2,dots 20$. All the weaker wrestlers from $A_i$ beat the weaker wrestlers from $A_{i-1}$, and all the stronger wrestlers from $A_i$ beat all wrestlers from $A_{i-1}$. The number the fights in which the wrestlers from the house $A_i$ win is $i(i-1) + (20-i)20 = i^2-21i + 400$. This number is the smallest when $i = 10$ or $i = 11$ and then it is exactly 290. In addition, $19$ stronger wrestlers from the house $A_1$ beat all the wrestlers from the house $A_{20}$, so there were $20cdot 19 = 380>290$ victories and the house $A_1$ is stronger than the house $A_{20}$, which proves the claim.







share|cite|improve this answer











$endgroup$









  • 1




    $begingroup$
    Well there is not explained how did they get this 290. They just prove that 290 is OK but there is no methodological way to find this number. So, my question is how would someone find this 290.
    $endgroup$
    – greedoid
    Oct 19 '17 at 13:24










  • $begingroup$
    @JohnWatson I also don’t see a clear way to this number. I guess that both participants and jury of IMO selection have a common belief that the first should be sufficiently smart to find lower and upper bounds which are good up to coincidence. :-)
    $endgroup$
    – Alex Ravsky
    Oct 19 '17 at 14:11










  • $begingroup$
    Even when you were writing this comment I have encountered the same problem with an other contest math bounty question, about which OP have told “I have heard my country's there are no people who solved this problem”. :-) Let’s wait what other MSE members will say.
    $endgroup$
    – Alex Ravsky
    Oct 19 '17 at 14:12








  • 3




    $begingroup$
    @JohnWatson I do agree with you, this expectation of coming up with solutions by "divine inspiration" is one of the things that turned me off math contests in school in favour of physics. But this one's not that bad. I started looking at 3 houses, 3 wrestlers each, and that gave me the idea of how to construct the example which shows some $k$ works. I think you could get to 290 then by seeing how far you can push that construction. For me it turned out trickier to prove that 291 can't be done some other way - now that I read this solution, I'm embarrassed by the simplicity of that part.
    $endgroup$
    – Nick Pavlov
    Oct 22 '17 at 14:55
















3





+50







$begingroup$

Too long for a comment.



I don’t understand why you are unsatisfied with the official solution. I am for a quarter of a century in math competitions and may assure you that this is a typical solution of (such) a competition problem. It is short, simple and clear. Also it is correct. I provide its English translation for not easy reading Slavic languages people.




The required number is $k = 290$. Let's first show that $k>290$ is impossible. In every house
we rank the wrestlers with respect to their strength (from $1$ to $20$) and choose a wrestler who is tenth by strength in each house. Let the weakest among the chosen wrestlers live in the house $A$. Then in
every other house $B$ (and, in particular, in the house neighbor to house $A$) there are at least $10$ wrestlers
(from 1st to 10th strength rank) who beat at least $11$ wrestlers (from 10th to 20th strength rank)
from $A$. So the number of fights in which the wrestlers from $A$ beat wrestlers from its neighbor house is at most $20cdot 20 – 10cdot 11 = 290$, which is a contradiction with the assumption that house $A$ is stronger than its neighbor.



An example that shows that for $k = 290$ the cyclic house strength order is possible can be constructed as
follows. Rank all $400$ wrestlers from the weakest to the strongest, and we mark
$210$ weaker (for $1$ to $210$) and $190$ stronger wrestlers (from $211$ to $400$). For each $i = 1, dots, 20$, let's
in the house $A_i$ live $i$ weaker and $20-i$ and stronger wrestlers. More precisely, in $A_1$ live wrestlers with ranks $1$ and from $211$ to $229$, in $A_2$ live wrestlers with ranks $2$, $3$ and form $230$ to $247$ etc.



Let us show that the house $A_i$ is stronger than the house $A_{i-1}$ for each $i = 2,dots 20$. All the weaker wrestlers from $A_i$ beat the weaker wrestlers from $A_{i-1}$, and all the stronger wrestlers from $A_i$ beat all wrestlers from $A_{i-1}$. The number the fights in which the wrestlers from the house $A_i$ win is $i(i-1) + (20-i)20 = i^2-21i + 400$. This number is the smallest when $i = 10$ or $i = 11$ and then it is exactly 290. In addition, $19$ stronger wrestlers from the house $A_1$ beat all the wrestlers from the house $A_{20}$, so there were $20cdot 19 = 380>290$ victories and the house $A_1$ is stronger than the house $A_{20}$, which proves the claim.







share|cite|improve this answer











$endgroup$









  • 1




    $begingroup$
    Well there is not explained how did they get this 290. They just prove that 290 is OK but there is no methodological way to find this number. So, my question is how would someone find this 290.
    $endgroup$
    – greedoid
    Oct 19 '17 at 13:24










  • $begingroup$
    @JohnWatson I also don’t see a clear way to this number. I guess that both participants and jury of IMO selection have a common belief that the first should be sufficiently smart to find lower and upper bounds which are good up to coincidence. :-)
    $endgroup$
    – Alex Ravsky
    Oct 19 '17 at 14:11










  • $begingroup$
    Even when you were writing this comment I have encountered the same problem with an other contest math bounty question, about which OP have told “I have heard my country's there are no people who solved this problem”. :-) Let’s wait what other MSE members will say.
    $endgroup$
    – Alex Ravsky
    Oct 19 '17 at 14:12








  • 3




    $begingroup$
    @JohnWatson I do agree with you, this expectation of coming up with solutions by "divine inspiration" is one of the things that turned me off math contests in school in favour of physics. But this one's not that bad. I started looking at 3 houses, 3 wrestlers each, and that gave me the idea of how to construct the example which shows some $k$ works. I think you could get to 290 then by seeing how far you can push that construction. For me it turned out trickier to prove that 291 can't be done some other way - now that I read this solution, I'm embarrassed by the simplicity of that part.
    $endgroup$
    – Nick Pavlov
    Oct 22 '17 at 14:55














3





+50







3





+50



3




+50



$begingroup$

Too long for a comment.



I don’t understand why you are unsatisfied with the official solution. I am for a quarter of a century in math competitions and may assure you that this is a typical solution of (such) a competition problem. It is short, simple and clear. Also it is correct. I provide its English translation for not easy reading Slavic languages people.




The required number is $k = 290$. Let's first show that $k>290$ is impossible. In every house
we rank the wrestlers with respect to their strength (from $1$ to $20$) and choose a wrestler who is tenth by strength in each house. Let the weakest among the chosen wrestlers live in the house $A$. Then in
every other house $B$ (and, in particular, in the house neighbor to house $A$) there are at least $10$ wrestlers
(from 1st to 10th strength rank) who beat at least $11$ wrestlers (from 10th to 20th strength rank)
from $A$. So the number of fights in which the wrestlers from $A$ beat wrestlers from its neighbor house is at most $20cdot 20 – 10cdot 11 = 290$, which is a contradiction with the assumption that house $A$ is stronger than its neighbor.



An example that shows that for $k = 290$ the cyclic house strength order is possible can be constructed as
follows. Rank all $400$ wrestlers from the weakest to the strongest, and we mark
$210$ weaker (for $1$ to $210$) and $190$ stronger wrestlers (from $211$ to $400$). For each $i = 1, dots, 20$, let's
in the house $A_i$ live $i$ weaker and $20-i$ and stronger wrestlers. More precisely, in $A_1$ live wrestlers with ranks $1$ and from $211$ to $229$, in $A_2$ live wrestlers with ranks $2$, $3$ and form $230$ to $247$ etc.



Let us show that the house $A_i$ is stronger than the house $A_{i-1}$ for each $i = 2,dots 20$. All the weaker wrestlers from $A_i$ beat the weaker wrestlers from $A_{i-1}$, and all the stronger wrestlers from $A_i$ beat all wrestlers from $A_{i-1}$. The number the fights in which the wrestlers from the house $A_i$ win is $i(i-1) + (20-i)20 = i^2-21i + 400$. This number is the smallest when $i = 10$ or $i = 11$ and then it is exactly 290. In addition, $19$ stronger wrestlers from the house $A_1$ beat all the wrestlers from the house $A_{20}$, so there were $20cdot 19 = 380>290$ victories and the house $A_1$ is stronger than the house $A_{20}$, which proves the claim.







share|cite|improve this answer











$endgroup$



Too long for a comment.



I don’t understand why you are unsatisfied with the official solution. I am for a quarter of a century in math competitions and may assure you that this is a typical solution of (such) a competition problem. It is short, simple and clear. Also it is correct. I provide its English translation for not easy reading Slavic languages people.




The required number is $k = 290$. Let's first show that $k>290$ is impossible. In every house
we rank the wrestlers with respect to their strength (from $1$ to $20$) and choose a wrestler who is tenth by strength in each house. Let the weakest among the chosen wrestlers live in the house $A$. Then in
every other house $B$ (and, in particular, in the house neighbor to house $A$) there are at least $10$ wrestlers
(from 1st to 10th strength rank) who beat at least $11$ wrestlers (from 10th to 20th strength rank)
from $A$. So the number of fights in which the wrestlers from $A$ beat wrestlers from its neighbor house is at most $20cdot 20 – 10cdot 11 = 290$, which is a contradiction with the assumption that house $A$ is stronger than its neighbor.



An example that shows that for $k = 290$ the cyclic house strength order is possible can be constructed as
follows. Rank all $400$ wrestlers from the weakest to the strongest, and we mark
$210$ weaker (for $1$ to $210$) and $190$ stronger wrestlers (from $211$ to $400$). For each $i = 1, dots, 20$, let's
in the house $A_i$ live $i$ weaker and $20-i$ and stronger wrestlers. More precisely, in $A_1$ live wrestlers with ranks $1$ and from $211$ to $229$, in $A_2$ live wrestlers with ranks $2$, $3$ and form $230$ to $247$ etc.



Let us show that the house $A_i$ is stronger than the house $A_{i-1}$ for each $i = 2,dots 20$. All the weaker wrestlers from $A_i$ beat the weaker wrestlers from $A_{i-1}$, and all the stronger wrestlers from $A_i$ beat all wrestlers from $A_{i-1}$. The number the fights in which the wrestlers from the house $A_i$ win is $i(i-1) + (20-i)20 = i^2-21i + 400$. This number is the smallest when $i = 10$ or $i = 11$ and then it is exactly 290. In addition, $19$ stronger wrestlers from the house $A_1$ beat all the wrestlers from the house $A_{20}$, so there were $20cdot 19 = 380>290$ victories and the house $A_1$ is stronger than the house $A_{20}$, which proves the claim.








share|cite|improve this answer














share|cite|improve this answer



share|cite|improve this answer








edited Oct 19 '17 at 3:01

























answered Oct 19 '17 at 2:55









Alex RavskyAlex Ravsky

40.5k32282




40.5k32282








  • 1




    $begingroup$
    Well there is not explained how did they get this 290. They just prove that 290 is OK but there is no methodological way to find this number. So, my question is how would someone find this 290.
    $endgroup$
    – greedoid
    Oct 19 '17 at 13:24










  • $begingroup$
    @JohnWatson I also don’t see a clear way to this number. I guess that both participants and jury of IMO selection have a common belief that the first should be sufficiently smart to find lower and upper bounds which are good up to coincidence. :-)
    $endgroup$
    – Alex Ravsky
    Oct 19 '17 at 14:11










  • $begingroup$
    Even when you were writing this comment I have encountered the same problem with an other contest math bounty question, about which OP have told “I have heard my country's there are no people who solved this problem”. :-) Let’s wait what other MSE members will say.
    $endgroup$
    – Alex Ravsky
    Oct 19 '17 at 14:12








  • 3




    $begingroup$
    @JohnWatson I do agree with you, this expectation of coming up with solutions by "divine inspiration" is one of the things that turned me off math contests in school in favour of physics. But this one's not that bad. I started looking at 3 houses, 3 wrestlers each, and that gave me the idea of how to construct the example which shows some $k$ works. I think you could get to 290 then by seeing how far you can push that construction. For me it turned out trickier to prove that 291 can't be done some other way - now that I read this solution, I'm embarrassed by the simplicity of that part.
    $endgroup$
    – Nick Pavlov
    Oct 22 '17 at 14:55














  • 1




    $begingroup$
    Well there is not explained how did they get this 290. They just prove that 290 is OK but there is no methodological way to find this number. So, my question is how would someone find this 290.
    $endgroup$
    – greedoid
    Oct 19 '17 at 13:24










  • $begingroup$
    @JohnWatson I also don’t see a clear way to this number. I guess that both participants and jury of IMO selection have a common belief that the first should be sufficiently smart to find lower and upper bounds which are good up to coincidence. :-)
    $endgroup$
    – Alex Ravsky
    Oct 19 '17 at 14:11










  • $begingroup$
    Even when you were writing this comment I have encountered the same problem with an other contest math bounty question, about which OP have told “I have heard my country's there are no people who solved this problem”. :-) Let’s wait what other MSE members will say.
    $endgroup$
    – Alex Ravsky
    Oct 19 '17 at 14:12








  • 3




    $begingroup$
    @JohnWatson I do agree with you, this expectation of coming up with solutions by "divine inspiration" is one of the things that turned me off math contests in school in favour of physics. But this one's not that bad. I started looking at 3 houses, 3 wrestlers each, and that gave me the idea of how to construct the example which shows some $k$ works. I think you could get to 290 then by seeing how far you can push that construction. For me it turned out trickier to prove that 291 can't be done some other way - now that I read this solution, I'm embarrassed by the simplicity of that part.
    $endgroup$
    – Nick Pavlov
    Oct 22 '17 at 14:55








1




1




$begingroup$
Well there is not explained how did they get this 290. They just prove that 290 is OK but there is no methodological way to find this number. So, my question is how would someone find this 290.
$endgroup$
– greedoid
Oct 19 '17 at 13:24




$begingroup$
Well there is not explained how did they get this 290. They just prove that 290 is OK but there is no methodological way to find this number. So, my question is how would someone find this 290.
$endgroup$
– greedoid
Oct 19 '17 at 13:24












$begingroup$
@JohnWatson I also don’t see a clear way to this number. I guess that both participants and jury of IMO selection have a common belief that the first should be sufficiently smart to find lower and upper bounds which are good up to coincidence. :-)
$endgroup$
– Alex Ravsky
Oct 19 '17 at 14:11




$begingroup$
@JohnWatson I also don’t see a clear way to this number. I guess that both participants and jury of IMO selection have a common belief that the first should be sufficiently smart to find lower and upper bounds which are good up to coincidence. :-)
$endgroup$
– Alex Ravsky
Oct 19 '17 at 14:11












$begingroup$
Even when you were writing this comment I have encountered the same problem with an other contest math bounty question, about which OP have told “I have heard my country's there are no people who solved this problem”. :-) Let’s wait what other MSE members will say.
$endgroup$
– Alex Ravsky
Oct 19 '17 at 14:12






$begingroup$
Even when you were writing this comment I have encountered the same problem with an other contest math bounty question, about which OP have told “I have heard my country's there are no people who solved this problem”. :-) Let’s wait what other MSE members will say.
$endgroup$
– Alex Ravsky
Oct 19 '17 at 14:12






3




3




$begingroup$
@JohnWatson I do agree with you, this expectation of coming up with solutions by "divine inspiration" is one of the things that turned me off math contests in school in favour of physics. But this one's not that bad. I started looking at 3 houses, 3 wrestlers each, and that gave me the idea of how to construct the example which shows some $k$ works. I think you could get to 290 then by seeing how far you can push that construction. For me it turned out trickier to prove that 291 can't be done some other way - now that I read this solution, I'm embarrassed by the simplicity of that part.
$endgroup$
– Nick Pavlov
Oct 22 '17 at 14:55




$begingroup$
@JohnWatson I do agree with you, this expectation of coming up with solutions by "divine inspiration" is one of the things that turned me off math contests in school in favour of physics. But this one's not that bad. I started looking at 3 houses, 3 wrestlers each, and that gave me the idea of how to construct the example which shows some $k$ works. I think you could get to 290 then by seeing how far you can push that construction. For me it turned out trickier to prove that 291 can't be done some other way - now that I read this solution, I'm embarrassed by the simplicity of that part.
$endgroup$
– Nick Pavlov
Oct 22 '17 at 14:55


















draft saved

draft discarded




















































Thanks for contributing an answer to Mathematics Stack Exchange!


  • Please be sure to answer the question. Provide details and share your research!

But avoid …



  • Asking for help, clarification, or responding to other answers.

  • Making statements based on opinion; back them up with references or personal experience.


Use MathJax to format equations. MathJax reference.


To learn more, see our tips on writing great answers.




draft saved


draft discarded














StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2394824%2fcroatia-team-selection-test-for-imo-2012-combinatorics%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown





















































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown

































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown







-

Popular posts from this blog

Ellipse (mathématiques)

Image
Pour les articles homonymes, voir Ellipse. L'ellipse est le lieu des points dont la somme des distances à deux points fixes, dits foyers, est constante. Section du cône ou projection du cercle. En géométrie, une ellipse est une courbe plane fermée obtenue par l’intersection d’un cône de révolution avec un plan, à condition que celui-ci coupe l'axe de rotation du cône ou du cylindre : c'est une conique d'excentricité strictement comprise entre 0 et 1. On peut également la définir comme le lieu des points dont la somme des distances à deux points fixes, dits foyers, est constante (sa construction par la méthode du jardinier est très simple). Dans la vie courante, l’ellipse est la forme qu'on perçoit en regardant un cercle en perspective, ou la figure formée par l’ombre d'un disque sur une surface plane. On retrouve aussi, en première approximation [ 1 ] , des ellipses dans les trajectoires des corps célestes (planètes, comètes ou satellites arti...
Read more

Quarter-circle Tiles

Image
up vote 0 down vote favorite I have $99$ identical square tiles, each with a quarter-circle drawn on it like this: [asy] size(1.5cm); draw(Arc((2,0),1,90,180),red+1); draw((0,0)--(2,0)--(2,2)--(0,2)--(0,0)); [/asy] When I arrange the tiles in a $9times 11$ rectangular grid, each with a random orientation, what is the expected value of the number of full circles I form? I think this problem has to do with finding the chance any given 2x2 square has a circle, but I can't find it. expected-value share | cite | improve this question asked Nov 20 at 15:03 6minecraftninja 1 2 ...
Read more

Mont Emei

Image
Mont Emei.mw-parser-output .entete.map{background-image:url("//upload.wikimedia.org/wikipedia/commons/7/7a/Picto_infobox_map.png")} Vue du sommet Wanfo du mont Emei Géographie Altitude 3 099  m , Wanfo Coordonnées 29° 31′ 11″ nord, 103° 19′ 57″ est Administration Pays   Chine Province Sichuan Ville-préfecture Leshan Géolocalisation sur la carte : Sichuan Mont Emei Géolocalisation sur la carte : Chine Mont Emei modifier   Paysage panoramique du mont Emei, incluant le paysage panoramique du grand Bouddha de Leshan *   Patrimoine mondial de l'UNESCO Passerelle en bois sur le versant ouest Pays   Chine Subdivision Sichuan Type Mixte Critères (iv) (vi) (x) Superficie 15 400 ha Numéro d’identification 779 Zone géographique Asie et Pacifique  ** Année d’inscription 1996 (20 e session) * Descriptif officiel UNESCO ** Classification géog...
Read more