MatMod logo

Tommy’s Birthday (math10)

Run LPL Code  ,  PDF Document

Problem

Tommy was given 15 coins for his birthday (half-crowns, shillings and sixpence). When he added it up, he found that he had £1. 5s. 6d (one pound 5 shillings and 6 pences, see below). How many half-crowns was he given?

(This puzzle involve coins from the old British currency. A pound is 20 shillings and a shilling is 12 pence (hence, a pound is 20 12 = 240 pence). A half-sovereign is 10 shillings, a crown is 5 shillings, a double-florin is four shillings, a half-crown is 2 shillings and sixpence (hence, a half-crown is 2 12 + 6 = 30 pence), a florin is 2 shillings. £3. 2s. 6d. means three pounds, two shillings and six pence.) (see [2] and [1]).

Modeling Steps

The different coins are listed in a set c. There are three: half-crowns, shillings and sixpence.

  1. Hence we have

    c = {half - crowns, shillings, sixpence }
  2. The value of the three coins is expressed in pence in a parameter vc = [30, 12, 6].

  3. The total value received (£1. 5s. 6d.) is the same as 2012+512+6 (=306) pences.

  4. We introduce three variables xc for the number of half-crowns, shillings and sixpence given.

  5. The sum of the values times the number of coins must be the received value, hence:

    ∑  vcxc = 306   c
  6. Furthermore, the number of coins is 15. Hence, we have the following constraint:

    ∑ x  = 15   c  c
  7. We are looking for a feasible solution.

Listing 1: The Complete Model implemented in LPL [4]

model math10 "Tommy's Birthday"; 
  set c := ['half-crowns', 'shillings', 'sixpence']; 
  parameter v{c}  := [30,12,6] "Coin value in pence"; 
  integer variable x{c} [1..50]; 
  constraint 
    V: sum{c} v*x = 20*12 + 5*12 + 6; 
    N: sum{c} x = 15; 
  solve; 
  Writep(x); 
end

Solution

Tommy got 8 half-crowns, 4 shillings and 3 sixpence. This is the unique solution. To check, add the constraint x1 = 8 and solve. The problem is infeasible. Hence, there is no solution where the number of half-crowns is not 8.

Questions

  1. Solve the problem with 16, 17, then 18 coins.

  2. What is the smallest possible number of coins which could be given to Tommy for the amount £1. 5s. 6d. ?

  3. What is the maximal number of coins for the same amount?

  4. Is the problem solvable for all numbers of coins between the minimum and maximum obtained in the previous questions?

Answers

  1. One only needs to change the right hand side constant from 15 to the values 16, then 17 and 18 and solve the problem each time.

  2. The minimum is 13 coins: 9 half-crowns, 2 shillings, and 2 sixpence. One could try now with different right hand side constants: 14 then 13 then 12 and so on and solve the problem each time. We will see that the problem is not solvable for numbers smaller than 13.

    Another systematic way to approach the problem is as follows: Add a new integer variable y and replace the right hand side constant 15 by this variable then minimize y. The complete model is as follows:

    model math10a "Tommy's Birthday Coins"; 
      set c:=['half-crowns', 'shillings', 'sixpence']; 
      parameter v{c}  := [30,12,6]; 
      integer variable x{c} [1,50]; y; 
      constraint 
        TVAL: sum{c} v*x = 20*12 + 5*12 + 6; 
        TNUM: sum{c} x = y; 
      minimize obj: y; 
      write x; 
    end
  3. The maximum is 46 coins: 1 half-crowns, 1 shilling, and 44 sixpence. Simply use the same model as in the previous answer and maximize y instead of minimizing.

  4. Yes. All numbers of coins between 13 and 46 are possible. To check this, we add a loop to the model and solve it for each value between 13 and 46. The model is then as follows (see also math10a) :

    model math10a "Tommy's Birthday Coins (II)"; 
      set c := ['half-crowns', shillings, sixpence]; 
      parameter v{c}  := [30,12,6]; 
        NrCoins := 12; 
      integer variable x{c} [1..50]; 
      constraint 
        V: sum{c} v*x = 20*12 + 5*12 + 6; 
        N: sum{c} x = NrCoins; 
      while NrCoins<=47 do 
        solve; 
        if GetSolverStatus=7 then 
          Write('%3d : x =%3d' n', NrCoins, {c}x); 
        else 
          Write('%3d number of coins (not solvable)' n', NrCoins); 
        end 
        NrCoins := NrCoins+1; 
      end 
    end

    GetSolverStatus() is a function in LPL that returns the status of the solver. If it is 7 then the model was solved to optimality (check the LPL manual for other values). The loop begins with 12 coins and ends with 47 coins as we know already that 13 is the smallest and 46 is the largest number. This confirms again that indeed for 12 and 47 coins the problem is not solvable.

References

[1]   Nolan Clare. http://www.chlond.demon.co.uk/academic/puzzles.html.

[2]   Clarke L.H. Fun with Figures. William Heinemann Ltd., 1954.

[3]   MatMod. Homepage for Learning Mathematical Modeling :  https://matmod.ch.

[4]   Hürlimann T. Reference Manual for the LPL Modeling Language, most recent version. https://matmod.ch/lpl/doc/manual.pdf.