BrainDen.com - Brain Teasers

Question

You are to color a 5x5 square grid using green, red, blue, and yellow.  You must color it in a way where a square cannot share a side or a vertex with another square of the same color.  What is the fewest amount of yellow squares needed to color this appropriately?

Now instead lets divide each square diagonally from the top left corner to the bottom right corner.  What is the fewest amount of yellow colorings needed?

Recommended Posts

• 0

I did it in 3 Share on other sites

• 0
On 8/22/2017 at 2:45 PM, CBG said:

I did it in 3 Hi CBG, welcome to the Den.

Share on other sites

• 0

Proof that CaptainEd's answer is minimal.

Spoiler

Start with any interior 2x2 region and color the 4 squares differently.

Without loss of generality,

x x x x x
x x
2 3 x
x x
1 4 x
x x x x x
x x x x x

Square(3,2), to the left of color 1 can only be 3 or 4

Case 1: color(3,2) = 3

Spoiler

This choice forces the coloring of 15 squares:

x 3 1 4 x
x 4 2 3 x
x
3 1 4 x
x 4 2 3 x
x 3 1 4 x

where all the x squares receive (only) colors 1 or 2.

There are already 5 squares colored 3 and 4.
Colors 1 and 2 must each occur at least 4 more times,
making at least 7 squares with oolor 1
and at least 6 squares with color 2.

Case 2: color(3,2) = 4

Spoiler

This choice forces only one other square

x x x x x
x 3 2 3 x
x
4 1 4 x
x x x x x
x x x x x

Square (4,2) can only be color 2 or color 3.

Case 2a: color(4,2) = 2

Spoiler

This choice forces the color of 15 squares:

x x x x x
2 3 2 3 2
1 4 1 4 1
3
2 3 2 3
x x x x x

where all the x squares receive (only) colors 1 or 4.

There are already 5 squares colored 2 and 3
Colors 1 and 4 must each occur at least 4 more times,
making at least 7 squares with color 1
and at least 6 squares with color 4.

Case 2b: color(4,2) = 3

Spoiler

This choice forces the color of 9 squares:

x x x x x
x
3 2 3 x
x 4 1 4 x
3 2 3 x
x x x x x

where all the x squares receive (only) colors 1, 2 or 4.

Colors 1, 2 and 4 must each occur at least 4 more times,
making at least 5 squares with color 1,
and at least 6 squares with colors 2 and 4.

Solution: There are exactly 4 squares with color 3.

Make color 3 Yellow

With hindsight,

Spoiler

Squares (2,2) (2,4) (4,2) and (4,4)collectively touch ALL the other squares and and do not touch each other. So one solution is 4 squares. Enumeration of all cases proves that 4 is minimal.

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account. ×   Pasted as rich text.   Paste as plain text instead

Only 75 emoji are allowed.

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.