Difference between revisions of "1976 IMO Problems/Problem 5"
(New page: == Problem == {{problem}} == Solution == {{solution}} == See also == {{IMO box|year=1976|num-b=1|num-a=3}}) |
|||
| (2 intermediate revisions by one other user not shown) | |||
| Line 1: | Line 1: | ||
== Problem == | == Problem == | ||
| − | {{ | + | We consider the following system |
| + | with <math>q = 2p</math>: | ||
| + | |||
| + | <math>\begin{matrix} a_{11}x_{1} + \ldots + a_{1q}x_{q} = 0, \\ | ||
| + | a_{21}x_{1} + \ldots + a_{2q}x_{q} = 0, \\ | ||
| + | \ldots , \\ | ||
| + | a_{p1}x_{1} + \ldots + a_{pq}x_{q} = 0, \\ | ||
| + | \end{matrix}</math> | ||
| + | |||
| + | in which every coefficient is an element from the set <math>\{ - 1,0,1\}</math><math>.</math> Prove that there exists a solution <math>x_{1}, \ldots,x_{q}</math> for the system with the properties: | ||
| + | |||
| + | '''a.)''' all <math>x_{j}, j = 1,\ldots,q</math> are integers<math>;</math> | ||
| + | |||
| + | '''b.)''' there exists at least one j for which <math>x_{j} \neq 0;</math> | ||
| + | |||
| + | '''c.)''' <math>|x_{j}| \leq q</math> for any <math>j = 1, \ldots ,q.</math> | ||
== Solution == | == Solution == | ||
| − | {{ | + | First of all note that we have <math> (q + 1)^q - 1</math> possible nonzero vectors <math> (x_1,\cdots,x_q)</math> such that <math> 0\leq x_i\leq q</math> are integers. |
| + | |||
| + | |||
| + | But <math> a_{j1}x_1 + \cdots + a_{jq}x_q</math> can only assume <math> q^2 + 1</math> different values, because if it is maximized/minimized by <math> (M_1,M_2,\cdots,M_q)/(m_1,m_2,\cdots,m_q)</math>, we have that <math> \sum_{i = 1}^{q}a_{ji}(M_i - m_i)\leq q\times q = q^2</math> (if <math> a_{ji} = 0</math>, it doesn't affect the sum, if it is <math> 1</math>, <math> M_i = q,m_i = 0</math>, and if it is <math> - 1</math>, <math> M_i = 0,m_i = q</math>). | ||
| + | |||
| + | |||
| + | From this we conclude that there are at most <math> (q^2 + 1)^p = (q^2 + 1)^{q/2}</math> possible values for the vector <math> (a_{11}x_{1} + \ldots + a_{1q}x_{q},\cdots,a_{p1}x_{1} + \ldots + a_{pq}x_{q})</math>. | ||
| + | But we have that: | ||
| + | <math> (q + 1)^q - 1 = (q^2 + 1 + 2q)^{q/2} - 1 =</math> | ||
| + | <math> = (q^2 + 1)^{q/2} + \left( - 1 + \sum_{j = 1}^{q/2}{{q/2}\choose j}(q^2 + 1)^{q/2 - j}(2q)^j\right) > (q^2 + 1)^{q/2}</math> | ||
| + | |||
| + | We conclude that by the pigeonhole principle there are two distinct vectors being mapped to the same vector. Taking their difference we have a vector with the desired properties. | ||
| + | |||
| + | The above solution was posted and copyrighted by Jorge Miranda. The original thread for this problem can be found here: [https://aops.com/community/p1758997] | ||
== See also == | == See also == | ||
| − | {{IMO box|year=1976|num-b= | + | {{IMO box|year=1976|num-b=4|num-a=6}} |
Latest revision as of 16:28, 29 January 2021
Problem
We consider the following system
with 
:
in which every coefficient is an element from the set 
Prove that there exists a solution 
for the system with the properties:
a.) all 
are integers
b.) there exists at least one j for which 
c.) 
for any 
Solution
First of all note that we have 
possible nonzero vectors 
such that 
are integers.
But 
can only assume 
different values, because if it is maximized/minimized by 
, we have that 
(if 
, it doesn't affect the sum, if it is 
, 
, and if it is 
, 
).
From this we conclude that there are at most 
possible values for the vector 
.
But we have that:
We conclude that by the pigeonhole principle there are two distinct vectors being mapped to the same vector. Taking their difference we have a vector with the desired properties.
The above solution was posted and copyrighted by Jorge Miranda. The original thread for this problem can be found here: [1]
See also
| 1976 IMO (Problems) • Resources | ||
| Preceded by Problem 4 |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 6 |
| All IMO Problems and Solutions | ||
