Byzantine Basketball

The problem of Byzantine Basketball with solution was sent to me by Prof. W. McWorter:

Byzantine Basketball is like regular basketball except that foul shots are worth a points instead of two points and field shots are worth b points instead of three points. Moreover, in Byzantine Basketball there are exactly 35 scores that never occur in a game, one of which is 58. What are a and b?

|Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny

Byzantine Basketball is like regular basketball except that foul shots are worth a points instead of two points and field shots are worth b points instead of three points. Moreover, in Byzantine Basketball there are exactly 35 scores that never occur in a game, one of which is 58. What are a and b?

Solution

Without difficulty one can see that, for there to be only finitely many scores that never occur, a and b must be relatively prime positive integers. All scores have the form ax + by, where x and y are nonnegative integers. Let's say a nonnegative integer c is representable if c has the form ax + by, with x and y nonnegative integers, and c nonrepresentable otherwise. We count the number of nonrepresentable integers. The plan is to show that (a - 1)(b - 1) - 1 is the largest nonrepresentable nonnegative integer, and that exactly half the integers in the interval [0, (a - 1)(b - 1) - 1] comprise all nonrepresentable nonnegative integers.

First we show that all integers greater than (a - 1)(b - 1) - 1 are representable. Any such integer can be written (a-1)(b-1)-1 + c, for some c > 0. Since a and b are relatively prime, c can be written c = au + bv, where -b < u ≤ 0 and v > 0 (see Remark 1.) Thus,

(a - 1)(b - 1) - 1 + c = a(b - 1) - b + c = a(b - 1) - b + au + bv = a(b - 1 + u) + b(-1 + v).

The restrictions on u and v insure that b - 1 + u ≥ 0 and -1 + v ≥ 0. Hence (a - 1)(b - 1) - 1 + c is representable, and so all integers greater than (a - 1)(b - 1) - 1 are representable.

Next, we show that (a - 1)(b - 1) - 1 is not representable. Suppose that (a - 1)(b - 1) - 1 = ax + by, for some nonnegative x and y. Then

ax + by = (a - 1)(b - 1) - 1 = a(b - 1) - b.

Hence a(b - 1 - x) = b(y + 1). Since x ≥ 0, and y ≥ 0, we have y + 1 > 0 and b - 1 - x is positive and less than b. Hence, since a and b are relatively prime, b divides b - 1 - x, a contradiction. Thus (a - 1)(b - 1) - 1 is not representable, and, with the previous paragraph, it is the largest nonrepresentable integer.

Finally, we show that exactly half the integers between 0 and (a - 1)(b - 1) - 1 are nonrepresentable. We show this by showing that the map f(c) = (a - 1)(b - 1) - 1 - c interchanges representable integers with nonrepresentable integers (see Remark 2.) If c is representable and f(c) is representable, then so is (a - 1)(b - 1) - 1 = c + f(c), contradiction. Hence f(c) is nonrepresentable if c is representable. Now suppose c is nonrepresentable. Then, since a and b are relatively prime, there are integers u and v such that c = au + bv, with 0 ≤ u < b (see Remark 1) and v < 0 (c nonrepresentable forces v < 0). Hence

f(c) = (a - 1)(b - 1) - 1 - c = a(b - 1) - bau - bv = a(b - 1 - u) + b(-1 - v).

The restrictions on u and v imply that b - 1 - u ≥ 0 and -1 - v ≥ 0, whence f(c) is representable.

Well, that just about does it. Now we know that there are exactly (a - 1)(b - 1)/2 nonrepresentable integers. Hence (a - 1)(b - 1)/2 = 35. This implies that a = 2, b = 71; a = 3, b = 36; a = 6, b = 15; or a = 8, b = 11. The second two possibilities are out because a and b are not relatively prime. a = 2 and b = 71 is out because 58 is representable. Hence a = 8 and b = 11, and, for these values, 58 is nonrepresentable.

Remark 1

c = ax + by, for some integers x and y, then c = a(x + bt) + b(y - at), for every integer t. Hence, for some t, x + bt is between 0 and b - 1, and, for some other t, x + bt is between -b + 1 and 0. In short, there is always a choice for x which is a residue modulo b.

Remark 2

The function f maps [0, (a - 1)(b - 1) - 1] onto itself.

Remark 3

The problem was included into the Putnam 1971 competition. Two of its solutions appear in Mathematical Gems, II, by Ross Honsberger (MAA, 1976).

|Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny

72112863