Question

A school has less than 5000 students and if the students are divided equally into teams of either 9 or 10 or 12 or 25 each, exactly 4 are always left out. However, if they are divided into teams of 11 each, no one is left out. The maximum number of teams of 12 each that can be formed out of the students in the school is

Accepted Answer

150. Let $N$ be the number of students, $N < 5000$. $N \equiv 4 \pmod{	ext{LCM}(9, 10, 12, 25)}$. $	ext{LCM}(9, 10, 12, 25) = 900$. So $N = 900k + 4$ for some integer $k$. Also, $N$ is divisible by 11: $$900k + 4 \equiv 0 \pmod{11}$$ $$900 \equiv 9 \pmod{11}$$ $$9k + 4 \equiv 0 \pmod{11} \implies 9k \equiv 7 \pmod{11} \implies k \equiv 2 \pmod{11}$$ Possible values of $k$: $k = 2, 13, 24, \dots$ For $k = 2$, $N = 900(2) + 4 = 1804 < 5000$. For $k = 13$, $N = 900(13) + 4 = 11704 > 5000$. So $N = 1804$. Maximum number of teams of 12 each $= \lfloor 1804 / 12 floor = 150$.

Maximum Number of Teams

Explanation

Practise this under exam conditions