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

Copyright © 1996-2009 Alexander Bogomolny

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,

The restrictions on u and v insure that b - 1 + u0 and -1 + v0. 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

Hence a(b - 1 - x) = b(y + 1). Since x0, and y0, 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

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.

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 3

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

Copyright © 1996-2009 Alexander Bogomolny