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 "2006 Romanian NMO Problems/Grade 8/Problem 2"
 
(One intermediate revision by one other user not shown)
Line 1: Line 1:
 
==Problem==
 
==Problem==
 
Let <math>n</math> be a positive integer. Prove that there exists an integer <math>k</math>, <math>k\geq 2</math>, and numbers <math>a_i \in \{ -1, 1 \}</math>, such that <center><math>n = \sum_{1\leq i < j \leq k } a_ia_j</math>.</center>
 
Let <math>n</math> be a positive integer. Prove that there exists an integer <math>k</math>, <math>k\geq 2</math>, and numbers <math>a_i \in \{ -1, 1 \}</math>, such that <center><math>n = \sum_{1\leq i < j \leq k } a_ia_j</math>.</center>
 +
 
==Solution==
 
==Solution==
 +
Suppose that there exists such an integer <math>k</math> and numbers <math>a_i \in \{ -1, 1 \}</math>, <math>i\in \{1,\ldots,k\}</math> such that <math>n = \sum_{1\leq i < j \leq k } a_ia_j</math>. Let <cmath>\begin{align*}X &= \#\{i\in [k] \;:\; a_{i}=-1\} \\ Y &= \#\{i\in [k] \;:\; a_{i}=1\}\end{align*}</cmath>
 +
then <cmath>n=\sum_{1\leq i < j \leq k } a_ia_j = \binom{X}{2}+\binom{Y}{2}-XY = \frac{(X-Y)^{2}-(X+Y)}{2}. </cmath> We see that if <math>X</math> and <math>Y</math> are increased by <math>1</math>, then <math>n</math> is decreased by <math>1</math>. This motivates the following construction: Let <math>m</math> be large enough such that <math>\binom{m}{2} > n</math>, let <math>Y = \binom{m}{2} - n</math> and <math>X = Y+m</math>, let <math>k = X+Y</math>, and let <math>a_{1},\ldots,a_{X} = -1</math> and <math>a_{X+1},\ldots,a_{X+Y} = 1</math>. Then <cmath>\begin{align*}\sum_{1\leq i < j \leq k } a_ia_j &= \binom{X}{2}+\binom{Y}{2}-XY\\ &= \frac{(X-Y)^{2}-(X+Y)}{2} \\ &= \frac{m^{2}-\left(m+\binom{m}{2} - n+\binom{m}{2} - n\right)}{2} \\ &= n.\end{align*}</cmath>
 +
 
==See also==
 
==See also==
 
*[[2006 Romanian NMO Problems]]
 
*[[2006 Romanian NMO Problems]]
 
[[Category:Olympiad Number Theory Problems]]
 
[[Category:Olympiad Number Theory Problems]]

Latest revision as of 23:08, 5 June 2011

Problem

Let $n$ be a positive integer. Prove that there exists an integer $k$, $k\geq 2$, and numbers $a_i \in \{ -1, 1 \}$, such that

$n = \sum_{1\leq i < j \leq k } a_ia_j$.

Solution

Suppose that there exists such an integer $k$ and numbers $a_i \in \{ -1, 1 \}$, $i\in \{1,\ldots,k\}$ such that $n = \sum_{1\leq i < j \leq k } a_ia_j$. Let \begin{align*}X &= \#\{i\in [k] \;:\; a_{i}=-1\} \\ Y &= \#\{i\in [k] \;:\; a_{i}=1\}\end{align*} then \[n=\sum_{1\leq i < j \leq k } a_ia_j = \binom{X}{2}+\binom{Y}{2}-XY = \frac{(X-Y)^{2}-(X+Y)}{2}.\] We see that if $X$ and $Y$ are increased by $1$, then $n$ is decreased by $1$. This motivates the following construction: Let $m$ be large enough such that $\binom{m}{2} > n$, let $Y = \binom{m}{2} - n$ and $X = Y+m$, let $k = X+Y$, and let $a_{1},\ldots,a_{X} = -1$ and $a_{X+1},\ldots,a_{X+Y} = 1$. Then \begin{align*}\sum_{1\leq i < j \leq k } a_ia_j &= \binom{X}{2}+\binom{Y}{2}-XY\\ &= \frac{(X-Y)^{2}-(X+Y)}{2} \\ &= \frac{m^{2}-\left(m+\binom{m}{2} - n+\binom{m}{2} - n\right)}{2} \\ &= n.\end{align*}

See also

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2006_Romanian_NMO_Problems/Grade_8/Problem_2&oldid=39256"