All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Just Math
Chinese remainder to the rescue (Posted on 2020-10-31) Difficulty: 3 of 5
A lattice point in the coordinate plane with origin O is called invisible if the segment OA contains a lattice point other than O and A. Let L be a positive integer. Show that there exists a square with side length L and sides parallel to the coordinate axes, such that all points in the square are invisible.

No Solution Yet Submitted by Danish Ahmed Khan    
Rating: 3.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
some progress | Comment 1 of 3

I had several problems here: 

1) - The problem says: L must be positive as an integer length as the side of a square. I wondered about the "positive". There is no such thing as a square with negative side. 

2) - The problem asks us to show that there is a square containing only "invisible" lattice points, but it is never stated if the lattice points on the side of a square are to be considered to be "in" the square or out. I will assume "within", or otherwise there is an easy solution of the 2x2 lattice (around the invisible point (2,2), where the square perimeter is: (1,1), (2,1), (3,1) (3,2), (3,3), (2,3) (1,3), (1,2) 

3) Why would we look for anything larger than a square of side 2 (4 points) to satisfy the problem? If there is a larger square with all invisible points, there will be a 2x2 square of invisible points within it. 

4) It is not mentioned if all four quadrants are to be considered. However, since the four lines:  x=1, x=-1, y=1, y=-1 are made entirely of visible points, they can not be overlaid by a square holding all invisible points. Therefore, only squares positioned entirely within one quadrant can be candidates. So, by symmetry, we need only search quadrant I. 

5) I understand that a point A=(x,y) is proven invisible if OA crosses another point, and that this happens when x and y have a mutual factor. E.g., if A= (2,6), OA then also crosses (1,3) and A is invisible. 

However,  I don't see how the Chinese Remainder Theorem comes to the rescue, since it is more concerned with divisors (x) that the do _not_ share prime factors with y but rather leave a remainder in a division.

6) I have seen somewhere before this "comb" of lines (of multiples) used to search for primes (where new primes would lie off of any lines of multiples of known primes.) 

Anyway, I performed a computer search of Quadrant I out to x=100,000, y=100,000 and found no 2x2 square of invisible grid points. 

The program is here, and the first 80 rows and columns are shown here, where where "V" means "visible". The rows and columns are labeled. 

In summary, I did not find any of the squares asked for, but I have no proof that none exist.  

Perhaps i have misunderstood the problem...


Edited on February 5, 2021, 11:47 pm
  Posted by Steven Lord on 2020-11-02 05:11:00

Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (11)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2024 by Animus Pactum Consulting. All rights reserved. Privacy Information