Browse · MathNet
PrintSecond Round
Netherlands counting and probability
Problem
Alicia writes down distinct integers on a piece of paper and Britt writes down 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 . Daan counts how many of the integers that have been written down by Alicia, have also been written down by Britt; let be this number. For example, if Alicia wrote down , , and , and Britt wrote down , , , and , then we have and while and .
a. Find an example for which and .
b. Is it possible that ? Give an example or prove that it is impossible.
c. Is it possible that ? Give an example or prove that it is impossible.
a. Find an example for which and .
b. Is it possible that ? Give an example or prove that it is impossible.
c. Is it possible that ? Give an example or prove that it is impossible.
Solution
We first note that there is a useful relation between , , , and . The total number of integers on the two pieces of paper is , 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 : the total number of distinct integers, plus the total number of integers that have been written down twice. Hence, we get that .
a. We choose and look for a solution to . We use the fact that . This means that we are looking for solutions to . If we substitute , then we find that , so . Together with , we find that , so . This situation happens for example if Alicia writes down the numbers to , and Britt writes down the numbers to .
b. With a little bit of trying, and by choosing not too large, we find that , , and is a solution: . The numbers also satisfy the equation . This situation can occur if Alicia writes down the numbers , , and , and Britt writes down the numbers , , and , for example.
c. Suppose that there are numbers such that . We already deduced that , or . Substituting this yields If we now subtract from both sides of this equation, we find , so . Because Britt wrote down at least one number that Alicia did not write down, we have . Therefore, we can divide the equation by the positive number , and we find that . On the other hand, Alicia wrote down at least one number that Britt did not write down, hence . This gives a contradiction and hence there cannot exist numbers such that .
a. We choose and look for a solution to . We use the fact that . This means that we are looking for solutions to . If we substitute , then we find that , so . Together with , we find that , so . This situation happens for example if Alicia writes down the numbers to , and Britt writes down the numbers to .
b. With a little bit of trying, and by choosing not too large, we find that , , and is a solution: . The numbers also satisfy the equation . This situation can occur if Alicia writes down the numbers , , and , and Britt writes down the numbers , , and , for example.
c. Suppose that there are numbers such that . We already deduced that , or . Substituting this yields If we now subtract from both sides of this equation, we find , so . Because Britt wrote down at least one number that Alicia did not write down, we have . Therefore, we can divide the equation by the positive number , and we find that . On the other hand, Alicia wrote down at least one number that Britt did not write down, hence . This gives a contradiction and hence there cannot exist numbers such that .
Final answer
a) Example exists: Alicia writes 1 through 2022 and Britt writes 1012 through 3033; then d = 1011 and v = 3033 and the equality holds. b) Yes: Alicia {1, 2, 3} and Britt {3, 4, 5}; then a = b = 3, d = 1, v = 5 and the equality holds. c) Impossible: the relation forces a = d while the conditions require a > d, a contradiction.
Techniques
Counting two waysInclusion-exclusion