Mixing
A question about IMO 1986 P3
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
IMO 1986 P3: To each vertex of a pentagon, we assign an integer $x_i$ with sum $s=sum x_i>0$. If $x,y,z$ are numbers assigned to three successive vertices and if $y<0$, then we replace $(x,y,z)$ by $(x+y,-y,y+z)$. This step is repeated as long as there is a $y<0$. Decide if the algorithm always stops. (Most difficult problem of the IMO).
After generating some examples, I found the following pattern: if $s$ is the sum of the integers at the vertices, then $sum_i=1^5 (s-x_i)^2$ is a weakly decreasing function. Is this true? The solution, which was apparently given by only 11 students in the world, uses the function $sum (x_i-x_i+2)^2$, and shows that it is strictly decreasing. Moreover, if the function $sum_i=1^5 (s-x_i)^2$ is indeed weakly decreasing, does it become strictly decreasing every $j$ iterations, where $j>1$?
combinatorics contest-math combinatorial-game-theory
edited Jul 31 at 15:40
Batominovski
22.8k22776
asked Jul 31 at 13:32
fierydemon
4,32312151
add a comment |Â
up vote
2
down vote
favorite
IMO 1986 P3: To each vertex of a pentagon, we assign an integer $x_i$ with sum $s=sum x_i>0$. If $x,y,z$ are numbers assigned to three successive vertices and if $y<0$, then we replace $(x,y,z)$ by $(x+y,-y,y+z)$. This step is repeated as long as there is a $y<0$. Decide if the algorithm always stops. (Most difficult problem of the IMO).
After generating some examples, I found the following pattern: if $s$ is the sum of the integers at the vertices, then $sum_i=1^5 (s-x_i)^2$ is a weakly decreasing function. Is this true? The solution, which was apparently given by only 11 students in the world, uses the function $sum (x_i-x_i+2)^2$, and shows that it is strictly decreasing. Moreover, if the function $sum_i=1^5 (s-x_i)^2$ is indeed weakly decreasing, does it become strictly decreasing every $j$ iterations, where $j>1$?
combinatorics contest-math combinatorial-game-theory
edited Jul 31 at 15:40
Batominovski
22.8k22776
asked Jul 31 at 13:32
fierydemon
4,32312151
@saulspatz- Edited, thanks
– fierydemon
Jul 31 at 14:00
Can you add the proof that your sum $sum_i=1^5,(s-x_i)^2$ is weakly decreasing? Maybe we will notice something and be able to help out. However, in my opinion, this is not a natural choice. In this kind of problems, I would expect that a good semivariant would measure how much the data $x_1,x_2,ldots,x_5$ are different. Something like $sum |x_i-x_j|$ or $sum (x_i-x_j)^2$ would be a good choice. And it is no surprising at all that $sum (x_i-x_i+2)^2$ turns out to be a good semivariant.
– Batominovski
Jul 31 at 14:13
@Batominovski What is the definition of semivariant, please? I can find a few uses of the term by googling, but no definition.
– saulspatz
Jul 31 at 14:18
Well, if you have a combinatorial process, a semivariance is a function that takes your current state and returns some real number (usually a positive integer). We want this function to either increase only or decrease only (weakly or strongly), as the process progresses further. (This is why the prefix semi- is there. The change is in only one direction, instead of both up and down.) This is in contrast with an invariance, which does not change as progresses are made.
– Batominovski
Jul 31 at 14:22
@Batominovski Thanks for the explanation.
– saulspatz
Jul 31 at 14:23
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
IMO 1986 P3: To each vertex of a pentagon, we assign an integer $x_i$ with sum $s=sum x_i>0$. If $x,y,z$ are numbers assigned to three successive vertices and if $y<0$, then we replace $(x,y,z)$ by $(x+y,-y,y+z)$. This step is repeated as long as there is a $y<0$. Decide if the algorithm always stops. (Most difficult problem of the IMO).
After generating some examples, I found the following pattern: if $s$ is the sum of the integers at the vertices, then $sum_i=1^5 (s-x_i)^2$ is a weakly decreasing function. Is this true? The solution, which was apparently given by only 11 students in the world, uses the function $sum (x_i-x_i+2)^2$, and shows that it is strictly decreasing. Moreover, if the function $sum_i=1^5 (s-x_i)^2$ is indeed weakly decreasing, does it become strictly decreasing every $j$ iterations, where $j>1$?
combinatorics contest-math combinatorial-game-theory
edited Jul 31 at 15:40
Batominovski
22.8k22776
asked Jul 31 at 13:32
fierydemon
4,32312151
IMO 1986 P3: To each vertex of a pentagon, we assign an integer $x_i$ with sum $s=sum x_i>0$. If $x,y,z$ are numbers assigned to three successive vertices and if $y<0$, then we replace $(x,y,z)$ by $(x+y,-y,y+z)$. This step is repeated as long as there is a $y<0$. Decide if the algorithm always stops. (Most difficult problem of the IMO).
After generating some examples, I found the following pattern: if $s$ is the sum of the integers at the vertices, then $sum_i=1^5 (s-x_i)^2$ is a weakly decreasing function. Is this true? The solution, which was apparently given by only 11 students in the world, uses the function $sum (x_i-x_i+2)^2$, and shows that it is strictly decreasing. Moreover, if the function $sum_i=1^5 (s-x_i)^2$ is indeed weakly decreasing, does it become strictly decreasing every $j$ iterations, where $j>1$?
combinatorics contest-math combinatorial-game-theory
edited Jul 31 at 15:40
Batominovski
22.8k22776
asked Jul 31 at 13:32
fierydemon
4,32312151
edited Jul 31 at 15:40
Batominovski
22.8k22776
edited Jul 31 at 15:40
Batominovski
22.8k22776
edited Jul 31 at 15:40
Batominovski
22.8k22776
22.8k22776
asked Jul 31 at 13:32
fierydemon
4,32312151
asked Jul 31 at 13:32
fierydemon
4,32312151
asked Jul 31 at 13:32
fierydemon
4,32312151
4,32312151
@saulspatz- Edited, thanks
– fierydemon
Jul 31 at 14:00
Can you add the proof that your sum $sum_i=1^5,(s-x_i)^2$ is weakly decreasing? Maybe we will notice something and be able to help out. However, in my opinion, this is not a natural choice. In this kind of problems, I would expect that a good semivariant would measure how much the data $x_1,x_2,ldots,x_5$ are different. Something like $sum |x_i-x_j|$ or $sum (x_i-x_j)^2$ would be a good choice. And it is no surprising at all that $sum (x_i-x_i+2)^2$ turns out to be a good semivariant.
– Batominovski
Jul 31 at 14:13
@Batominovski What is the definition of semivariant, please? I can find a few uses of the term by googling, but no definition.
– saulspatz
Jul 31 at 14:18
Well, if you have a combinatorial process, a semivariance is a function that takes your current state and returns some real number (usually a positive integer). We want this function to either increase only or decrease only (weakly or strongly), as the process progresses further. (This is why the prefix semi- is there. The change is in only one direction, instead of both up and down.) This is in contrast with an invariance, which does not change as progresses are made.
– Batominovski
Jul 31 at 14:22
@Batominovski Thanks for the explanation.
– saulspatz
Jul 31 at 14:23
add a comment |Â
@saulspatz- Edited, thanks
– fierydemon
Jul 31 at 14:00
Can you add the proof that your sum $sum_i=1^5,(s-x_i)^2$ is weakly decreasing? Maybe we will notice something and be able to help out. However, in my opinion, this is not a natural choice. In this kind of problems, I would expect that a good semivariant would measure how much the data $x_1,x_2,ldots,x_5$ are different. Something like $sum |x_i-x_j|$ or $sum (x_i-x_j)^2$ would be a good choice. And it is no surprising at all that $sum (x_i-x_i+2)^2$ turns out to be a good semivariant.
– Batominovski
Jul 31 at 14:13
@Batominovski What is the definition of semivariant, please? I can find a few uses of the term by googling, but no definition.
– saulspatz
Jul 31 at 14:18
Well, if you have a combinatorial process, a semivariance is a function that takes your current state and returns some real number (usually a positive integer). We want this function to either increase only or decrease only (weakly or strongly), as the process progresses further. (This is why the prefix semi- is there. The change is in only one direction, instead of both up and down.) This is in contrast with an invariance, which does not change as progresses are made.
– Batominovski
Jul 31 at 14:22
@Batominovski Thanks for the explanation.
– saulspatz
Jul 31 at 14:23
@saulspatz- Edited, thanks
– fierydemon
Jul 31 at 14:00
@saulspatz- Edited, thanks
– fierydemon
Jul 31 at 14:00
Can you add the proof that your sum $sum_i=1^5,(s-x_i)^2$ is weakly decreasing? Maybe we will notice something and be able to help out. However, in my opinion, this is not a natural choice. In this kind of problems, I would expect that a good semivariant would measure how much the data $x_1,x_2,ldots,x_5$ are different. Something like $sum |x_i-x_j|$ or $sum (x_i-x_j)^2$ would be a good choice. And it is no surprising at all that $sum (x_i-x_i+2)^2$ turns out to be a good semivariant.
– Batominovski
Jul 31 at 14:13
Can you add the proof that your sum $sum_i=1^5,(s-x_i)^2$ is weakly decreasing? Maybe we will notice something and be able to help out. However, in my opinion, this is not a natural choice. In this kind of problems, I would expect that a good semivariant would measure how much the data $x_1,x_2,ldots,x_5$ are different. Something like $sum |x_i-x_j|$ or $sum (x_i-x_j)^2$ would be a good choice. And it is no surprising at all that $sum (x_i-x_i+2)^2$ turns out to be a good semivariant.
– Batominovski
Jul 31 at 14:13
@Batominovski What is the definition of semivariant, please? I can find a few uses of the term by googling, but no definition.
– saulspatz
Jul 31 at 14:18
@Batominovski What is the definition of semivariant, please? I can find a few uses of the term by googling, but no definition.
– saulspatz
Jul 31 at 14:18
Well, if you have a combinatorial process, a semivariance is a function that takes your current state and returns some real number (usually a positive integer). We want this function to either increase only or decrease only (weakly or strongly), as the process progresses further. (This is why the prefix semi- is there. The change is in only one direction, instead of both up and down.) This is in contrast with an invariance, which does not change as progresses are made.
– Batominovski
Jul 31 at 14:22
Well, if you have a combinatorial process, a semivariance is a function that takes your current state and returns some real number (usually a positive integer). We want this function to either increase only or decrease only (weakly or strongly), as the process progresses further. (This is why the prefix semi- is there. The change is in only one direction, instead of both up and down.) This is in contrast with an invariance, which does not change as progresses are made.
– Batominovski
Jul 31 at 14:22
@Batominovski Thanks for the explanation.
– saulspatz
Jul 31 at 14:23
@Batominovski Thanks for the explanation.
– saulspatz
Jul 31 at 14:23
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
1
down vote
accepted
I checked that $y:=sumlimits_i=1^5,(s-x_i)^2$ is not even a semivariant (apparently, the correct ending is t, not ce). For example, if we start with $(x_1,x_2,x_3,x_4,x_5):=(1,-3,1,1,1)$, then at the beginning, we have $$y=0^2+0^2+4^2+0^2+0^2=16,.$$
The only allowed move is $(x_1,x_2,x_3,x_4,x_5)mapsto (-2,3,-2,1,1)$. At this point,
$$y=0^2+3^2+(-2)^2+3^2+0^2=22,.$$
Therefore, $y=sumlimits_i=1^5,(s-x_i)^2$ is not a good function to be used.
For the sake of completeness, I shall supply a full answer to this IMO problem. I shall use the OP's hint. However, there is another semivariant, but it is very ugly. This semivariant is in the hidden box below.
The ugly semivariant ($u$ for ugly) I know is $$u:=sum_i=1^5,|x_i|+sum_i=1^5,|x_i+x_i+1|+sum_i=1^5,|x_i+x_i+1+x_i+2|+sum_i=1^5,|x_i+x_i+1+x_i+2+x_i+3|,.$$ If you feel somewhat bored today, then please have fun with this semivariant.
To not cause any confusion, suppose the $k$-th state is denoted by $left(x_1^k,x_2^k,x_3^k,x_4^k,x_5^kright)$. We shall prove that
$$z^k:=sum_i=1^5,left(x_i^k-x_i+2^kright)^2$$
is a (strong) semivariant. (The indices in the sum above are considered modulo $5$.) That is, $z^k>z^k+1$ as long as the game has not terminated. I should like to note that $s=sumlimits_i=1^5,x_i^k$ at all possible $k$.
Now, suppose without loss of generality that, at the $k$-th step, the transformation into the $(k+1)$-st step is given by $$left(x_1^k+1,x_2^k+1,x_3^k+1,x_4^k+1,x_5^k+1right)=left(x_1^k+x_2^k,-x_2^k,x_2^k+x_3^k,x_4^k,x_5^kright),.$$
Hence,
$$beginalignz^k+1-z^k
&=(-x_2^k-x_4^k)^2-(x_2^k-x_4^k)^2+(x_2^k+x_3^k-x_5^k)^2-(x_3^k-x_5^k)^2
\
&phantomaaaa+(x_4^k-x_1^k-x_2^k)^2-(x_4^k-x_1^k)^2+(x_5^k+x_2^k)^2-(x_5^k-x_2^k)^2
\
&=4x_2^kx_4^k+2(x_2^k)^2+2x_2^k(x_3^k-x_5^k)-2x_2^k(x_4^k-x_1^k)+4x_2^kx_5^k
\
&=2x_2^k(x_1^k+x_2^k+x_3^k+x_4^k+x_5^k)=2s,x_2^k,.
endalign$$
Since this move is only allowed when $x_2^k<0$ and since $s>0$, we conclude that $z^k+1-z^k<0$.
answered Jul 31 at 15:01
Batominovski
22.8k22776
I suppose semivariance is "the state of being a semivariant," or "the quality of a semivariant," those it's hard to say what either of those phrases mean. :-)
– saulspatz
Jul 31 at 15:06
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
I checked that $y:=sumlimits_i=1^5,(s-x_i)^2$ is not even a semivariant (apparently, the correct ending is t, not ce). For example, if we start with $(x_1,x_2,x_3,x_4,x_5):=(1,-3,1,1,1)$, then at the beginning, we have $$y=0^2+0^2+4^2+0^2+0^2=16,.$$
The only allowed move is $(x_1,x_2,x_3,x_4,x_5)mapsto (-2,3,-2,1,1)$. At this point,
$$y=0^2+3^2+(-2)^2+3^2+0^2=22,.$$
Therefore, $y=sumlimits_i=1^5,(s-x_i)^2$ is not a good function to be used.
For the sake of completeness, I shall supply a full answer to this IMO problem. I shall use the OP's hint. However, there is another semivariant, but it is very ugly. This semivariant is in the hidden box below.
The ugly semivariant ($u$ for ugly) I know is $$u:=sum_i=1^5,|x_i|+sum_i=1^5,|x_i+x_i+1|+sum_i=1^5,|x_i+x_i+1+x_i+2|+sum_i=1^5,|x_i+x_i+1+x_i+2+x_i+3|,.$$ If you feel somewhat bored today, then please have fun with this semivariant.
To not cause any confusion, suppose the $k$-th state is denoted by $left(x_1^k,x_2^k,x_3^k,x_4^k,x_5^kright)$. We shall prove that
$$z^k:=sum_i=1^5,left(x_i^k-x_i+2^kright)^2$$
is a (strong) semivariant. (The indices in the sum above are considered modulo $5$.) That is, $z^k>z^k+1$ as long as the game has not terminated. I should like to note that $s=sumlimits_i=1^5,x_i^k$ at all possible $k$.
Now, suppose without loss of generality that, at the $k$-th step, the transformation into the $(k+1)$-st step is given by $$left(x_1^k+1,x_2^k+1,x_3^k+1,x_4^k+1,x_5^k+1right)=left(x_1^k+x_2^k,-x_2^k,x_2^k+x_3^k,x_4^k,x_5^kright),.$$
Hence,
$$beginalignz^k+1-z^k
&=(-x_2^k-x_4^k)^2-(x_2^k-x_4^k)^2+(x_2^k+x_3^k-x_5^k)^2-(x_3^k-x_5^k)^2
\
&phantomaaaa+(x_4^k-x_1^k-x_2^k)^2-(x_4^k-x_1^k)^2+(x_5^k+x_2^k)^2-(x_5^k-x_2^k)^2
\
&=4x_2^kx_4^k+2(x_2^k)^2+2x_2^k(x_3^k-x_5^k)-2x_2^k(x_4^k-x_1^k)+4x_2^kx_5^k
\
&=2x_2^k(x_1^k+x_2^k+x_3^k+x_4^k+x_5^k)=2s,x_2^k,.
endalign$$
Since this move is only allowed when $x_2^k<0$ and since $s>0$, we conclude that $z^k+1-z^k<0$.
answered Jul 31 at 15:01
Batominovski
22.8k22776
I suppose semivariance is "the state of being a semivariant," or "the quality of a semivariant," those it's hard to say what either of those phrases mean. :-)
– saulspatz
Jul 31 at 15:06
add a comment |Â
up vote
1
down vote
accepted
I checked that $y:=sumlimits_i=1^5,(s-x_i)^2$ is not even a semivariant (apparently, the correct ending is t, not ce). For example, if we start with $(x_1,x_2,x_3,x_4,x_5):=(1,-3,1,1,1)$, then at the beginning, we have $$y=0^2+0^2+4^2+0^2+0^2=16,.$$
The only allowed move is $(x_1,x_2,x_3,x_4,x_5)mapsto (-2,3,-2,1,1)$. At this point,
$$y=0^2+3^2+(-2)^2+3^2+0^2=22,.$$
Therefore, $y=sumlimits_i=1^5,(s-x_i)^2$ is not a good function to be used.
For the sake of completeness, I shall supply a full answer to this IMO problem. I shall use the OP's hint. However, there is another semivariant, but it is very ugly. This semivariant is in the hidden box below.
The ugly semivariant ($u$ for ugly) I know is $$u:=sum_i=1^5,|x_i|+sum_i=1^5,|x_i+x_i+1|+sum_i=1^5,|x_i+x_i+1+x_i+2|+sum_i=1^5,|x_i+x_i+1+x_i+2+x_i+3|,.$$ If you feel somewhat bored today, then please have fun with this semivariant.
To not cause any confusion, suppose the $k$-th state is denoted by $left(x_1^k,x_2^k,x_3^k,x_4^k,x_5^kright)$. We shall prove that
$$z^k:=sum_i=1^5,left(x_i^k-x_i+2^kright)^2$$
is a (strong) semivariant. (The indices in the sum above are considered modulo $5$.) That is, $z^k>z^k+1$ as long as the game has not terminated. I should like to note that $s=sumlimits_i=1^5,x_i^k$ at all possible $k$.
Now, suppose without loss of generality that, at the $k$-th step, the transformation into the $(k+1)$-st step is given by $$left(x_1^k+1,x_2^k+1,x_3^k+1,x_4^k+1,x_5^k+1right)=left(x_1^k+x_2^k,-x_2^k,x_2^k+x_3^k,x_4^k,x_5^kright),.$$
Hence,
$$beginalignz^k+1-z^k
&=(-x_2^k-x_4^k)^2-(x_2^k-x_4^k)^2+(x_2^k+x_3^k-x_5^k)^2-(x_3^k-x_5^k)^2
\
&phantomaaaa+(x_4^k-x_1^k-x_2^k)^2-(x_4^k-x_1^k)^2+(x_5^k+x_2^k)^2-(x_5^k-x_2^k)^2
\
&=4x_2^kx_4^k+2(x_2^k)^2+2x_2^k(x_3^k-x_5^k)-2x_2^k(x_4^k-x_1^k)+4x_2^kx_5^k
\
&=2x_2^k(x_1^k+x_2^k+x_3^k+x_4^k+x_5^k)=2s,x_2^k,.
endalign$$
Since this move is only allowed when $x_2^k<0$ and since $s>0$, we conclude that $z^k+1-z^k<0$.
answered Jul 31 at 15:01
Batominovski
22.8k22776
I suppose semivariance is "the state of being a semivariant," or "the quality of a semivariant," those it's hard to say what either of those phrases mean. :-)
– saulspatz
Jul 31 at 15:06
add a comment |Â
up vote
1
down vote
accepted
up vote
1
down vote
accepted
I checked that $y:=sumlimits_i=1^5,(s-x_i)^2$ is not even a semivariant (apparently, the correct ending is t, not ce). For example, if we start with $(x_1,x_2,x_3,x_4,x_5):=(1,-3,1,1,1)$, then at the beginning, we have $$y=0^2+0^2+4^2+0^2+0^2=16,.$$
The only allowed move is $(x_1,x_2,x_3,x_4,x_5)mapsto (-2,3,-2,1,1)$. At this point,
$$y=0^2+3^2+(-2)^2+3^2+0^2=22,.$$
Therefore, $y=sumlimits_i=1^5,(s-x_i)^2$ is not a good function to be used.
For the sake of completeness, I shall supply a full answer to this IMO problem. I shall use the OP's hint. However, there is another semivariant, but it is very ugly. This semivariant is in the hidden box below.
The ugly semivariant ($u$ for ugly) I know is $$u:=sum_i=1^5,|x_i|+sum_i=1^5,|x_i+x_i+1|+sum_i=1^5,|x_i+x_i+1+x_i+2|+sum_i=1^5,|x_i+x_i+1+x_i+2+x_i+3|,.$$ If you feel somewhat bored today, then please have fun with this semivariant.
To not cause any confusion, suppose the $k$-th state is denoted by $left(x_1^k,x_2^k,x_3^k,x_4^k,x_5^kright)$. We shall prove that
$$z^k:=sum_i=1^5,left(x_i^k-x_i+2^kright)^2$$
is a (strong) semivariant. (The indices in the sum above are considered modulo $5$.) That is, $z^k>z^k+1$ as long as the game has not terminated. I should like to note that $s=sumlimits_i=1^5,x_i^k$ at all possible $k$.
Now, suppose without loss of generality that, at the $k$-th step, the transformation into the $(k+1)$-st step is given by $$left(x_1^k+1,x_2^k+1,x_3^k+1,x_4^k+1,x_5^k+1right)=left(x_1^k+x_2^k,-x_2^k,x_2^k+x_3^k,x_4^k,x_5^kright),.$$
Hence,
$$beginalignz^k+1-z^k
&=(-x_2^k-x_4^k)^2-(x_2^k-x_4^k)^2+(x_2^k+x_3^k-x_5^k)^2-(x_3^k-x_5^k)^2
\
&phantomaaaa+(x_4^k-x_1^k-x_2^k)^2-(x_4^k-x_1^k)^2+(x_5^k+x_2^k)^2-(x_5^k-x_2^k)^2
\
&=4x_2^kx_4^k+2(x_2^k)^2+2x_2^k(x_3^k-x_5^k)-2x_2^k(x_4^k-x_1^k)+4x_2^kx_5^k
\
&=2x_2^k(x_1^k+x_2^k+x_3^k+x_4^k+x_5^k)=2s,x_2^k,.
endalign$$
Since this move is only allowed when $x_2^k<0$ and since $s>0$, we conclude that $z^k+1-z^k<0$.
answered Jul 31 at 15:01
Batominovski
22.8k22776
I checked that $y:=sumlimits_i=1^5,(s-x_i)^2$ is not even a semivariant (apparently, the correct ending is t, not ce). For example, if we start with $(x_1,x_2,x_3,x_4,x_5):=(1,-3,1,1,1)$, then at the beginning, we have $$y=0^2+0^2+4^2+0^2+0^2=16,.$$
The only allowed move is $(x_1,x_2,x_3,x_4,x_5)mapsto (-2,3,-2,1,1)$. At this point,
$$y=0^2+3^2+(-2)^2+3^2+0^2=22,.$$
Therefore, $y=sumlimits_i=1^5,(s-x_i)^2$ is not a good function to be used.
For the sake of completeness, I shall supply a full answer to this IMO problem. I shall use the OP's hint. However, there is another semivariant, but it is very ugly. This semivariant is in the hidden box below.
The ugly semivariant ($u$ for ugly) I know is $$u:=sum_i=1^5,|x_i|+sum_i=1^5,|x_i+x_i+1|+sum_i=1^5,|x_i+x_i+1+x_i+2|+sum_i=1^5,|x_i+x_i+1+x_i+2+x_i+3|,.$$ If you feel somewhat bored today, then please have fun with this semivariant.
To not cause any confusion, suppose the $k$-th state is denoted by $left(x_1^k,x_2^k,x_3^k,x_4^k,x_5^kright)$. We shall prove that
$$z^k:=sum_i=1^5,left(x_i^k-x_i+2^kright)^2$$
is a (strong) semivariant. (The indices in the sum above are considered modulo $5$.) That is, $z^k>z^k+1$ as long as the game has not terminated. I should like to note that $s=sumlimits_i=1^5,x_i^k$ at all possible $k$.
Now, suppose without loss of generality that, at the $k$-th step, the transformation into the $(k+1)$-st step is given by $$left(x_1^k+1,x_2^k+1,x_3^k+1,x_4^k+1,x_5^k+1right)=left(x_1^k+x_2^k,-x_2^k,x_2^k+x_3^k,x_4^k,x_5^kright),.$$
Hence,
$$beginalignz^k+1-z^k
&=(-x_2^k-x_4^k)^2-(x_2^k-x_4^k)^2+(x_2^k+x_3^k-x_5^k)^2-(x_3^k-x_5^k)^2
\
&phantomaaaa+(x_4^k-x_1^k-x_2^k)^2-(x_4^k-x_1^k)^2+(x_5^k+x_2^k)^2-(x_5^k-x_2^k)^2
\
&=4x_2^kx_4^k+2(x_2^k)^2+2x_2^k(x_3^k-x_5^k)-2x_2^k(x_4^k-x_1^k)+4x_2^kx_5^k
\
&=2x_2^k(x_1^k+x_2^k+x_3^k+x_4^k+x_5^k)=2s,x_2^k,.
endalign$$
Since this move is only allowed when $x_2^k<0$ and since $s>0$, we conclude that $z^k+1-z^k<0$.
answered Jul 31 at 15:01
Batominovski
22.8k22776
edited Jul 31 at 19:30
answered Jul 31 at 15:01
Batominovski
22.8k22776
answered Jul 31 at 15:01
Batominovski
22.8k22776
answered Jul 31 at 15:01
Batominovski
22.8k22776
22.8k22776
I suppose semivariance is "the state of being a semivariant," or "the quality of a semivariant," those it's hard to say what either of those phrases mean. :-)
– saulspatz
Jul 31 at 15:06
add a comment |Â
I suppose semivariance is "the state of being a semivariant," or "the quality of a semivariant," those it's hard to say what either of those phrases mean. :-)
– saulspatz
Jul 31 at 15:06
I suppose semivariance is "the state of being a semivariant," or "the quality of a semivariant," those it's hard to say what either of those phrases mean. :-)
– saulspatz
Jul 31 at 15:06
I suppose semivariance is "the state of being a semivariant," or "the quality of a semivariant," those it's hard to say what either of those phrases mean. :-)
– saulspatz
Jul 31 at 15:06
add a comment |Â
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2868046%2fa-question-about-imo-1986-p3%23new-answer', 'question_page');
);
Post as a guest
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
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
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
@saulspatz- Edited, thanks
– fierydemon
Jul 31 at 14:00
Can you add the proof that your sum $sum_i=1^5,(s-x_i)^2$ is weakly decreasing? Maybe we will notice something and be able to help out. However, in my opinion, this is not a natural choice. In this kind of problems, I would expect that a good semivariant would measure how much the data $x_1,x_2,ldots,x_5$ are different. Something like $sum |x_i-x_j|$ or $sum (x_i-x_j)^2$ would be a good choice. And it is no surprising at all that $sum (x_i-x_i+2)^2$ turns out to be a good semivariant.
– Batominovski
Jul 31 at 14:13
@Batominovski What is the definition of semivariant, please? I can find a few uses of the term by googling, but no definition.
– saulspatz
Jul 31 at 14:18
Well, if you have a combinatorial process, a semivariance is a function that takes your current state and returns some real number (usually a positive integer). We want this function to either increase only or decrease only (weakly or strongly), as the process progresses further. (This is why the prefix semi- is there. The change is in only one direction, instead of both up and down.) This is in contrast with an invariance, which does not change as progresses are made.
– Batominovski
Jul 31 at 14:22
@Batominovski Thanks for the explanation.
– saulspatz
Jul 31 at 14:23