was it $c\in (0,\sqrt2)$?

I posted my solution here. Might have some flaws; what score can i expect?

The answer is $c < \sqrt 2$. Density arguments don't work as far as I know, unfortunately...

That's the solution set I found, but I wasn't able to rigorously prove it.

I proved that $c=\sqrt{2}$ does not work. Will I get any points?

UrInvalid I'm not sure that works. Jasonhu4 what was your solution?

At least two or three.

Darn, I did a density solution.. how many points?

I think it's probably easier to show everything under root 2 works (hoping for 1 pt for a semi proof of this). Density doesn't do anything really because 8 for example can fill more than $\frac{1}{2^8}$ of the grid (not hard to see why), which makes it a bit trickier.

What is the idea for $c\neq \sqrt{2}$?

I basically just proved the label $n$ can only fill up $\frac{1}{2^n}$ of the points and since there are a finite number of labels it can't sum up to 1..

How does that work? I got that idea and couldn't finish it...

jasonhu4 wrote: I basically just proved the label $n$ can only fill up $\frac{1}{2^n}$ of the points and since there are a finite number of labels it can't sum up to 1.. yeah it's kind of hard because equilateral triangles give more than $\frac{1}{2^n}$. Tried that for too long during the test and failed.

You can use density for $c>\sqrt{2}$, but I don't know how to disprove $c=\sqrt{2}$. There's an easy inductive solution to prove all $c<\sqrt{2}$ work.

jasonhu4 wrote: I basically just proved the label $n$ can only fill up $\frac{1}{2^n}$ of the points and since there are a finite number of labels it can't sum up to 1.. Hard to prove since a brute regionalization fails starting at label 3

inb4 $c=\sqrt{2}$ actually works

v_Enhance wrote: The answer is $c < \sqrt 2$. Density arguments don't work as far as I know, unfortunately...

Shaddoll wrote: jasonhu4 wrote: I basically just proved the label $n$ can only fill up $\frac{1}{2^n}$ of the points and since there are a finite number of labels it can't sum up to 1.. yeah it's kind of hard because equilateral triangles give more than $\frac{1}{2^n}$. Tried that for too long during the test and failed. How can there be equilaterals over Z^2?

UrInvalid wrote: Shaddoll wrote: jasonhu4 wrote: I basically just proved the label $n$ can only fill up $\frac{1}{2^n}$ of the points and since there are a finite number of labels it can't sum up to 1.. yeah it's kind of hard because equilateral triangles give more than $\frac{1}{2^n}$. Tried that for too long during the test and failed. How can there be equilaterals over Z^2? We can have near equilaterals as the labels grow big

And turns out this problem was proposed by Ricky Liu. Probably could have guessed from the fact that $\mathbf Z$ was used in lieu of $\mathbb Z$. That's certainly something that Titu and Zuming don't do

@above, why are you aZuming their LaTeX style habits!?

@above titu just make a pun!?

darn, puns are too tRicky for me

zephyrcrush78 wrote: darn, puns are too tRicky for me really? evan I can make puns...

Uhhh so to avoid derailing this thread entirely I will post my construction for $c < \sqrt2$. We will iteratively construct a series of patterns $P_1, P_2, \ldots$ with which to tessellate the plane, and such that each $P_n$ achieves $c \le (\sqrt2)^{n/(n+1)}$. First, for $n=1$, tessellate the plane with the pattern $P_1 = \begin{bmatrix} 1 & 2 \\ 2 & 1 \end{bmatrix}$. Then for each $n > 1$, construct $P_n$ by taking $P_{n-1}$, copying it four times into a $2 \times 2$ array of itself, and replacing half the entries $n$ in a square pattern with $(n+1)$s. For instance, to get $P_2$ from $P_1$ we do \[ \begin{bmatrix} 1 & 2 \\ 2 & 1 \end{bmatrix} \to \begin{bmatrix} 1 & 2 & 1 & 2 \\ 2 & 1 & 2 & 1 \\ 1 & 2 & 1 & 2 \\ 2 & 1 & 2 & 1 \end{bmatrix} \to \begin{bmatrix} 1 & 2 & 1 & 2 \\ 3 & 1 & 3 & 1 \\ 1 & 2 & 1 & 2 \\ 3 & 1 & 3 & 1 \end{bmatrix} \]and to get $P_3$ from $P_2$ we do \[ \begin{bmatrix} 1 & 2 & 1 & 2 \\ 3 & 1 & 3 & 1 \\ 1 & 2 & 1 & 2 \\ 3 & 1 & 3 & 1 \end{bmatrix} \to \begin{bmatrix} 1 & 2 & 1 & 2 & 1 & 2 & 1 & 2 \\ 3 & 1 & 3 & 1 & 3 & 1 & 3 & 1 \\ 1 & 2 & 1 & 2 & 1 & 2 & 1 & 2 \\ 3 & 1 & 3 & 1 & 3 & 1 & 3 & 1 \\ 1 & 2 & 1 & 2 & 1 & 2 & 1 & 2 \\ 3 & 1 & 3 & 1 & 3 & 1 & 3 & 1 \\ 1 & 2 & 1 & 2 & 1 & 2 & 1 & 2 \\ 3 & 1 & 3 & 1 & 3 & 1 & 3 & 1 \\ \end{bmatrix} \to \begin{bmatrix} 1 & 2 & 1 & 2 & 1 & 2 & 1 & 2 \\ 4 & 1 & 3 & 1 & 4 & 1 & 3 & 1 \\ 1 & 2 & 1 & 2 & 1 & 2 & 1 & 2 \\ 3 & 1 & 4 & 1 & 3 & 1 & 4 & 1 \\ 1 & 2 & 1 & 2 & 1 & 2 & 1 & 2 \\ 4 & 1 & 3 & 1 & 4 & 1 & 3 & 1 \\ 1 & 2 & 1 & 2 & 1 & 2 & 1 & 2 \\ 3 & 1 & 4 & 1 & 3 & 1 & 4 & 1 \\ \end{bmatrix}\]EDIT: I think this is isomorphic to Evan's construction, but all the better for me in that case

is this the reason they didn't allow graph paper?

lol i asked for graph paper from my paper, only to find it's not allowed

trashbagcheater234 wrote: lol i asked for graph paper from my paper, only to find it's not allowed i'd imagine not many papers would be willing to hand their brethren over

hi my sol is identical to evans but where he says 2n doesnt work i said n+1 because i messed up square roots could i get 5+?????

Yes, if the idea is there you will get points.

USAMO #5 wrote: only finitely many distinct labels occur imo, this wording was not very good. I'm still not sure I understand it correctly. During the test, I took it to mean only finitely many labelings occur, meaning there are only a finite number of labelings of the lattice points which satisfy the 2nd condition. It really means (I hope this is correct) only finitely many positive integers are labels of some lattice point. Because I misread the problem in this way, I only "proved" that $c\le \sqrt{2}$ does not work, because there are an infinite number of labelings for $c\le \sqrt{2}$ such that the second condition holds. I guess this is my fault, but I'm pretty sure if I had read the problem more meticulously, I might not have understood it. Did anyone else have the same problem? (It was probably just me) rip any partial credit on this.

Proving $\sqrt{2}$ is not possible is sufficient. It is relatively easy to prove $c<\sqrt{2}$ by defining an n-board as the centers of black squares on an infinitely large checkerboard, where each square is size nxn. After this is done, it is kind of obvious that if some $c$ works, then any $c' < c$ also works because you can use the exact same tiling. Thus after proving $\sqrt{2}$ does not work, that means any $c>\sqrt{2}$ does not work because otherwise would imply $\sqrt{2}$ works, a contradiction. Then you just prove $\sqrt{2}$ doesnt work by considering a $2^n x 2^n$ set of latices, and you need $n+3$

The answer is the interval $(0,\sqrt{2})$. For any $c<\sqrt{2}$, there exists a positive integer $k$ such that $c^k < (\sqrt{2})^{k-1}$, so one can label the lattice with finitely many integers. The construction is already mentioned many times: paint $\mathbb{Z}^2$ in the checkerboard fashion, and the remaining set of points is just $\mathbb{Z}^2$ scaled up by a factor of $\sqrt{2}$, so we can repeat the process until $c^k$ gets smaller than $(\sqrt{2})^{k-1}$ and then we can label all points at once. From now on, it suffices to prove $c=\sqrt{2}$ does not work. Suppose for contradiction that there is a valid labeling: Claim. In any $2^k\times 2^k$ square, there is a point labeled with a number at least $2k+1$.

The claim ensures that we will need arbitrarily many labels to label the full lattice, a contradiction.

Can someone check the following solution? Apologies if it's written poorly, and for the lack of diagrams.