Maths Olympiad Prep

Library / /56 of 61

Combinatorics Difficulty 6.9 National Olympiad Prove it Ibero-American Mathematical Olympiad

Problem:
Let o(n)o(n) be the number of 2n2n-tuples (a1,a2,,an,b1,b2,,bn)(a_{1}, a_{2}, \ldots, a_{n}, b_{1}, b_{2}, \ldots, b_{n}) such that each ai,bj=0a_{i}, b_{j} = 0 or 11 and a1b1+a2b2++anbna_{1} b_{1} + a_{2} b_{2} + \ldots + a_{n} b_{n} is odd. Similarly, let e(n)e(n) be the number for which the sum is even. Show that o(n)e(n)=2n12n+1\dfrac{o(n)}{e(n)} = \dfrac{2^{n} - 1}{2^{n} + 1}.

Solution

Solution:
We prove by induction that o(n)=22n12n1o(n) = 2^{2n-1} - 2^{n-1}. For n=1n = 1, this reads o(1)=2120=1o(1) = 2^{1} - 2^{0} = 1, which is obviously true—the only such 22-tuple is (1,1)(1, 1). Suppose it is true for nn.

If (a1,a2,,an,b1,b2,,bn)(a_{1}, a_{2}, \ldots, a_{n}, b_{1}, b_{2}, \ldots, b_{n}) gives an odd sum, then we can take (an+1,bn+1)(a_{n+1}, b_{n+1}) to be any of (0,0),(0,1),(1,0)(0, 0), (0, 1), (1, 0) and still get an odd sum for (a1,a2,,an+1,b1,b2,,bn+1)(a_{1}, a_{2}, \ldots, a_{n+1}, b_{1}, b_{2}, \ldots, b_{n+1}). On the other hand, if (a1,a2,,an,b1,b2,,bn)(a_{1}, a_{2}, \ldots, a_{n}, b_{1}, b_{2}, \ldots, b_{n}) is even, then we must have an+1=bn+1=1a_{n+1} = b_{n+1} = 1 to get an odd sum. Thus o(n+1)=3o(n)+e(n)o(n+1) = 3 o(n) + e(n).

But o(n)=22n12n1o(n) = 2^{2n-1} - 2^{n-1} and e(n)=(o(n)+e(n))o(n)=22n(22n12n1)=22n1+2n1e(n) = (o(n) + e(n)) - o(n) = 2^{2n} - (2^{2n-1} - 2^{n-1}) = 2^{2n-1} + 2^{n-1}.

So o(n+1)=3o(n)+e(n)=3(22n12n1)+(22n1+2n1)=422n122n1=22(n+1)12(n+1)1o(n+1) = 3 o(n) + e(n) = 3(2^{2n-1} - 2^{n-1}) + (2^{2n-1} + 2^{n-1}) = 4 \cdot 2^{2n-1} - 2 \cdot 2^{n-1} = 2^{2(n+1)-1} - 2^{(n+1)-1}, which establishes the result for n+1n+1 and hence for all nn.

Hence e(n)=22no(n)=22n1+2n1e(n) = 2^{2n} - o(n) = 2^{2n-1} + 2^{n-1} and o(n)e(n)=2n12n+1\dfrac{o(n)}{e(n)} = \dfrac{2^{n} - 1}{2^{n} + 1}.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.