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?

L L K L K L L K L L 
L K L L L K L L L K 
K L K L K L K L K L 
L L L K L L L K L L 
K L K L K L K L K L 
L K L L L K L L L K 
L L K L K L K L K L 
K L L K L L L K L L 
L L K L K L K L K L 
L K L L L K L L L K

The above pattern permits each Knight and Liar to make the declaration that they are surrounded by their opposite persuasion. The percentage of 10-by-10 markers (100 participants, 35 Knights) upon the parade ground, yet, does not allow for the requirement of at least 37% Knights.
By keeping to the pattern, adding two columns and two rows at a time (to keep the number of columns and rows even for the illusion to work), the percentage of Knights primarily increases (dropping a little every fourth addition of rows and columns, and again, due to changing 2 Knights into Liars to remove the isolated Liars that are created in the top-right and bottom-left corners at every fourth column and row added beginning at 14x14 -- this change in pattern is only if the parade ground were to be, e.g., 14x14, otherwise there is no need to make the change). At 48-by-48 markers (2304 participants, 853 Knights), the required percentage is reached.

ROWS x 
COLUMNS  KNIGHTS   PERCENT
10 x 10    35      35
12 x 12    51     ~35.4167
14 x 14    69     ~36.2041
16 x 16    93     ~36.3281
18 x 18   117     ~36.1111
20 x 20   145      36.25
22 x 22   175     ~36.1570
24 x 24   211     ~36.6319
26 x 26   247     ~36.5385
28 x 28   287     ~36.6071
30 x 30   329     ~36.5556
32 x 32   377     ~36.8164
34 x 34   425     ~36.7647
36 x 36   477     ~36.8056
38 x 38   531     ~36.7729
40 x 40   591     ~36.9375
42 x 42   651     ~36.9048
44 x 44   715     ~36.9318
46 x 46   781     ~36.9093
48 x 48   853     ~37.0226 <--
50 x 50   925      37

Edited on January 23, 2008, 10:21 am

Posted by Dej Mar on 2008-01-23 03:18:58