Maths Olympiad Prep

Library / /65 of 106

Combinatorics Difficulty 8.5 Shortlist Find the answer

Let n>0n > 0 be an integer. We are given a balance and nn weights of weight 20,21,,2n12^0, 2^1, \cdots, 2^{n-1}. We are to place each of the nn weights on the balance, one after another, in such a way that the right pan is never heavier than the left pan. At each step we choose one of the weights that has not yet been placed on the balance, and place it on either the left pan or the right pan, until all of the weights have been placed.
Determine the number of ways in which this can be done.

*

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Consider an integer n>0 n > 0 and a balance with n n weights of weights 20,21,,2n1 2^0, 2^1, \ldots, 2^{n-1} . Our task is to place each of these weights on the balance, one by one, so that the right pan is never heavier than the left pan. We aim to determine the number of ways to achieve this.

### Understanding the Problem

The setup involves choosing at each step one of the n n weights that has not yet been placed on the balance and deciding whether it should be placed on the left pan or the right pan. This continues until all weights are placed.

### Key Constraints

1. At every step during the placement of the weights, the total weight in the right pan must not exceed the total weight in the left pan.
2. Once a weight is placed, it cannot be moved again.

### Solution Approach

To solve this problem, we consider each weight 2k 2^k as a decision point: each weight can either be placed on the left or right pan, constrained by the requirement that the right pan never becomes heavier.

#### Combinatorial Enumeration using Catalan Paths

This is combinatorially equivalent to finding the number of ways to arrange the sequence of weights, where each step of adding a weight to the left is analogous to taking an upward step (U U ), and adding a weight to the right is analogous to a downward step (D D ). For the configuration to satisfy the condition (i.e., right pan never heavier than the left), it is essentially a "path" problem where paths never fall below the "starting level".

The number of distinct configurations achievable with these constraints is closely related to Catalan numbers, calculated in terms of "factorial double" or semifactorials, which specifically articulate the number of valid parenthesis combinations for a sequence of terms.

#### Calculation

The correct formula for the number of valid sequences like described above where the sequence never "falls below ground" is given by the formula:

(2n1)!! (2n-1)!!

where (2n1)!!(2n-1)!! denotes the product of all odd integers up to 2n1 2n-1 .

Thus, the number of ways the weights can be placed on the balance so that the right pan is never heavier than the left pan is:

(2n1)!! \boxed{(2n-1)!!}

This result reflects the combinatorial counting of valid balanced arrangements, revealing the complexity and richness of the constraining arrangement task akin to classic path and matching problems in combinatorics.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.