Maths Olympiad Prep

Library / /11 of 16

Combinatorics Difficulty 6.2 National olympiad Prove it Brazil

Let N={0,1,2,3,}N = \{0, 1, 2, 3, \dots\}. Given sets A,BNA, B \subset N, for each positive integer nn denote r(A,B,n)r(A, B, n) as the number of solutions to the equation a+b=na + b = n, aA,bBa \in A, b \in B.
Prove that there exists n0Nn_0 \in N such that r(A,B,n+1)>r(A,B,n)r(A, B, n+1) > r(A, B, n) for all n>n0n > n_0 if and only if NAN \setminus A and NBN \setminus B are both finite.

Solution

First suppose that r(A,B,n)r(A, B, n) is increasing for n>n0n > n_0. For the sake of simplicity, let Aˉ=NA\bar{A} = N \setminus A and Bˉ=NB\bar{B} = N \setminus B. Then
n+1=r(N,N,n)=r(A,B,n)+r(Aˉ,B,n)+r(A,Bˉ,n)+r(Aˉ,Bˉ,n)    r(Aˉ,B,n)+r(A,Bˉ,n)+r(Aˉ,Bˉ,n)=n+1r(A,B,n) n+1 = r(N, N, n) = r(A, B, n) + r(\bar{A}, B, n) + r(A, \bar{B}, n) + r(\bar{A}, \bar{B}, n) \\ \iff r(\bar{A}, B, n) + r(A, \bar{B}, n) + r(\bar{A}, \bar{B}, n) = n+1 - r(A, B, n)
Since r(A,B,n)r(A, B, n) is increasing, there exists a constant cc such that n+1r(A,B,n)cn+1 - r(A, B, n) \le c for all nn. In particular, for all nn, r(Aˉ,N,n)=r(Aˉ,B,n)+r(Aˉ,Bˉ,n)<cr(\bar{A}, N, n) = r(\bar{A}, B, n) + r(\bar{A}, \bar{B}, n) < c, implying Aˉ<c|\bar{A}| < c. In fact, if Aˉ={a1,a2,a3,,al,}\bar{A} = \{a_1, a_2, a_3, \dots, a_l, \dots\}, a1<a2<a3<a_1 < a_2 < a_3 < \dots, for ak<n<ak+1a_k < n < a_{k+1}, we have r(Aˉ,N,n)=kr(\bar{A}, N, n) = k. Therefore if Aˉ\bar{A} were infinite, r(Aˉ,N,n)r(\bar{A}, N, n) would be unbounded. Analogously Bˉ\bar{B} must be finite as well.

Conversely, suppose Aˉ\bar{A} and Bˉ\bar{B} are both finite. For all n>max(Aˉ)+max(Bˉ)n > \max(\bar{A}) + \max(\bar{B}), if aAˉa \in \bar{A} then na>maxBˉn - a > \max \bar{B}, so naBˉn - a \notin \bar{B}, hence naBn - a \in B. In a similar fashion, if bBˉb \in \bar{B} then nbAˉn - b \notin \bar{A}, hence nbAn - b \in A. Thus
r(A,B,n)=n+1AˉBˉ<n+2AˉBˉ=r(A,B,n+1) r(A, B, n) = n + 1 - |\bar{A}| - |\bar{B}| < n + 2 - |\bar{A}| - |\bar{B}| = r(A, B, n + 1)
So r(A,B,n)r(A, B, n) is increasing for n>max(Aˉ)+max(Bˉ)n > \max(\bar{A}) + \max(\bar{B}).

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 and solution reproduced as published; topic and difficulty added by this site.