Jump to content
BrainDen.com - Brain Teasers
  • 0
BMAD

Coloring a grid

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?

Share this post


Link to post
Share on other sites

6 answers to this question

  • 1
 

part A: I can do it in 4 Y

R B R B R

G Y G Y G

R B R B R

G Y G Y G

R B R B R

 

 

 

Edited by CaptainEd
Check out spoiler first

Share this post


Link to post
Share on other sites
  • 0

Part b

no way

make a 2x2 square of four squares, cut each in half from northwest corner to southeast corner. The center vertex of the 2x2 is shared by six triangles, so you need at least six colors.

Share this post


Link to post
Share on other sites
  • 0
On 8/22/2017 at 2:45 PM, CBG said:

I did it in 3 :rolleyes:

Hi CBG, welcome to the Den.

Care to share your solution?

Share this post


Link to post
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.

 

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now


  • Recently Browsing   0 members

    No registered users viewing this page.

×