4
$\begingroup$

You must determine what can be concluded from the 60 true statements below. The numbers in each statement represent binary values (true / false, 1 / 0), or attributes that either are present or are not present.

For example, in words, Statement 1 reads:
If 3 is true and 29 is true then 13 is false.

Statement 1: if 3 and 29 then not 13
Statement 2: if (27 and 9) or (14 and not 10) then 4
Statement 3: if 14 and 28 then not 6
Statement 4: if (2 and 16) or (27 and not 18) then 24
Statement 5: if 14 and 29 then 11
Statement 6: if 7 and 11 and not 10 then 21
Statement 7: if 30 and 3 and not 12 then 11
Statement 8: if 3 and 7 and not 1 then 23
Statement 9: if (10 and 1) or (23 and not 16) then 27
Statement 10: if 19 and 9 then not 27
Statement 11: if 26 and 8 then not 5
Statement 12: if 10 or 19 then not 13
Statement 13: if (1 and 6) or (9 and not 13) then 25
Statement 14: if 11 and 3 and not 4 then 17
Statement 15: if 28 or 16 then 8
Statement 16: if (2 and 7) or (14 and not 13) then 20
Statement 17: if 27 and 26 then 15
Statement 18: if 27 or 7 then 4
Statement 19: if 30 and 11 and not 24 then 28
Statement 20: if 27 and 10 and not 30 then 29
Statement 21: if 27 and 9 and not 24 then 4
Statement 22: if 4 and 28 then 15
Statement 23: if 16 or 23 then not 25
Statement 24: if 20 and 17 then 11
Statement 25: if 6 or 28 then 30
Statement 26: if (5 and 18) or (6 and not 26) then 16
Statement 27: if 23 or 21 then 20
Statement 28: if 25 or 6 then 20
Statement 29: if 29 and 8 and not 23 then 7
Statement 30: if 9 or 18 then 16
Statement 31: if 12 and 11 and not 24 then 2
Statement 32: if 6 and 24 then not 15
Statement 33: if 9 or 5 then not 25
Statement 34: if 17 and 8 and not 26 then 22
Statement 35: if 15 and 1 then 11
Statement 36: if 28 and 5 then 2
Statement 37: if 2 and 9 and not 12 then 6
Statement 38: if 26 and 14 then 22
Statement 39: if 12 or 16 then 13
Statement 40: if 9 and 8 then 16
Statement 41: if 8 and 15 then not 27
Statement 42: if 18 or 7 then 25
Statement 43: if 30 and 2 then not 17
Statement 44: if 23 and 4 then not 9
Statement 45: if 17 and 11 and not 18 then 29
Statement 46: if 10 and 5 then not 28
Statement 47: if 12 and 18 and not 9 then 23
Statement 48: if 9 and 17 then not 18
Statement 49: if 21 or 5 then not 22
Statement 50: if (21 and 16) or (19 and not 17) then 25
Statement 51: if 13 or 24 then not 6
Statement 52: if 1 and 18 and not 2 then 30
Statement 53: if 8 and 30 and not 1 then 9
Statement 54: if 10 and 28 then 6
Statement 55: if 13 or 12 then not 21
Statement 56: if 1 and 22 and not 20 then 23
Statement 57: if (3 and 30) or (12 and not 13) then 23
Statement 58: if 8 or 11 then 14
Statement 59: if (27 and 16) or (17 and not 28) then 21
Statement 60: if (27 and 16) or (22 and not 14) then 28

$\endgroup$
  • $\begingroup$ Hi there, what is the source of this puzzle? $\endgroup$ – Hugh Dec 8 '18 at 19:47
  • 1
    $\begingroup$ All 60 statements are true. Of course the attributes within each statement may be true or false as noted. This is a problem of my own devising and the solution is very concise. $\endgroup$ – Bob Bixler Dec 8 '18 at 22:22
  • $\begingroup$ Thanks for clarifying that this is a puzzle of yours. $\endgroup$ – Hugh Dec 8 '18 at 22:27
  • 1
    $\begingroup$ Please re-read the problem. The numbers within each statement refer to binary values or attributes and not statement numbers. $\endgroup$ – Bob Bixler Dec 8 '18 at 23:40
  • $\begingroup$ so 27 is like b[27].? and the array goes from 1..30? is the system consistent, or are we working this out? $\endgroup$ – JonMark Perry Dec 9 '18 at 11:25
1
$\begingroup$

We can see that 18 is definitely False. There are many solutions that satisfy all the requirements. But other numbers can go either way, that is, they can all be either true or false in different solutions.

This can be seen as follows:

Assume 18 is True
Then (S30) means that 16 is True
And (S42) means that 25 is True
And (S23) means that 25 is False - whoops!
Therefore 18 is False (by contradiction)

I'm not sure what else we're looking for. It's possible to do a similar sort of thing for other numbers:

E.g. if you start with all falses, except 6, and use the below methodology, you will find a solution in which 6 is false. However, deeper searching yields a stable solution of (0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1) which has 6 equal to True.

I found 1486 solutions as follows:

  1. Set all the values to 0
  2. Change {0,1,2,3} of the values to 1 (all possible combinations)
  3. Run all the statements, adjusting the outputs if necessary (see below).
  4. Repeat 3 until stability is reached or until I've iterated 60 times without reaching stability.
  5. Save all stable solutions (discarding any repeated solutions).

[Notes for point 3: All statements are "if X then Y". So if X is true and Y is false, then I adjust the variable in Y and rerun. Notes for point 4: Obviously, stability might be found later than this in principle. I haven't yet checked, but I suspect that they are mostly cycling.]

In this situation:

Starting with all false, there is a solution immediately (all false).
Starting with 1 true, there are 29 solutions (only 17=True doesn't yield a stable solution immediately).
Starting with 2 trues, there are 253 solutions.
Starting with 3 trues, there are 1203 solutions.
So, I have found a total of 1203 solutions.
Starting on the other end (with all trues and adjusting {0,1,2,3} to false yields no stable solutions with this method.

Here's 31 consistent solutions showing how each other number can be True:

(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
(1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
(0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
(0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
(0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
(0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
(0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1)
(0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1) (Bonus one from setting 29 and 30 to True)
(0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0)
(0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
(0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
(0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
(0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
(0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0)
(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
(0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
(0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
(0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0)
(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0)
(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0)
(0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1)
(0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0)
(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0)
(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0)
(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0)
(0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0)
(0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1)
(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0)
(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1)
$\endgroup$
  • 1
    $\begingroup$ Congratulations, Dr. Xorile, you have solved this correctly. Your hard work has paid off here. I plan on posting another problem that will look similar but will have an interesting twist. $\endgroup$ – Bob Bixler Dec 10 '18 at 3:16
3
$\begingroup$

Let's try, is it correct that

all numbers are false

because

if you look at the statements, all of them are in a form of "if X then Y" which is only wrong when both X is true and Y is false. By setting all numbers are false, all X will be false hence all statements will be automatically true.

$\endgroup$
  • $\begingroup$ that's a really clever solution, and is definitely correct, +1 from me. Although it probably isn't the intended answer. $\endgroup$ – Hugh Dec 9 '18 at 0:24
  • 5
    $\begingroup$ You have found 1 combination of numbers (all false) that satisfy all statements. However that cannot be the conclusion to be derived if there are other combinations of numbers (some false, some true) that also satisfy all the statements. $\endgroup$ – Bob Bixler Dec 9 '18 at 0:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.