Spies - how to get an inequality?
$begingroup$
In problem 6 from Olimpiada Matemática Española 1996 there are 16 spies. Each spy spies some of their colleagues; moreover, given any two spies A and B, if A spies B then B does not spy A. We also know that if we take any subset of 10 spies it is possible to sort them in a chain where the first spies the second, the second the third, and so on with the tenth which spies the first. The problem asks to show that for each group of 11 spies such a chain can be made.
The solution starts with defining three numbers for each spy $A_i$. $a_i$ is the number of spies spied by $A_i$; $b_i$ is the number of spies who spy $A_i$; $c_i$ is the number of spies never spying not spied by $A_i$. Then it says that $a_i+b_i+c_i = 15$, and that's clear. But is also says that $a_i+c_i le 8$ and $b_i+c_ile 8$, "because otherwise it is not possible to order 10 spies as required" (if my understanding of Spanish is correct). I cannot understand the reason of this. Can somebody help me?
combinatorics contest-math proof-explanation puzzle
edited Dec 24 '18 at 18:44
Shaun
9,268113684
asked Dec 24 '18 at 18:37
maumau
7,06523263
$endgroup$
add a comment |
$begingroup$
In problem 6 from Olimpiada Matemática Española 1996 there are 16 spies. Each spy spies some of their colleagues; moreover, given any two spies A and B, if A spies B then B does not spy A. We also know that if we take any subset of 10 spies it is possible to sort them in a chain where the first spies the second, the second the third, and so on with the tenth which spies the first. The problem asks to show that for each group of 11 spies such a chain can be made.
The solution starts with defining three numbers for each spy $A_i$. $a_i$ is the number of spies spied by $A_i$; $b_i$ is the number of spies who spy $A_i$; $c_i$ is the number of spies never spying not spied by $A_i$. Then it says that $a_i+b_i+c_i = 15$, and that's clear. But is also says that $a_i+c_i le 8$ and $b_i+c_ile 8$, "because otherwise it is not possible to order 10 spies as required" (if my understanding of Spanish is correct). I cannot understand the reason of this. Can somebody help me?
combinatorics contest-math proof-explanation puzzle
edited Dec 24 '18 at 18:44
Shaun
9,268113684
asked Dec 24 '18 at 18:37
maumau
7,06523263
$endgroup$
1
$begingroup$
Supposing by way of contradiction that $a_i+c_ige 9$, then it is possible to find $9$ spies such that none of them spy on $A_i$. Imagine trying to make a chain using $A_i$ and those $9$ spies.
$endgroup$
– Mike Earnest
Dec 24 '18 at 18:46
$begingroup$
silly me, I kept considering the complementary of the set and got nothing. Do you think it's better to delete the question, or would you put this as an answer so that I can approve it?
$endgroup$
– mau
Dec 24 '18 at 20:45
$begingroup$
Well, I do not feel the need to write an answer, do what you like.
$endgroup$
– Mike Earnest
Dec 24 '18 at 22:11
$begingroup$
It's a valid question, even if the answer was more simple than you expected. Someone in the future may find it helpful. I suggest you leave it. I do not believe that there is any problem with leaving it without an accepted answer. Many such questions exist in this forum.
$endgroup$
– Paul Sinclair
Dec 25 '18 at 11:31
add a comment |
$begingroup$
In problem 6 from Olimpiada Matemática Española 1996 there are 16 spies. Each spy spies some of their colleagues; moreover, given any two spies A and B, if A spies B then B does not spy A. We also know that if we take any subset of 10 spies it is possible to sort them in a chain where the first spies the second, the second the third, and so on with the tenth which spies the first. The problem asks to show that for each group of 11 spies such a chain can be made.
The solution starts with defining three numbers for each spy $A_i$. $a_i$ is the number of spies spied by $A_i$; $b_i$ is the number of spies who spy $A_i$; $c_i$ is the number of spies never spying not spied by $A_i$. Then it says that $a_i+b_i+c_i = 15$, and that's clear. But is also says that $a_i+c_i le 8$ and $b_i+c_ile 8$, "because otherwise it is not possible to order 10 spies as required" (if my understanding of Spanish is correct). I cannot understand the reason of this. Can somebody help me?
combinatorics contest-math proof-explanation puzzle
edited Dec 24 '18 at 18:44
Shaun
9,268113684
asked Dec 24 '18 at 18:37
maumau
7,06523263
$endgroup$
In problem 6 from Olimpiada Matemática Española 1996 there are 16 spies. Each spy spies some of their colleagues; moreover, given any two spies A and B, if A spies B then B does not spy A. We also know that if we take any subset of 10 spies it is possible to sort them in a chain where the first spies the second, the second the third, and so on with the tenth which spies the first. The problem asks to show that for each group of 11 spies such a chain can be made.
The solution starts with defining three numbers for each spy $A_i$. $a_i$ is the number of spies spied by $A_i$; $b_i$ is the number of spies who spy $A_i$; $c_i$ is the number of spies never spying not spied by $A_i$. Then it says that $a_i+b_i+c_i = 15$, and that's clear. But is also says that $a_i+c_i le 8$ and $b_i+c_ile 8$, "because otherwise it is not possible to order 10 spies as required" (if my understanding of Spanish is correct). I cannot understand the reason of this. Can somebody help me?
combinatorics contest-math proof-explanation puzzle
combinatorics contest-math proof-explanation puzzle
edited Dec 24 '18 at 18:44
Shaun
9,268113684
asked Dec 24 '18 at 18:37
maumau
7,06523263
edited Dec 24 '18 at 18:44
Shaun
9,268113684
asked Dec 24 '18 at 18:37
maumau
7,06523263
edited Dec 24 '18 at 18:44
Shaun
9,268113684
edited Dec 24 '18 at 18:44
Shaun
9,268113684
edited Dec 24 '18 at 18:44
Shaun
9,268113684
9,268113684
asked Dec 24 '18 at 18:37
maumau
7,06523263
asked Dec 24 '18 at 18:37
maumau
7,06523263
asked Dec 24 '18 at 18:37
maumau
7,06523263
7,06523263
1
$begingroup$
Supposing by way of contradiction that $a_i+c_ige 9$, then it is possible to find $9$ spies such that none of them spy on $A_i$. Imagine trying to make a chain using $A_i$ and those $9$ spies.
$endgroup$
– Mike Earnest
Dec 24 '18 at 18:46
$begingroup$
silly me, I kept considering the complementary of the set and got nothing. Do you think it's better to delete the question, or would you put this as an answer so that I can approve it?
$endgroup$
– mau
Dec 24 '18 at 20:45
$begingroup$
Well, I do not feel the need to write an answer, do what you like.
$endgroup$
– Mike Earnest
Dec 24 '18 at 22:11
$begingroup$
It's a valid question, even if the answer was more simple than you expected. Someone in the future may find it helpful. I suggest you leave it. I do not believe that there is any problem with leaving it without an accepted answer. Many such questions exist in this forum.
$endgroup$
– Paul Sinclair
Dec 25 '18 at 11:31
add a comment |
1
$begingroup$
Supposing by way of contradiction that $a_i+c_ige 9$, then it is possible to find $9$ spies such that none of them spy on $A_i$. Imagine trying to make a chain using $A_i$ and those $9$ spies.
$endgroup$
– Mike Earnest
Dec 24 '18 at 18:46
$begingroup$
silly me, I kept considering the complementary of the set and got nothing. Do you think it's better to delete the question, or would you put this as an answer so that I can approve it?
$endgroup$
– mau
Dec 24 '18 at 20:45
$begingroup$
Well, I do not feel the need to write an answer, do what you like.
$endgroup$
– Mike Earnest
Dec 24 '18 at 22:11
$begingroup$
It's a valid question, even if the answer was more simple than you expected. Someone in the future may find it helpful. I suggest you leave it. I do not believe that there is any problem with leaving it without an accepted answer. Many such questions exist in this forum.
$endgroup$
– Paul Sinclair
Dec 25 '18 at 11:31
1
1
$begingroup$
Supposing by way of contradiction that $a_i+c_ige 9$, then it is possible to find $9$ spies such that none of them spy on $A_i$. Imagine trying to make a chain using $A_i$ and those $9$ spies.
$endgroup$
– Mike Earnest
Dec 24 '18 at 18:46
$begingroup$
Supposing by way of contradiction that $a_i+c_ige 9$, then it is possible to find $9$ spies such that none of them spy on $A_i$. Imagine trying to make a chain using $A_i$ and those $9$ spies.
$endgroup$
– Mike Earnest
Dec 24 '18 at 18:46
$begingroup$
silly me, I kept considering the complementary of the set and got nothing. Do you think it's better to delete the question, or would you put this as an answer so that I can approve it?
$endgroup$
– mau
Dec 24 '18 at 20:45
$begingroup$
silly me, I kept considering the complementary of the set and got nothing. Do you think it's better to delete the question, or would you put this as an answer so that I can approve it?
$endgroup$
– mau
Dec 24 '18 at 20:45
$begingroup$
Well, I do not feel the need to write an answer, do what you like.
$endgroup$
– Mike Earnest
Dec 24 '18 at 22:11
$begingroup$
Well, I do not feel the need to write an answer, do what you like.
$endgroup$
– Mike Earnest
Dec 24 '18 at 22:11
$begingroup$
It's a valid question, even if the answer was more simple than you expected. Someone in the future may find it helpful. I suggest you leave it. I do not believe that there is any problem with leaving it without an accepted answer. Many such questions exist in this forum.
$endgroup$
– Paul Sinclair
Dec 25 '18 at 11:31
$begingroup$
It's a valid question, even if the answer was more simple than you expected. Someone in the future may find it helpful. I suggest you leave it. I do not believe that there is any problem with leaving it without an accepted answer. Many such questions exist in this forum.
$endgroup$
– Paul Sinclair
Dec 25 '18 at 11:31
add a comment |
0
active
oldest
votes
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
});
}
});
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3051534%2fspies-how-to-get-an-inequality%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
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.
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3051534%2fspies-how-to-get-an-inequality%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
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
1
$begingroup$
Supposing by way of contradiction that $a_i+c_ige 9$, then it is possible to find $9$ spies such that none of them spy on $A_i$. Imagine trying to make a chain using $A_i$ and those $9$ spies.
$endgroup$
– Mike Earnest
Dec 24 '18 at 18:46
$begingroup$
silly me, I kept considering the complementary of the set and got nothing. Do you think it's better to delete the question, or would you put this as an answer so that I can approve it?
$endgroup$
– mau
Dec 24 '18 at 20:45
$begingroup$
Well, I do not feel the need to write an answer, do what you like.
$endgroup$
– Mike Earnest
Dec 24 '18 at 22:11
$begingroup$
It's a valid question, even if the answer was more simple than you expected. Someone in the future may find it helpful. I suggest you leave it. I do not believe that there is any problem with leaving it without an accepted answer. Many such questions exist in this forum.
$endgroup$
– Paul Sinclair
Dec 25 '18 at 11:31