Mixing
A game with coins
$begingroup$
You have 15 coins which are split to number of piles, in each step you must collect 1 coin from each pile and form a new pile and so on.
Prove that no matter how the arrangement was in the beginning you will end up in the stable case in which you have 5 piles of coins (1 with 1 coin, one with 2 coins .. till 1 with 5 coins).
It can be generalized to a number of coins N which equals N=m(m+1) where m is natural
elementary-number-theory
asked Jan 16 at 13:25
Joshua Haim MamouJoshua Haim Mamou
245
$endgroup$
add a comment |
$begingroup$
You have 15 coins which are split to number of piles, in each step you must collect 1 coin from each pile and form a new pile and so on.
Prove that no matter how the arrangement was in the beginning you will end up in the stable case in which you have 5 piles of coins (1 with 1 coin, one with 2 coins .. till 1 with 5 coins).
It can be generalized to a number of coins N which equals N=m(m+1) where m is natural
elementary-number-theory
asked Jan 16 at 13:25
Joshua Haim MamouJoshua Haim Mamou
245
$endgroup$
$begingroup$
What have you tried so far?
$endgroup$
– Mindlack
Jan 16 at 13:33
$begingroup$
I only have time for a hint. A standard way to approach such kind of question is to construct certain invariant and keep track on them after each step. If the invariant is strictly monotone then you can claim that your operation stabilizes. For this question, the idea is to sort the piles in descending order and see how many coins are above the $5,4,3,2,1$-triangle. For instance, if the initial state is $3,3,3,2,2,2$, then $0+0+0+0+1+2=3$ coins are above the triangle. After the first step, it will give you $6,2,2,2,1,1,1$ and $1+0+0+0+0+1+1=3$ will be above the triangle.
$endgroup$
– Hw Chu
Jan 16 at 14:59
$begingroup$
Sadly the "above the triangle" invariant is only decreasing, but not strictly decreasing. So you need to get an auxiliary invariant to finish up, and that invariant is actually also something recording the coins above the triangle, but something more informative.
$endgroup$
– Hw Chu
Jan 16 at 15:00
$begingroup$
Like what? What more information?
$endgroup$
– Joshua Haim Mamou
Jan 17 at 9:51
add a comment |
$begingroup$
You have 15 coins which are split to number of piles, in each step you must collect 1 coin from each pile and form a new pile and so on.
Prove that no matter how the arrangement was in the beginning you will end up in the stable case in which you have 5 piles of coins (1 with 1 coin, one with 2 coins .. till 1 with 5 coins).
It can be generalized to a number of coins N which equals N=m(m+1) where m is natural
elementary-number-theory
asked Jan 16 at 13:25
Joshua Haim MamouJoshua Haim Mamou
245
$endgroup$
You have 15 coins which are split to number of piles, in each step you must collect 1 coin from each pile and form a new pile and so on.
Prove that no matter how the arrangement was in the beginning you will end up in the stable case in which you have 5 piles of coins (1 with 1 coin, one with 2 coins .. till 1 with 5 coins).
It can be generalized to a number of coins N which equals N=m(m+1) where m is natural
elementary-number-theory
elementary-number-theory
asked Jan 16 at 13:25
Joshua Haim MamouJoshua Haim Mamou
245
asked Jan 16 at 13:25
Joshua Haim MamouJoshua Haim Mamou
245
edited Jan 16 at 14:04
Joshua Haim Mamou
asked Jan 16 at 13:25
Joshua Haim MamouJoshua Haim Mamou
245
asked Jan 16 at 13:25
Joshua Haim MamouJoshua Haim Mamou
245
asked Jan 16 at 13:25
Joshua Haim MamouJoshua Haim Mamou
245
245
$begingroup$
What have you tried so far?
$endgroup$
– Mindlack
Jan 16 at 13:33
$begingroup$
I only have time for a hint. A standard way to approach such kind of question is to construct certain invariant and keep track on them after each step. If the invariant is strictly monotone then you can claim that your operation stabilizes. For this question, the idea is to sort the piles in descending order and see how many coins are above the $5,4,3,2,1$-triangle. For instance, if the initial state is $3,3,3,2,2,2$, then $0+0+0+0+1+2=3$ coins are above the triangle. After the first step, it will give you $6,2,2,2,1,1,1$ and $1+0+0+0+0+1+1=3$ will be above the triangle.
$endgroup$
– Hw Chu
Jan 16 at 14:59
$begingroup$
Sadly the "above the triangle" invariant is only decreasing, but not strictly decreasing. So you need to get an auxiliary invariant to finish up, and that invariant is actually also something recording the coins above the triangle, but something more informative.
$endgroup$
– Hw Chu
Jan 16 at 15:00
$begingroup$
Like what? What more information?
$endgroup$
– Joshua Haim Mamou
Jan 17 at 9:51
add a comment |
$begingroup$
What have you tried so far?
$endgroup$
– Mindlack
Jan 16 at 13:33
$begingroup$
I only have time for a hint. A standard way to approach such kind of question is to construct certain invariant and keep track on them after each step. If the invariant is strictly monotone then you can claim that your operation stabilizes. For this question, the idea is to sort the piles in descending order and see how many coins are above the $5,4,3,2,1$-triangle. For instance, if the initial state is $3,3,3,2,2,2$, then $0+0+0+0+1+2=3$ coins are above the triangle. After the first step, it will give you $6,2,2,2,1,1,1$ and $1+0+0+0+0+1+1=3$ will be above the triangle.
$endgroup$
– Hw Chu
Jan 16 at 14:59
$begingroup$
Sadly the "above the triangle" invariant is only decreasing, but not strictly decreasing. So you need to get an auxiliary invariant to finish up, and that invariant is actually also something recording the coins above the triangle, but something more informative.
$endgroup$
– Hw Chu
Jan 16 at 15:00
$begingroup$
Like what? What more information?
$endgroup$
– Joshua Haim Mamou
Jan 17 at 9:51
$begingroup$
What have you tried so far?
$endgroup$
– Mindlack
Jan 16 at 13:33
$begingroup$
What have you tried so far?
$endgroup$
– Mindlack
Jan 16 at 13:33
$begingroup$
I only have time for a hint. A standard way to approach such kind of question is to construct certain invariant and keep track on them after each step. If the invariant is strictly monotone then you can claim that your operation stabilizes. For this question, the idea is to sort the piles in descending order and see how many coins are above the $5,4,3,2,1$-triangle. For instance, if the initial state is $3,3,3,2,2,2$, then $0+0+0+0+1+2=3$ coins are above the triangle. After the first step, it will give you $6,2,2,2,1,1,1$ and $1+0+0+0+0+1+1=3$ will be above the triangle.
$endgroup$
– Hw Chu
Jan 16 at 14:59
$begingroup$
I only have time for a hint. A standard way to approach such kind of question is to construct certain invariant and keep track on them after each step. If the invariant is strictly monotone then you can claim that your operation stabilizes. For this question, the idea is to sort the piles in descending order and see how many coins are above the $5,4,3,2,1$-triangle. For instance, if the initial state is $3,3,3,2,2,2$, then $0+0+0+0+1+2=3$ coins are above the triangle. After the first step, it will give you $6,2,2,2,1,1,1$ and $1+0+0+0+0+1+1=3$ will be above the triangle.
$endgroup$
– Hw Chu
Jan 16 at 14:59
$begingroup$
Sadly the "above the triangle" invariant is only decreasing, but not strictly decreasing. So you need to get an auxiliary invariant to finish up, and that invariant is actually also something recording the coins above the triangle, but something more informative.
$endgroup$
– Hw Chu
Jan 16 at 15:00
$begingroup$
Sadly the "above the triangle" invariant is only decreasing, but not strictly decreasing. So you need to get an auxiliary invariant to finish up, and that invariant is actually also something recording the coins above the triangle, but something more informative.
$endgroup$
– Hw Chu
Jan 16 at 15:00
$begingroup$
Like what? What more information?
$endgroup$
– Joshua Haim Mamou
Jan 17 at 9:51
$begingroup$
Like what? What more information?
$endgroup$
– Joshua Haim Mamou
Jan 17 at 9:51
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
generale case :
First you can show that because the number of pile is constant, exactly one pile should have one coin at each step.
Then by induction you can show that for each $i$ less or equal to the number of pile. There is exactly one pile with $i$ coins.
answered Jan 16 at 14:23
IevgeniIevgeni
1
$endgroup$
$begingroup$
How is the number of piles constant ? If the initial state is $3,3,3,3,3$ then the next state is $2,2,2,2,2,5$ and the number of piles has increased from $5$ to $6$ surely ?
$endgroup$
– gandalf61
Jan 16 at 15:15
$begingroup$
@levgeni That works if you can show that game always eventually reaches a single stable state. But how do you know it does not repeat a cycle of two (or more) states ? For example with $4$ coins $(1,3)$, $(2,2)$ and $(1,1,2)$ form a repeating cycle with three states.
$endgroup$
– gandalf61
Jan 16 at 15:34
$begingroup$
You have right, it misses something in my reasoning...
$endgroup$
– Ievgeni
Jan 16 at 15:45
add a comment |
$begingroup$
As Levgeni shows above, a single fixed state (as opposed to a cycle which loops through multiple states) must have the form $(1,2,3,dots,n)$.
I can also show that any state that differs from a $(1,2,3,dots,n)$ state by $1$ in one or more places will be part of cycle of length $n+1$. So for $16$ coins, for example, there is a cycle
$(1,2,3,4,6) rightarrow (1,2,3,5,5) rightarrow (1,2,4,4,5) rightarrow (1,3,3,4,5) rightarrow (2,2,3,4,5) rightarrow (1,1,2,3,4,5) rightarrow (1,2,3,4,6)$
and for $17$ coins there are two distinct $6$-cycles:
$(1,2,3,5,6) rightarrow (1,2,4,5,5) rightarrow (1,3,4,4,5) rightarrow (2,3,3,4,5) rightarrow (1,2,2,3,4,5) rightarrow (1,1,2,3,4,6) rightarrow (1,2,3,5,6)$
and
$(1,2,4,4,6) rightarrow (1,3,3,5,5) rightarrow (2,2,4,4,5) rightarrow (1,1,3,3,4,5) rightarrow (2,2,3,4,6) rightarrow (1,1,2,3,5,5) rightarrow (1,2,4,4,6)$
I cannot yet prove that these are the only possible cycles.
answered Jan 21 at 8:56
gandalf61gandalf61
8,771725
$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
});
}
});
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%2f3075719%2fa-game-with-coins%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
generale case :
First you can show that because the number of pile is constant, exactly one pile should have one coin at each step.
Then by induction you can show that for each $i$ less or equal to the number of pile. There is exactly one pile with $i$ coins.
answered Jan 16 at 14:23
IevgeniIevgeni
1
$endgroup$
$begingroup$
How is the number of piles constant ? If the initial state is $3,3,3,3,3$ then the next state is $2,2,2,2,2,5$ and the number of piles has increased from $5$ to $6$ surely ?
$endgroup$
– gandalf61
Jan 16 at 15:15
$begingroup$
@levgeni That works if you can show that game always eventually reaches a single stable state. But how do you know it does not repeat a cycle of two (or more) states ? For example with $4$ coins $(1,3)$, $(2,2)$ and $(1,1,2)$ form a repeating cycle with three states.
$endgroup$
– gandalf61
Jan 16 at 15:34
$begingroup$
You have right, it misses something in my reasoning...
$endgroup$
– Ievgeni
Jan 16 at 15:45
add a comment |
$begingroup$
generale case :
First you can show that because the number of pile is constant, exactly one pile should have one coin at each step.
Then by induction you can show that for each $i$ less or equal to the number of pile. There is exactly one pile with $i$ coins.
answered Jan 16 at 14:23
IevgeniIevgeni
1
$endgroup$
$begingroup$
How is the number of piles constant ? If the initial state is $3,3,3,3,3$ then the next state is $2,2,2,2,2,5$ and the number of piles has increased from $5$ to $6$ surely ?
$endgroup$
– gandalf61
Jan 16 at 15:15
$begingroup$
@levgeni That works if you can show that game always eventually reaches a single stable state. But how do you know it does not repeat a cycle of two (or more) states ? For example with $4$ coins $(1,3)$, $(2,2)$ and $(1,1,2)$ form a repeating cycle with three states.
$endgroup$
– gandalf61
Jan 16 at 15:34
$begingroup$
You have right, it misses something in my reasoning...
$endgroup$
– Ievgeni
Jan 16 at 15:45
add a comment |
$begingroup$
generale case :
First you can show that because the number of pile is constant, exactly one pile should have one coin at each step.
Then by induction you can show that for each $i$ less or equal to the number of pile. There is exactly one pile with $i$ coins.
answered Jan 16 at 14:23
IevgeniIevgeni
1
$endgroup$
generale case :
First you can show that because the number of pile is constant, exactly one pile should have one coin at each step.
Then by induction you can show that for each $i$ less or equal to the number of pile. There is exactly one pile with $i$ coins.
answered Jan 16 at 14:23
IevgeniIevgeni
1
answered Jan 16 at 14:23
IevgeniIevgeni
1
answered Jan 16 at 14:23
IevgeniIevgeni
1
answered Jan 16 at 14:23
IevgeniIevgeni
1
1
$begingroup$
How is the number of piles constant ? If the initial state is $3,3,3,3,3$ then the next state is $2,2,2,2,2,5$ and the number of piles has increased from $5$ to $6$ surely ?
$endgroup$
– gandalf61
Jan 16 at 15:15
$begingroup$
@levgeni That works if you can show that game always eventually reaches a single stable state. But how do you know it does not repeat a cycle of two (or more) states ? For example with $4$ coins $(1,3)$, $(2,2)$ and $(1,1,2)$ form a repeating cycle with three states.
$endgroup$
– gandalf61
Jan 16 at 15:34
$begingroup$
You have right, it misses something in my reasoning...
$endgroup$
– Ievgeni
Jan 16 at 15:45
add a comment |
$begingroup$
How is the number of piles constant ? If the initial state is $3,3,3,3,3$ then the next state is $2,2,2,2,2,5$ and the number of piles has increased from $5$ to $6$ surely ?
$endgroup$
– gandalf61
Jan 16 at 15:15
$begingroup$
@levgeni That works if you can show that game always eventually reaches a single stable state. But how do you know it does not repeat a cycle of two (or more) states ? For example with $4$ coins $(1,3)$, $(2,2)$ and $(1,1,2)$ form a repeating cycle with three states.
$endgroup$
– gandalf61
Jan 16 at 15:34
$begingroup$
You have right, it misses something in my reasoning...
$endgroup$
– Ievgeni
Jan 16 at 15:45
$begingroup$
How is the number of piles constant ? If the initial state is $3,3,3,3,3$ then the next state is $2,2,2,2,2,5$ and the number of piles has increased from $5$ to $6$ surely ?
$endgroup$
– gandalf61
Jan 16 at 15:15
$begingroup$
How is the number of piles constant ? If the initial state is $3,3,3,3,3$ then the next state is $2,2,2,2,2,5$ and the number of piles has increased from $5$ to $6$ surely ?
$endgroup$
– gandalf61
Jan 16 at 15:15
$begingroup$
@levgeni That works if you can show that game always eventually reaches a single stable state. But how do you know it does not repeat a cycle of two (or more) states ? For example with $4$ coins $(1,3)$, $(2,2)$ and $(1,1,2)$ form a repeating cycle with three states.
$endgroup$
– gandalf61
Jan 16 at 15:34
$begingroup$
@levgeni That works if you can show that game always eventually reaches a single stable state. But how do you know it does not repeat a cycle of two (or more) states ? For example with $4$ coins $(1,3)$, $(2,2)$ and $(1,1,2)$ form a repeating cycle with three states.
$endgroup$
– gandalf61
Jan 16 at 15:34
$begingroup$
You have right, it misses something in my reasoning...
$endgroup$
– Ievgeni
Jan 16 at 15:45
$begingroup$
You have right, it misses something in my reasoning...
$endgroup$
– Ievgeni
Jan 16 at 15:45
add a comment |
$begingroup$
As Levgeni shows above, a single fixed state (as opposed to a cycle which loops through multiple states) must have the form $(1,2,3,dots,n)$.
I can also show that any state that differs from a $(1,2,3,dots,n)$ state by $1$ in one or more places will be part of cycle of length $n+1$. So for $16$ coins, for example, there is a cycle
$(1,2,3,4,6) rightarrow (1,2,3,5,5) rightarrow (1,2,4,4,5) rightarrow (1,3,3,4,5) rightarrow (2,2,3,4,5) rightarrow (1,1,2,3,4,5) rightarrow (1,2,3,4,6)$
and for $17$ coins there are two distinct $6$-cycles:
$(1,2,3,5,6) rightarrow (1,2,4,5,5) rightarrow (1,3,4,4,5) rightarrow (2,3,3,4,5) rightarrow (1,2,2,3,4,5) rightarrow (1,1,2,3,4,6) rightarrow (1,2,3,5,6)$
and
$(1,2,4,4,6) rightarrow (1,3,3,5,5) rightarrow (2,2,4,4,5) rightarrow (1,1,3,3,4,5) rightarrow (2,2,3,4,6) rightarrow (1,1,2,3,5,5) rightarrow (1,2,4,4,6)$
I cannot yet prove that these are the only possible cycles.
answered Jan 21 at 8:56
gandalf61gandalf61
8,771725
$endgroup$
add a comment |
$begingroup$
As Levgeni shows above, a single fixed state (as opposed to a cycle which loops through multiple states) must have the form $(1,2,3,dots,n)$.
I can also show that any state that differs from a $(1,2,3,dots,n)$ state by $1$ in one or more places will be part of cycle of length $n+1$. So for $16$ coins, for example, there is a cycle
$(1,2,3,4,6) rightarrow (1,2,3,5,5) rightarrow (1,2,4,4,5) rightarrow (1,3,3,4,5) rightarrow (2,2,3,4,5) rightarrow (1,1,2,3,4,5) rightarrow (1,2,3,4,6)$
and for $17$ coins there are two distinct $6$-cycles:
$(1,2,3,5,6) rightarrow (1,2,4,5,5) rightarrow (1,3,4,4,5) rightarrow (2,3,3,4,5) rightarrow (1,2,2,3,4,5) rightarrow (1,1,2,3,4,6) rightarrow (1,2,3,5,6)$
and
$(1,2,4,4,6) rightarrow (1,3,3,5,5) rightarrow (2,2,4,4,5) rightarrow (1,1,3,3,4,5) rightarrow (2,2,3,4,6) rightarrow (1,1,2,3,5,5) rightarrow (1,2,4,4,6)$
I cannot yet prove that these are the only possible cycles.
answered Jan 21 at 8:56
gandalf61gandalf61
8,771725
$endgroup$
add a comment |
$begingroup$
As Levgeni shows above, a single fixed state (as opposed to a cycle which loops through multiple states) must have the form $(1,2,3,dots,n)$.
I can also show that any state that differs from a $(1,2,3,dots,n)$ state by $1$ in one or more places will be part of cycle of length $n+1$. So for $16$ coins, for example, there is a cycle
$(1,2,3,4,6) rightarrow (1,2,3,5,5) rightarrow (1,2,4,4,5) rightarrow (1,3,3,4,5) rightarrow (2,2,3,4,5) rightarrow (1,1,2,3,4,5) rightarrow (1,2,3,4,6)$
and for $17$ coins there are two distinct $6$-cycles:
$(1,2,3,5,6) rightarrow (1,2,4,5,5) rightarrow (1,3,4,4,5) rightarrow (2,3,3,4,5) rightarrow (1,2,2,3,4,5) rightarrow (1,1,2,3,4,6) rightarrow (1,2,3,5,6)$
and
$(1,2,4,4,6) rightarrow (1,3,3,5,5) rightarrow (2,2,4,4,5) rightarrow (1,1,3,3,4,5) rightarrow (2,2,3,4,6) rightarrow (1,1,2,3,5,5) rightarrow (1,2,4,4,6)$
I cannot yet prove that these are the only possible cycles.
answered Jan 21 at 8:56
gandalf61gandalf61
8,771725
$endgroup$
As Levgeni shows above, a single fixed state (as opposed to a cycle which loops through multiple states) must have the form $(1,2,3,dots,n)$.
I can also show that any state that differs from a $(1,2,3,dots,n)$ state by $1$ in one or more places will be part of cycle of length $n+1$. So for $16$ coins, for example, there is a cycle
$(1,2,3,4,6) rightarrow (1,2,3,5,5) rightarrow (1,2,4,4,5) rightarrow (1,3,3,4,5) rightarrow (2,2,3,4,5) rightarrow (1,1,2,3,4,5) rightarrow (1,2,3,4,6)$
and for $17$ coins there are two distinct $6$-cycles:
$(1,2,3,5,6) rightarrow (1,2,4,5,5) rightarrow (1,3,4,4,5) rightarrow (2,3,3,4,5) rightarrow (1,2,2,3,4,5) rightarrow (1,1,2,3,4,6) rightarrow (1,2,3,5,6)$
and
$(1,2,4,4,6) rightarrow (1,3,3,5,5) rightarrow (2,2,4,4,5) rightarrow (1,1,3,3,4,5) rightarrow (2,2,3,4,6) rightarrow (1,1,2,3,5,5) rightarrow (1,2,4,4,6)$
I cannot yet prove that these are the only possible cycles.
answered Jan 21 at 8:56
gandalf61gandalf61
8,771725
answered Jan 21 at 8:56
gandalf61gandalf61
8,771725
answered Jan 21 at 8:56
gandalf61gandalf61
8,771725
answered Jan 21 at 8:56
gandalf61gandalf61
8,771725
8,771725
add a comment |
add a comment |
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%2f3075719%2fa-game-with-coins%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
$begingroup$
What have you tried so far?
$endgroup$
– Mindlack
Jan 16 at 13:33
$begingroup$
I only have time for a hint. A standard way to approach such kind of question is to construct certain invariant and keep track on them after each step. If the invariant is strictly monotone then you can claim that your operation stabilizes. For this question, the idea is to sort the piles in descending order and see how many coins are above the $5,4,3,2,1$-triangle. For instance, if the initial state is $3,3,3,2,2,2$, then $0+0+0+0+1+2=3$ coins are above the triangle. After the first step, it will give you $6,2,2,2,1,1,1$ and $1+0+0+0+0+1+1=3$ will be above the triangle.
$endgroup$
– Hw Chu
Jan 16 at 14:59
$begingroup$
Sadly the "above the triangle" invariant is only decreasing, but not strictly decreasing. So you need to get an auxiliary invariant to finish up, and that invariant is actually also something recording the coins above the triangle, but something more informative.
$endgroup$
– Hw Chu
Jan 16 at 15:00
$begingroup$
Like what? What more information?
$endgroup$
– Joshua Haim Mamou
Jan 17 at 9:51