Decide if it is possible to choose $330$ points in the plane so that among all the distances that are formed between two of them there are at least $1700$ that are equal.
Problem
Source:
Tags: algebra, contests
CT17
19.06.2022 06:30
redacted$ $
Justpassingby
19.06.2022 17:59
@above shouldn’t you prove no subdivision of $K_5$ and $K_{3,3}$ exist, as opposed to just $K_5$ and $K_{3,3}$?
407420
19.06.2022 18:04
CT17 wrote: Solved with Eyed, amuthup, ETS1331, AI216 We claim the answer is no. Let the distance we are considering be $d$. Draw a graph where two points are connected iff they are distance $d$ apart. Clearly this graph contains no $K_5$ or $K_{3,3}$, so it is planar by Kuratowski's theorem. But then it has at most $3\cdot 330 - 6 = 984$ edges, so we're done.
Actually, the answer is yes.