Riddler Express
Duke Leto Atreides knows for a fact that there are not one, but two traitors within his royal household. The suspects are Lady Jessica, Dr. Wellington Yueh, Gurney Halleck and Duncan Idaho. Leto’s advisor, Thufir Hawat, will assist him in questioning the four suspects. Anyone who is a traitor will tell a lie, while anyone who is not a traitor will tell the truth.
Upon interrogation, Jessica says that she is not the traitor, while Wellington similarly says that he is not the traitor. Gurney says that Jessica or Wellington is a traitor. Finally, Duncan says that Jessica or Gurney is a traitor. (Thufir, being the logician that he is, notes that when someone says thing A is true or thing B is true, both A and B can technically be true.)
After playing back the interrogations in his mind, Thufir is ready to report the name of one of the traitors to the duke. Whose name does he report?
Computational Solution
Let be the boolean variables indicating whether or not Jessica, Wellington, Gurney and Duncan are traitors or not. The statements made by them and the fact that there are traitors reduce to the following set of logical propositions:
- If
- If
- If
- If
Here is the Python code in Z3 to check if the propositions above can be satisfied:
from z3 import *
j = Bool('j')
w = Bool('w')
g = Bool('g')
d = Bool('d')
s = Solver()
s.add(Implies(g,Not(Or(j,w))))
s.add(Implies(Not(g),Or(j,w)))
s.add(Implies(d,Not(Or(j,g))))
s.add(Implies(Not(d),Or(j,g)))
s.add(Or([And(j,w), And(j,g), And(j,d), And(w,g), And(w,d), And(g,d)]))
while s.check() == sat:
m = s.model()
print(m)
s.add(Or(j != m[j], g != m[g], w != m[w], d != m[d]))
We see that there are two cases where the propositions above are satisfied:
[g = False, j = True, w = True, d = False]
[w = True, g = False, j = False, d = True]
In both the cases, Wellington is one of the traitors, which means that Thufir reported as one of the traitors to the Duke.
Riddler Classic
Suppose you have an equilateral triangle. You pick three random points, one along each of its three edges, uniformly along the length of each edge — that is, each point along each edge has the same probability of being selected.
With those three randomly selected points, you can form a new triangle inside the original one. What is the probability that the center of the larger triangle also lies inside the smaller one?
Computational Solution
The logic for determining if a point is inside or outside a given triangle is described here.
The Python code for implementing the above logic is given below:
import numpy as np
from math import sqrt
from random import random
triangle = [np.array([-.5,-sqrt(3)/6]),
np.array([.5,-sqrt(3)/6]),
np.array([0, sqrt(3)/3])]
center = np.array([0,0])
def exp_percent_center_inside(triangle, center, runs = 100000):
det = np.cross
c=0
for _ in range(runs):
[A, B, C], v = triangle, center
D, E, F = A + random()*(B - A), B + random()*(C - B), C + random()*(A - C)
v0, v1, v2 = D, E - D, F - D
a = (det(v, v2) - det(v0, v2))/det(v1, v2)
b = -((det(v, v1) - det(v0, v1))/det(v1, v2))
if a > 0 and b > 0 and a + b < 1:
c += 1
return c/runs
print(exp_percent_center_inside(triangle, center))
From the simulation, we see that the probability the center of the equilateral triangle lies inside the smaller random triangle is .