Problem 3

A collection of

n

squares on the plane is called tri-connected if the following criteria are satisfied: (i) All the squares are congruent. (ii) If two squares have a point

P

in common, then

P

is a vertex of each of the squares. (iii) Each square touches exactly three other squares. How many positive integers

n

are there with

2018\le n\le 3018

, such that there exists a collection of

n

squares that is tri-connected?

Step 1 of 4: Count touching incidences

Previous step Next step

\#\{(A,B): A\sim B\}=3n\ \text{is even}\ \Longrightarrow\ n\ \text{is even}

Detailed analysis

Write $A\sim B$ to mean squares $A$ and $B$ touch. Since $A\sim B$ if and only if $B\sim A$ , and each of the $n$ squares touches exactly three others, the number of ordered pairs $(A,B)$ with $A\sim B$ equals $3n$ , and this count is automatically even because ordered pairs come in reversible pairs $(A,B),(B,A)$ . Hence $3n$ is even, so $n$ is even.