AMC 10 · 2011 · #19

Grade 11 number-theoryalgebra

Archetype Small-Domain Constrained Search └ Sub-archetype Factor / Divisibility Constraint

floor-functionlogarithm-propertiesexponents convert-to-algebrabound-inequality-then-enumerate ↑ Prerequisites: exponents

📏 Long solution 💡 3 insights

Problem

A count built from a rounded logarithm comes out to a fixed number. Add the two smallest sizes that do it.

Pick an answer.

(A)

(B)

(C)

154

(D)

406

(E)

1024

How to solve

Strategy Introduce a Variable

Tool #4 (Introduce a Variable): the logarithm and the floor bar are the only hard part, and naming m=⌊log₂(N-1)⌋ trades them for two plain inequalities on N. Tool #15 (Organize Information in More Ways): once the log is gone the formula reads as a sentence — the elite count is the distance from N up to the next power of two — and that reading makes the whole problem visible at once. Tool #14 (Extreme Principle): the question asks for the two smallest N, so the real work is finding the first block that is wide enough to hold a gap of 19; that boundary is where the answer lives. Tool #3 (Eliminate Possibilities): the naive candidate list contains fake solutions that must be thrown out, and the answer choices give a second, independent way to confirm the survivor.

1STEP 1

Name the exponent, kill the log

Naming the exponent removes the logarithm.

m=⌊log₂(N-1)⌋ ⇔ 2^m ≤ N-1 ＜ 2^m+1 ⇔ 2^m+1 ≤ N ≤ 2^m+1, and then 2¹+⌊log₂(N-1)⌋-N=2^m+1-N

2STEP 2

Read the formula in plain words

In words, it is the gap to the next power of two.

elite(N)=(smallest power of 2 that is ≥ N)-N

3STEP 3

Set the count to 19

Setting the count gives one candidate per exponent.

2^m+1-N=19 ⟹ N=2^m+1-19

4STEP 4

Check m against its own block

One candidate falls outside its own block and is fake.

2^m+1 ≤ 2^m+1-19 ⇔ 2^m ≥ 20 ⇔ m ≥ 5; and m=4 gives the fake candidate N=13, whose real elite count is 16-13=3

5STEP 5

The two smallest legal N

The two smallest real ones are 45 and 109.

m=5: N=2⁶-19=45, 2⁶-45=19; m=6: N=2⁷-19=109, 2⁷-109=19

6STEP 6

Add and match the choices

Their sum is 154, choice (C).

45+109=154 → (C)

Answer

154

Both values survive a direct test in the original formula: 2¹+⌊log₂ 44⌋-45=64-45=19 and 2¹+⌊log₂ 108⌋-109=128-109=19. Nothing smaller than 45 can work, and here is why without any candidate list. If N ≤ 32, then N sits in a block with m ≤ 4, where the elite count is at most 2⁴-1=15, too small to be 19. If 33 ≤ N ≤ 44, then m=5 and the elite count is 64-N ≥ 20, too big. So 45 really is the first, and the next block gives 109. The size of the sum is also sane: each N is just under a power of two, so the sum sits a bit under 64+128=192, and 154 fits while 38, 90, 406 and 1024 do not.

💡Key takeaway

The elite count is just how far N is from the next power of two, so 19 elite players means N is 19 below a power of two — and only blocks at least 20 wide can hold a gap that big.

Name the exponent, kill the log
Read the formula in plain words
Set the count to 19
Check m against its own block
The two smallest legal N
Add and match the choices