# Lattice points [combinatorics]

We see, in Figures 1 and 2, examples of lock screens from a cellphone that only works with a password that is not typed but drawn with straight line segments. Those segments form a polygonal line with vertices in a lattice. When drawing the pattern that corresponds to a password, the finger can't lose contact with the screen. Every polygonal line corresponds to a sequence of digits and this sequence is, in fact, the password. The tracing of the polygonal obeys the following rules:

i. The tracing starts at some of the detached points which correspond to the digits from $$1$$ to $$9$$ (Figure 3).

ii. Each segment of the pattern must have as one of its extremes (on which we end the tracing of the segment) a point that has not been used yet.

iii. If a segment connects two points and contains a third one (its middle point), then the corresponding digit to this third point is included in the password. That does not happen if this point/digit has already been used.

iv. Every password has at least four digits.

Thus, every polygonal line is associated to a sequence of four or more digits, which appear in the password in the same order that they are visited. In Figure 1, for instance, the password is $$218369$$, if the first point visited was $$2$$. Notice how the segment connecting the points associated with $$3$$ and $$9$$ includes the points associated to digit $$6$$. If the first visited point were the $$9$$, then the password would be $$963812$$. If the first visited point were the $$6$$, then the password would be $$693812$$. In this case, the $$6$$ would be skipped, because it can't be repeated. On the other side, the polygonal line of Figure 2 is associated to a unique password.

Determine the smallest $$n$$ $$(n \geq 4)$$ such that, given any subset of $$n$$ digits from $$1$$ to $$9$$, it's possible to elaborate a password that involves exactly those digits in some order.

What I thought: Clearly $$n \geq 6$$, since for $$n=4$$ we can just choose $$1,3,7,9$$ and for $$n=5$$ we can choose $$1,3,5,7,9$$. To show that $$n=6$$, I just named points with symmetric properties by the same letters, i.e. C for Center, M for the Middle of the sides, and E for the Extremes of the sides. If we take all the triples containing only these three symmetric points and do some casework, we can show that we can make passwords with the other combinations of $$6$$ points, and we are done.

What would an elegant / formalized solution look like?

• I think tackling cases is probably the way to go, but perhaps it can be made easier to follow using symmetry. The way I'd go is divide into two 'large' cases: one where there is a full row/column in the password (which by symmetry we can assume to be, say, the top row) and the other is when no such row/column exists. In this latter case, each row and each column must contain $2$ digits of the password, and by symmetry we can suppose that for the top row those digits are either $\{1,2\}$ or $\{1,3\}$. Using symmetry can further reduce other cases down the line. Commented Nov 16, 2019 at 15:09

These types of problems usually don’t have a better attack route than pure casework. Of course, that doesn’t mean that we can’t be ordered. So, here are all the cases, excluding symmetry, for $$n=6,7,8,9$$ (edited digitally since for some reason, I forgot a few cases).