Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "1986 IMO Problems/Problem 3"

(Created page with "==Problem== To each vertex of a regular pentagon an integer is assigned, so that the sum of all five numbers is positive. If three consecutive vertices are assigned the number...")
 
(→‎Solution: make the proof more readable)
 
Line 3: Line 3:
  
 
==Solution==
 
==Solution==
−
The algorithm always stops. Consider the function<cmath>f(x_1, x_2, x_3, x_4, x_5)=\displaystyle\sum_{i=1}^5(x_i-x_{i+2})^2, x_6=x_1, x_7=x_2.</cmath>Clearly <math>f>0</math> always and <math>f</math> is integer valued. Suppose, WLOG, that <math>y=x_4<0</math>. Then <math>f_{\text{new}}-f_{\text{old}}=2Sx_4<0</math> since <math>S>0</math>. Thus if the algorithm does not stop, we can find an infinite decreasing sequence of nonnegative integers <math>f_0>f_1>f_2>\cdots</math>. This is impossible, so the algorithm must stop. <math>\Box</math>
+
The algorithm always stops. Indeed, consider the five numbers on the vertices of the pentagon as forming a <math>5</math>-tuple <math>\mathbf{x} = (x_1, x_2, x_3, x_4, x_5) \in \mathbb{Z}^5</math>. The sum of the five entries of this <math>5</math>-tuple is positive (by assumption), and stays unchanged through the entire process (since our operation does not change the sum); thus, it is always positive. Now, define the function <math>f : \mathbb{Z}^5 \to \mathbb{Z}</math> by
 +
<cmath>f(x_1, x_2, x_3, x_4, x_5)=\sum_{i=1}^5(x_i-x_{i+2})^2, \text{ where } x_6=x_1 \text{ and } x_7=x_2.</cmath>
 +
Clearly, <math>f \geq 0</math> always. Now, let <math>\mathbf{x}_{\text{old}} = (x_1, x_2, x_3, x_4, x_5)</math> and <math>\mathbf{x}_{\text{new}}</math> be two consecutive <math>5</math>-tuples obtained in this process. Thus, <math>\mathbf{x}_{\text{new}}</math> is obtained from <math>\mathbf{x}_{\text{old}}</math> by applying our operation once. Suppose, WLOG, that <math>y=x_4<0</math>, and that the last three entries <math>x_3, x_4, x_5</math> of <math>\mathbf{x}_{\text{old}}</math> are replaced by <math>x_3 + x_4, -x_4, x_5 + x_4</math> in <math>\mathbf{x}_{\text{new}}</math>. Let <math>S = x_1 + x_2 + x_3 + x_4 + x_5</math> be the sum of all entries of <math>\mathbf{x}_{\text{old}}</math> (or <math>\mathbf{x}_{\text{new}}</math>). Then, a straightforward computation shows that <math>f(\mathbf{x}_{\text{new}}) - f(\mathbf{x}_{\text{old}}) = 2Sx_4 < 0</math> (since <math>S>0</math> and <math>x_4 < 0</math>). Thus, if the algorithm does not stop, we can find an infinite decreasing sequence of nonnegative integers <math>f_0>f_1>f_2>\cdots</math> (by applying <math>f</math> to each of the <math>5</math>-tuples). This is impossible, so the algorithm must stop. <math>\Box</math>
  
 
This solution was posted and copyrighted by tc1729. The original thread for this problem can be found here: [https://aops.com/community/p2632377]
 
This solution was posted and copyrighted by tc1729. The original thread for this problem can be found here: [https://aops.com/community/p2632377]

Latest revision as of 12:20, 17 July 2021

Problem

To each vertex of a regular pentagon an integer is assigned, so that the sum of all five numbers is positive. If three consecutive vertices are assigned the numbers $x,y,z$ respectively, and $y<0$, then the following operation is allowed: $x,y,z$ are replaced by $x+y,-y,z+y$ respectively. Such an operation is performed repeatedly as long as at least one of the five numbers is negative. Determine whether this procedure necessarily comes to an end after a finite number of steps.

Solution

The algorithm always stops. Indeed, consider the five numbers on the vertices of the pentagon as forming a $5$-tuple $\mathbf{x} = (x_1, x_2, x_3, x_4, x_5) \in \mathbb{Z}^5$. The sum of the five entries of this $5$-tuple is positive (by assumption), and stays unchanged through the entire process (since our operation does not change the sum); thus, it is always positive. Now, define the function $f : \mathbb{Z}^5 \to \mathbb{Z}$ by \[f(x_1, x_2, x_3, x_4, x_5)=\sum_{i=1}^5(x_i-x_{i+2})^2, \text{ where } x_6=x_1 \text{ and } x_7=x_2.\] Clearly, $f \geq 0$ always. Now, let $\mathbf{x}_{\text{old}} = (x_1, x_2, x_3, x_4, x_5)$ and $\mathbf{x}_{\text{new}}$ be two consecutive $5$-tuples obtained in this process. Thus, $\mathbf{x}_{\text{new}}$ is obtained from $\mathbf{x}_{\text{old}}$ by applying our operation once. Suppose, WLOG, that $y=x_4<0$, and that the last three entries $x_3, x_4, x_5$ of $\mathbf{x}_{\text{old}}$ are replaced by $x_3 + x_4, -x_4, x_5 + x_4$ in $\mathbf{x}_{\text{new}}$. Let $S = x_1 + x_2 + x_3 + x_4 + x_5$ be the sum of all entries of $\mathbf{x}_{\text{old}}$ (or $\mathbf{x}_{\text{new}}$). Then, a straightforward computation shows that $f(\mathbf{x}_{\text{new}}) - f(\mathbf{x}_{\text{old}}) = 2Sx_4 < 0$ (since $S>0$ and $x_4 < 0$). Thus, if the algorithm does not stop, we can find an infinite decreasing sequence of nonnegative integers $f_0>f_1>f_2>\cdots$ (by applying $f$ to each of the $5$-tuples). This is impossible, so the algorithm must stop. $\Box$

This solution was posted and copyrighted by tc1729. The original thread for this problem can be found here: [1]

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

See Also

1986 IMO (Problems) • Resources
Preceded by
Problem 2 		1 • 2 • 3 • 4 • 5 • 6 Followed by
Problem 4
All IMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1986_IMO_Problems/Problem_3&oldid=158645"