Разобьём всех го­стей на упо­ря­до­чен­ные трой­ки; пер­во­му че­ло­ве­ку из трой­ки на­де­нем ци­линдр с бук­вой A, вто­ро­му  — с бук­вой Б, тре­тье­му  — с бук­вой В. Для этого по­ста­вим го­стей в ше­рен­гу (это можно сде­лать (3n)! спо­со­ба­ми), пер­вых трёх объ­еди­ним в одну трой­ку, вто­рых трёх  — в дру­гую и т. д. По­сколь­ку трой­ки можно пе­ре­став­лять внут­ри ше­рен­ги и по­лу­чать то же самое раз­би­е­ние на трой­ки, то каж­дое раз­би­е­ние по­счи­та­но n! раз. Таким об­ра­зом, ко­ли­че­ство спо­со­бов раз­бить го­стей на упо­ря­до­чен­ные трой­ки равно

Те­перь для того, чтобы раз­бить го­стей на хо­ро­во­ды, до­ста­точ­но раз­бить на хо­ро­во­ды пер­вых n че­ло­век из своих троек (эти хо­ро­во­ды могут со­сто­ять из од­но­го че­ло­ве­ка), a затем по­ста­вить после каж­до­го че­ло­ве­ка его трой­ку, что можно сде­лать един­ствен­ным об­ра­зом. До­ка­жем ин­дук­ци­ей по n, что ко­ли­че­ство спо­со­бов сде­лать это равно n!, что за­вер­шит ре­ше­ние.

База для оче­вид­на. Пусть утвер­жде­ние верно для n, до­ка­жем его для Рас­ста­вим n че­ло­век в хо­ро­во­ды, это можно сде­лать n! спо­со­ба­ми. В каж­дом раз­би­е­нии на хо­ро­во­ды n че­ло­век есть ровно место, куда можно по­ста­вить остав­ше­го­ся че­ло­ве­ка: в каж­дом су­ще­ству­ю­щем хо­ро­во­де из k че­ло­век таких мест ровно k, а ещё можно вы­де­лить этого че­ло­ве­ка в новый хо­ро­вод.

За­ме­ча­ние.

По­след­нее рас­суж­де­ние можно упро­стить, если за­ме­тить, что каж­дое раз­би­е­ние на хо­ро­во­ды со­от­вет­ству­ет пе­ре­ста­нов­ке на мно­же­стве из n эле­мен­тов, пред­став­лен­ной в форме цик­лов, а ко­ли­че­ство пе­ре­ста­но­вок, как из­вест­но, равно n!.

При­ве­дем дру­гое ре­ше­ние.

За­ну­ме­ру­ем людей чис­ла­ми от 1 до 3n. Есть как раз (3n)! спо­со­бов рас­ста­вить этих людей в ряд, по­это­му до­ста­точ­но уста­но­вить вза­им­но од­но­знач­ное со­от­вет­ствие между та­ки­ми рас­ста­нов­ка­ми и раз­би­е­ни­я­ми на хо­ро­во­ды.

Возьмём любую рас­ста­нов­ку, на­де­нем всем ци­лин­дры в по­ряд­ке АБ­ВА­БВ...АБВ слева на­пра­во. Мыс­лен­но раз­де­лим людей под­ряд на n троек. В пер­вый хо­ро­вод берём под­ряд всех людей от на­ча­ла и до той трой­ки вклю­чи­тель­но, где стоит че­ло­век с но­ме­ром 1 (и за­мы­ка­ем в хо­ро­вод); во вто­рой хо­ро­вод берём сле­ду­ю­щие трой­ки под­ряд до той вклю­чи­тель­но, где стоит че­ло­век с наи­мень­шим из остав­ших­ся но­ме­ров (и за­мы­ка­ем в хо­ро­вод), и так далее.

Об­рат­но, по на­бо­ру хо­ро­во­дов легко вос­ста­но­вить рас­ста­нов­ку: берём хо­ро­вод, где стоит че­ло­век 1, на­хо­дим трой­ку АБВ, в ко­то­рой он на­хо­дит­ся, раз­ре­за­ем хо­ро­вод сразу за этой трой­кой, вы­тя­ги­ва­ем в линию и ста­вим в на­ча­ло рас­ста­нов­ки. Далее берём че­ло­ве­ка с наи­мень­шим но­ме­ром из остав­ших­ся, на­хо­дим «его» хо­ро­вод, так же раз­ре­за­ем и под­со­еди­ня­ем к рас­ста­нов­ке и т. д.