POTWs 3

Every week, we will select three notable or interesting problems, marked with E,M,H (“easy”, “medium”, “hard”) for the relative difficulty. Easy problems will be around TMO or easier than TMO; medium problems will be around Oct Camp / easy IMO, and hard problems will be around medium / hard IMO.

E3 [adapted from IMO 2006 P4]

Show that for all primes , is divisible by .

M3 [Bulgaria TST 2005]

Find the number of the subsets  of the set  such that the sum of the elements of  is congruent to  modulo .

H3 [reddit]

From any pair of positive integers , in each turn, you can choose to move to either or . Show that, starting from any pair of positive integers , you can reach a pair of two equal positive integers.

Solution will be available next week.