Maths Olympiad Prep

Library / /62 of 115

Algebra Difficulty 7.4 National olympiad, round 2 Find the answer

( Elgin Johnston ) Legs L1,L2,L3,L4L_1, L_2, L_3, L_4 of a square table each have length nn , where nn is a positive integer. For how many ordered 4-tuples (k1,k2,k3,k4)(k_1, k_2, k_3, k_4) of nonnegative integers can we cut a piece of length kik_i from the end of leg Li  (i=1,2,3,4)L_i \; (i = 1,2,3,4) and still have a stable table?
(The table is stable if it can be placed so that all four of the leg ends touch the floor. Note that a cut leg of length 0 is permitted.)

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

Solution

The problem involves determining how many ways we can cut legs of a square table such that the table remains stable. Specifically, we aim to find the number of ordered 4-tuples (k1,k2,k3,k4)(k_1, k_2, k_3, k_4) where the lengths of the cuts kik_i are non-negative integers, and the legs of the table after cutting are stable, i.e., they can all touch the floor simultaneously.

### Stability Condition

For the table to be stable, the difference in lengths between the longest leg and the shortest leg should be at most the length of the shortest leg that remains. Thus, we need to ensure the difference between the longest and shortest cut is within the original length of the leg:

max(nk1,nk2,nk3,nk4)min(nk1,nk2,nk3,nk4)n. \max(n - k_1, n - k_2, n - k_3, n - k_4) - \min(n - k_1, n - k_2, n - k_3, n - k_4) \leq n.

Simplifying this inequality, we have:

(max(nk1,nk2,nk3,nk4))n+min(nk1,nk2,nk3,nk4). (\max(n - k_1, n - k_2, n - k_3, n - k_4)) \leq n + \min(n - k_1, n - k_2, n - k_3, n - k_4).

Which translates to:

(nmin(k1,k2,k3,k4))n+(kminkmax). (n - \min(k_1, k_2, k_3, k_4)) \leq n + (k_{\text{min}} - k_{\text{max}}).

Identifying min(k1,k2,k3,k4)\min(k_1, k_2, k_3, k_4) as mm and max(k1,k2,k3,k4)\max(k_1, k_2, k_3, k_4) as MM:

M+mn, M + m \leq n,

where M=max(k1,k2,k3,k4)M = \max(k_1, k_2, k_3, k_4), and m=min(k1,k2,k3,k4)m = \min(k_1, k_2, k_3, k_4).

This is equivalent to:

k1+k2+k3+k44m+(n2m). k_1 + k_2 + k_3 + k_4 \leq 4m + (n - 2m).

We redefine the variables to convert this into a combinatorial problem about distributing the reductions in leg lengths. Consider the space of all possible reductions in leg lengths and form a combinatorial problem:

### Combinatorial Translation

Since kik_i are non-negative integers and M+mnM + m \leq n, if we let:

s=nk1k2k3k4, s = n - k_1 - k_2 - k_3 - k_4,

then we are essentially looking for the number of solutions in non-negative integers for:

k1+k2+k3+k4=ns, k_1 + k_2 + k_3 + k_4 = n - s,

where 0sn0 \leq s \leq n.

### Solving for ss

This problem is equivalent to distributing nsn - s into 4 categories (legs), where each category can have zero units. This boils down to a classic stars and bars combinatorial problem, where the number of distributions of nsn-s stars into 4 bars is:

(ns+33). \binom{n-s + 3}{3}.

To find the total count, we sum over all valid ss:

s=0n(ns+33)=k=3n+3(k3)(variable transform) \sum_{s=0}^{n} \binom{n-s + 3}{3} = \sum_{k=3}^{n+3} \binom{k}{3} \quad \text{(variable transform)}

This simplifies, due to the combination identity of the sum:

This evaluates to:

(n+34). \binom{n+3}{4}.

Thus, the total number of valid configurations is given by:

(n+33). \boxed{\binom{n+3}{3}}.

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.