1 At random you choose a subset S of mathbbZ What is the sma

1. At random, you choose a subset S of mathbb{Z}. What is the smallest cardinality of S that guarantees that your set S contains two elements (m, n) and (m? , n? ) such that m ? m? (mod 6) and n ? n ? (mod 9)?

Solution

The smallest cardinality is 1 with the assumption of m=m\' ,n =n\' .

consider set S having an element (0,0), thus m ? m\' (mod 6) and n ? n\' (mod 9) becomes 0 ? 0 (mod 6) and 0 ? 0 (mod 9)

note : if m and m\' are different(also with n and n\'), the smallest cardinality is 2.

eg : (0,1) and (6,10)