Puzzle #186: 4×4 Grid

This is another wonderful puzzle from A Moscow Math Circle, Week by week problem Sets by Sergey Dorichenko.

There are two parts to the problem:

(a) Place seven stars in a 4×4 grid so that, no matter which two rows and which two columns are erased, at least one star will remain.

(b) Prove that if six stars are placed in a 4×4 grid, one can always erase all of them by erasing two rows and two columns.

As always, please send your answers as comments within the blog (preferred), or send an e-mail to alokgoyal_2001@yahoo.com. Please do share the puzzle with others if you like, and please also send puzzles that you have come across that you think I can share in this blog.

Happy Eid to everyone!

 

This entry was posted in Puzzles and tagged , . Bookmark the permalink.

One Response to Puzzle #186: 4×4 Grid

  1. On part 2,
    When 6 stars are placed in 4 rows, either at least one row has at least 3 stars or at least two has two stars each. So you can always find 2 rows with 4 stars. Pick these two rows and remove them. Now 2 stars remain and we can remove two columns. So, we can always remove all stars by removing two rows and two columns.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s