Number Theory · Chapter 28

Miscellaneous Number Theory

Palindromes, coin problems and a grab bag of number-theory tricks: pair numbers up, find the largest total two coins can't make, and spot patterns in digits and grids.

What's this chapter about?

28.1 Palindromes
28.2 Chicken McNugget Theorem
28.3 Practice Problems

You'll need

open on YouTube

28.10%

Palindromes

In this section you will be able to build palindromes digit by digit, and use their place values to find means and divisibility.

Pair $101$ with $999$ , then $111$ with $989$ , then $121$ with $979$ . Every pair adds to $1100$ , so each pair averages $550$ . That is the mean of all three-digit palindromes, with no big sum needed.

A palindrome is fixed by its first half. The second half just copies it in mirror order. So a three-digit palindrome $\overline{aba}$ has $9 \cdot 10 = 90$ choices.

Look: write a palindrome in place values. $\overline{aba} = 101a + 10b$ and $\overline{abba} = 1001a + 110b$ . Since $1001 = 7 \cdot 11 \cdot 13$ and $110 = 10 \cdot 11$ , every four-digit palindrome is a multiple of $11$ .

Exploreplay first, formulas later

Try this: Turn on Pair with its complement. Change the digits: does palindrome + complement ever change? So what is the mean?
Try this: Set 4 digits and test divisibility by 11. Why does a 4-digit palindrome always divide by 11? Show the formula and read the place values.
Try this: Keep 4 digits and test 7 instead. Which middle digits make it work?

Name it

Definition 28.1.1 · Palindrome

A palindrome is a number that reads the same forward and backward, such as $777$ , $383$ or $15951$ .

Watch itpredict, then reveal

Example 28.1

AIME

Find the arithmetic mean of all the three-digit palindromes. (Recall that a palindrome is a number that reads the same forward and backward, such as $777$ or $383$ .)

1
A three-digit palindrome looks like $\overline{aba}$ . You choose $a$ (not $0$ ) and $b$ . How many three-digit palindromes are there?

Predict first:
Your prediction

Try it

Problem 28.3.2

AMC 10

Driving along a highway, Megan noticed that her odometer showed $15951$ (miles). This number is a palindrome: it reads the same forward and backward. Then $2$ hours later, the odometer displayed the next higher palindrome. What was her average speed, in miles per hour, during this $2$ -hour period?

Problem 28.3.3

AMC 10

A palindrome, such as $83438$ , is a number that remains the same when its digits are reversed. The numbers $x$ and $x + 32$ are three-digit and four-digit palindromes, respectively. What is the sum of the digits of $x$ ?

Problem 28.3.8(additional)

AMC 10

How many $7$ -digit palindromes (numbers that read the same backward as forward) can be formed using the digits $2, 2, 3, 3, 5, 5, 5$ ?

Contest cornerreal contest problems

Problem 28.3.7(additional)

AMC 10/12

A palindrome between $1000$ and $10{,}000$ is chosen at random. What is the probability that it is divisible by $7$ ?

digits4

divide by7

Tap a solid slot to change it. Dashed slots copy their mirror twin.

1,001 = 7 × 143: divisible by 7.

Divisible by 7: ? (hidden until the end of the example) of 90 4-digit palindromes

9 × 10 = 90 4-digit palindromes

9 \times 10^{1} = 90

Place value: $\overline{abba} = 1001a + 110b$

Problem 28.3.10(additional)

AMC 12

A palindrome is a nonnegative integer number that reads the same forwards and backwards when written in base $10$ with no leading zeros. A $6$ -digit palindrome $n$ is chosen uniformly at random. What is the probability that $\dfrac{n}{11}$ is also a palindrome?

digits6

divide by11

Tap a solid slot to change it. Dashed slots copy their mirror twin.

123,321 = 11 × 11,211: divisible by 11.

Divisible by 11: 900 of 900 6-digit palindromes

9 × 10 × 10 = 900 6-digit palindromes

9 \times 10^{2} = 900

Place value: $\overline{abccba} = 100001a + 10010b + 1100c$

Checkpoint for section 28.1

Get 2 of 3 right to master this section. One try each, no hints.

28.20%

Chicken McNugget Theorem

In this section you will be able to find the largest total two coin sizes can't make, and count the totals they miss.

You only have $3$ -cent and $5$ -cent coins. You can pay $8$ , $9$ and $10$ cents. Then you can pay everything after that: just add another $3$ . So $7$ is the largest amount you can never pay.

With two coin sizes $a$ and $b$ that share no factor, the largest amount you can’t make is $ab - a - b$ . Once you can make $a$ amounts in a row, adding $a$ again and again reaches every larger amount.

Look: if $a$ and $b$ share a factor, like $4$ and $6$ , every total is even. Then infinitely many amounts are missed, and the theorem does not apply.

The last example in this section is a different kind of number puzzle: spot a digit pattern in small cases first.

Exploreplay first, formulas later

Try this: Predict the largest total you can't make with 3 and 5 before you fill in. Then press Fill in what you can make.
Try this: Count the gaps for 3 and 5, then for 4 and 7. Is it (a − 1)(b − 1)/2 each time?
Try this: In Hamlet the total is 13h + 5c. Set the packs to 13 and 5: which of 41, 47, 59, 61, 66 is stuck?

Name it

Theorem 28.2.1 · Chicken McNugget Theorem

If $a$ and $b$ are relatively prime positive integers, the largest number that cannot be written as a sum of non-negative multiples of $a$ and $b$ is

ab - a - b.

Moreover, exactly

\frac{(a - 1)(b - 1)}{2}

positive integers cannot be written in the form $ma + nb$ with $m$ and $n$ non-negative integers.

Remark 28.2.2

This theorem is useful for problems like "the largest amount of money that can't be made with $3$ -cent and $5$ -cent coins".

Watch itpredict, then reveal

Example 28.2

AMC 10

The town of Hamlet has $3$ people for each horse, $4$ sheep for each cow, and $3$ ducks for each person. Which of the following could not possibly be the total number of people, horses, sheep, cows, and ducks in Hamlet?

(A) $41$
(B) $47$
(C) $59$
(D) $61$
(E) $66$

1
Say there are $h$ horses and $c$ cows. Then there are $3h$ people. How many ducks are there for each horse?

Predict first:
Your prediction

Example 28.3

AMC 10

The product $(8)(888\ldots8)$ , where the second factor has $k$ digits, is an integer whose digits have a sum of $1000$ . What is $k$ ?

(A) $901$
(B) $911$
(C) $919$
(D) $991$
(E) $999$

Try small cases first.

$k$	product	digit sum
$1$	$8 \cdot 8 = 64$	$10$
$2$	$8 \cdot 88 = 704$	$11$
$3$	$8 \cdot 888 = 7104$	$12$
$4$	$8 \cdot 8888 = 71104$	$13$

What is $8 \cdot 88888$ ?

Predict first:

Contest cornerreal contest problems

Problem 28.3.13(additional)

AIME

Ninety-four bricks, each measuring $4'' \times 10'' \times 19''$ , are to be stacked one on top of another to form a tower $94$ bricks tall. Each brick can be oriented so it contributes $4''$ or $10''$ or $19''$ to the total height of the tower. How many different tower heights can be achieved using all ninety-four of the bricks?

Problem 28.3.16(additional)

AIMEChallenge

Find the sum of all positive integers $n$ such that, given an unlimited supply of stamps of denominations $5$ , $n$ , and $n + 1$ cents, $91$ cents is the greatest postage that cannot be formed.

pack a5

pack b24

pack c25

Predict first: which numbers can you make? Then fill in.

check a number11

11 can't be made from packs of 5, 24 and 25

Find the largest total you can't make.

Checkpoint for section 28.2

Get 2 of 3 right to master this section. One try each, no hints.

Stamps come in $4$ -cent and $7$ -cent values. What is the largest postage that cannot be made?

How many positive integers cannot be written as $5m + 8n$ with $m, n$ non-negative integers?

In Coinland, coins are worth $6$ , $10$ and $15$ cents. There is no formula for three coins, so use the grid below. What is the most expensive item that cannot be paid for exactly?

28.3

Practice Problems

In this section you will be able to mix palindromes, coin problems, games and digit patterns on contest problems.

These problems don’t share one big idea. They share a habit: try small cases, find the pattern, then prove it.

Write out the first few rows, piles or squares before you compute anything big. Spirals, games and floor sums all repeat in a way you can see after a few steps.

Contest cornerreal contest problems

Problem 28.3.1

AMC 12B

Suppose

2 + \cfrac{1}{1 + \cfrac{1}{2 + \cfrac{2}{3 + x}}} = \frac{144}{53}.

What is the value of $x$ ?

Problem 28.3.4

AMC 10

Mr. Zhou places all the integers from $1$ to $225$ into a $15$ by $15$ grid. He places $1$ in the middle square (eighth row and eighth column) and places other numbers one by one clockwise, as shown in part in the diagram below. What is the sum of the greatest number and the least number that appear in the second row from the top?

Problem 28.3.5

AMC 10/12

A set of numbers is called sum-free if whenever $x$ and $y$ are (not necessarily distinct) elements of the set, $x + y$ is not an element of the set. For example, $\{1, 4, 6\}$ and the empty set are sum-free, but $\{2, 4, 5\}$ is not. What is the greatest possible number of elements in a sum-free subset of $\{1, 2, 3, \ldots, 20\}$ ?

Problem 28.3.6

AMC 12Challenge

Let $d(n)$ denote the number of positive integers that divide $n$ , including $1$ and $n$ . For example, $d(1) = 1$ , $d(2) = 2$ , and $d(12) = 6$ . (This function is known as the divisor function.) Let

f(n) = \frac{d(n)}{\sqrt[3]{n}}.

There is a unique positive integer $N$ such that $f(N) > f(n)$ for all positive integers $n \ne N$ . What is the sum of the digits of $N$ ?

Problem 28.3.9(additional)

AIME

Alice and Bob are playing a game with $n$ coins in a pile. Every turn, a player can take $1$ or $4$ coins from the pile, and Alice goes first. The player that takes the last coin wins. How many values of $n$ less than or equal to $2024$ are there such that no matter what Alice does, Bob has a winning strategy?

Problem 28.3.11(additional)

AMC 10

What is the ones digit of the sum

\lfloor \sqrt{1} \rfloor + \lfloor \sqrt{2} \rfloor + \lfloor \sqrt{3} \rfloor + \cdots + \lfloor \sqrt{2025} \rfloor?

(Recall that $\lfloor x \rfloor$ represents the greatest integer less than or equal to $x$ .)

Problem 28.3.12(additional)

AMC 10

This problem also appears in the book as 21.3.18.

Joey and Chloe and their daughter Zoe all have the same birthday. Joey is $1$ year older than Chloe, and Zoe is exactly $1$ year old today. Today is the first of the $9$ birthdays on which Chloe's age will be an integral multiple of Zoe's age. What will be the sum of the two digits of Joey's age the next time his age is a multiple of Zoe's age?

Problem 28.3.14(additional)

AMC 10

Let $N$ be the positive integer $7777\ldots777$ , a $313$ -digit number where each digit is a $7$ . Let $f(r)$ be the leading digit of the $r$ th root of $N$ . What is

f(2) + f(3) + f(4) + f(5) + f(6)?

Problem 28.3.15(additional)

AMC 10

An array of numbers is constructed beginning with the numbers $-1 \quad 3 \quad 1$ in the top row. Each adjacent pair of numbers is summed to produce a number in the next row. Each row begins and ends with $-1$ and $1$ , respectively.

\begin{array}{ccccccccc} & & -1 & & 3 & & 1 & & \\ & -1 & & 2 & & 4 & & 1 & \\ -1 & & 1 & & 6 & & 5 & & 1 \end{array}

If the process continues, one of the rows will sum to $12{,}288$ . In that row, what is the third number from the left?