8
$\begingroup$

You live on an infinite plane with a house at each integer lattice point. The plane is inhabited by horrible worms who can only walk in straight lines. You want to paint the houses so that all the worms constantly get lost, but you don't get lost yourself. You have an unlimited number of colors. Can you do it?

To put it mathematically: can you paint each house a color so that

  • For each straight line intersecting at least two houses, the sequence of house colors on that line is periodic --
  • But the overall coloring is not periodic (i.e. not equal to any translation of itself)?

Good luck!

Improve this question
$\endgroup$
6
  • $\begingroup$ Just to make sure I understood the problem: you don't get lost because you know the pattern strategy, while the worms don't know it so they can't find their path? $\endgroup$
    – leoll2
    Commented Apr 7, 2015 at 11:44
  • $\begingroup$ @leoll2 The idea is, each worm can only travel in a straight line. If a worm's line has a periodic sequence of colors, then the worm can never figure out where along that line it is. Imagine living on an infinite line of houses with colors red, blue, red, blue, red, blue, red, blue, ... -- you could never figure out where you are without some outside help. $\endgroup$
    – Lopsy
    Commented Apr 7, 2015 at 11:48
  • $\begingroup$ Worms can move along diagonal lines (like bisector), right? $\endgroup$
    – leoll2
    Commented Apr 7, 2015 at 11:53
  • 1
    $\begingroup$ I'm not clear how knowing the colour-filling-strategy lets me work out where I am. If the worms are confused about their location then won't I be confused about my location too? $\endgroup$
    – A E
    Commented Apr 8, 2015 at 8:47
  • 1
    $\begingroup$ It seems to me that the human painter has an advantage over the worms, in that he can travel along any path he chooses, while the worms can only go in a straight line. This can enable some strategies like "go forward one, then turn right, then go forward. If the colors you passed were red-orange-yellow, you are at coordinates (X,Y)". Worms can't turn right, so they can't use this method. $\endgroup$
    – Kevin
    Commented Apr 9, 2015 at 18:00

3 Answers 3

Reset to default
7
$\begingroup$

I believe one such house painting scheme is the Chair Tiling.

Gotta love them tilings

The picture gives a good idea of how to construct a chair tiling of arbitrary size (rotated 45 degrees).
One square on the diagram represents the color of a house at a specific lattice point. The chair tiling is nonperiodic - that is, it is not equal to any translation of itself. This way of painting the houses in the lattice has the property that any infinite line that intersects with at least 2 of the houses will have a periodic pattern. Why? The chair tiling is limitperiodic - That is, it is constructed from a combination of countably many finite tile sets. This is easier to see on a larger diagram:

enter image description here

This is the same tiling. You can begin to see patterns - subsequences that seem to repeat. However, the overall tiling is still nonperiodic.

The Tilings Encyclopedia states that "the chair tiling is the union of a countable set of fully periodic tile sets $L_1$, $L_2$, $L_3$..., where each $L_i$ possesses period vectors of length $2 × 2^i$". Hence, any line drawn will have the colors of the houses repeat after it has intersected $2^i$ houses, for some $i$ (obviously, $2$ is divisible by $2^i$ for all $i\ge1$).

Improve this answer
$\endgroup$
2
  • 3
    $\begingroup$ Just wondering one thing. Assuming I know the layout, but the plane is infinite.. how the hell do I myself know where I am, let alone where I'm going? $\endgroup$
    – Tim Couwelier
    Commented Apr 7, 2015 at 16:01
  • 1
    $\begingroup$ xnor's answer was the intended one, but this is surprising and pretty enough that I'm totally greenchecking it. $\endgroup$
    – Lopsy
    Commented Apr 9, 2015 at 19:22
3
$\begingroup$

Another cheap just-do-it proof! Just list the constraints and crank out a construction. No cleverness required.

We need to satisfy the following constraints:

  • Each line is periodic
  • Each displacement does not produce a 2D periodic tiling.

There are countably many lines and countably many displacements, so that's countably many constraint total. Enumerate them. We will satisfy them in turn by coloring cells in one of two colors.

For a displacement, ruin its potential periodicity by coloring two cells at that displacement different colors.

For each line constraint, color all its uncolored cells to make it periodic. We can do this because only a finite number of its cells have been colored, allowing us to repeat that pattern. (The number is finite because each previous line intersects this one at most once, and each displacement constrains colors only two cells.)

One a constraint is met, no further coloring of uncolored cells can ruin it, so all constraints will be satisfied.

Improve this answer
$\endgroup$
7
  • $\begingroup$ When you ruin the periodicity, doesn't that allow the worms to orientate themselves? $\endgroup$
    – Lawrence
    Commented Apr 8, 2015 at 6:15
  • $\begingroup$ @Lawrence The lines will still be made periodic over the cells colored to ruin the non-tilingness. $\endgroup$
    – xnor
    Commented Apr 8, 2015 at 6:58
  • $\begingroup$ Since the cells are on the lines, if you restore / create periodicity to the line that includes the two cells, doesn't this undo the effect of initially colouring the two cells? Perhaps you could give a concrete example - I don't see how the line can be both periodic and non-periodic at the same time. $\endgroup$
    – Lawrence
    Commented Apr 8, 2015 at 12:35
  • $\begingroup$ This was the intended solution, nice job! (But for meaningless internet points purposes, I have to give the green check to Tryth for his cool pictures.) $\endgroup$
    – Lopsy
    Commented Apr 9, 2015 at 19:31
  • $\begingroup$ @xnor In the first step, you need to ruin the periodicity for all periods. Consider the case of a period of 2 on a displacement along the x-axis, so we need only consider a single line. Then the colouring in your step 1 of two cells for every two cells fills the whole line, leaving no space for the second step to make it periodic. How are the worms confused? $\endgroup$
    – Lawrence
    Commented Apr 10, 2015 at 2:41
1
$\begingroup$

For ease of reference, call each integer lattice point a house. Without loss of generality, let the lattice in the question be the set of all points with integer coordinates on an $XY$ plane.

Given a house $H$, let its colour be given by a function $C(H)$. We call $C$ a colouring.

We call a vector a house vector if the vector is parallel to a line that contains at least two houses.

The first constraint requires every straight line passing through at least 2 houses to be periodic. That is, given a house $H$ and a house vector $v$ whose magnitude is the period associated with the line containing $H$ and parallel to $v$, then for any integer $k$, $H + kv$ is also a house and has the same colour as $H$. $$\forall k \in Z: C(H) = C(H + kv) \tag{1} \label{1}$$

The second constraint in the question requires $C$ to be non-periodic. This implies the existence of a non-empty set $F$ of houses such that there is no house vector $u$ for which $C$ remains invariant when translated any non-zero distance in the direction of $u$. The following shows by contradiction that $F$ does not exist.

Suppose we had a colouring $C$ that contained such a set $F$.

Select any house vector $v$.

For each house $F_i$ in $F$, let $p_i$ be the period of the line passing through $F_i$ and parallel to $v$.

Let $p$ be the LCM of all the $p_i$ and let $u$ be the vector parallel to $v$ and with magnitude $p$. By equation $\eqref{1}$, since $p$ is a multiple of each $p_i$, the colour of each $F_i$ repeats periodically in the direction of $u$. $$\forall k \in Z: C(F_i) = C(F_i + ku) \tag{2} \label{2}$$

This means that the colour pattern of the whole set $F$ is periodic with period $p$ in the direction of $u$, contradicting the second condition. Therefore $F$ doesn't exist.

So the houses cannot be painted as proposed.

Improve this answer
$\endgroup$
10
  • $\begingroup$ I know xnor and Tryth have provided positive answers while this is a negative answer. Perhaps I have misunderstood something in the question - hopefully this answer will provide enough reasoning for someone to point out what it is. $\endgroup$
    – Lawrence
    Commented Apr 9, 2015 at 11:00
  • $\begingroup$ Your Worm Paths Lemma can't possibly be right, because you can make a counterexample ala xnor's proof. $\endgroup$
    – Lopsy
    Commented Apr 9, 2015 at 19:30
  • $\begingroup$ @Lopsy The main observation I used is that if something recurs at displacements of $p$, it also recurs at displacements of any multiple of $p$. Xnor's approach is to create a feature, then make the paths periodic. But making the paths periodic then also makes the feature periodic, which defeats the purpose of the feature. Alternatively, xnor's first step makes it impossible to colour the remainder in a periodic fashion. $\endgroup$
    – Lawrence
    Commented Apr 9, 2015 at 23:01
  • $\begingroup$ @Lopsy Have a look at <en.wikipedia.org/wiki/Aperiodic_tiling>. The 1D tiling example illustrates the problem quite well: if you have a string aa..aaabaaa..aa ('a' represents a 1-space tile and 'b' represents a 2-space tile), then you get a non-periodic tiling you can use for orientation. However, your worms don't get confused. If you repeat the 'b' periodically, you confuse your worms but lose the ability to use 'b' for orientation. It seems that Tryth's tiling is like the former and xnor's like the latter. $\endgroup$
    – Lawrence
    Commented Apr 10, 2015 at 2:33
  • $\begingroup$ In your proof of the lemma, when you deduce that $L$ is periodic, you seem to assume that hat-x and hat-y are the same for every row and column. This need not be true. $\endgroup$
    – Lopsy
    Commented Apr 10, 2015 at 11:36

Not the answer you're looking for? Browse other questions tagged or ask your own question.