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?

A first look at the setup of the problem, with each person in rows and columns forming a perfect square, would indicate that, for two people A and B, if A is next to B, B is next to A.
Suppose A is a knight. For him to say that B is of the opposite persuasion (a liar), B must indeed be a liar since A always tells the truth.
For B to say that A is of the opposite persuasion (a knight), however, A must be a liar, so that B will untruthfully say that he is a knight.
From this, it seems to be impossible, since each knight must be surrounded by all liars, and each liar must be surrounded by all liars, therefore there can be no knights in the arrangement.

That was my first impression.

Since the problem states, however, that each person will say that all adjacent persons are of the opposite persuasion, then a liar surrounded by, say, all knights and one liar, or anything but all knights, will be able to say that he is surrounded by knights and still be lying.

Therefore, any arrangement in which no two knights are next to each other, and each liar is next to at least one other liar, will work.

Since we need at least 100 people, the smallest could be 10x10. Of these 100 people, at least 37 must be knights.

I would guess that knights should be placed on every third diagonal, so as to fit as many as possible with none adjacent to each other. There are two distinct ways to do this:

K L L K L L K L L K


L L K L L K L L K L


L K L L K L L K L L


K L L K L L K L L K


L L K L L K L L K L


L K L L K L L K L L


K L L K L L K L L K


L L K L L K L L K L


L K L L K L L K L L


K L L K L L K L L K  K=34





L K L L K L L K L L


K L L K L L K L L K


L L K L L K L L K L


L K L L K L L K L L


K L L K L L K L L K


L L K L L K L L K L


L K L L K L L K L L


K L L K L L K L L K


L L K L L K L L K L


L K L L K L L K L L  K=33

These arrangements give us 34 and 33 knights out of 100, respectively, which is not enough.
So, there must be another way to arrange them, or the grid must be yet bigger.

That's all I have for now.

Posted by DJ on 2003-06-24 10:49:45