A coloring problem

Coloring problems are, I think, one of the most elegant ways of visualising a problem, that might otherwise be impossible or increasingly difficult to handle.

Here I present a problem, and my coloring solution that really lifted my spirits.

The problem was something like this:

On a 9x99x9 grid, two squares are said to be neighboring if they share a common side. There are 65 bugs, each occupying a single square. At t=0, each bug moves to any of the neighboring squares of the square it was previously in. After t=0, each of the bug moves into a square that is to the right of it, or to the left of the square it is presently in. The orientation of the bug, is decided in the following way,

Suppose a bug is at the square AA at first, and at t=0, it decides to move into square CC (It could have moved to BB or II or FF as well at t=0). The head of the bug is shown by the pointer at its tip. Now it is facing east and it has two options, either to move to DD or to EE, which are to the left and right of it at this moment.

( Note that the initial position of the pointer of the bug is pointed towards BB but then it decides to go towards the right, this is because at AA it's choices are totally random, so it can actually go to any of the neighboring squares.)

We need to prove that at some point of time t, there will exist a square containing more than one bug.

Solution

First we begin by noting that by the given move scheme, the bug will be on HH or DD or EE or GG square after 2 moves, So after 2 moves, the bug will have moved one place along a diagonal in any direction.

According to that scheme here is my coloring:

We set the notation by defining that the set of all squares colored red is RR, that consisting of orange colored squares is OO, and correspondingly YY and GG for those containing yellow and green colored squares.

We note that all the bugs from RR will migrate to OO after 2 moves and vice versa, and all the bugs from YY will migrate to GG after 2 moves and vice versa.

So we have by our colouring |RR|=25, |OO|=16, |YY|=20, |GG|=20. Now by Pigeon-Hole Principle we have that there are 65 bugs and 4 kinds of coloured squares they can be put in.

So there are at least 1717 bugs all of which occupy squares of the same color.

In the next two cases we are going to talk about these 1717 bugs exclusively.

Case 1

If they are all initially in OO, then we are done, because 17 bugs in 16 squares ensures more than one bug in at least one square by the Pigeon Hole Principle.

Case 2

If all of them initially in RR, then after 2 moves all 1717 will be in OO, whence we are done again, by the Pigeon Hole Principle as in Case 1.

Another case can happen for which we make the following couple of observations.

After one move, a bug from RR or OO will always land in YY or GG.

Case

So, in the third case, we apply Pigeon Hole Principle in the following way:

We have 65 bugs and two classes of colored squares AA (consisting of the squares from RR and OO ) and BB (consisting of the squares from YY and GG ). So there must be at least 33 bugs in one of the two classes AA and BB.

If the 33 bugs are in class AA then there are a total of 33 bugs in RR and OO, so by Pigeon Hole Principle again, there is at least 17 bugs in one of them, and the first 2 cases ensure that more than one bug can be located in the same square in such cases.

If the 33 bugs are in BB then after one move they will have moved to AA, by the observation given above. So after one move we have 33 bugs in A, whence the argument immediately before this ensures more than one bug in one square.

Hence we are done!

Note An interesting thing to note from this proof is that we can achieve the goal of having more than one bug in one square after a maximum of three moves. So at t=3 we can actually ensure that there is more than one bug in some square.

That's the beauty of coloring proofs, a way to visualize.

Note by Soumava Pal
3 years, 6 months ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

wow

Chandrachur Banerjee - 3 years, 6 months ago

Log in to reply

"After one move, a bug from R R will always land in Y Y and vice versa. Similarly a bug from O O will always land in G G and vice versa."
I believe you meant,
"After one move, a bug from R R or O O will always land in Y Y or GG and vice versa."
 

Otherwise, it's clear, and simple to understand. Thanks for sharing!
Would you mind contributing to the Coloring wiki?

Ameya Daigavane - 3 years, 6 months ago

Log in to reply

@Ameya Daigavane I am so sorry, I totally missed that. I am editing it right now.

Yea I would love to contribute to it.

Soumava Pal - 3 years, 6 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...