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?

Playing around with symbols, I noticed a diamond patern kept appearing when I'd try to optimize the knights ( .'s are liar, |'s are knights):

..|..
.|.|.
|...|
.|.|.
..|..

While on a single patern, it doesn't produce a high enough percentage, repeating it does. It looks like this generates a 3:8 (37.5%) ratio:

|...|...
.|.|.|.|
..|...|.
.|.|.|.|
|...|...
.|.|.|.|
..|...|.
.|.|.|.|

This has 24 knights out of 64 people. However, 4 liars are surrounded by 3 knights only (no liars), so it appears that I need to make the dimensions large enough that some of the outside knights can be turned into liars (the extra 0.5%). At 20x20, there are 150 knights, but 148 are needed; however, there are 9 knights that have to be changed. At 40x40, I have 600, I only need 592, but 19 need to be changed.

After looking at it, 1/4 of the rows and 1/4 of the columns need 1 knight changed. If a corner knight is changed and the rows/columns are a multiple of 4, than you can subtract 1 from this because of the knight being both on a row and column.

So in a NxN square, there are (3/8)*N*N knights, with (37/100)*N*N needed, resulting in (1/200)*N*N extra. If N is a multiple of 4, then (1/2)*N-1 knights will need to be changed. So solving:
(1/200)*N*N > N/2-1
N*N > 200*N/2-200
N*N - 100*N + 200 > 0
2 <= N <= 98
So 98x98 is the smallest number of rows/columns that might work with this solution. However, that is not a multiple of 4, so I think 100x100 will be needed.

Posted by Ender on 2003-06-24 11:29:20