S2T2

Jim Randell 10:35 am on 12 August 2021 Permalink Reply
Tags: by: James Fitzgibbon   

• 

  Jim Randell 10:37 am on 12 August 2021 Permalink | Reply

  We know there are (at least) 4 contestants. And we quite quickly find (by considering marks awarded by B) that exactly 4 contestants is not possible, so there must be at least one more we are not told about.

  If we suppose there are k contestants, and consider constructing a k × k table, where the rows give the marks awarded, and the columns the marks received. Then each row and column must be derived from a unique distribution of the 12 marks.

  The puzzle states that D gave herself the the highest possible marks. This would be achieved by giving everyone else a score of 1. However this seems to contradict the fact the the distribution of marks in the rows and columns are all different, as if D gave herself the highest possible mark, then the other entries in D’s row and column must all be 1’s, giving a row and a column with the same distribution.

  Instead I suggest we adopt: “The highest number of marks awarded were by D, to herself”.

  Now, if we consider the number of decompositions of 12 into k positive integers, then there must be a unique arrangement for each of the rows and columns, i.e. at least 2k decompositions. And since we can’t use the decomposition with (k − 1) 1’s, we need there to be at least (2k + 1) decompositions. For k = 6 it turns out there are only 11 decompositions, so k = 5 is the only possible number of contestants.

  With that in mind this Python 3 program is implemented to solve the k = 5 case (although it also shows other values are not possible). It runs in 406ms.

  Run: [ @replit ]

  from enigma import (irange, inf, cproduct, subsets, group, all_different, ordered, printf)
  
  # attempt to solve the puzzle for k contestants, decompositions = <ds>
  def solve(k, ds):
  
    # group the decompositions by span
    d = group(ds, by=(lambda s: max(s) - min(s)))
  
    # A's row has minimal span
    rAs = d[min(d.keys())]
  
    # B's has 3 sharing max marks
    rBs = list(s for s in ds if s.count(max(s)) == 3)
  
    # C's has exactly 4 odd numbers
    rCs = list(s for s in ds if sum(x % 2 for x in s) == 4)
  
    # choose rows (unordered) for A, B, C
    for (rA, rB, rC) in cproduct([rAs, rBs, rCs]):
      if not all_different(rA, rB, rC): continue
      # max points awarded (so far)
      (mA, mB, mC) = (max(r) for r in (rA, rB, rC))
  
      # D's row contains a (single) max value greater than mA, mB, mC
      mABC = max(mA, mB, mC)
      for rD in ds:
        if rD in (rA, rB, rC): continue
        mD = max(rD)
        if not (mD > mABC and rD.count(mD) == 1): continue
  
        # solve for the remaining rows
        if k == 5:
          solve5(ds, rA, rB, rC, rD, mA, mB, mC, mD)
        else:
          assert False, "Not reached"
  
  # use multiset permutations (to remove duplication)
  permutations = lambda s: subsets(s, size=len, select="mP")
  
  # solve for k = 5
  def solve5(ds, rA, rB, rC, rD, mA, mB, mC, mD):
    # choose an ordering for A, st A [0] is not max, and B [1] is odd
    for A in permutations(rA):
      if not (A[1] % 2 == 1 and A[0] < mA): continue
  
      # choose an ordering for B, st B [1] is max
      for B in permutations(rB):
        if not (B[1] == mB): continue
  
        # chose an ordering for C, st C [2] is max
        for C in permutations(rC):
          if not (C[2] == mC): continue
  
          # chose an ordering for D, st D [3] is max
          for D in permutations(rD):
            if not (D[3] == mD): continue
  
            # construct row E
            E = tuple(12 - sum(x) for x in zip(A, B, C, D))
            # all values are between 0 and mD (exclusive)
            if not all(0 < x < mD for x in E): continue
            # and E [4] is max
            if not (E[4] == max(E)): continue
            # check E is a valid decomposition
            rE = ordered(*E)
            if not (rE in ds and rE not in (rA, rB, rC, rD)): continue
  
            # calculate the column distributions
            cds = list(ordered(*x) for x in zip(A, B, C, D, E))
            # check all distributions are distinct
            if not all_different(rA, rB, rC, rD, rE, *cds): continue
  
            # output solution
            printf("k=5: A={A} B={B} C={C} D={D} E={E}")
  
  # decompose total <t> into <k> numbers, minimum <m>
  def decompose(t, k, m=1, ns=[]):
    if k == 1:
      if not (t < m):
        yield tuple(ns + [t])
    else:
      k_ = k - 1
      for n in irange(m, t - k_ * m):
        yield from decompose(t - n, k_, n, ns + [n])
  
  # try possible k values
  for k in irange(4, inf):
    # consider the number of decompositions for the rows/columns
    ds = list(ns for ns in decompose(12, k) if ns.count(1) < k - 1)
    printf("[k={k}: {n} decompostions]", n=len(ds))
    if len(ds) < 2 * k: break
    # solve the puzzle
    solve(k, ds)
  

  Solution: The marks awarded are as follows:

  

  LikeLike