At the end of the school year, a teacher wanted to give some gifts to the students. He made up a game to see who would get gifts. He lined up the children and found he had 100. He gave the first child 100 sticks. He asked him to keep one and then walk down the line and give each child a stick. After doing his duty, the first child returned to the line, never to be called on again. Then the teacher told the second child to walk down the line and take a stick from each even-numbered child starting with himself. The third child walked down the line looking only at children who were multiples of 3 and did two things. He took a stick from any child who had one, and he gave a stick to any who didn’t. The fourth child did the same thing with children who were multiples of 4, and this continued all the way to the hundredth child. The game continued in this way until every child had given or collected sticks. The teacher gave a gift to any child who still had a stick at the end of the game. How many gifts did he give out?

Hint: Look for a pattern!