Maths Olympiad Prep

Library / /834 of 860

Algebra Difficulty 5.7 AIME, harder Find the answer

Determine the number of triples 0k,m,n1000 \leq k, m, n \leq 100 of integers such that 2mn2nm=2k 2^{m} n-2^{n} m=2^{k}

A number or a short expression. Spacing and $ signs are ignored.

Solution

First consider when nmn \geq m, so let n=m+dn=m+d where d0d \geq 0. Then we have 2m(m+d2dm)=2^{m}\left(m+d-2^{d} m\right)= 2m(m(12d)+d)2^{m}\left(m\left(1-2^{d}\right)+d\right), which is non-positive unless m=0m=0. So our first set of solutions is m=0,n=2jm=0, n=2^{j}. Now, we can assume that m>nm>n, so let m=n+dm=n+d where d>0d>0. Rewrite 2mn2nm=2n+dn2^{m} n-2^{n} m=2^{n+d} n- 2n(n+d)=2n((2d1)nd)2^{n}(n+d)=2^{n}\left(\left(2^{d}-1\right) n-d\right). In order for this to be a power of 2,(2d1)nd2,\left(2^{d}-1\right) n-d must be a power of 2. This implies that for some j,2jd(mod2d1)j, 2^{j} \equiv-d\left(\bmod 2^{d}-1\right). But notice that the powers of 2(mod2d1)2\left(\bmod 2^{d}-1\right) are 1,2,4,,2d1(2d11,2,4, \ldots, 2^{d-1}\left(2^{d} \equiv 1\right. so the cycle repeats )). In order for the residues to match, we need 2j+d=c(2d1)2^{j}+d=c\left(2^{d}-1\right), where 0jd10 \leq j \leq d-1 and c1c \geq 1. In order for this to be true, we must have 2d1+d2d1d+12d12^{d-1}+d \geq 2^{d}-1 \Longleftrightarrow d+1 \geq 2^{d-1}. This inequality is only true for d=1,2,3d=1,2,3. We plug each of these into the original expression (2d1)nd\left(2^{d}-1\right) n-d. For d=1:n1d=1: n-1 is a power of 2 . This yields the set of solutions (2j+2,2j+1)\left(2^{j}+2,2^{j}+1\right) for j0j \geq 0. For d=2:3n2d=2: 3 n-2 is a power of 2 . Note that powers of 2 are 2(mod3)-2(\bmod 3) if and only if it is an even power, so n=22j+23n=\frac{2^{2 j}+2}{3}. This yields the solution set (22j+83,22j+23),j0\left(\frac{2^{2 j}+8}{3}, \frac{2^{2 j}+2}{3}\right), j \geq 0. For d=3:7n3d=3: 7 n-3 is a power of 2 . Powers of 2 have a period of 3 when taken (mod7)(\bmod 7), so inspection tells us 7n3=23j+27 n-3=2^{3 j+2}, yielding the solution set (23j+2+247,23j+2+37),j0\left(\frac{2^{3 j+2}+24}{7}, \frac{2^{3 j+2}+3}{7}\right), j \geq 0. Therefore, all the solutions are of the form (m,n)=(0,2j),(2j+2,2j+1)(22j+83,22j+23),(23j+2+247,23j+2+37) \begin{gathered} (m, n)=\left(0,2^{j}\right),\left(2^{j}+2,2^{j}+1\right) \\ \left(\frac{2^{2 j}+8}{3}, \frac{2^{2 j}+2}{3}\right),\left(\frac{2^{3 j+2}+24}{7}, \frac{2^{3 j+2}+3}{7}\right) \end{gathered} for j0j \geq 0. Restricting this family to m,n100m, n \leq 100 gives 7+7+5+3=227+7+5+3=22.

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.