2024 AMC 10B Problem 16

Question

Jerry likes to play with numbers. One day, he wrote all the integers from

1

to

2024

on the whiteboard. Then he repeatedly chose four numbers on the whiteboard, erased them, and replaced them by either their sum or their product. (For example, Jerry’s first step might have been to erase

1,

2,

3,

and

5,

and then write either

11,

their sum, or

30,

their product, on the whiteboard.) After repeatedly performing this operation, Jerry noticed that all the remaining numbers on the whiteboard were odd. What is the maximum possible number of integers on the whiteboard at that time?

1010

1011

1012

1013

1014

Answer: A

Concepts:parity invariant optimization

Difficulty rating: 1800

Small hint:

Each move turns

4

numbers into

1,

so the count drops by

3;

maximizing the count means minimizing the moves

Big hint:

There are

1012

even entries, and any move decreases their number by at most

3

Solution:

Among

1, \ldots, 2024

there are

1012

even numbers and

1012

odd numbers. Each operation replaces

4

entries by

1,

so the total count falls by

3.

If a move consumes

e

even entries, its output is either odd, reducing the even count by

e,

or even, reducing it by

e-1.

In either case the even count falls by at most

3.

Therefore eliminating all

1012

even entries takes at least

\lceil\frac{1012}{3}\rceil=338

moves. This is achievable: use

337

sums containing one odd and three evens, then one sum containing three odds and the final even. Every output is odd. Thus the maximum remaining count is

2024-3\cdot338=1010.

Therefore, the answer is A.