22. Misc Number Theory · Mastering AMC 8

22.10%

Palindromes

In this section you will be able to spot palindromes and count them by choosing only the first half of the digits.

Read 383 backwards. You get 383 again! Numbers like 7, 44 and 12321 do the same trick. How many three-digit ones are there?

A palindrome is a mirror: once you pick the first half of the digits, the second half is forced. So to count palindromes, count only the first half. The first digit can’t be 0, so it has 9 choices; the others have 10.

Watch the palindromes lecture.

Exploreplay first, formulas later

Try this: Tap the first digit a few times. Which other slot changes with it? Why?
Try this: Set the length to 4, then 5. How many slots can you actually choose each time?
Try this: Why does the first slot have only 9 choices while the others have 10?
Try this: Turn on Show the formula. Predict the number of 7-digit palindromes, then check.

Name it

Definition 22.1.1 · Palindrome

A palindrome is a number that reads the same forward and backward.

For example, $7$ , $44$ , $383$ and $12321$ are palindromes, but $123$ is not.

Try it

Problem 22.5.17(additional)

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.)

Checkpoint for section 22.1

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

22.20%

Money Problems

In this section you will be able to solve coin and price puzzles by setting coins aside, splitting into cases, and writing equations.

Josh has 9 coins worth 101 cents, with at least one of each kind. Can you figure out exactly which coins are in his pocket?

Money problems have two kinds of clues: how many coins and how much they’re worth. Three tricks help:

Set aside any coins you’re told you must have, then solve the smaller problem.
Split into cases by the biggest coin, since it has the fewest choices.
Look at the last digit. Pennies are the only coins that can fix an amount ending in 1.

Exploreplay first, formulas later

Try this: Make 30 cents with as few coins as you can. Now with as many as you can.
Try this: Turn on Show every way. How many ways make 30 cents? Which coin did you decide first in each row?
Try this: Change the target to 31 cents. What must be true about the number of pennies now?

Watch itpredict, then reveal

Example 22.1

Omega Learn

Josh has some quarters, dimes, nickels and pennies worth 101 cents. He has a total of 9 coins, at least 1 of each type of coin, how many nickels and dimes does he have?

1
Is there any way we can easily simplify our problem and remove the condition of must having at least 1 of each coin?

Predict first:
Your prediction

Example 22.2

MATHCOUNTS

A restaurant sells three sizes of drinks: small for $1.20, medium for $1.30 and large for $1.80. Each person at a table of ten ordered one drink, for a total cost of $14.90, before sales tax. How many people ordered a large drink?

1
Pretend all ten people ordered a small. What would the bill be?

Predict first:
Your prediction

open on YouTube

Try it

Problem 22.5.12

Omega Learn Math Contest

Josh went to the store with a number of dollars between 50 and 100, both inclusive. He spent a third of his money on lunch. He then tipped 15 dollars. After that, he deposited two-thirds of his remaining money in his bank account. After that, he donated a fifth of his remaining money to charity. He was then left with an integer number of dollars. How many dollars did he have at the beginning?

Contest cornerreal contest problems

Problem 22.5.1

AMC 8

Loki, Moe, Nick and Ott are good friends. Ott had no money, but the others did. Moe gave Ott one-fifth of his money, Loki gave Ott one-fourth of his money and Nick gave Ott one-third of his money. Each gave Ott the same amount of money. What fractional part of the group's money does Ott now have?

Problem 22.5.2

AMC 8

You have nine coins: a collection of pennies, nickels, dimes, and quarters having a total value of $1.02, with at least one coin of each type. How many dimes must you have?

Problem 22.5.3

AMC 10A

The average value of all the pennies, nickels, dimes, and quarters in Paula's purse is 20 cents. If she had one more quarter, the average value would be 21 cents. How many dimes does she have in her purse?

Problem 22.5.4

AMC 10A

Joe has a collection of 23 coins, consisting of 5-cent coins, 10-cent coins, and 25-cent coins. He has 3 more 10-cent coins than 5-cent coins, and the total value of his collection is 320 cents. How many more 25-cent coins does Joe have than 5-cent coins?

Checkpoint for section 22.2

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

22.30%

Integer Operations

In this section you will be able to follow number machines and operations step by step, using prime factorizations and working backwards.

A machine halves even numbers and turns an odd N into 3N + 1. Feed it 7 and you get 22, 11, 34, 17, 52, 26. What goes in if 1 comes out six steps later?

Integer operation problems describe a process. Your job is to track it without doing every step by hand.

Use prime factorizations. Multiplying and dividing only change exponents, so count those.
Work backwards when you know the output. Ask “what could have come just before this?”
Averages are totals in disguise: total = average × how many.

Exploreplay first, formulas later

Try this: Start at 6 and press Run once a few times. Which rule did the machine use at each step?
Try this: Press Run to 1. How many operations did it take? Try 7 and then 27. Any pattern?
Try this: Set N to 1 and press Run once three times: 1 → 4 → 2 → 1. Is 1 a fair answer in Example 22.5?

Watch itpredict, then reveal

Example 22.3

MATHCOUNTS

John inserts some number of parentheses into the expression shown to create a valid mathematical expression. What is the smallest possible integer value of John's expression?

1 \div 2 \div 3 \div 4 \div 5 \div 6 \div 7 \div 8 \div 9 \div 10

1
However you place the parentheses, every number ends up either on top (numerator) or on the bottom (denominator). Where must 1 and 2 always go?

Predict first:

open on YouTube

Example 22.4

Omega Learn

Sohil has received a new TI-84 Calculator from MATHCOUNTS. He is very excited, so he enters the following expression $2^6 \times 3^5 \times 5^7$ into the calculator. On any given operation, Sohil will divide the number by it's largest prime factor, $p$ . Then, he will multiply the number by $p - 1$ . He continues this process until he reaches a final number of 1. How many operations, including the final operation, will it take for this to happen?

A smaller twin: try the machine on $2^2 \cdot 3 \cdot 5^2$ first.

1
To start, what prime number will divide our number first?

Predict first:
Your prediction

Example 22.5

AMC 8

When a positive integer $N$ is fed into a machine, the output is a number calculated according to the rule shown below.

Input	Output
$N$ is even	$\frac{N}{2}$
$N$ is odd	$3N + 1$

For example, starting with an input of $N = 7$ , the machine will output $3 \cdot 7 + 1 = 22$ . Then if the output is repeatedly inserted into the machine five more times, the final output is 26.

7 \to 22 \to 11 \to 34 \to 17 \to 52 \to 26

When the same 6-step process is applied to a different starting value of $N$ , the final output is 1. What is the sum of all such integers $N$ ?

N \to \underline{\quad} \to \underline{\quad} \to \underline{\quad} \to \underline{\quad} \to \underline{\quad} \to 1

The machine on the book's example, starting from 7.

1
Work backwards. Which numbers go into the machine and come out as $1$ ?

Predict first:
Your prediction

open on YouTube

Try it

Problem 22.5.7

AMC 10A

Mr. Patrick teaches math to 15 students. He was grading tests and found that when he graded everyone's test except Payton's, the average grade for the class was 80. After he graded Payton's test, the test average became 81. What was Payton's score on the test?

Problem 22.5.5

AMC 8

Isabella must take four 100-point tests in her math class. Her goal is to achieve an average grade of 95 on the tests. Her first two test scores were 97 and 91. After seeing her score on the third test, she realized she can still reach her goal. What is the lowest possible score she could have made on the third test?

Problem 22.5.20(additional)

MATHCOUNTS

If C is a digit such that the product of the three-digit numbers 2C8 and 3C1 is the five-digit number 90C58, what is the value of C?

Problem 22.5.16(additional)

MATHCOUNTS

What fraction of the first 100 triangular numbers are evenly divisible by 7? Express your answer as a common fraction.

Contest cornerreal contest problems

Problem 22.5.6

AMC 8

Laila took five math tests, each worth a maximum of 100 points. Laila's score on each test was an integer between 0 and 100, inclusive. Laila received the same score on the first four tests, and she received a higher score on the last test. Her average score on the five tests was 82. How many values are possible for Laila's score on the last test?

Problem 22.5.8

AMC 8

Each of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9 is used only once to make two five-digit numbers so that they have the largest possible sum. Which of the following could be one of the numbers?

(A) 76531 (B) 86724 (C) 87431 (D) 96240 (E) 97403

Problem 22.5.9

Laura added two three-digit positive integers. All six digits in these numbers are different. Laura's sum is a three-digit number $S$ . What is the smallest possible value for the sum of the digits of $S$ ?

Problem 22.5.10

AMC 8

What is the largest power of 2 that is a divisor of $13^4 - 11^4$ ?

Checkpoint for section 22.3

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

22.40%

Chicken McNugget Theorem

In this section you will be able to find the largest amount you can't make from two coin sizes with ab − a − b.

Your country only makes 3-cent and 5-cent coins. You can pay 8 cents or 11 cents exactly. What’s the biggest price you can never pay exactly?

Once you can make $a$ numbers in a row, you can make everything after them: just add one more $a$ -coin. The Chicken McNugget theorem tells you exactly where the gaps stop, as long as the two sizes share no common factor.

Exploreplay first, formulas later

Try this: With 3-cent and 5-cent coins, predict: which numbers up to 15 can you make? Then press Fill in.
Try this: Look at the last crossed-out number. After it, can you make every number? Why do three in a row help?
Try this: Try packs of 4 and 7, then 5 and 8. Predict the largest gap before you press Show the largest gap.
Try this: Now try 6 and 9. Why does it never stop having gaps?

Name it

Theorem 22.4.1 · Chicken McNugget Theorem

The maximum value that cannot be expressed as the sum of non-negative multiples of $a$ and $b$ is

ab - a - b

if $a$ and $b$ are relatively prime.

For relatively prime positive integers $a, b$ , there are exactly

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

positive integers which cannot be expressed in the form $ma + nb$ where $m$ and $n$ are non-negative integers.

Checkpoint for section 22.4

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

22.5

Practice Problems

In this section you will be able to mix every trick from this chapter on contest puzzles.

Time for logic puzzles! Read every clue, use the one that pins things down first, and check your answer against all the others.

Want every problem from this chapter on one page? Open the problem set.

Contest cornerreal contest problems

Problem 22.5.11

AMC 8

Students guess that Norb's age is 24, 28, 30, 32, 36, 38, 41, 44, 47, and 49. Norb says, "At least half of you guessed too low, two of you are off by one, and my age is a prime number." How old is Norb?

Problem 22.5.13

AMC 8

In a tournament there are six teams that play each other twice. A team earns 3 points for a win, 1 point for a draw, and 0 points for a loss. After all the games have been played it turns out that the top three teams earned the same number of total points. What is the greatest possible number of total points for each of the top three teams?

Problem 22.5.14

Omega Learn Math Contest

Bryan chooses a number between 1 and 1000. He gives a few conditions about the number:

The number has no prime factors greater than 5
The number is not a perfect power (of anything greater than 1)
The number has 6 positive factors
The number leaves a remainder of 5 when divided by 7

Find the sum of all possible numbers Bryan could choose based on the conditions.

Problem 22.5.15(additional)

MATHCOUNTS

In eight games this season, Kelly's basketball team scored 22, 30, 33, 44, 50, 55, 61 and 66 points, respectively. They exactly tripled their opponent's score three times and exactly doubled their opponent's score three times. They lost two games by 4 points each. How many points did their opponents score altogether?

Problem 22.5.18(additional)

AMC 8

The grid below is to be filled with integers in such a way that the sum of the numbers in each row and the sum of the numbers in each column are the same. Four numbers are missing. The number $x$ in the lower left corner is larger than the other three missing numbers. What is the smallest possible value of $x$ ?

Problem 22.5.19(additional)

AMC 8

A scientist walking through a forest recorded as integers the heights of 5 trees standing in a row. She observed that each tree was either twice as tall or half as tall as the one to its right. Unfortunately some of her data was lost when rain fell on her notebook. Her notes are shown below, with blanks indicating the missing numbers. Based on her observations, the scientist was able to reconstruct the lost data. What was the average height of the trees, in meters?

Tree	Height
Tree 1	___ meters
Tree 2	11 meters
Tree 3	___ meters
Tree 4	___ meters
Tree 5	___ meters
Average height	___.2 meters

Problem 22.5.21(additional)

Omega Learn

I am thinking of a number between 1000 and 9999, inclusive. It satisfies the following conditions

The digits strictly increase from left to right
The sum of the 1st and 2nd digits equals the 3rd digit
The 2nd digit is 1 or 2 more than the first digit
The sum of the first 3 digits is greater than the 4th digit
When the number is squared, the units digit is 1
The number is divisible by 37

What number am I thinking of?