We say that two non-negative integers are related if their sum uses only the digits 0 and 1. For example 22 and 79 are related. Let A and B be two infinite sets of non-negative integers such that: (1) if a ∈ A and b ∈ B, then a and b are related, (2) if c is related to every member of A, then it belongs to B, (3) if c is related to every member of B, then it belongs to A. Show that in one of the sets A, B we can find an infinite number of pairs of consecutive numbers.
Solution
Suppose there is a member of A with last digit d. Then every member of B must have one of two possible last digits. Suppose there are members of B with both possibilities. Then every member of A must have last digit d. So either every member of A has the same last digit or every member of B has the same last digit (or both). Suppose every member of A has the same last digit d.
But now if n belongs to B and n + d has last digit 0, then n+1 + d has last digit 1. Moreover, if m is any member of A, then m+n has last digit 0 and other digits all 0 or 1. Hence m+n+1 last last digit 1 and other digits all 0 or 1, so n+1 must also belong to B. Similarly, if n is in B and n+d has last digit 1, then n-1 must also belong to B. So in either case there are infinitely many pairs of consecutive numbers in B.
© John Scholes
jscholes@kalva.demon.co.uk
31 July 2002