Let $ n$ be an integer, $ n\geq 2$, and the integers $ a_1,a_2,\ldots,a_n$, such that $ 0 < a_k\leq k$, for all $ k = 1,2,\ldots,n$. Knowing that the number $ a_1 + a_2 + \cdots + a_n$ is even, prove that there exists a choosing of the signs $ +$, respectively $ -$, such that \[ a_1 \pm a_2 \pm \cdots \pm a_n= 0. \]
Problem
Source: Romania JBTST 2008, Problem 5
Tags: induction, combinatorics proposed, combinatorics
mto
02.05.2008 03:07
By induction on n Suppose that we could choose the sign +, - when n=k and we have to show that we could find an arrane when n=k+1 If a(k+1) does not equal ak, then apply induction hypothes for k number a1,a2,..., a(k-1), |a(k+1) -ak| If a(k+1)=ak, then apply induction hypothes for k-1 number a1,a2,.., a(k-1) and put a - between ak, a(k+1)
prowler
03.05.2008 10:11
It is very similar to Chvatal Theorem about Hamiltonian paths. Consider a graph with vertices of degree $ a_i$. Then they satisfy $ \sum a_i =2E$. Then the for a Hamiltonian path pass we add degrees for even vertices on the path and subtract odd. It is not the same problem, but remind me about graph theory.
Professor33
05.10.2023 11:37
mto wrote: By induction on n Suppose that we could choose the sign +, - when n=k and we have to show that we could find an arrane when n=k+1 If a(k+1) does not equal ak, then apply induction hypothes for k number a1,a2,..., a(k-1), |a(k+1) -ak| If a(k+1)=ak, then apply induction hypothes for k-1 number a1,a2,.., a(k-1) and put a - between ak, a(k+1) VERY SMOOTH