|
If the only restriction were for the knights to be able to say all adjoining markers contain people of the opposite persuasion (i.e. liars), then the entire illusion could be filled with alternating liars and knights like the light and dark squares of a checkerboard, and there could be up to 50% knights. But when a liar says all adjoining markers contain people of the opposite persuasion, for this statement to be a lie at least one adjoining marker needs to have another liar on it.
Consider a vast checkerboard with black squares representing knights, and ignore the edges of the board for now. If every other diagonal line of knights were replaced with an alternating KLKLKL diagonal line, the result would be a pattern that allowed both liars and knights to make the required statement, and this pattern would also optimize the ratio of knights to liars. This pattern allows up to 3/8 (37.5%) of the population to be knights.
When the edges of the checkerboard are taken into account, we have to make sure that the KLKLKL diagonal lines end with a liar at each end, otherwise a liar at the end of an adjacent all-liar diagonal line will have knights on all sides of him, thus making him unable to lie that all adjacent cells contain people of the opposite persuasion. For an NxN grid where N is even (as stated in the problem), there are N black diagonals with an odd number of cells. N/2 of these will be the KLKLKL lines, and for these lines to have a liar at each end requires an average of one extra liar for every two such lines, or N/4 additional liars. In other words, the equation for the maximum number of knights in the wizard's illusion is Kmax=3/8 * N² – N/4
Note: the exception to this rule is for N=4, where 6 knights can be safely housed using a deviant pattern. This solution is inadequate for Kazaam's illusion, since he wants hundreds of people in it. For Kmax=0.37, N=50. Thus the minimum number of rows and columns in Kazzam's illusion is 50. 2500 liars and knights (at least!) will be required for this illusion. As the number of rows and columns approches infinity, K/L approaches 0.375.
|
