A castle has infinitely many rooms labeled $1,2,3, \ldots$, which are divided into several halls. Suppose room $n$ is on the same hall as rooms $3 n+1$ and $n+10$ for every $n$. Determine the maximum possible number of different halls in the castle.
There are at most three different halls in the castle. Because rooms $n$ and $n+10$ are on the same hall, any two rooms with the same units digit must be on the same hall.

Now, repeatedly using the rule that rooms $n$ and $3 n+1$ are on the same hall, we find that room 1 is on the same hall as rooms 4, 13, and 40, and 121, so all rooms with units digit $0,1,3$, or 4 are on the same hall. There need not be any other rooms on this hall, since whenever $n$ has units digit in this set, so does $3 n+1$, and so does $(n-1) / 3$, if it is a whole number.

Similarly, room 2 is on the same hall as rooms 7 and 22 , so all rooms with units digit 2 or 7 are on the same hall, and there need not be any other rooms on this hall. Finally, rooms 5, 16, 49, and 148 are on the same hall, so all rooms with units digit $5,6,8$ or 9 are on the same hall. Thus, we see that there are at most three different halls in the castle.