Kazaam the wizard lives in the kingdom of Liars and Knights. He is planning a grand illusion for the King's golden jubilee, in which he will make hundreds of people appear to turn into gold.

Kazaam plans to lay out markers on the parade ground for the people in the illusion to stand on. For the illusion to work, the markers must be laid out in a perfectly square grid, with an even number of rows and columns. Every marker must have a liar or knight standing on it, arranged such that they each can say that every person standing next to them in the same row or the same column is of the opposite persuasion (i.e. every knight can say that all adjacent markers have a liar standing on it, and vice versa).

The last detail required for Kazaam's spell to work is that at least 37% of the people in the illusion must be knights. What is the minimum number of rows and columns needed to accommodate this ratio of knights to liars, keeping in mind Kazaam wants at least 100 people in the illusion?

(In reply to Please post more about Solution by Ender)

Ender, sorry to keep you waiting. Yes, a picture helps immensely with this puzzle. Unfortunately, a 50x50 grid is a little unwieldy in this format, so I will explain with a 10x10 grid.

One early solution posted was to repeat a pattern such as:

l...
.l.l
..l.
.l.l

where a period (“.”) represents a liar, while an “l” represents a knight. This is almost correct, but if you look at a 10x10 grid of this you get:

l...l...l.
.l.l.l.l.l
..l...l...
.l.l.l.l.l
l...l...l.
.l.l.l.l.l
..l...l...
.l.l.l.l.l
l...l...l.
.l.l.l.l.l

Obviously, there are a few liars on the bottom and right-hand edges that are surrounded by knights, which violates the requirements of this problem. Instead, lets start with a pure checkerboard pattern:

l.l.l.l.l.
.l.l.l.l.l
l.l.l.l.l.
.l.l.l.l.l
l.l.l.l.l.
.l.l.l.l.l
l.l.l.l.l.
.l.l.l.l.l
l.l.l.l.l.
.l.l.l.l.l

If you count the diagonals of l’s that travel from the upper right corner to the lower left, there are ten of them (or n diagonals for an nxn grid), each with an odd number of l’s. To generate a pattern where no liar is completely surrounded by knights, we will change every other diagonal of l’s, removing every other l, always starting by removing an l from the edge of the grid. The resulting pattern looks like:

l...l...l.
.l.l.l.l..
..l...l.l.
.l.l.l...l
l...l.l.l.
.l.l...l..
..l.l.l.l.
.l...l...l
l.l.l.l.l.
...l...l..

Thus from the initial n²/2 l’s of a pure checkerboard, we subtract one fourth of them (n²/8) when we subtract every other l from every other diagonal, and we subtract an addition n/4 l’s when we force the altered diagonals to start and end with a liar (“.”). The n/4 may not be obvious at first blush, but try this with grids of 14x14 etc. and this term is confirmed.

Sorry I didn’t submit a diagram with the original solution.

Posted by Bryan on 2003-07-14 06:40:30