Skip to content

Instantly share code, notes, and snippets.

@hectorpefo
Created September 21, 2016 17:39
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save hectorpefo/f8f856fb9ca334e0a4519187d5311b6b to your computer and use it in GitHub Desktop.
Save hectorpefo/f8f856fb9ca334e0a4519187d5311b6b to your computer and use it in GitHub Desktop.
Testimony = [[0,[0,2,5,6,7]],[0,[1,3,4,6,7]],[0,[1,2,3,4,6]],[0,[0,1,3,4,6]],\
[1,[0,2,4,5,7]],[1,[1,3,4,5,6]],[1,[0,2,3,5,7]],[1,[0,1,2,5,7]]]
for liars in range(0,255):
success = 1
for witness in Testimony:
if sum([(liars&2**i)//2**i for i in witness[1]])%2 == witness[0]:
success = 0
if success: print("{0:08b}".format(liars))
@hectorpefo
Copy link
Author

The puzzle:

You are interrogating eight people on a very odd island. They are situated at the eight vertices of a large cube (and so 4 of them are above ground). The people are numbered in such a way that #1, #2, #3 and #4 are at the four top corners of the cube, in clockwise order, and #5, #6, #7 and #8 are on the four bottom corners of the cube, with #5 directly below #1, and #6 directly below #2, and so on. From each person’s point of view, there are three people adjacent along edges of the cube, and the other four are farther away. Each person individually counts the number of liars among the four who are farther away from themself.

Persons #1, #2, #5 and #7 tell you that their counts are odd, and the other four tell you that their counts are even. What, if anything, can you deduce?

In the program, Testimony is coded as odd (0) or even (1), and the list of nodes (0 to 7) that must be odd or even given that testimony (see Mark's reply to laura in the Numberplay comments). The possibilities ("liars") are binary representations of non-liar (0) and liar (1). The output is "00111010", which is the binary numeral representing the answer, with the least significant digit (person #1) on the right.

@hectorpefo
Copy link
Author

hectorpefo commented Sep 22, 2016

Some extensions I came up with, and my answers to them:

  1. How hard did Prof. Loh have to work to come up with a set of even-odd answers that determines a unique solution? If one picks a set of answers at random, how likely is there to be a unique solution?
    The answer is that every distribution of liars produces a unique set of even-odd answers and vice versa--there is a one-to-one mapping between distributions and answers, so all he had to do was pick random answers. We can show this by mimicking Mark's solution, and just replacing his "odd" and "even" as specified by the original problem with variables for arbitrary testimony by all of the six people.
    Letting a through h be 1 or 0 depending on whether people #1 through #8 are liars and A through H be 1 or 0 depending on their odd/even testimony, we are given that testimony is determined as follows (where "=" will now always mean equality mod 2):
    A = a+ +c+ + +f+g+h
    B = +b+ +d+e+ +g+h
    C = a+ +c+ +e+f+ +h
    D = +b+ +d+e+f+g+
    E = +b+c+d+e+ +g+
    F = a+ +c+d+ +f+ +h
    G = a+b+ +d+e+ +g+
    H = a+b+c+ + +f+ +h
    Subtracting, we get:
    A-H = g-b
    A-F = g-d
    C-F = e-d
    And so the testimony tells us the relative samenesses or difference among pairs in {b,g,e,d}. Similar subtractions give use the samenesses or differences in {a,c,f,h}. Then,
    A+B = (a+c+f+h) + (b+d+e+g) + (g+h)
    We know from the samenesses and differences what the two first addends are (mod 2), in terms of the testimonies A-H. And so this delivers the sameness or difference of g and h, and thereby all the samenesses and differences across the vertices.
    That leaves two possible, mutually inverted distributions of a through h. But when, say, person #1 is testifying about four people, the correct testimony (odd or even) remains the same under inversion, and so what she would say when inverted becomes the opposite. So an inverted complete distributions never produces the same testimony as the original, and only one distribution of a through h is compatible with any given values of A through H. Thus each distribution produces a different testimony, and so there are at least as many possible testimonies as there are distributions. But the mathematical limit is 2^8, or 256, which is also the number of distributions. Therefore, every mathematically possible testimony is produced by exactly one distribution, and Prof. Loh could have chosen any testimony at random.
  2. Interesting that Prof. Loh chose people's non-neighbors rather than neighbors for them to report on. Call a testimony (a collection of claims of even and odd numbers of liars) decisive if it is produced by exactly one distribution of truth-tellers and liars. We've seen that at least one way in which people might report on their non-neighbors is decisive. Is the same true if everyone instead reports on their immediate neighbors?
    No it is not. The easiest way to see this is that, because everyone now is reporting on an odd number of people, the testimony they will give is constant under inversion of everyone's actual status as a liar. The correct answers will change, but so will the correctness of each answer, and so the actual answers will remain constant.
    In fact, for each distribution of liars, there are seven others that produce identical testimony: the inverse distribution plus, for each edge of the cube, what you get by inverting the two vertices on that edge as well as the vertices on the parallel edge farthest away. Since there are 256 possible distributions, there are only 32 logically possible testimonies (so 224 the 256 mathematically possible testimonies cannot be produced by any distribution).
  3. What about reporting on immediate neighbors, but at the vertices not of a cube but of a tetrahedron? An octahedron? Dodecahedron? Icosahedron?
    The answer for all but the octahedron is that, as with the cube, no testimony is decisive; for instance, because each vertex has three neighbors, all inverted distributions of liars share testimonies. For the tetrahedron there are only two possible testimonies (all-even or all-odd) each produced by 8 of the 16 possible distributions. For a dodecahedron there are 32,768 possible testimonies, each produced by 16 distributions, and the icosahedron is left as an exercise for the reader.
    In an octahedron each vertex has four neighbors, and so, as in the cube, inverting a distribution inverts the answers because it preserves the correct answers and inverts the correctness of the actual answers. In fact just as with the original problem case of vertices on a cube reporting on non-neighbors, there is only one distribution per testimony, which can be established in exactly the same way.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment