CEMC Banner

Problem of the Month
Solution to Problem 3: December 2023

For solutions to the original problem from the Canadian Intermediate Mathematics Contest, please refer to the solutions on our website.

We will start by presenting two general facts. It is worth spending some time digesting them before reading the rest of the solution.

Fact 1: For all positive integers m and n with mn, if the integer mn is not in Row n, then there are positive integers a and b such that ab=mn and m<ab<n.

Proof. Assume that m and n are positive integers with mn such that mn is not in Row n. Then mn must be in an earlier row since mnn2. Thus, mn is in Row b for some integer b<n. The integers in Row b are multiples of b that are no larger than b2, which means that mn=ab for some positive integer a with ab. Rearranging mn=ab, we get am=nb. Since b<n, nb>1, and so am>1 which implies a>m. Therefore, there are positive integers a and b such that mn=ab and m<ab<n. ◻

Fact 2: For all positive integers m and n with mn, if there are positive integers a and b such that ab=mn and m<ab<n, then the integer mn is not in Row n.

Proof. Assume that m and n are positive integers with mn and that there are positive integers a and b with mn=ab and m<ab<n. We are assuming ab and that a and b are positive, so abb2, which implies mnb2 since we are assuming mn=ab. Therefore, mn is a positive multiple of b that does not exceed b2, so mn cannot appear any later than Row b. Since b<n, mn is not in Row n. ◻

  1. Suppose k is a positive integer. If n is a positive integer with nk, then n2kn0, and so n2kn is not in Row n. Therefore, we might as well assume that n>k as we look for the largest n such that n2kn is not in Row n.

    Assume now that n2kn=n(nk) is not in Row n. By Fact 1 with m=nk, there must be integers a and b such that ab=n(nk) and nk<ab<n.

    Because a and b are integers strictly between nk and n, there must exist integers x and y with 1<xy<k such that a=ny and b=nx. We are assuming that n2nk=ab, so we can substitute to get n2nk=(ny)(nx)=n2(x+y)n+xy. This can be simplified and rearranged to get (x+yk)n=xy. The integers x and y are both positive, so xy is positive, which implies that x+yk is positive so we can solve for

    n to get n=xyx+yk.

    Now suppose x+y>k+1 and consider the expression (x1)y(x1)+ykxyx+yk, which we can simplify as follows: (x1)y(x1)+ykxyx+yk=(x1)y(x+yk)(xy)(x+y1k)(x+yk)(x+y1k)=x2y+xy2xykxyy2+ykx2yxy2+xy+xyk(x+yk)(x+y1k)=y2+yk(x+yk)(x+y1k)=y(ky)(x+yk)(x+y1k) Carefully considering the components of the fraction above, we have that y is a positive integer with y<k, so the quantity ky must be negative, and since x+y>k+1, the quantities x+yk and x+yk1 are both positive. Therefore, the fraction at the end of the calculation above is negative, so we get that (x1)y(x1)+ykxyx+yk<0 which implies that (x1)y(x1)+yk<xyx+yk.

    We have shown that if x+y>k+1, then the quantity xyx+yk can be made larger by decreasing x by 1. A similar argument shows that if x+y>k+1, then the quantity gets larger when y is decreased by 1. Since n=xyx+yk and we seek the largest possible n, we conclude that n can always be made larger by decreasing x+y by 1, provided x+y is larger than k+1. Therefore, the maximum value of n must occur when x+y=k+1.

    Note: It is possible (and essentially assured) that xyx+yk is not always an integer. However, since it is maximized when x+y=k+1, which makes the denominator equal to 1, the maximum possible value of xyx+yk given the constraints on x and y happens to be an integer. Therefore, the maximum possible integer value of xyx+yk is the maximum possible value, which occurs when x+y=k+1.

    Substituting x+y=k+1 into n=xyx+yk, we get n=xy. Therefore, the task is to maximize xy subject to the conditions 1<xy<k and x+y=k+1.

    Substituting y=k+1x into xy, we get xy=x(k+1x)=(k+1)xx2. Since k is fixed, the expression (k+1)xx2 is a quadratic in x with a negative coefficient of x2. Therefore, it has a maximum value and it occurs when x=k+12.

    We are looking for the maximum among integer values of x, so if k+12 is an integer, the maximum occurs exactly when x=k+12. Since x+y=k+1, this implies that y=k+12 as well.

    Otherwise, the maximum will occur at the integer nearest k+12. There is a tie between k+1212=k2 and k+12+12=k+22. Notice that the sum of these two possible values of x is k2+k+22=k+1, so one of the values must be x and the other must be y. Since xy, we have that x=k2 and y=k+22.

    Now to summarize what we have so far: if we assume that n2kn is not in Row n, then n is no larger than (k+12)2 when k is odd and n is no larger than k2(k+22)=k(k+2)4 when k is even. Note that when k=10, we get 10(12)4=30, which agrees with the answer to part (c) of the original problem.

    To finish the argument, we need to verify that [(k+12)2]2k(k+12)2 is not in Row (k+12)2 when k is odd and that (k(k+2)4)2k(k(k+2)4) is not in Row k(k+2)4 when k is even. We will only include the verification for when k is odd here. The verification when k is even is similar.

    Expanding and simplifying, we have [(k+12)2]2k(k+12)2=(k+12)2[(k+12)2k]=(k+12)2[k2+2k+14k4]=(k+12)2[k22k+14]=(k214)2 Now set n=(k+12)2, m=nk, and a=b=k214. It follows from the calculation above that mn=ab. If we can show that m<ab<n, then we can apply Fact 2 to get that mn=n2kn is not in Row n. Note that a=b by definition, so ab is automatically true. Expanding gives n=k2+2k+14 and m=k22k+14, and it is easily checked that m=k22k+14<k214<k2+2k+14=n for all k>1. This means we can apply Fact 2 as long as k>1, which completes the verification that the maximum value of n is exactly (k+12)2 when k is odd and k>1.

    Finally, if k=1, then n2kn=n2n. By the original contest problem, n2n is in Row n for n3. Also, n2n is in Row n when n=2, but when n=1, n2n=0 is not in Row n. Therefore, when k=1, the maximum value of n for which n2kn is not in Row n is n=1. Notice that (k+12)2 evaluates to 1 when k=1, so the formula works even in this case.

  2. Suppose m is a positive integer with mp such that mp is not in Row p. By Fact 1, there exist positive integers a and b such that mp=ab and m<ab<p. The equation mp=ab implies that ab is a multiple of p, and since p is a prime number, a or b must be a multiple of p. (This is by a fact often known as Euclid’s Lemma.) We also have that a and b are positive and both less than p, so it is impossible for either of them to be a multiple of p because p is prime.

    We conclude that there are no positive integers m with mp such that mp is not in Row p. In other words, mp is in Row p for every positive integer m with mp.

    Since 0 is not in any row and 0=0×p is a multiple of p, 0 is the largest integer m with the property that mp and mp is not in Row p. Thus, f(p)=0 when p is a prime number.

  3. We will show that f(pq)=(p1)(q1). To do this, we need to establish two things:

    We will assume that pq. If not, then qp and the proof is essentially identical.

    To see that the first point is true, set n=pq, m=(p1)(q1), a=q(p1), and b=p(q1) and apply Fact 2. Note that p1<p so (p1)(q1)<p(q1) or m<a. We also have pq, which can be rearranged to get qp, and so pqqpqp, which can be factored to get q(p1)p(q1) or ab. Finally, q1<q, so b=p(q1)<pq=n. Putting these inequalities together, we have m<ab<n. Since mn=(p1)(q1)pq=ab, the conditions of Fact 2 are satisfied and we can conclude that (p1)(q1)pq is not in Row pq.

    Now suppose k is an integer such that (p1)(q1)<kpq. We wish to show that kpq must be in Row pq. To do this, we will assume that it is not in Row pq and deduce a contradiction.

    To that end, assume that kpq is not in Row pq. By Fact 1, there must be integers a and b with k<ab<pq such that kpq=ab. If a is a multiple of pq, then we would have pqa, but a<pq by assumption, so this is impossible. Therefore, a is not a multiple of pq. Similarly, b is not a multiple of pq.

    Since ab is a multiple of pq and p and q are prime, either a is a multiple of p and b is a multiple of q, or a is a multiple of q and b is a multiple of p. We will assume that a is a multiple of p and b is a multiple of q. The other situation is similar. This implies the existence of integers x and y such that px=a and qy=b. Observe that since a<pq, we must have x<q, and similarly y<p. Since x, y, p, and q are integers, we conclude that xq1 and yp1.

    Since we are assuming that kpq=ab, we have k=abpq=pxqypq=xy(p1)(q1) However, we are also assuming that (p1)(q1)<k, so we can deduce that k(p1)(q1)<k which is impossible because it implies k<k. Therefore, our assumption that kpq is not in Row pq must be false, and we conclude that kpq is in Row pq.

    Therefore, f(pq)=(p1)(q1) as claimed earlier.

  4. The value of f(pd) depends on whether d is even or odd. If d=2r for some integer r, then f(pd)=(pr1)2. If d=2r+1 for some integer r, then f(pd)=(pr1)(pr+11).

    Here we include a proof in the case where d is even. The proof when d is odd is a slight modification of the proof given for when d is even.

    Assume d=2r for some positive integer r. As with part (c), we need to show that

    If we set m=(pr1)2, n=p2r, and a=b=pr(pr1), then we will have m<ab<n and mn=ab, so p2r(pr1)2 is not in Row p2r by Fact 2. This establishes the first bullet point above.

    For the second, suppose kp2r is not in Row p2r for some k with (pr1)2<kp2r. By Fact 1, there must be integers a and b with (pr1)2<ab<p2r and kp2r=ab.

    The product ab must have at least 2r factors of the prime number p, meaning the two integers a and b have at least a total of 2r factors of p between them. Therefore, there are non-negative integers u and v such that u+v=2r, a is a multiple of pu, and b is a multiple of pv. By definition, there are positive integers x and y such that pux=a and pvy=b.

    We are also assuming that ab<p2r=pu+v=pupv, so a=pux<pupv and b=pvy<pupv, which implies x<pv and y<pu. Since x, p, u, and v are non-negative integers, we have xpv1 and ypu1. Multiplying these inequalities, we obtain xy(pu1)(pv1). We are also assuming that kp2r=ab, so we can substitute to get kp2r=xypupv=xypu+v=xyp2r Thus, kp2r=xyp2r, so k=xy, which implies k(pu1)(pv1).

    We can now conclude that (pr1)2<k(pu1)(pv1). To finish the argument, we will show that (pu1)(pv1)(pr1)2, which would imply that (pr1)2<(pr1)2, which is clearly false.

    To show that (pu1)(pv1)(pr1)2, we will show that if u and v are non-negative integers with u+v=2r, then the quantity (pu1)(pv1) is maximized when u=v=r.

    Suppose u and v are non-negative integers with u>v and u+v=2r. Consider the quantity (pu11)(pv+11)(pu1)(pv1). We can manipulate this difference as follows. (pu11)(pv+11)(pu1)(pv1)=pu+vpu1pv+1+1pu+v+pu+pv1=pu+pvpu1pv+1=pv(puv+1puv1p)=pv(puvp)(11p) We are assuming that u>v. Since u+v is even, it must also be true that uv is even. Therefore, uv2. As well, p is a prime number so p2, which implies puvp>0 and 11p>0. The quantity pv is positive, and so we conclude that pv(puvp)(11p)>0, which implies that (pu11)(pv+11)(pu1)(pv1)>0. Rearranging this inequality, we get (pu11)(pv+11)>(pu1)(pv1).

    What we have shown is that if u and v are non-negative integers with u+v=2r and u>v, we can increase the value of (pu1)(pv1) by decreasing u by 1 and increasing v by 1. It follows that (pu1)(pv1) is maximized when u and v are as close together as possible, which happens when u=v=2r2=r.

  5. In general, f(n) can be computed as follows: find the unique positive integers x and y with xy, xy=n, and yx as small as possible. Then f(n)=(x1)(y1).

    For example, if n=p is a prime number, then the only positive factor pair is p=1×p, so x=1 and y=p. Indeed, from part (b), f(p)=0=(11)(p1)=(x1)(y1). If n is a perfect square, then n=z2 for some positive integer z. Here, we must have x=y=z because this gives yx=0, which is the smallest that the difference between the factors in a factor pair could possibly be. Indeed, f(z2)=(z1)2 agrees with the case from part (d) where n=p2r. As a final example, consider n=72. Its positive factor pairs are (1,72), (2,36), (3,24), (4,18), (6,12), and (8,9). The pair with the smallest difference between the factors is (8,9), so we have x=8 and y=9, giving (x1)(y1)=(81)(91)=56. Indeed, 56×72=63×64, so 56×72 is not in Row 72. As well, you can check that 72m is in Row 72 for each m from 57 through 72, which shows that f(72)=56.

    We will now justify that this "formula" always works.

    Fix an integer n and suppose x, y, u, and v are positive integers with xy, uv, and xy=uv=n.

    If yxvu, then since xy, we have 0yxvu, so we can conclude that (yx)2(vu)2. Expanding these expressions and adding 4n to both sides, we have y22xy+x2v22uv+u2y22xy+x2+4nv22uv+u2+4ny22xy+x2+4xyv22uv+u2+4uvy2+2xy+x2v2+2uv+u2(y+x)2(v+u)2 and since y+x and v+u are both positive, we must have y+xv+u. Essentially the same argument in reverse shows that if y+xv+u, then yxvu.

    We have shown that yxvu exactly when y+xv+u. This implies that if we consider all positive factor pairs of n, the one that has the smallest difference is also the one that has the smallest sum. Therefore, we can restate our "formula" as follows: Given a positive integer n, let x and y be positive integers with xy=n and x+y as small as possible. Then f(n)=(x1)(y1). We will assume that the integers x and y satisfy xy. If not, then they can be relabelled.

    The overall structure of the argument will resemble the arguments for parts (c) and (d). That is, we will show that xy(x1)(y1) is not in Row n, but if (x1)(y1)<mn, then mxy is in Row n. The solution presented will use, without proof, a few well-known facts about divisibility and greatest common divisors.

    To see that xy(x1)(y1) is not in Row n, take m=(x1)(y1), a=y(x1), and b=x(y1) and apply Fact 2. That these choices of m, a, b, and c satisfy the conditions of Fact 2 can be verified in essentially the same way as they were in the solutions to parts (c) and (d).

    Now suppose m is an integer with (x1)(y1)<mn=xy such that mn is not in Row n. By Fact 1, there are integers a and b such that m<ab<n and ab=mn. Let d=gcd(n,b) and then define e=nd and f=bd. Observe that the integers e and f must satisfy gcd(e,f)=1 since if they had a common divisor larger than 1, then the greatest common divisor of n and b would need to be larger than d.

    Dividing both sides of ab=mn by d, we get af=me, which shows that af is a multiple of e. We have already noted that e and f have no common divisors larger than 1, so we are forced to conclude that a is a multiple of e. That is, there must be some integer g such that a=eg.

    To summarize, so far we have that d=gcd(b,n), de=n, df=b, and eg=a. Consider the integers e and f and suppose ef. Multiplying both sides by d gives dedf or nb, but this contradicts our assumption that b<n, so we cannot have ef. Therefore, f<e, and since both e and f are integers, we get fe1. Similarly, if dg, then deeg or na, which contradicts our assumption, so we conclude that g<d and so gd1.

    We are assuming that (x1)(y1)<m, so we have the following n(x1)(y1)<mn=ab=egdfde(e1)(d1) which implies n(x1)(y1)<de(d1)(e1). Using that n=de, we cancel to get (x1)(y1)<(d1)(e1) which can be expanded to get xyxy+1<dede+1, and since de=xy=n, this simplifies to d+e<x+y. However, xy=n is the factorization of n into a product of positive integers that minimizes the sum of the factors. Since de=n, the inequality d+e<x+y is a contradiction of this minimality.

    We conclude that our assumption that mn is not in Row n must be false, which means mn is in Row n. This completes the proof.