Maths Olympiad Prep

Library / /7 of 10

Combinatorics Difficulty 6.6 National olympiad Prove it Netherlands

Alicia writes down aa distinct integers on a piece of paper and Britt writes down bb distinct integers on another piece of paper. Alicia wrote down at least one integer that Britt did not write down, and Britt wrote at least one integer down that Alicia did not write down. Vera counts the number of distinct integers on the two pieces of paper; let this number of distinct integers be vv. Daan counts how many of the integers that have been written down by Alicia, have also been written down by Britt; let dd be this number. For example, if Alicia wrote down 11, 22, and 55, and Britt wrote down 22, 55, 77, and 88, then we have a=3a = 3 and b=4b = 4 while v=5v = 5 and d=2d = 2.

a. Find an example for which a=b=2022a = b = 2022 and ab=d(v+d)a \cdot b = d \cdot (v + d).

b. Is it possible that ab=d(v+4)a \cdot b = d \cdot (v + 4)? Give an example or prove that it is impossible.

c. Is it possible that ab=dva \cdot b = d \cdot v? Give an example or prove that it is impossible.

Solution

We first note that there is a useful relation between aa, bb, dd, and vv. The total number of integers on the two pieces of paper is a+ba + b, the number of integers on Alicia's piece of paper plus the number of integers on Britt's piece of paper. This, however, also equals v+dv + d: the total number of distinct integers, plus the total number of integers that have been written down twice. Hence, we get that a+b=v+da + b = v + d.

a. We choose a=b=2022a = b = 2022 and look for a solution to ab=d(v+d)a \cdot b = d \cdot (v + d). We use the fact that a+b=v+da + b = v + d. This means that we are looking for solutions to ab=d(a+b)a \cdot b = d \cdot (a + b). If we substitute a=b=2022a = b = 2022, then we find that 20222022=d(2022+2022)=d220222022 \cdot 2022 = d(2022 + 2022) = d \cdot 2 \cdot 2022, so d=1011d = 1011. Together with a+b=v+da + b = v + d, we find that 2022+2022=v+10112022 + 2022 = v + 1011, so v=3033v = 3033. This situation happens for example if Alicia writes down the numbers 11 to 20222022, and Britt writes down the numbers 10121012 to 30333033.

b. With a little bit of trying, and by choosing dd not too large, we find that a=b=3a = b = 3, d=1d = 1, and v=5v = 5 is a solution: 33=1(5+4)3 \cdot 3 = 1 \cdot (5 + 4). The numbers also satisfy the equation a+b=v+da + b = v + d. This situation can occur if Alicia writes down the numbers 11, 22, and 33, and Britt writes down the numbers 33, 44, and 55, for example.

c. Suppose that there are numbers such that ab=vda \cdot b = v \cdot d. We already deduced that a+b=v+da + b = v + d, or v=a+bdv = a + b - d. Substituting this yields
ab=vd=(a+bd)d=ad+bdd2.ab = vd = (a + b - d)d = ad + bd - d^2.
If we now subtract adad from both sides of this equation, we find abad=bdd2ab - ad = bd - d^2, so a(bd)=d(bd)a(b - d) = d(b - d). Because Britt wrote down at least one number that Alicia did not write down, we have b>db > d. Therefore, we can divide the equation a(bd)=d(bd)a(b - d) = d(b - d) by the positive number bdb - d, and we find that a=da = d. On the other hand, Alicia wrote down at least one number that Britt did not write down, hence a>da > d. This gives a contradiction and hence there cannot exist numbers such that ab=vda \cdot b = v \cdot d.

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.