lattice point visible from the origin

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

lattice point visible from the origin

G H J

Reveal topic tags

combinatorics unsolved

L

G H BBookmark kLocked kLocked NReply

Source: 11-th Taiwanese Mathematical Olympiad 2002

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3595 posts

#1 h Jan 23, 2007, 9:41 AM • 1 Y

Y by Adventure10

A lattice point $X$ in the plane is said to be visible from the origin $O$ if the line segment $OX$ does not contain any other lattice points. Show that for any positive integer $n$ , there is square $ABCD$ of area $n^{2}$ such that none of the lattice points inside the square is visible from the origin.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

126 posts

#2 h Feb 4, 2007, 8:51 PM • 2 Y

Y by Adventure10, Mango247

The point (a,b) is not visible if and only if a and b are not coprime.
The square with vertices (a,b) ,(a+n,b),(a+n,b+n),(a,b+n) satisfies the condition of the problem if for each i and j a+i and b+j are not coprime but by chinese remainder theorem if we pick $p_{ij}$ to be different primes we can set $p_{ij}$ to divide a+i and b+j for all i,j=0,1,2...n.

So no points in this square is visible from the origin

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

RayThroughSpace

426 posts

RayThroughSpace

#3 h Mar 12, 2018, 2:11 AM • 1 Y

Y by Adventure10

How does the above construction ensure that the visible points when scaled down will also be contained inside a square with area $n^2$ ?

This post has been edited 1 time. Last edited by RayThroughSpace, Mar 12, 2018, 2:27 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1292 posts

#4 h Aug 15, 2023, 5:37 PM

Y by

The key is to see that if $\gcd(x_i,y_i)\ne 1$ then a point is invisible. Then, we know by CRT there exists a solution with primes $p_l\forall 1\le l\le n^2$ s.t. if $x_1,y_1$ is the coordinate of the bottom left corner, we have $x_1+i\equiv0\pmod{\prod_{k=1}^{n}p_{k+in}},y_1+i\equiv0\pmod{\prod_{j=0}^{n-1}p_{i+1+jn}}\forall 0\le i\le n-1.$

This post has been edited 2 times. Last edited by huashiliao2020, Aug 15, 2023, 5:39 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1340 posts

#5 h Oct 29, 2024, 5:13 PM

Y by

A Nice Problem

:

Note that, a point is visible if $\gcd(x, y)=1$ . So, we must have a common factor to both $x, y$ co-ordinates inorder for it to be invisible.

Let $(x_1, y_1)$ denote the left-bottom most point of the square.
Notice that, due to Chinese Remainder Theorem, we can find primes $p_{i, j}$ for $1 \le i, j \le n$ such that: $x_1 \equiv 0 \pmod {p_{1, 1} p_{1, 2} \cdots p_{1, n}}$ $x_1+1 \equiv 0 \pmod {p_{2, 1} p_{2, 2} \cdots p_{2, n}}$ $\cdots$ $x_1+n-1 \equiv 0 \pmod {p_{n, 1} p_{n, 2} \cdots p_{n, n}}$ $y_1 \equiv 0 \pmod {p_{1, 1} p_{2, 1} \cdots p_{n, 1}}$ $y_1+1 \equiv 0 \pmod {p_{1, 2} p_{2, 2} \cdots p_{n, 2}}$ $\cdots$ $y_1+n-1 \equiv 0 \pmod {p_{1, n} p_{2, n} \cdots p_{n, n}}$
Hence we can find such an invisible square and we are done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1005 posts

#6 h Jan 16, 2025, 12:38 PM

Y by

CRT FORCE FTW!!!!

Consider pairwise distinct primes $\{p_{i,j}\}_{1 \le i, j \le n+1}$ . Choose integers $x$ and $y$ such that
$x \equiv -i+1 \pmod{p_{i,j}}, y \equiv -j+1 \pmod{p_{i,j}}$ for all $(i, j) \in \{1, 2, \dots, n+1\}^2$ .
Then the square with diagonally opposite vertices $(x, y), (x+n, y+n)$ works.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a