Problem of the Day: June 24
Find the largest positive integer N such that there are integers x1,...,xN such that xi2 - xixj is not divisible by 1111 for any i,j, i=/=j.
Edited to add solution: We have xi2 - xixj = xi(xi - xj) is not 0 mod 1111. Thus xi and xj have different remainders mod 1111. Since 1111 = 101 * 11, we also need to make sure we don't have xi be 0 mod 11 and xi - xj be 0 mod 101, or vice versa. We thus start with a list of 1111 integers, one for each remainder mod 1111, and then remove those which are 0 mod 11 and those which are 0 mod 101. That leaves 1000 integers on the list. (Some remaining clean-up work: show that that list of 1000 is maximal.)
(Problem source: 2016 Benelux Mathematical Olympiad #1.)
Edited to add solution: We have xi2 - xixj = xi(xi - xj) is not 0 mod 1111. Thus xi and xj have different remainders mod 1111. Since 1111 = 101 * 11, we also need to make sure we don't have xi be 0 mod 11 and xi - xj be 0 mod 101, or vice versa. We thus start with a list of 1111 integers, one for each remainder mod 1111, and then remove those which are 0 mod 11 and those which are 0 mod 101. That leaves 1000 integers on the list. (Some remaining clean-up work: show that that list of 1000 is maximal.)
(Problem source: 2016 Benelux Mathematical Olympiad #1.)
Comments
Post a Comment