To solve this puzzle, you need to use a formula associated with J J Sylvester and the Frobenius money changing problem. In that case, we assume that we have two distinct (integral) coin denominations, p and q. We also assume that p and q have no common factor, that is, that they are relatively prime. Under these assumptions, "almost every" positive integer can be formed by combinations of p's and q's. The number of missing values will be
( p - 1 ) ( q - 1 ) / 2and the largest missing value will be
( p - 1 ) ( q - 1 ) - 1
The Byzantine basketball problem is similar to the money changing problem, as long as we think about the basketball score as being the amount of change we need to assemble, and the two scoring moves as being the two denominations we can use to assemble the change.
So let t be the value of the free throw, and g be the value of a field goal. We are told that the number of impossible scores is finite; therefore we can deduce that the two values are relatively prime.
We don't know that 58 is the largest unattainable score, but we do know that there are 35 unattainable scores. Sylvester's formula for the quantity M of unattainable values is
( t - 1 ) ( g - 1 ) / 2 = Mor, from our data:
( t - 1 ) ( g - 1 ) / 2 = 35or:
( t - 1 ) ( g - 1 ) = 70
Factor pairs of 70 are (1,70), (2,35), (5,14), (7,10), giving us possible (t,g) pairs of (2,71), (3,36), (6,15) and (8,11). But we know that t and g must be coprime, which leaves us with (2,71) or (8,11). Since we are told that the score of 58 cannot be attained, the pair (2,71) is not acceptable, since we could use 29 free throws of two points to reach 58. Therefore, the only acceptable pair is (8,11). A free throw is worth 8 points, and a field goal 11 points.
This puzzle is from "Litton's Problematical Recreations".References:
For the Ruthenian postage stamp question, we can use the results of the first puzzle. Note that 9 and 20 are relatively prime, and that therefore, just using 9 and 20 croc stamps, we are guaranteed to form every sum that is greater than (9-1)*(20-1)-1 = 151, and we cannot form 151 in this way. Also, there are 75 numbers that cannot be formed with just 9 and 20 croc stamps.
Since we also have a 6 croc stamp, perhaps we can form 151 with its help. In fact, 151 = 2*6+11*9+2*20, so the biggest number we can't form must be strictly less than 151.
If we realize that 6 = 3*2 and 9 = 3*3, we can see that this implies that 6 and 9 can make all but one multiple of 3 (namely, 3 itself).
At this point, one can try a simple exhaustive technique, and discover that the number 43 is the largest sum that cannot be formed by any (nonnegative) combination of Ruthenian stamps.
Back to The Byzantine Basketball Puzzle.
You can go back to the main puzzle page.