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 re(2): Solution? by Ender)

The diamond pattern is 4x4, so allowing partial repeats of the pattern gives different results. Note that no knights need to change on odd numbers. I believe 49 is the smallest number using this diamond pattern (discounting n < 4, since the statement requires n > 10).

These all assume this is the top left corner, with the pattern repeated down and right as needed:
|...
.|.|
..|.
.|.|
On ones where the knights change, I made the second to bottom row and second to last column entirely liars.

If (n mod 4 = 0):
-----------------
Number of knights minus changed knights:
(3/8*n*n) - ((1/2)*n-1) = 1/8*(3n^2-4n+8)

Solving inequality (number of knights >= 37%):
1/8*(3n^2-4n+8) >= 37/100*n^2
n^2 - 100n + 200 >= 0
2 <= n <= 98
n = 100,104,108,...


If (n mod 4 = 1):
-----------------
Number of knights in n-1 square plus knights in columns-1 plus knights in rows-1 plus corner knight:
(3/8*(n-1)*(n-1)) + ((1/4)*(n-1)) + ((1/4)*(n-1)) + 1
= 1/8( 3*n^2 - 2*n + 7 )

Solving inequality:
1/8( 3n^2 - 2n + 7 ) >= 37/100*n^2
n^2 - 50n + 175 >= 0
3 <= n <= 47
n = 49,53,57,...


If (n mod 4 = 2):
-----------------
Number of knights minus changed knights:
(3/8*(n^2) + 1/2) - (n/2) = 1/8*(3n^2 - 4n + 4)

Solving inequality:
1/8*(3n^2 - 4n + 4) >= 37/100*n^2
n^2 - 100n + 100 >= 0
1 <= n <= 99
n = 102,106,110,...


If (n mod 4 = 3):
-----------------
Number of knights in n+1 square minus knights in columns+1 minus knights in rows+1 plus knight in corner (was taken out twice - by rows and columns):
3/8*(n+1)*(n+1)- (1/2)(n+1) - (1/2)(n+1) + 1
= 1/8*(3n^2 - 2n + 3)

Solving inequality:
1/8*(3n^2 - 2n + 3) >= 37/100*n^2
n^2 - 50n + 75 >= 0
1 <= n <= 49
n = 51,55,59,...

Posted by Ender on 2003-06-25 08:30:18