greentreeroad wrote: For part 2, observe that any distance should be the square root of an integer between 1 and $ 3n^2$, again establishing the desired inequality. How could this work? My way to part 2: Lemma: Let $ x_1,\ldots ,x_n$ be reals with $ m \leq x_i \leq M$. Then $ \sum_{1\leq i<j \leq n}(x_i-x_j)^2 \leq \frac{n^2}{4}(M-m)^2$. Proof The condition shows $ (x_i-m)(x_i-M) \leq 0$ or $ x_i^2 \leq (m+M)x_i-mM$ take sum over $ i=1,\ldots ,n$: $ \sum_{i=1}^{n}x_i^2 \leq (m+M) \sum_{i=1}^{n}x_i-nmM$. So $ \sum_{1\leq i<j \leq n}(x_i-x_j)^2 = n\sum x_i^2-(\sum x_i)^2 \leq n(m+M) \sum x_i-n^2mM-(\sum x_i)^2 \leq \frac{n^2}{4}(M-m)^2$ Suppose there are $ k$ points, with coordinates $ A_i(x_i,y_i,z_i),i=1, \ldots ,k$. We calculate $ f=\sum_{1 \leq i<j \leq k}A_iA_j^2$. First, all $ A_iA_j^2$'s are different positive integers so $ f \geq 1+2+ \ldots +\frac{k(k+1)}{2}=\frac{k(k+1)}{2} [\frac{k(k+1)}{2}+1]$ Second, $ f=\sum_{1\leq i<j \leq k}[(x_i-x_j)^2+(y_i-y_j)^2+(z_i-z_j)^2] \leq 3\frac{k^2}{4}(n-1)^2$. So we can conclude that $ k<\sqrt{6}(n-1)+1 <\sqrt{6}n$.

Sorry, should be each distance is a square root of an integer between 1 and $ 3(n - 1)^2$. let number of points be k, so $ \frac{k(k - 1)}{2} < = 3(n - 1)^2$ which gives the desired bound for 2nd part. I should state that number of points is k in last post.

greentreeroad wrote: Sorry, should be each distance is a square root of an integer between 1 and $ 3(n - 1)^2$. let number of points be k, so $ \frac {k(k - 1)}{2} < = 3(n - 1)^2$ which gives the desired bound for 2nd part. Well done! Much simpler than mine.

Actually I didn't solve this part on the contest.(I did the harder part) Many people got more or less stuck on this problem despite the fact that it almost seems trivial after scanning the solution.

Is there any nice solution for the first part, namely proving that it's less than $ (n+2)\sqrt{n/3}$? I know one only needs to prove it for a finite quantity of integers, because $ (n+2)\sqrt{n/3}$ is asymptotically bigger than $ n\sqrt 6$. I made a slight improvement on the second part, using $ \frac 78\cdot3(n-1)^2 + 1$ instead of $ 3(n-1)^2$ (numbers$ \equiv 7\pmod 8$ can't be written as sum of three squares), but I still needed to work out the cases $ n \leq 7$, which I solved by brute force.

cyshine wrote: Is there any nice solution for the first part, namely proving that it's less than $ (n + 2)\sqrt {n/3}$? I know one only needs to prove it for a finite quantity of integers, because $ (n + 2)\sqrt {n/3}$ is asymptotically bigger than $ n\sqrt 6$. I made a slight improvement on the second part, using $ \frac 78\cdot3(n - 1)^2 + 1$ instead of $ 3(n - 1)^2$ (numbers$ \equiv 7\pmod 8$ can't be written as sum of three squares), but I still needed to work out the cases $ n \leq 7$, which I solved by brute force. Look at my first post. since x,y,z direction difference must be within 0 to n-1. If they are the same, gives n-1 different distances. If two of them are same, gives n(n-1) different distances. If all three are different, gives n(n-1)(n-2)/6 different distances. Adding them up gives another expression for the maximum number of distances in this space.

Hi greentreeroad, I didn't read your first message. Sorry about that. What I'm wondering now is if this maximum number of points is $ O(n)$. Are there any examples with, say, $ n$ points? I haven't thought about it, so I'll give it a try later.

Let $p=|S|$. Then, since there are at most $(n-1)\sqrt3$ different distances between points, we know that $p(p-1)<n\sqrt{12}$. We can use this to prove both bounds. We start by proving $p<n\sqrt6$. If $n=1$ then it's trivial. If $n>1$ then $n>\frac{(2+\sqrt2)\sqrt3}{6}$ so $6n^2-n\sqrt6>n\sqrt{12}$. Now we assume $p\ge n\sqrt6$, for sake of contradiction. Then $p(p-1)\ge 6n^2-n\sqrt6 > n\sqrt{12}$, so contradiction. Now we prove that $p<(n+2)\sqrt{n/3}$. We know that $(n+1)^2\geq 2n$ for all $n$, so $(n+2)^2\times\sqrt{n/3}-n-2>2\sqrt{n}$. Therefore $(n+2)^2\times\frac{n}{3}-(n+2)\times\sqrt{\frac{n}{3}}>n\sqrt{12}$. If $p\ge (n+2)\sqrt{n/3}$ then $p(p-1)\ge (n+2)^2\times\frac{n}{3}-(n+2)\times\sqrt{\frac{n}{3}}>n\sqrt{12}$. Contradiction.

cyshine wrote: Is there any nice solution for the first part, namely proving that it's less than $ (n+2)\sqrt{n/3}$? I know one only needs to prove it for a finite quantity of integers, because $ (n+2)\sqrt{n/3}$ is asymptotically bigger than $ n\sqrt 6$. I made a slight improvement on the second part, using $ \frac 78\cdot3(n-1)^2 + 1$ instead of $ 3(n-1)^2$ (numbers$ \equiv 7\pmod 8$ can't be written as sum of three squares), but I still needed to work out the cases $ n \leq 7$, which I solved by brute force. This solution works for $n\neq 4,7$ if you add floor signs. If $n=7$, notice that $28, 60, 88$ can't be written as the sum of three squares, and if $n=4$, $25,26\neq x^2+y^2+z^2~(x,y,z\in\{0,1,2,3\})$, so one can prove that $\binom{|S|}{2}\le 90, 20$ for each case.