Problem:
Let be the number of positive integers that are less than or equal to and whose base- representation has more 's than 's. Find the remainder when is divided by .
Solution:
Since , the integers in question have at most digits in base . Since the base- representation of a positive integer must begin with , the number of -digit numbers with exactly 's is . The number of 's exceeds the number of 's if and only if , or . Thus the number of integers whose base- representation consists of at most digits and that have more 's than 's is the sum of the entries in rows through in Pascal's Triangle that are on or to the right of the vertical symmetry line. The sum of all entries in these rows is , and the sum of the center elements is , so the sum of the entries on or to the right of the line is . The integers less than and greater than all have at least six 's, because they are all greater than , which is in base , so they have all been included in the total. Thus the required number is , whose remainder upon division by is .
The problems on this page are the property of the MAA's American Mathematics Competitions