Let be a positive integer and . Find out in how many ways we can split the set into three mutually disjoint nonempty sets so that both the following are true:
(i) for each and , the remainder of the division of by belongs to ,
(ii) for each there exists and such that is the remainder of the division of by .
Mircea Fianu
Solution
We notice that , for all and . Indeed, the contrary would imply that , so the remainder of the division of by is and belongs to both and . This shows that is made by consecutive numbers and .
Take . From the assumption there exists and so that . Then , hence , therefore . If we suppose that , then , whence . So, if , then and, since contains consecutive numbers, must contain at least one multiple of – false.
Henceforth , so there exists so that . From for all follows .
The remainders of the divisions of the elements of to the elements of are the numbers . This shows that and . The number can be every element of the set , so there are possible splits.
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.