## Monday, December 9, 2013

### Solving Logic Riddles using AI Programming

Consider three persons, Caesar, Brutus, and Cassius. One is a king, another is a bureaucrat, and the third is a spy. The king never lies, whereas the bureaucrat always lies. The spy either lies or tells the truth. Caesar claims that Cassius is a bureaucrat, Brutus claims that Caesar is a king, Cassius claims that he is a spy.

Who is who?

## The solution, by hand

Let's start by solving this without computer assistance. Cassius cannot be a king: he is asserting that he is a spy, so if he were king, he would be lying - which is impossible for the king to do. Likewise, Brutus cannot be king, since he claims Caesar is, and so would be lying. So Caesar is the king. Brutus is then telling the truth, so he cannot be a bureaucrat (the Bureaucrat always lies). So Brutus must be a spy, and, by exclusion, Cassius is a bureaucrat (which is consistent, since Cassius is lying when asserting he is a spy). To summarize, there is a unique solution, which is:

Caesar: king.
Brutus: spy.
Cassius: bureaucrat.

## The solution, AI programming

How would you encode information about this problem in such a way as to let the computer solve it? Sure, in this case the solution was easy to obtain, but if you had 100+ rules and a lot more people it would not be easy to solve the problem by hand (think of the problem as an equation with values true/false). Logic programming, as the name suggest, provides an intuitive and natural way to express logical riddles (among other things). The following in Prolog:

First, tell the computer Caesar, Brutus, and Cassius are persons:

person(caesar).
person(brutus).
person(cassius).

Next, we would like to assign King, Liar (Bureaucrat is too long to type), and spy to these persons:

assign(K,L,S) :-
person(K), % king is a person
person(L), % liar is a person
person(S), % spy is a person
king(K,L,S), % constraints for king (to be defined later)
liar(K,L,S),  % constraints for liar
spy(K,L,S), % constraints for spy
different(K,L,S). % king, liar, and spy must be different people

We must thus defined the constraints imposed by virtue of being King, Liar, and Spy:

king(K,L,S) :- says(K,K,L,S). % Whatever King says is true
liar(K,L,S) :- \+ says(L,K,L,S). % Whatever Liar says is false (think of "\+" as "not true")
spy(_,_,_). % Anybody can be a spy

Now onto the claims that each of them make:

says(caesar,K,L,S) :- L = cassius. % Caesar says Cassius is Liar
says(brutus,K,L,S) :- K = caesar. % Brutus says Caesar is King
says(cassius,K,L,S) :- S = cassius. % Cassius says he himself is Spy

Finally, we define what "different" means:

different(X,Y,Z) :- X \= Y, X \= Z, Y \= Z. % Not the same: X,Y,Z

Now we may query Prolog to obtain all solutions:

?- assign(K,L,S).
K = caesar, <--- Caesar is King
L = cassius, <--- Liar is Cassius
S = brutus ; <--- Spy is Brutus
false. <---- This means there are no more solutions

## An interesting change

To see that this really works, consider what would happen if we don't require that there must be a unique King, Liar, and Spy. For example, one person could then be both King and Spy. This is effectively done by removing the requirement that they are all different: either remove different(K,L,S) from assign(K,L,S), or define it trivially as different(_,_,_), meaning there are no constraints).

Before executing the query, let's make some observations: a person cannot both the king and liar, assuming that person makes at least one claim. Since everybody makes a claim here, nobody can be both king and liar. So at least two people must be assigned the properties {king, liar, spy}. Clearly anybody can in principle be both king and spy, or liar and spy, since spy adds no new constraints. Furthermore, our original solution should still be part of the new solution set, since we've only removed one constraint.

How many solutions do you count? This problem is clearly more difficult than the previous one. Our query will reveal all solutions:

?- assign(K,L,S).
Solution 1:
K = S, S = caesar, <--- Caesar is both king and spy
L = cassius  <--- Cassius is liar

Solution 2 (This is the original solution):
K = caesar,
L = cassius,
S = brutus

Solution 3:
K = S, S = cassius, <--- Cassius is king and spy
L = caesar <--- Caesar is Liar

Solution 4:
K = S, S = cassius, <--- As above, Cassius is king and spy
L = brutus <--- This time Brutus is the liar (instead of Caesar)

false. <--- No more solutions.

There is an asymmetry of solutions: when Cassius is both king and spy (solution 3 and 4), the liar can be Caesar or Brutus. But when Caesar is king and spy (solution 1), only Cassius can be a liar, not Brutus. This is because Brutus asserts that Caesar is king, and liars are never allowed to tell the truth.

## The Isoperimetric Inequality

Given a rope of length L, say 100 meters, what is the largest closed area you can make?
If we try a square, each side has to be L/4 (25 meters), and we'll end up with an area of (L/4)^2 = 625 square meters. If we however try a circle, the circumference is L=2πR, where R is the radius. Thus R = L/(2π), and the area is π(L/2π)^2 = L^2/(4π) = 796 square meters, which is better than the square.

But there's plenty more shapes to try, in fact, infinitely many. So which should we pick to maximize the area?
The ancients knew the answer but could not prove it: it's the circle. The proof of this is surprisingly simple using calculus. Let L be the length of the rope, and let A be the enclosed area.

Note that for a circle, the relationship between A and L is L=2πR and A=πR^2, where R is the radius, so that:

$A&space;=&space;\pi&space;R^2&space;=&space;\pi&space;\left(\frac{L}{2\pi}\right)^2&space;=&space;\frac{L^2}{4\pi}$

Given the belief that the circle gives the largest area, we expect that for any shape,

$4\pi&space;A&space;\leq&space;L^2$

This is known as the isoperimetric inequality.

## Hurwitz's Proof

Assume that the curve (x(t),y(t)) is parametrized so that it does one full revolution when t goes from 0 to π. The arc length is defined by s = Lt/(2π). Note that when t=0, s=0, and when t=2π, s=L.

We then have:

$\int_{0}^{2\pi}&space;\left(\frac{dx}{dt}\right)^2&space;+&space;\left(\frac{dy}{dt}\right)^2&space;dt&space;=&space;\int_{0}^{2\pi}&space;\left(\frac{ds}{dt}\right)^2&space;dt&space;=&space;\int_{0}^{2\pi}&space;\left(\frac{L}{2\pi}\right)^2&space;dt&space;=&space;\frac{L^2}{2\pi}$

As for the area, we use Green's theorem:

$A&space;=&space;\int_{A}&space;dx&space;dy&space;=&space;\int_{\partial&space;A}&space;(-y)&space;dx&space;=&space;\int_{0}^{2\pi}&space;(-y)&space;\frac{dx}{dt}&space;dt$

Now, simply take the difference we want to show is always non-negative:

$L^2&space;-&space;4\pi&space;A&space;\\&space;=&space;2\pi&space;\int_0^{2\pi}&space;\left(\frac{dx}{dt}\right)^2&space;+&space;\left(\frac{dy}{dt}\right)^2&space;dt&space;-&space;2\int_{0}^{2\pi}&space;(-y)&space;dx&space;\\&space;=&space;2\pi&space;\int_0^{2\pi}&space;\left(\frac{dx}{dt}\right)^2&space;+&space;\left(\frac{dy}{dt}\right)^2&space;+&space;2y\frac{dx}{dt}&space;dt&space;\\&space;=&space;2\pi&space;\int_0^{2\pi}&space;\left(\frac{dx}{dt}&space;+&space;y\right)^2&space;-&space;y^2&space;+&space;\left(\frac{dy}{dt}\right)^2&space;dt&space;\\&space;=&space;2\pi&space;\int_0^{2\pi}&space;\left(\frac{dx}{dt}&space;+&space;y\right)^2&space;+&space;2\pi&space;\int_0^{2\pi}&space;\left(\frac{dy}{dt}\right)^2&space;-&space;y^2&space;dt$

We want to conclude that this expression is non-negative for any curve. The first integral is clearly non-negative, since its integrand is a square. As for the second integral, the result is not obvious until one consider its Fourier series (this is called Wirtinger's inequality):

$y(t)&space;=&space;\frac{a_0}{2}&space;+&space;\sum&space;(a_n&space;\sin(nt)&space;+&space;b_n&space;\cos(nt))$

As we will see soon, for this to work, we must place the curve in coordinates such that:

$a_0&space;=&space;\frac{1}{\pi}&space;\int_0^{2\pi}&space;y(t)&space;dt&space;=&space;0$

This can always be done, as the placement of the curve is arbitrary: if the integral of y(t) is V, then the translated function y(t)-V/(2π) will have integral 0.

Next, differentiate y(t) to obtain:

$\frac{dy}{dt}&space;=&space;\sum&space;(na_n&space;\cos(nt)&space;-&space;nb_n&space;\sin(nt))$

Then, by Parseval's identity:

$\int_0^{2\pi}&space;\left(\frac{dy}{dt}\right)^2&space;dt&space;=&space;\sum&space;n^2(a_n^2+b_n^2)&space;\geq&space;\sum&space;(a_n^2&space;+&space;b_n^2)&space;=&space;\int_0^{2\pi}&space;y(t)^2&space;dt$

which concludes the proof. (The requirement a0=0 is to ensure that the last inequality holds for n=0).
The inequality thus obtained is known as the isoperimetric inequality:

$4\pi&space;A&space;\leq&space;L^2$

## Only the Circle Yields Maximum Area

As we saw in the beginning, the circle turns the inequality into an equality, thus yielding the maximum possible area. But this still leaves open the possibility that other shapes may be equally good. We can show that only the circle yields max area by considering when the inequality becomes an equality: precisely when the two integrals are zero.

Starting with the second integral, the inequality was obtained from comparing the square sums after applying Parseval's identity. To have equality, the terms in those sums must be 0 except when n=1, which means that

$y(t)&space;=&space;a_1&space;\sin(t)&space;+&space;b_1&space;\cos(t)&space;=&space;C&space;\sin(t+\alpha)$

The first integral must also be zero, which means that

$\frac{dx}{dt}&space;=&space;-y(t)$

Integrating, we get

$x(t)&space;=&space;C&space;\cos(t+\alpha)&space;+&space;D$

So indeed we must have a circle centered at (D,0).

The fact that the circle must be centered around y=0 is due to our previous choice of fixing the integral of y(t) over one period. The center of mass must be such that equally much is positive and negative, which for a circle clearly means fixing it around y=0.

## How general is this proof?

The use of Green's theorem requires that we deal with a curve (x(t),y(t)) that has a continuous derivative except in finitely many points (piecewise smooth). Piecewise smoothness is also enough to ensure that the Fourier series can be differentiated term by term. Any area you can physically construct will certainly satisfy these conditions, as will anything you draw with a pen, since it is impossible to create or draw infinitely many edged points.