S2T2

Jim Randell 9:49 am on 24 March 2020 Permalink Reply
Tags: by: Peter Harrison ( 6 )   

• 

  Jim Randell 9:50 am on 24 March 2020 Permalink | Reply

  We dealt with a similar puzzle in Enigma 1589 (also set by Peter Harrison). For that puzzle I wrote a program that searches for a minimal decision tree.

  For an analytical solution the paper Weighing Coins: Divide and Conquer to Detect a Counterfeit by Mario Martelli and Gerald Gannon [ link ] provides an elegant analysis to determine the maximum number of coins that can be distinguished using a certain number of weighings for four related problems.

  And this gives us the solution to this puzzle:

  Solution: 4 weighings can be used to find the rogue object in a set of 39.

  LikeLike

• 

  Jim Randell 9:44 pm on 24 March 2020 Permalink | Reply

  For Enigma 1589 I wrote the following code to generate the decision trees for the four types of problem described in the linked paper.

  It can be used to generate decision trees for either puzzle.

  Run: [ @codepad ] [ @repl.it ]

  from enigma import (irange, arg, printf)
  
  # weigh 3^n coins in n weighings, suspect coin is lighter
  def solve_lighter(n, coins, p=''):
    assert len(coins) == 3**n
    # 3 coins
    if n == 1:
      # weigh two of the coins
      printf("{p}{coins[0]} < {coins[1]} -> {coins[0]}L")
      printf("{p}{coins[0]} = {coins[1]} -> {coins[2]}L")
      printf("{p}{coins[0]} > {coins[1]} -> {coins[1]}L")
    else:
      # divide the coins into 3 piles
      k = len(coins) // 3
      (c1, c2, c3) = (coins[:k], coins[k:2 * k], coins[2 * k:])
      printf("{p}{c1} < {c2}")
      solve_lighter(n - 1, c1, p + '  ')
      printf("{p}{c1} = {c2}")
      solve_lighter(n - 1, c3, p + '  ')
      printf("{p}{c1} > {c2}")
      solve_lighter(n - 1, c2, p + '  ')
  
  
  # weigh 3^n coins in n weighings
  # suspect coin is in reds if heavier, in blacks if lighter
  def solve_red_black(n, reds, blacks, red='H', black='L', p=''):
    assert len(reds) + len(blacks) == 3**n and len(reds) == len(blacks) + 1
    # 2 red, 1 black
    if n == 1:
      # weigh the two reds
      printf("{p}{reds[0]} < {reds[1]} -> {x[0]}{x[1]}", x=((reds[1], 'H') if red == 'H' else (reds[0], 'L')))
      printf("{p}{reds[0]} = {reds[1]} -> {blacks[0]}{black}")
      printf("{p}{reds[0]} > {reds[1]} -> {x[0]}{x[1]}", x=((reds[0], 'H') if red == 'H' else (reds[1], 'L')))
    else:
      # weigh (3^(n-1) + 1)/2 reds against (3^(n-1) - 1)/2 of the blacks
      k = (3**(n - 1) + 1) // 2
      (r1, r2, r3) = (reds[:k], reds[k:2 * k], reds[2 * k:])
      (b1, b2, b3) = (blacks[:k - 1], blacks[k - 1:2 * k - 2], blacks[2 * k - 2:])
      (left, right) = (r1 + b1, r2 + b2)
      printf("{p}{left} < {right}")
      solve_red_black(n - 1, r2, b1, red, black, p + '  ')
      printf("{p}{left} = {right}")
      solve_red_black(n - 1, b3, r3, black, red, p + '  ')
      printf("{p}{left} > {right}")
      solve_red_black(n - 1, r1, b2, red, black, p + '  ')
  
  
  # weigh (3^n - 1) / 2 suspect coins in n weighings
  # given a known good coin
  def solve_test_coin(n, good, coins, p=''):
    assert len(coins) == ((3**n) - 1) // 2
    if n == 1:
      # weigh the coin against the good coin
      printf("{p}{good} < {coins[0]} -> {coins[0]}H")
      printf("{p}{good} = {coins[0]} -> #")
      printf("{p}{good} > {coins[0]} -> {coins[0]}L")
    else:
      k = (3**(n - 1) + 1) // 2
      (c1, c2, c3) = (coins[:k], coins[k:2 * k - 1], coins[2 * k - 1:])
      (left, right) = (c1, [good] + c2)
      printf("{p}{left} < {right}")
      solve_red_black(n - 1, c1, c2, 'L', 'H', p + '  ')
      printf("{p}{left} = {right}")
      solve_test_coin(n - 1, good, c3, p + '  ')
      printf("{p}{left} > {right}")
      solve_red_black(n - 1, c1, c2, 'H', 'L', p + '  ')
  
  
  # weigh (3^n - 3) / 2 suspect coins in n weighings
  def solve_general(n, coins, p=''):
    assert len(coins) == ((3**n) - 3) // 2
    # divide the coins into 3 piles
    k = len(coins) // 3
    (c1, c2, c3) = (coins[:k], coins[k:2 * k], coins[2 * k:])
    printf("{p}{c1} < {c2}")
    solve_red_black(n - 1, c1 + c3[:1], c2, 'L', 'H', p + '  ')  
    printf("{p}{c1} = {c2}")
    solve_test_coin(n - 1, c1[0], c3, p + '  ')
    printf("{p}{c1} > {c2}")
    solve_red_black(n - 1, c1 + c3[:1], c2, 'H', 'L', p + '  ')
    
  
  # number of weighings and problem type
  n = arg(3, 0, int, prompt="number of weighings")
  p = arg(2, 1, int, prompt="problem number")
  printf("[n={n}; p={p} (of 1-4)]")
  
  if p == 1:
    # solve the general case
    k = (3**n - 3) // 2
    if k > 0:
      printf("---\n{n} weighings finds the suspect coin from {k} coins\n---")
      solve_general(n, list(irange(1, k)))
  
  elif p == 2:
    # solve with a known good coin
    k = (3**n - 1) // 2
    printf("---\n{n} weighings finds the suspect coin from {k} coins, with an extra known good coin (0)\n---")
    solve_test_coin(n, 0, list(irange(1, k)))
  
  elif p == 3:
    # solve red/black
    k = 3**n
    j = (k + 1) // 2
    printf("---\n{n} weighings finds the suspect coin from {k} coins, where {j} of the coins are red and {j1} of the coins are black\nif the suspect coin is red it is heavier, if it is black it is lighter\n---", j1=j - 1)
    solve_red_black(n, list(irange(1, j)), list(irange(j + 1, k)))
  
  elif p == 4:
    # solve lighter
    k = 3**n
    printf("---\n{n} weighings finds the suspect lighter coin from {k} coins\n---")
    solve_lighter(n, list(irange(1, k)))
  

  LikeLike