Let $\mathbb{K}$ be two-dimensional integer lattice. Is there a bijection $f:\mathbb{N} \rightarrow \mathbb{K}$, such that for every distinct $a,b,c \in \mathbb{N}$ we have: \[\gcd(a,b,c)>1 \Rightarrow f(a),f(b),f(c) \mbox{ are not colinear? }\]
Problem
Source: Serbian National Olympiad 2012, Problem 5
Tags: combinatorics proposed, combinatorics
shinichiman
05.04.2012 08:46
Can you post the problem 3 for this Serbian NO 2012 ?
Djile
05.04.2012 11:01
shinichiman wrote: Can you post the problem 3 for this Serbian NO 2012 ? Posted http://www.artofproblemsolving.com/Forum/viewtopic.php?t=473461&p2650827#p2650827 Problem 6 is left, I will post it soon.
shinichiman
05.04.2012 14:29
I posted all problem of Serbian NO 2012 in here .
SCP
06.04.2012 12:17
Djile wrote: Let $\mathbb{K}$ be two-dimensional integer lattice. Assume there is a bijection $f:\mathbb{N} \rightarrow \mathbb{K}$, such that for every distinct $a,b,c \in \mathbb{N}$ we have if $f(a),f(b),f(c) $ are colinear , then $gcd(a,b,c)=1 $ Just look to all even numbers at a line: there would only be $2$ maximum or $gcd(a,b,c)\ge 2$ and $f(a),f(b),f(c)$ are collineair. But this means in each $n*n$ sublatice, we have max. $2n$ even numbers and so we place a lot more of odd integers, taking $n$ big enough, we get a contradiction.
Djile
06.04.2012 18:50
SCP wrote: Just look to all even numbers at a line: there would only be $2$ maximum or $gcd(a,b,c)\ge 2$ and $f(a),f(b),f(c)$ are collineair. But this means in each $n*n$ sublatice, we have max. $2n$ even numbers and so we place a lot more of odd integers, taking $n$ big enough, we get a contradiction. Well, this reasoning isn't correct. Just look at this sequence: $2, 1, 3, 4 , 5, 7, 9, 11, 6, 13, 15, 17, 19, 21, 23, 8, ...$, every even number $2n$ is followed by $2n$ odd numbers. In every block of this sequence, there is more odd numbers than even (a lot more), but nevertheless, every natural number is somewhere in this sequence.
SCP
06.04.2012 19:46
Yes, that is correct (even it seems normally illogical, we don't may take $N$ big enough, because $\infty$ is really so big). I can't find the genious solution, but could already find a counterexample: we can take each even number $n$ to $(n,n^2)$ and fill in each odd number in the square around the origin, then also every number will be placed somewhere, but if we just take finite numbers, they won't be in a square and many even numbers are outside our convex hull. But I'm unsure, because we have to show for all primes they won't be on a line. The dense become small for other values, so I can't guess the answer, do you know?
RaleD
06.04.2012 20:39
The solution goes like this (without details ): In (0,0) we write 1, now we think about squares that have (0,0) as the center. All integer points on sides of a square we call a layer of this square. Then in a layer we write numbers in such way: Suppose number $k$ is the last written, then we go to the next point in the layer (if there is any) in which we write the smallest composite number that is not already written if no line contains three points with the property (the one from statement); else we write the smallest prime that is not already written. Condition from problem will fail if no more composite numbers is possible to write. But that means that only finitely lines cover all integer points. (The process in beginning skips some composite, but not primes so all primes will be written) Sorry for not writing details.
SCP
07.04.2012 14:42
Today, I also thought the question could be solved so easy because $\infty$ is infinitely large. So we can fill in a new boundary around a previous square, starting with a $1$ in a square $(0,0)$ also for ex, with new primes. If a number isn't a prime, we just set it somewhere where the question yet is correct: just take a line $y=N$ and take $N^2$ points and by pigeon hole principle, we can even set is on a place so that no two points are collineair with it. (but obviously we normally also can place it closer where $N$ was our number). Now each square can be filled because there are $\infty$ primes and each natural number is places somewhere. genious and too easy in once, sentences like Djile wrote can work always to $\infty$ but almost never to some fixed number then.
JuanOrtiz
31.12.2013 06:49
YES
.
Firstly, note that finitely many lines cannot pass through every lattice point.
We define $B_k=\{(x,y) | max\{|x|,|y|\}=k \}$ sets of lattice points. Clearly $B_0$, $B_1$, ..., are a partition of $\mathbb{K}$. Now, we will say that we "assign" $a$ to $(b,c)$ if $f(a)=(b,c)$. First, assign $1$ to $(0,0)$ (the only element of $B_0$). Then, follow this process to assure that all numbers are assigned to some element of $\mathbb{K}$ and to assure that all elements of $\mathbb{K}$ have some number assigned to them.
Suppose all the elements of $B_0 \cup ... \cup B_n$ have some number assigned to them, and suppose no other element of $\mathbb{K}$ has a number assigned to it. Also, suppose $1,...,m$ are assigned to some lattice point and $m+1$ isn't. Then, the $(2n+1)^2$ lattice points which already have some number assigned to them can define only finitely many lines (at most ${(2n+1)^2}\choose{2}$). Therefore, there is some lattice point that doesn't belong to any of these lines. Assign $m+1$ to a lattice point that satisfies this property that belongs to $B_p$, with $p$ minimal. Now, say we have $X$ lattice points belonging to $B_{n+1}$, ..., $B_{p-1}$ or $B_p$ that haven't been assigned any number. We call these lattice points $L_1$, ..., $L_X$. Take $X$ primes that are greater than all the numbers that have been assigned to some lattice point so far, say $q_1$, ..., $q_X$, and assign $q_i$ to $L_i$ for all $1 \le i \le X$. Then all the elements of $B_0 \cup ... \cup B_p$ have some number assigned to them, and no other lattice point has, and $p \textgreater n$, and the numbers $1,...,m+1$ have been assigned to some lattice point, and we have not broken any rules, clearly.
Then if we repeat this process we will successfully construct $f$.
Maretangens
08.05.2021 23:29
Not sure why but isn't it trivial, just map $n \mapsto (n,\frac{n(n+1)}{2})$?
djmathman
09.05.2021 02:59
Maretangens wrote: Not sure why but isn't it trivial, just map $n \mapsto (n,\frac{n(n+1)}{2})$? The function $f$ needs to biject onto an integer lattice $\mathbb K$, i.e. a collection of points of the form $\{a\vec{u} + b\vec{v}:a,b\in\mathbb Z\}$ for some integer vectors $\vec{u}$ and $\vec{v}$.