Problem

Source: Thailand Mathematical Olympiad 2015 p10

Tags: combinatorics



A Boy Scouts camp holds a campfire. The camp has scarfs of m colors with n scarves of each color, and gives each of its $mn$ scouts a scarf, where $m, n \ge 2$ are integers. The camp then divides its scouts into troops by the color of their scarfs. At the beginning of the campfire, the scouts are seated in a circle so that scouts in the same troop are seated next to each other. The camp organizer then proceeds to select, round by round, representatives to perform a show, with the following conditions: there must be at least two representatives in each round, they must come from the same troop, and any specific set of representatives can only perform once. (For example, if $\{A, B\}$ has performed, then $\{A, B\}$ cannot perform again, but $\{A, B, C\}$ can still perform.) This process is repeated until all valid sets of representatives have performed. At this point, the organizers order each scout to hand their scarfs to the scout to the left, and re-group the scouts into troops, again according to their scarf color, and the process above is resumed, until the set of valid sets of representatives is exhausted again. (The sets of representatives after re-grouping must also be distinct from the sets before re-grouping.) When that happens, the organizers order another re-group, and resumes the process, and this repeats until there can be no further performances. Find, in simple form, the total number of performances that will be performed.