KING OF KING (combinatorics)

Probability Level 3

There is a 4 × 4 board whose squares are all white. What is the maximum number of squares that can be painted black, without forming a 1×3 horizontal or vertical strip of black squares? HINT - PHP pegion hole principle

12 9 19 11 13 10

Anshaj Shukla by Anshaj Shukla , 17, India

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Mark Hennings
Aug 17, 2018

Suppose it was possible to shade 12 12 squares without forming a 1 × 3 1\times3 shaded block. Then no row can be fully shaded, and so there must be 3 3 shaded squares per row. Since no horizontal 1 × 3 1 \times 3 shaded block exists, one of the middle two squares in each row must be unshaded. This means that the first and fourth columns are totally shaded, creating vertical 1 × 3 1 \times 3 shaded blocks. Thus it is not possible to shade 12 12 (or more) squares as required. The diagram shows that it is possible to shade 11 11 squares.

3 Helpful 0 Interesting 0 Brilliant 0 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...