Maths Olympiad Prep

Library / /363 of 860

Algebra Difficulty 5.1 AIME, harder Find the answer

Let SS be the set of integers of the form 2x+2y+2z2^{x}+2^{y}+2^{z}, where x,y,zx, y, z are pairwise distinct non-negative integers. Determine the 100th smallest element of SS.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

S is the set of positive integers with exactly three ones in its binary representation. The number of such integers with at most dd total bits is (d3)\binom{d}{3},andnotingthat(93)=84, and noting that \binom{9}{3}=84 and (103)=120\binom{10}{3}=120, we want the 16th smallest integer of the form 2^{9}+2^{x}+2^{y},where, where y<x<9.Ignoringthe. Ignoring the 2^{9}term,thereare(d2) term, there are \binom{d^{\prime}}{2} positive integers of the form 2x+2y2^{x}+2^{y} with at most dd^{\prime} total bits. Because (62)=15\binom{6}{2}=15,ouransweris, our answer is 2^{9}+2^{6}+2^{0}=577$. (By a bit, we mean a digit in base 2 .)

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.