Day 8: The Gift Exchange

When examined further, this problem can actually be solved fairly easily using group theory. We are given a group operation, which is addition modulo $1000$ , and a set of integers on which to act. Since this problem tells us we must include the mathematician with the $0$ designation within our subset of mathematicians, we can define $0$ to be the identity element of the subgroups that we are trying to find, since only subgroups will obey the given criteria within the question (the mathematicians must give a gift to the person with the number that is equivalent to the remainder when their own number plus $n$ is divided by $1000$ , and all mathematicians giving and receiving gifts must be completely contained within the subset). By Lagrange's Theorem, we know that $\frac{|G|}{|H|}$ , where $G$ is a group, and $H$ is some subgroup. The different $a$ values that we are trying to find are essentially the different orders of the subgroups, so we know that all $a$ values must divide the order of $G$ , which is $1000$ . Taking the prime factorization of $1000$ , we get $2^3 5^3$ . All $a$ values in the form $p^t$ that divide $2^3 5^3$ are ${2^1, \ 2^2, \ 2^3, \ 5^1, \ 5^2, \ 5^3}$ , therefore the number of different $a$ values is $6$ .