3
$\begingroup$

In an infinite plane, all segments of the grid are colored red or blue. We also know that for all points connected by a blue segment, there is a unique path between them made of red segments.

Prove that I can always find a path of red segments with length greater than or equal to 2022.

$\endgroup$

2 Answers 2

7
$\begingroup$

I assume we are talking about an infinite lattice with edges connecting orthogonally adjacent points (please correct me if I'm wrong).

If that is the case, I think this would work

First of all notice that from any point in the plane we can get to each orthogonally adjacent point using red segments (either directly if they are connected by a red segment or by the uniquely defined path if they are connected by a blue).

By a recursive procedure this means that we can get from any point in the plane to any other point in the plane using only red segments. In particular, we could get from the origin, say, to the point (2022, 0) using only red segments. Notice, that if we revisit any point along the way, this will create a loop and we can just remove all loops to yield a red path with no self-intersection. Such a path would have length 2022, at least, but it's clear from the argument that we can find a red path which is arbitrarily long.

For those interested, an example of such a configuration would be the following

A red path which begins at the origin and spirals outwards visiting every lattice point e.g, (0,0) -> (0,1) -> (1,1) -> (1,0) -> (1,-1) -> (0,-1) -> (-1,-1) ->... with every other edge coloured blue.

$\endgroup$
9
  • 1
    $\begingroup$ Extra kudos for proving that such a configuration can exist. $\endgroup$
    – Penguino
    Oct 11, 2022 at 20:27
  • $\begingroup$ @Penguino Thank you, I had to think about it for a while. $\endgroup$
    – hexomino
    Oct 11, 2022 at 20:32
  • 2
    $\begingroup$ Any two points directly connected by a blue edge have at least one red path between them, so the subgraph of red edges is a connected spanning graph. This red path is unique, so this subgraph is a spanning tree, right? So that's another way to prove your conclusion. $\endgroup$
    – Rosie F
    Oct 12, 2022 at 5:46
  • 1
    $\begingroup$ Your solution works no matter whether the path is unique, right? $\endgroup$
    – xd y
    Oct 12, 2022 at 7:32
  • 1
    $\begingroup$ @xdy yes, I don't think the uniqueness restriction matters $\endgroup$
    – hexomino
    Oct 12, 2022 at 11:08
0
$\begingroup$

On a blue path part of a region, any two adjacent points ($p_n$ to $p_m$) lead to a unique red path from $p_n$ to $p_m$, so there can't be multiple same-color paths from $p_n$ to $p_m$. This means any (adjacent or not) $p_n$ and $p_m$ points have a unique red path between them too. This means red segments behave the same as blue ones as long as the latter exist.

A point can't be part of a path of the same color in all four directions either, because it would make an opposite-color path to this point impossible. If a region has multiple opposite-color regions connected to it, these regions must be connected with the same color too.

That means a region is always surrounded by a larger one or is united by the other same-color regions, making it larger than 2022 units eventually.

$\endgroup$
6
  • $\begingroup$ It's the "segments" that are coloured red or blue; that is to say the edges between lattice points. The paths go along these edges from one lattice point to another. $\endgroup$ Oct 18, 2022 at 20:48
  • $\begingroup$ Edited my answer. I'd misunderstood it because when I read the word "segment", it sounded like two-dimensional parts to me for some reason. $\endgroup$
    – Nautilus
    Oct 23, 2022 at 14:29
  • $\begingroup$ It is unclear to me what you mean with blue points and red points. The lattice points are not coloured, and a points four edge can be any mix of colours. And "points can ovelap" also has no clear meaning. There can be branches, for example you could make all vertical edges and the x-axis edges red, and the remaining horizontal edges blue. This clearly satisfies the unique red path property and has branches. There are other valid arrangments in which there are blue loops. $\endgroup$ Oct 24, 2022 at 9:14
  • $\begingroup$ As long as blue segments exist, red segments behave the same way as blue ones. If there's no blue, all the points will be red, because they're connected to red segments from all four directions. If blue exists, a point can't be connected to same-color segments from all directions, making all the points both red and blue. $\endgroup$
    – Nautilus
    Oct 24, 2022 at 9:44
  • $\begingroup$ There are arrangements that contain blue edges and points with four red edges, such as the example in my previous comment. You still have not explained how you are colouring the points. $\endgroup$ Oct 24, 2022 at 9:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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