Enigmatic Code

Programming Enigma Puzzles

Enigma 398: Down on the farm

From New Scientist #1548, 19th February 1987 [link]

Farmer O. R. Midear has crossed a turnip with a mangel to get a tungel, and he now has many fields of tungels. As a tungel expert, he looks at a tungel to see if it is red or not, if it is smooth or not, and if it is firm or not. He knows that if a tungel is red then it is smooth.

Regulations have just been introduced which put fields of tungels into classes A, B, C, D, E; a field may be in more than one class.

Class A: All fields containing no red tungel.
Class B: All fields containing no smooth tungel.
Class C: All fields in which every red tungel is firm.
Class D: All fields in which every smooth tungel is firm.
Class E: All fields containing a red tungel which is not firm.

To test Farmer Midear’s understanding of the regulations he was asked to say which of the following statements are true.

1. If a field is in A then it is in B.
2. If a field is in B then it is in A.
3. If a field is in C then it is in B.
4. If a field is in B then it is in C.
5. If a field is in C then it is in D.
6. If a field is in D then it is in C.
7. If a field is in D then it is not in E.
8. If a field is not in E then it is in C.
9. In every field there is a tungel such that if it is not red then the field is in A.

What should Farmer Midear’s answer be?

[enigma398]

Advertisements

3 responses to “Enigma 398: Down on the farm

  1. Jim Randell 2 June 2017 at 11:28 am

    This Python program examines the statements by applying them to fields consisting of each possible population of the types of tungel. It runs in 39ms.

    from itertools import product
    from enigma import subsets, printf
    
    # logical implication: "<p> implies <q>"
    implies = lambda p, q: not(p) or q
    
    # first use the tuple (R, S, F) to represent (red, smooth, firm)
    ts = set(product((0, 1), repeat=3))
    
    # but all red tungels are smooth
    fn = lambda (r, s, f): implies(r, s)
    ts = filter(fn, ts)
    
    # categories:
    
    # A = field contains no red tungel
    A = lambda field: all(not(r) for (r, s, f) in field)
    
    # B = field contains no smooth tungel
    B = lambda field: all(not(s) for (r, s, f) in field)
    
    # C = every red tungel in field is firm
    C = lambda field: all(implies(r, f) for (r, s, f) in field)
    
    # D = every smooth tungel in field is firm
    D = lambda field: all(implies(s, f) for (r, s, f) in field)
    
    # E = there is a red tungel in the field that is not firm
    E = lambda field: any(r and not(f) for (r, s, f) in field)
    
    
    # test the categories on each type of tungel
    def test(label, p):
      for field in subsets(ts, min_size=1):
        if not p(field):
          printf("{label} = False, counterexample = {field}")
          return False
      printf("{label} = True")
      return True
    
    # statements
    
    def IMPLIES(P, Q):
      return (lambda field: implies(P(field), Q(field)))
    
    def NOT(P):
      return (lambda field: not(P(field)))
    
    # 1. "if a field is in A then it is in B"
    test(1, IMPLIES(A, B))
    
    # 2. "if a field is in B then it is in A"
    test(2, IMPLIES(B, A))
    
    # 3. "if a field is in C then it is in B"
    test(3, IMPLIES(C, B))
    
    # 4. "if a field is in B then it is in C"
    test(4, IMPLIES(B, C))
    
    # 5. "if a field is in C then it is in D"
    test(5, IMPLIES(C, D))
    
    # 6. "if a field is in D then it is in C"
    test(6, IMPLIES(D, C))
    
    # 7. "if a field is in D then it is not in E"
    test(7, IMPLIES(D, NOT(E)))
    
    # 8. "if a field is not in E then it is in C"
    test(8, IMPLIES(NOT(E), C))
    
    # 9. "In every field there is a tungel such that if it is not red then the field is in A."
    # so a counterexample would be a field that was not in A, but every
    # tungel in it was not red, as then you would be forced to choose a not
    # red tungel, but the field would be in A.
    test(9, NOT(lambda field: not(A(field)) and all(not(r) for (r, s, f) in field)))
    

    Solution: Statements 2, 4, 6, 7, 8, 9 are true.

    There are six different types of tungels, rather than eight, because (red, not smooth, firm) and (red, not smooth, not firm) are disallowed.

    Here are counter examples for the false statements:

    For statement 1, a field of tungels that are (not red, smooth, firm) would be in Class A (there are no red tungels), but not Class B (there are smooth tungels).

    For statement 3, a field of tungels that are (red, smooth, firm) would be in Class C (all red tungels are firm), but not Class B (there are smooth tungels).

    For statement 5, a field containing tungels that are (red, smooth, firm) and (not red, smooth, not firm) would be in Class C (all red tungels are firm), but not Class D (there are smooth tungels that are not firm).

    • Jim Randell 2 June 2017 at 6:21 pm

      Here’s the program written using the collection.namedtuple() function to create a specially packaged tuple to represent tungels, rather than the standard Python tuple used by the previous program (which also uses parameter unpacking in some places which was obsoleted in Python 3). This program should work in (recent versions of) Python 2 or Python 3.

      from collections import namedtuple
      from itertools import product
      from enigma import subsets, printf
      
      # logical implication: "<p> implies <q>"
      implies = lambda p, q: not(p) or q
      
      # tuple to represent a tungel
      Tungel = namedtuple('Tungel', 'is_red is_smooth is_firm')
      
      # make a set of all tungels
      tungels = set(Tungel(*v) for v in product((0, 1), repeat=3))
      
      # but all red tungels are smooth
      fn = lambda tungel: implies(tungel.is_red, tungel.is_smooth)
      tungels = set(filter(fn, tungels))
      
      # categories:
      
      # A = field contains no red tungel
      A = lambda field: all(not(tungel.is_red) for tungel in field)
      
      # B = field contains no smooth tungel
      B = lambda field: all(not(tungel.is_smooth) for tungel in field)
      
      # C = every red tungel in field is firm
      C = lambda field: all(implies(tungel.is_red, tungel.is_firm) for tungel in field)
      
      # D = every smooth tungel in field is firm
      D = lambda field: all(implies(tungel.is_smooth, tungel.is_firm) for tungel in field)
      
      # E = there is a red tungel in the field that is not firm
      E = lambda field: any(tungel.is_red and not(tungel.is_firm) for tungel in field)
      
      
      # test the categories on each type of tungel
      def test(label, p):
        for field in subsets(tungels, min_size=1):
          if not p(field):
            printf("{label} = False, counterexample = {field}")
            return False
        printf("{label} = True")
        return True
      
      # statements
      
      def IMPLIES(P, Q):
        return (lambda field: implies(P(field), Q(field)))
      
      def NOT(P):
        return (lambda field: not(P(field)))
      
      # 1. "if a field is in A then it is in B"
      test(1, IMPLIES(A, B))
      
      # 2. "if a field is in B then it is in A"
      test(2, IMPLIES(B, A))
      
      # 3. "if a field is in C then it is in B"
      test(3, IMPLIES(C, B))
      
      # 4. "if a field is in B then it is in C"
      test(4, IMPLIES(B, C))
      
      # 5. "if a field is in C then it is in D"
      test(5, IMPLIES(C, D))
      
      # 6. "if a field is in D then it is in C"
      test(6, IMPLIES(D, C))
      
      # 7. "if a field is in D then it is not in E"
      test(7, IMPLIES(D, NOT(E)))
      
      # 8. "if a field is not in E then it is in C"
      test(8, IMPLIES(NOT(E), C))
      
      # 9. "In every field there is a tungel such that if it is not red then the field is in A."
      # so a counterexample would be a field that was not in A, but every
      # tungel in it was not red, as then you would be forced to choose a not
      # red tungel, but the field would be in A.
      test(9, NOT(lambda field: not(A(field)) and all(not(tungel.is_red) for tungel in field)))
      

      Also note that field of tungels that is (not red, smooth, not firm) is a logical counterexample for all the false statements (1, 3 and 5).

  2. Brian Gladman 4 June 2017 at 12:43 pm
    from itertools import product
    
    # indexes in tuples for red, smooth and firm
    red, smooth, firm = 0, 1, 2
    
    # the different types of field that are possible
    fields = set(t for t in product((0, 1), repeat=3) 
                 if not (t[red] and not t[smooth]))
    
    # form the classses of fields (for classes C and D it appears
    # that non-existant red and smooth Tungels are firm!)
    
    # Class A: All fields containing no red tungel
    A = set(f for f in fields if not f[red])                
    
    # Class B: All fields containing no smooth tungel
    B = set(f for f in fields if not f[smooth])             
    
    # Class C: All fields in which every red tungel is firm
    C = set(f for f in fields if not f[red] or f[firm])
    
    # Class D: All fields in which every smooth tungel is firm
    D = set(f for f in fields if not f[smooth] or f[firm])
    
    # Class E: All fields containing a red tungel which is not firm
    E = set(f for f in fields if f[red] and not f[firm])
    
    # find the answers for each of the nine questions 
    ans = [i + 1 for i, a in enumerate((
      # 1. If a field is in A then it is in B
      all(f in B for f in fields if f in A),
      
      # 2. If a field is in B then it is in A
      all(f in A for f in fields if f in B),
      
      # 3. If a field is in C then it is in B
      all(f in B for f in fields if f in C),
      
      # 4. If a field is in B then it is in C
      all(f in C for f in fields if f in B),
      
      # 5. If a field is in C then it is in D
      all(f in D for f in fields if f in C),
      
      # 6. If a field is in D then it is in C
      all(f in C for f in fields if f in D),
      
      # 7. If a field is in D then it is not in E
      all(f not in E for f in fields if f in D),
      
      # 8. If a field is not in E then it is in C
      all(f in C for f in fields if f not in E),
      
      # 9. In every field there is a tungel such that 
      #    if it is not red then the field is in A.
      all(f in A for f in fields if not f[red])
    )) if a]
    
    print(*ans[:-1], 'and', ans[-1], 'are true.')
    

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: