Coloring a grid

[BMAD]

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?

[CaptainEd]

 

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 August 21, 2017 by CaptainEd
Check out spoiler first

[CaptainEd]

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.

[CBG]

I did it in 3 

[bonanova]

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

I did it in 3 

Hi CBG, welcome to the Den.

Care to share your solution?

[bonanova]

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
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.

 

[CaptainEd]

Nice compact proof, Bonanova, thank you!