Tagged: by: W. E. Chapman Toggle Comment Threads | Keyboard Shortcuts

  • Unknown's avatar

    Jim Randell 10:31 am on 23 January 2022 Permalink | Reply
    Tags: by: W. E. Chapman   

    A Brain Teaser: [Grains of rice] 

    From The Sunday Times, 21st December 1952 [link]

    An Eastern potentate, at the end of a game of chess with his professional chess player, broached the delicate question of a reward for his many years of service.

    The old man pointed to the board and said: “Suppose we number the squares from 1 to 64, thus. Your Majesty will observe that your King is on a lower-numbered square than mine. Pay me, I humbly beg, in grains of rice, for each square as many as the number of that square raised to the power of the number of the square occupied by your King, finishing at and including the square occupied by my King”.

    “But that will be ruinous”, protested the monarch. “Not so, for the sum total contains but nine figures”.

    “Then be it so. But will you take payment to the nearest thousand?”. “Certainly”, replied the sage, since if your men count accurately, I shall thereby forfeit only eight grains of rice”.

    What squares were occupied by the two Kings, and how many grains were the old man’s reward?

    This one of the occasional Holiday Brain Teasers published in The Sunday Times prior to the start of numbered Teasers in 1961. Prizes of 3 guineas and 2 guineas were offered.

    This puzzle was originally published with no title.

    [teaser-1952-12-21] [teaser-unnumbered]

     
    • Jim Randell's avatar

      Jim Randell 10:32 am on 23 January 2022 Permalink | Reply

      If the king is on square k, and the old man is on square j then the total number of grains t is given by:

      t = sum (i = 1 .. j) (i^k)

      This Python program runs in 52ms.

      Run: [ @replit ]

      from enigma import (irange, ndigits, printf)
      
      # consider the king's square
      for k in irange(1, 63):
        # t = total number of grains
        # j = old man's square
        t = j = 0
        while j < 64:
          j += 1
          t += j**k
          n = ndigits(t)
          if n > 9: break
          # check conditions
          if n == 9 and k < j and t % 1000 == 8:
            printf("k={k} j={j} t={t}")
      

      Solution: The kings are on squares 5 and 32. The reward consisted of 196,171,000 grains of rice.

      The actual total being:

      >>> sum(powers(1, 32, 5))
      196171008
      

      A grain of rice weighs approximately 1/64 gram, so the total prize would be just over 3065 kg of rice.

      Like

  • Unknown's avatar

    Jim Randell 9:33 am on 16 January 2022 Permalink | Reply
    Tags: by: W. E. Chapman   

    A Brain Teaser: Trial and Error 

    From The Sunday Times, 13th April 1952 [link]

    A bank cashier has a pile of 364 similar coins of which one Is known to be of abnormal weight, the remainder being all of equal weight. For testing, he has only a pair of scales, in which he can balance one pile of coins against another.

    What is the smallest number of such “trials” in which he can be sure of finding the odd coin, and what is the greatest number of coins among which he can likewise be sure of finding a single coin of odd weight in nine “trials”?

    This one of the occasional Holiday Brain Teasers published in The Sunday Times prior to the start of numbered Teasers in 1961. A prize of 5 guineas was offered.

    [teaser-1952-04-13] [teaser-unnumbered]

     
    • Jim Randell's avatar

      Jim Randell 9:38 am on 16 January 2022 Permalink | Reply

      We have tackled similar problems before, see: Enigma 1589, Teaser 2500.

      For Enigma 1589 I wrote a constructive solution that searches for a minimal decision tree.

      For Teaser 2500 I gave a program that will construct minimal decision trees for a set of related problems.

      For a “type 1” problem (where we need to find the counterfeit coin, and determine if it is heaver or lighter), with n weighings we can deal with a set of (3^n − 3) / 2 coins.

      However, each decision tree for the “type 1” problem has a leaf that is impossible to reach if we are guaranteed that there is exactly one counterfeit coin. But if there are no counterfeit coins then every weighing balances and we reach the impossible leaf.

      So, for this type of puzzle (where we need to determine which coin is counterfeit, but not if it is heavier or lighter), we can put one of the coins aside and then proceed with the weighings for a “type 1” puzzle, if we reach the impossible leaf we know that it must be the unweighed coin that is counterfeit, and we don’t need to determine whether it is lighter or heavier, so we can stop. This means we can manage 1 extra coin compared to the “type 1” puzzle.

      So in n weighings we can deal with a set of (3^n − 1) / 2 coins. (The same as a “type 2” problem, where we have to determine the counterfeit coin, and whether it is lighter or heavier, but we have a reference coin available).

      Hence:

      With 6 weighings we can deal with a set of (3^6 − 1) / 2 = 364 coins.

      And with 9 weighings we can determine the counterfeit coin from (3^9 − 1) / 2 = 9841 coins.

      Solution: 364 coins require 6 weighings. With 9 weighings we can deal with up to 9841 coins.


      Note that the formula applies to n ≥ 2 weighings.

      A set consisting of 1 coin requires 0 weighings (as the set must contain a counterfeit coin), and with a set consisting of 2 coins it is not possible to determine which coin is counterfeit (unless we have a reference coin, or are told that the counterfeit is light (or heavy)).

      With 4 coins (1, 2, 3, 4) we can weigh 1 against 2. If they balance (and so are both good), we weigh one of these good coins against 3. If the second weighing balances, the counterfeit is 4. If it doesn’t balance, it is 3. If the initial weighing does not balance, then the counterfeit coin is 1 or 2, and 3 and 4 are good. So weigh 1 against 3. If they balance, the counterfeit is 2. If not the counterfeit is 1. So we can solve 4 coins with 2 weighings.


      The published solution (27th April 1952) is as follows: [link]

      Readers were posed the problem before a cashier having a pile of coins of which he knows one to be abnormal in weight, and a pair of scales but no other Instrument. They were asked (a) the least number of trial weighings he must make to be sure of identifying the abnormal coin in a pile of 364, and (b) the largest number of coins among which he may be sure of Identifying the abnormal one In nine “trials.” This was a highly successful brain-teaser in respect of the number of clever brains which it evidently teased. There were nearly 1,500 entries, but barely one in ten of them gave both answers correctly. Answers to (a) ranged from 6 to 16, and to (b) from 22 to 19,683.

      On the other hand, correct entrants had little success in expressing the method of trial succinctly. The clue is to start by weighing 121 against 121. If they balance, the remaining 122 include the abnormal coin; if not, the 122 are known to be all “good” coins. Combinations from the good and doubtful groups then reduce the scale of alternative third trials to 27 or 40, fourth to 9 or 13, fifth to 3 or 4, and sixth to one coin in each pan.

      The correct answers are: (a) 6, (b) 9,841. The latter follows the formula (3^n − 1) / 2 where n = the maximum number of trials; many entrants offered 3^n (giving the answer 19,683), which is demonstrably incorrect, e.g., for n=2.

      Like

c
Compose new post
j
Next post/Next comment
k
Previous post/Previous comment
r
Reply
e
Edit
o
Show/Hide comments
t
Go to top
l
Go to login
h
Show/Hide help
shift + esc
Cancel
Design a site like this with WordPress.com
Get started