For any positive integer $n$, let $f(n)$ be the number of possible choices of signs $+\ \text{or}\ - $ in the algebraic expression $\pm 1\pm 2\ldots \pm n$, such that the obtained sum is zero. Show that $f(n)$ satisfies the following conditions: a) $f(n)=0$ for $n=1\pmod{4}$ or $n=2\pmod{4}$. b) $2^{\frac{n}{2}-1}\le f(n)\le 2^n-2^{\lfloor\frac{n}{2}\rfloor+1}$, for $n=0\pmod{4}$ or $n=3\pmod{4}$. Ioan Tomsecu
Problem
Source: Romanian TST 2002
Tags: modular arithmetic, floor function, combinatorics proposed, combinatorics
05.02.2011 17:05
For (i), it's easy; + and - are equal mod 2. So We can assume the summation to be $+1+2+3+4+...+n$. Since $n$ is 1 or 2 mod 4, then: $1+2+3+4+...+n = 1+2+3+4+...+(4m+k)$ for some integer m, $k \in \{1,2\}$ $1+2+3+4+...+(4m+k)=\dfrac{(4m+k)(4m+k+1)}{2}$ If there is a way to make the summation 0, then $\dfrac{(4m+k)(4m+k+1)}{2} \equiv 0 \mod 2$. But, since k = 1 or 2, the even term of the numerator is not divisible by 4, so the result must be odd, which is impossible to be 0.
16.01.2016 08:13
The following should work: $f(n)$ is the number of ordered pairs of sets $(A, B)$ where (1) $A \cup B = \{1, 2, 3, \cdots, n\}$, (2) $A \cap B = \emptyset$, and (3) $S(A) = S(B)$, i.e. the sum of the elements in $A$ equals the sum of the elements in $B$. a) If a representation exists, $\frac{n(n+1)}{2} = 2S(A)$, so $\frac{n(n+1)}{2}$ is even and the result follows immediately. b) The lower-bound can be obtained by induction as follows. For the base cases we have $(A, B) \in \{(\{1, 2\}, \{3\}), (\{3\}, \{1, 2\})\}$ or $(A, B) \in \{(\{1, 4\}, \{2, 3\}), (\{2, 3\}, \{1, 4\})\}$, so $f(3), f(4) \ge 2$. Next, construct for each pair $(A, B)$ four pairs $(A \cup \{n+1, n+4\}, B \cup \{n+2, n+3\})$, $(A \cup \{n+2, n+3\}, B \cup \{n+1, n+4\})$, $(A \cup \{2, n+1, n+2\}, B \cup \{n+3, n+4\} \setminus \{2\})$ if $2 \in B$, $(A \cup \{n+3, n+4\} \setminus \{2\}, B \cup \{2, n+1, n+2\} )$ if $2 \in A$, $(A \cup \{1, n+1, n+3\}, B \cup \{n+2, n+4\} \setminus \{1\})$ if $1 \in B$ and similarly if $1 \in A$. Hence $f(n+4) \ge 4f(n) \ge 2^{\frac{n}{2} + 1}$. For the upper bound observe that $2^n$ is the total number of ordered pairs satisfying only (1) and (2), and since the inequality $\frac{n(n+1)}{2} > (\lfloor\frac{n}{2}\rfloor+1)(\lfloor\frac{n}{2}\rfloor+ 2)$ is true for $n \ge 5$, we have for any $A \subseteq \{1, 2, .., \lfloor\frac{n}{2}\rfloor+1\}$, $S(A) \neq S(B)$, so $f(n) \le 2^n - 2^{\lfloor\frac{n}{2}\rfloor+1}$. This bound is very weak. The first few values of $f(n)$ for $n \ge 3$: 2 2 0 0 8 14 0 0 70 124 0 0 722 1314 0 0 8220 15272 0 0 99820