06/08/2020 (2011: National Sprint Round, Problem 24)

Q: Boxes are arranged in a 20-layer tower. The top layer has three boxes, and each subsequent layer has one more than twice the number of boxes in the layer above it. If 2^n is the largest power of two that is a factor of the total number of boxes, what is the value of n?

A: 3

Let's say the top layer has 1, that means the second layer has 2(1) + 1 = 3 boxes, the third layer has 2(3) + 1 = 7 boxes, the fourth layer has 2(7) + 1 = 15 boxes, the fifth layer has 2(15) + 1 = 31 boxes, the sixth layer has 2(31) + 1 = 63 boxes, seventh layer has 2(63) + 1 = 127 boxes, eight layer has 2(127) + 1 = 255 boxes, ninth layer has 2(255) + 1 = 511 boxes, 10th layer has 2(511) + 1 = 1023 boxes. As you can tell, each number is 1 less than a power of 2, starting from 2^2 - 1. That means we are adding 2^2 through 2^21 together and subtracting 20.

We know that 2^0 + 2^1 + 2^2 + 2^3 +... + 2^x = 2^(x+1) - 1, so that means that 2^0 + ... + 2^20 = 2^21 - 1, so 2^2 + ... + 2^20 = 2^21 - 4, but we're finding 20 less than that, so we get:  2^21 - 24. We find the greatest value of n in "2^n" that can divide 24, because we know that 2^21 > 24, and that 24 is divisible by fewer 2s than 2^21. 24 is divisible by 2^3, so the largest power of 2 that is a factor of the boxes is 2^3, making the answer 3.