Newsgroups: sci.math From: kirill@topaz.kiev.ua (Kirill E. Semenoff) Subject: A Cute Task! (Re: Your favourite proofs) Date: Mon, 18 Jul 1994 14:47:00 GMT I propose you a little task, in which I was impressed by both the problem and the solution. Here you are: There are square regular grid on the infinite plane. The length of each cell is 1 unit (accordingly, it's square is 1 sq.unit). Consider a blot on the plane that has arbitrary shape and has ssquare less than 1 sq.unit. --------------------------------------------------------- Prove that the blot can be moved (with no rotation) on the plane in such a way that it would not overlay any node of the grid. I know a beautiful solution for this task, which is, probably, my favourite proof. I'll post it soon, but first try to solve the problem. Good luck !!! ____________________________________________________ Everything You've Done Is A Mistake Kirill Semenoff, Topaz-Inform, Kiev, Ukraine ____________________________________________________ ============================================================================== Newsgroups: sci.math From: kfoster@rmii.com (Kurt Foster) Subject: A Cute Task! (Re: Your favourite proofs) Date: 18 Jul 1994 16:50:04 GMT Kirill E. Semenoff (kirill@topaz.kiev.ua) wrote: : I propose you a little task, in which I was impressed by both : the problem and the solution. Here you are: : There are square regular grid on the infinite plane. The : length of each cell is 1 unit (accordingly, it's square : is 1 sq.unit). Consider a blot on the plane that has : arbitrary shape and has ssquare less than 1 sq.unit. : --------------------------------------------------------- : Prove that the blot can be moved (with no rotation) on : the plane in such a way that it would not overlay any : node of the grid. Form a set T(S) in the region {(x,y) | each of x and y are in the interval [0,1) } by translating each point of S into that region. Clearly T(S) has area less than or equal to that of S (different points of S could translate to the same point in T(S) ). Also, if a translate of S includes a node, the same translate of T(S) also will include a node. Now, since the area of S is less than 1, so is that of T(S). There is therefore a point (a,b) with 0 < a < 1 and 0 < b < 1 which is NOT in T(S). The translation of T(S) by (-a, -b) does not include the node (0,0) since (a,b) is not in T(S). All the points (x-a, y-b) where (x,y) is in T(S) satisfy x-a in [-a, 1-a) and y-b in [-b, 1-b), so this translate of T(S) does not include any node points other than (0,0). The translation of S by (-a, -b) will therefore not include any nodes either. Standard stuff for the "geometry of numbers". ============================================================================== Newsgroups: sci.math From: kfoster@rmii.com (Kurt Foster) Subject: A Cute Task! (Re: Your favourite proofs) Date: 19 Jul 1994 01:54:54 GMT Kurt Foster (kfoster@rmii.com) wrote: : Form a set T(S) in the region {(x,y) | each of x and y are in the : interval [0,1) } by translating each point of S into that region. : Clearly T(S) has area less than or equal to that of S (different points : of S could translate to the same point in T(S) ). Also, if a translate : of S includes a node, the same translate of T(S) also will include a : node. I forgot to specify that the points of S are translated into T(S) by a node - in fact, you subtract the greatest integer from each coordinate. ^^^^ [deletia -- djr]