Track / Stage 5 / 10 of 400 #1090 of 2444

Problem 1090

AIME late

Number theory Difficulty 5.0 Prove it Harvard-MIT Mathematics Tournament · United States

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?

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official 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.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.