Maths Olympiad Prep

Library / /54 of 94

Number theory Difficulty 6.9 National Olympiad Prove it Japan

Let kk be an integer greater than or equal to 22, and let n1n_1, n2n_2, n3n_3 be positive integers, and a1a_1, a2a_2, a3a_3 be integers greater than or equal to 11 and less than or equal to k1k-1. Define
bi=aij=0nikj(i=1,2,3). b_i = a_i \sum_{j=0}^{n_i} k^j \quad (i = 1, 2, 3).
Determine all possible combinations (n1,n2,n3)(n_1, n_2, n_3) if b1b2=b3b_1 b_2 = b_3.

Solutions — 2

Solution 1

We may assume without loss of generality that n1n2n_1 \ge n_2. Since 0<a1b2<kkn2+1=kn2+20 < a_1 b_2 < k \cdot k^{n_2+1} = k^{n_2+2}, we can represent
a1b2=j=0n2+1djkj a_1 b_2 = \sum_{j=0}^{n_2+1} d_j k^j
by choosing djd_j with 0djk10 \le d_j \le k-1 (j=0,1,,n2+1j = 0, 1, \dots, n_2+1) suitably.
Set ej=d0+d1++dje_j = d_0 + d_1 + \dots + d_j (j=0,1,,n2+1j = 0, 1, \dots, n_2+1).
Now let us separate the two cases:
* When n1>n2n_1 > n_2.
We have
b1b2=j=0n1kj×j=0n2+1djkjj=0n2+1ejkj(modkn2+2) b_1 b_2 = \sum_{j=0}^{n_1} k^j \times \sum_{j=0}^{n_2+1} d_j k^j \equiv \sum_{j=0}^{n_2+1} e_j k^j \pmod{k^{n_2+2}}
Since 0e0=d0k10 \le e_0 = d_0 \le k-1, we get a3=e0a_3 = e_0 and a3e1(modk)a_3 \equiv e_1 \pmod k. Consequently, we see that d1=e1e0d_1 = e_1 - e_0 is a multiple of kk, and from 0d1<k10 \le d_1 < k-1, we must have d10d_1 \ne 0. This in turn implies that e0=e1=a3e_0 = e_1 = a_3 and hence e1=a3e2(modk)e_1 = a_3 \equiv e_2 \pmod k, and in the same way as above we conclude that d2=0d_2 = 0.
Repeating this argument we obtain that d1=d2==dn2+1=0d_1 = d_2 = \cdots = d_{n_2+1} = 0, which implies that a1b2=d0k1a_1 b_2 = d_0 \le k-1, which, in turn, contradicts the assumption that n1,n2,a1,a2n_1, n_2, a_1, a_2 are all positive integers. Thus, we see that there are no triples (n1,n2,n3)(n_1, n_2, n_3) which satisfy the requirements in this case.
* When n1=n2n_1 = n_2.
In this case
b1b2j=0n1kj×j=0n2+1djkjj=0n2ejkj(modkn2+1) b_1 b_2 \equiv \sum_{j=0}^{n_1} k^j \times \sum_{j=0}^{n_2+1} d_j k^j \equiv \sum_{j=0}^{n_2} e_j k^j \pmod{k^{n_2+1}}
is valid, and we can conclude that d1=d2==dn2=0d_1 = d_2 = \cdots = d_{n_2} = 0 hold as in the case where n1>n2n_1 > n_2. If we let a1a2=c0+c1ka_1 a_2 = c_0 + c_1 k (0c0,c1k10 \le c_0, c_1 \le k-1), then we have
a1b2=c0+(c0+c1)(k+k2++kn2)+c1kn2+1. a_1 b_2 = c_0 + (c_0 + c_1)(k + k^2 + \cdots + k^{n_2}) + c_1 k^{n_2+1}.
Since c0+c1c_0 + c_1 is a multiple of kk as d1=0d_1 = 0, and since 0<c0+c12k20 < c_0 + c_1 \le 2k-2, we have c0+c1=kc_0 + c_1 = k. If we assume that n1=n22n_1 = n_2 \ge 2, then we get d2=1d_2 = 1, contradicting d2=0d_2 = 0. Thus, we get n1=n2=1n_1 = n_2 = 1, and n3=2n1+1=3n_3 = 2n_1 + 1 = 3.
Conversely, if (n1,n2,n3)=(1,1,3)(n_1, n_2, n_3) = (1, 1, 3), we will show that (k,a1,a2,a3)(k, a_1, a_2, a_3) which satisfy the requirement exist. Since we have
a1(1+k)×a2(1+k)=a1a2(k+1)2,a3(1+k+k2+k3)=a3(k+1)(k2+1), a_1(1+k) \times a_2(1+k) = a_1 a_2(k+1)^2, \quad a_3(1+k+k^2+k^3) = a_3(k+1)(k^2+1),
if we can find a1,a2a_1, a_2 satisfying a1a2=k2+12a_1 a_2 = \frac{k^2+1}{2}, 1aik11 \le a_i \le k-1 (i=1,2i=1, 2) for some odd integer kk, then such a pair a1,a2a_1, a_2 together with a3=k+12a_3 = \frac{k+1}{2} will satisfy the desired conditions. By checking odd numbers in turn starting with 33, we find that the quadruple (k,a1,a2,a3)=(7,5,5,4)(k, a_1, a_2, a_3) = (7, 5, 5, 4) satisfies the requirement. Thus, the only triple (n1,n2,n3)(n_1, n_2, n_3) to satisfy the requirement of the problem is (1,1,3)(1, 1, 3).

Solution 2

If we rewrite the relation b1b2=b3b_1 b_2 = b_3 by using the summation formula for the geometric series, we get
a1a2kn1+11k1×kn2+11k1=a3kn3+11k1. a_1 a_2 \cdot \frac{k^{n_1+1}-1}{k-1} \times \frac{k^{n_2+1}-1}{k-1} = a_3 \cdot \frac{k^{n_3+1}-1}{k-1}.
By multiplying both sides of the equation above by (k1)2(k-1)^2, we get
a1a2(kn1+11)(kn2+11)=a3(kn3+11)(k1)() a_1 a_2 (k^{n_1+1} - 1) (k^{n_2+1} - 1) = a_3 (k^{n_3+1} - 1) (k-1) \quad (*)
Since kn2+11k21>a3(k1)k^{n_2+1} - 1 \ge k^2 - 1 > a_3(k-1) imply that kn1+11<kn3+11k^{n_1+1} - 1 < k^{n_3+1} - 1 holds, we get n1<n3n_1 < n_3. We similarly get n2<n3n_2 < n_3. We can also assume that n1n2n_1 \ge n_2 without loss of generality.
Assume that n22n_2 \ge 2. Considering the equation (*) in modk3\mod k^3, we get a1a2a3(k1)(modk3)a_1 a_2 \equiv -a_3(k-1) \pmod{k^3}. However, since
0<a1a2+a3(k1)<k2+k(k1)<2k2k3 0 < a_1 a_2 + a_3 (k-1) < k^2 + k(k-1) < 2k^2 \le k^3
hold, we get a contradiction. Thus, we conclude that n2=1n_2 = 1.
If we then divide both sides of the equation (*) by k1k-1, we obtain
a1a2(kn1+11)(k+1)=a3(kn3+11). a_1 a_2 (k^{n_1+1} - 1)(k+1) = a_3 (k^{n_3+1} - 1).
Suppose now n12n_1 \ge 2. If we consider both sides of the equation above in modk3\mod k^3, then we get a1a2(k+1)a3(modk3)-a_1a_2(k+1) \equiv -a_3 \pmod{k^3}. However, since
a1a2(k+1)a3(k+1)(k1)=2>0,a1a2(k+1)a3(k1)2(k+1)1=k3k2k<k3 \begin{aligned} a_1a_2(k+1) - a_3 &\ge (k+1) - (k-1) = 2 > 0, \\ a_1a_2(k+1) - a_3 &\le (k-1)^2(k+1) - 1 = k^3 - k^2 - k < k^3 \end{aligned}
hold, we get a contradiction. Therefore, we must have n1=1n_1 = 1.
Summarizing we get
a1a2(k21)(k+1)=a3(kn3+11), a_1a_2(k^2 - 1)(k + 1) = a_3(k^{n_3+1} - 1),
and furthermore, since
kn3+11a3(kn3+11)=a1a2(k21)(k+1)(k1)2(k21)(k+1)=k5k42k3+2k2+k1<k51, \begin{aligned} k^{n_3+1} - 1 &\le a_3(k^{n_3+1} - 1) = a_1a_2(k^2 - 1)(k + 1) \\ &\le (k-1)^2(k^2 - 1)(k + 1) \\ &= k^5 - k^4 - 2k^3 + 2k^2 + k - 1 \\ &< k^5 - 1, \end{aligned}
we obtain n3<4n_3 < 4.
If we suppose n3=2n_3 = 2, then we get a1a2(k+1)2=a3(k2+k+1)a_1a_2(k+1)^2 = a_3(k^2+k+1), so we conclude that 0<a1a2<a3<k0 < a_1a_2 < a_3 < k holds, since (k+1)2>k2+k+1(k+1)^2 > k^2+k+1. However, if we consider both sides of a1a2(k+1)2=a3(k2+k+1)a_1a_2(k+1)^2 = a_3(k^2+k+1) in modk\mod k, we get a1a2a3(modk)a_1a_2 \equiv a_3 \pmod{k}, which gives a contradiction. As n3>n1=1n_3 > n_1 = 1, we conclude from b1b2=b3b_1b_2 = b_3 that (n1,n2,n3)=(1,1,3)(n_1, n_2, n_3) = (1, 1, 3). We can get (k,a1,a2,a3)(k, a_1, a_2, a_3) satisfying the conditions of the problem when (n1,n2,n3)=(1,1,3)(n_1, n_2, n_3) = (1, 1, 3) as in the preceding solution to the problem.

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.