Competition problem — Number theory

Library / /158 of 377

Number theory Difficulty 5.0 AIME, harder Prove it United States

Problem:
There are 100 houses in a row on a street. A painter comes and paints every house red. Then, another painter comes and paints every third house (starting with house number 3) blue. Another painter comes and paints every fifth house red (even if it is already red), then another painter paints every seventh house blue, and so forth, alternating between red and blue, until 50 painters have been by. After this is finished, how many houses will be red?

Solution

Solution:
House $n$ ends up red if and only if the largest odd divisor of $n$ is of the form $4k+1$ . We have 25 values of $n=4k+1$ ; 13 values of $n=2(4k+1)$ (given by $k=0,1,2,\ldots,12$ ); 7 values of $n=4(4k+1)$ ( $k=0,1,\ldots,6$ ); 3 values of $n=8(4k+1)$ ( $k=0,1,2$ ); 2 of the form $n=16(4k+1)$ (for $k=0,1$ ); 1 of the form $n=32(4k+1)$ ; and 1 of the form $n=64(4k+1)$ . Thus we have a total of $25+13+7+3+2+1+1=52$ red houses.

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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.