Problem

Source: - All-Russian MO 2002 Regional (R4) 9.7 10.7 11.8

Tags: combinatorics, lattice points



(9.7) On the segment [0,2002] its ends and the point with coordinate d are marked, where d is a coprime number to 1001. It is allowed to mark the midpoint of any segment with ends at the marked points, if its coordinate is integer. Is it possible, by repeating this operation several times, to mark all the integer points on a segment? (10.7) On the segment [0,2002] its ends and n1>0 integer points are marked so that the lengths of the segments into which the segment [0,2002] is divided are corpime in the total (i.e., have no common divisor greater than 1). It is allowed to divide any segment with marked ends into n equal parts and mark the division points if they are all integers. (The point can be marked a second time, but it remains marked.) Is it possible, by repeating this operation several times, mark all the integer points on the segment? (11.8) On the segment [0,N] its ends and 2 more points are marked so that the lengths segments into which the segment [0,N] is divided are integer and coprime in total. If there are two marked points A and B such that the distance between them is a multiple of 3, then we can divide from cutting AB by 3 equal parts, mark one of the division points and erase one of the points A,B. Is it true that for several such actions you can mark any predetermined integer point of the segment [0,N]?