Ken's POTW


Check(er)s and Balances
A small selection of quick problems this week:
  1. Consider a small game of checkers, played on a 4x4 board. Black starts with two pieces on A1 and A3. Red starts with two pieces on D2 and D4. As in regular checkers, if a jump is possible it must be taken. Red moves first. Does either player have an advantage to win, or to at least not lose (stalemate)? What if a restriction is added: For one player, if the previous two moves have been to move one checker (a "king" or "crown") from A to B, then from B to A, the next move cannot be from A to B unless that is the only legal move.
  2. You have 4 weights weighing 2,3,5 and 7 pounds. The problem is none of them are marked. What is the least number of weighings you need using a balance scale figure out which weights are which?
  3. What are the fewest number of weights you need to weigh any integral number of pounds (from 1 to 40) on a balance scale?

Source: 1. Original. 2. Jason Telgren, who says it's public domain. 3. Sam Loyd.


Solutions were received from several people, as noted below:
  1. A solution was received from Philippe Fondanaiche. It doesn't quite address the option of no oscillating moves:
    We have the following 4x4 board
    
       1    2    3    4
    D  .    R    .    R
    C  *    .    *    .
    B  .    *    .    *
    A  B    .    B    .
    
    If every player is properly playing, nobody can win.
    If D2-C1,black wins with A1-B2,then D4-C3 and B2xD4
    If D4-C3,black wins again with A3-B4 followed by D2-C1 and B4xD2 
    [Philippe missed another possibility here in C3-B2. - KD]
    If D2-C3, there are 2 possibilities:
      1) If A3-B4, red wins with C3-B2 then A1xB3 and D4xB2
      2) If A3-B2, C3-B4, B2-C1,B4-A3=crown and C1-D2=crown.
         The game ends on a draw.
    
    KD: I have now convinced myself that Black can always play to win. There are a few additional moves needed, but Black can eventually make Red move into a single osciallation and the inability to continue it makes Red move into a jump position.

    Glenn Rhoads pointed out that Martin Gardner analyzed this puzzle in one of his Scientific American columns, showing the game is a draw (as shown above). But the 5x5 grid for checkers is not a draw.

  2. Solutions were received from Dennis Borris and Philippe Fondanaiche. Dennis' solutions follow:
    Answer: 4 weighings.
    There are 2 ways of doing this puzzle;
    
    My solution#1 is probably what everyone comes up with: isolate the
    7weight after 2 weighing; however (all being equal) this solution
    means 47 2/3 pounds on the poor scale.
    
    My solution#2 (I'm sure it's been noticed before) is a bit more
    complicated but means only 33 1/3 pounds on the grateful scale!
    
    I therefore think this puzzle's question should be extended to
    include "minimum total weights to be placed on scale, assuming 
    each weight has equal chance of being picked up.
    
                                                                       Average
    SOLUTION#1                                                         Weight:
    ==========                                                         =======
    Weighing#1 : 2 against 2; 7weight automatically on heavy side        17
    
    Weighing#2 : compare the 2 from heavy side; isolates 7weight         10 1/3
    
    (Let A = 7weight, B C D = the other 3 weights)
    
    Weighing#3 : weigh A against 2 others (call them B and C)
                 possibilities:    A     B C        D(default)
                    A is heavy     7     2 3 (5)       5
                         even      7     2 5 (7)       3
                         heavy     7     3 2 (5)       5
                         light     7     3 5 (8)       2
                         even      7     5 2 (7)       3
                         light     7     5 3 (8)       2                 13 2/3
                   
    Weighing#4 : compare B to C and you got it!                           6 2/3
                                                                         ======
                                                 Total weight handled:   47 2/3
    
    
                                                                       
    SOLUTION#2
    ==========
    STEP BY STEP SOLUTION:
    4 weighings, for total average weight of 33 1/3 pounds; like this:
    
    STEP 1:
    compare any 2 balls; call A the lighter and B the heavier.
    
    STEP 2:
    compare the other 2 balls; call C the lighter and D the heavier.
    Total weight so far is 17 (each ball used once)
    
    STEP 3:
    compare A to C. This isolates the 2weight; make A=2, C the other (3 or 5).
    3 equally likely possiblities exist:
         A   B   C   D
    (1)  2   3   5   7
    (2)  2   5   3   7
    (3)  2   7   3   5
    Average weight for C is (5 + 3 + 3) / 3 = 3 2/3.  
    Average weight for this Step = A + C = 2 + 3 2/3 = 5 2/3.
    So average weight so far = 17 + 5 2/3 = 22 2/3.
    
    STEP 4:
    compare A+C to B:  
    if (1), B is lighter, 
    if (2), both sides are equal, 
    if (3), B is heavier; so we are done.
    Average weight for this Step is A + B + C = 
    2 + 3 2/3 + (3 + 5 + 7) / 3 = 10 2/3.
    So total average weight is 22 2/3 + 10 2/3 = 33 1/3.
    
  3. Philippe Fondanaiche shows this solution and its generalization:
    With the 4 weights 1,3,9 and 27 it is possible to weigh any integral number from 1 to 40. Indeed, any integer n can be written as follows:
    n = a + 3b + 9c + 27d
    where a,b,c,d = -1 or 0 or 1. The coefficient is equal to -1 if the corresponding weight is on the left pan of the balance scale and equal to 1 if it is on the right one. The weight is not used if the coefficient is nil.

    It is easy to generalize with any number n included between 1 and N by determining k,the fewest number of weights, such that sum(3^k)>=N.


    Mail to Ken