Maths Olympiad Prep

Library / /84 of 97

Combinatorics Difficulty 8.5 Shortlist Find the answer

Let a,b,c,p,q,ra, b, c, p, q, r be positive integers with p,q,r2p, q, r \ge 2. Denote
Q={(x,y,z)Z3:0xa,0yb,0zc}.Q=\{(x, y, z)\in \mathbb{Z}^3 : 0 \le x \le a, 0 \le y \le b , 0 \le z \le c \}.
Initially, some pieces are put on the each point in QQ, with a total of MM pieces. Then, one can perform the following three types of operations repeatedly:
(1) Remove pp pieces on (x,y,z)(x, y, z) and place a piece on (x1,y,z)(x-1, y, z) ;
(2) Remove qq pieces on (x,y,z)(x, y, z) and place a piece on (x,y1,z)(x, y-1, z) ;
(3) Remove rr pieces on (x,y,z)(x, y, z) and place a piece on (x,y,z1)(x, y, z-1).

Find the smallest positive integer MM such that one can always perform a sequence of operations, making a piece placed on (0,0,0)(0,0,0), no matter how the pieces are distributed initially.

A number or a short expression. Spacing and $ signs are ignored.

Solution

Let a,b,c,p,q,ra, b, c, p, q, r be positive integers with p,q,r2p, q, r \ge 2. Denote
Q={(x,y,z)Z3:0xa,0yb,0zc}. Q = \{(x, y, z) \in \mathbb{Z}^3 : 0 \le x \le a, 0 \le y \le b, 0 \le z \le c\}.
Initially, some pieces are placed on each point in QQ, with a total of MM pieces. The following three types of operations can be performed repeatedly:
1. Remove pp pieces from (x,y,z)(x, y, z) and place a piece on (x1,y,z)(x-1, y, z);
2. Remove qq pieces from (x,y,z)(x, y, z) and place a piece on (x,y1,z)(x, y-1, z);
3. Remove rr pieces from (x,y,z)(x, y, z) and place a piece on (x,y,z1)(x, y, z-1).

We need to find the smallest positive integer MM such that it is always possible to perform a sequence of operations to place a piece on (0,0,0)(0,0,0), regardless of the initial distribution of pieces.

We claim that the smallest positive integer MM is paqbrcp^a q^b r^c.

To show that MpaqbrcM \ge p^a q^b r^c, consider the invariant
N=0xa,0yb,0zcf(x,y,z)pxqyrz, N = \sum_{0 \le x \le a, 0 \le y \le b, 0 \le z \le c} f(x, y, z) p^{-x} q^{-y} r^{-z},
where f(x,y,z)f(x, y, z) is the number of pieces at (x,y,z)(x, y, z). Initially, N=MpaqbrcN = M p^{-a} q^{-b} r^{-c}. After any operation, NN remains unchanged. To ensure that f(0,0,0)1f(0,0,0) \ge 1 at the end, we need N1N \ge 1, which implies MpaqbrcM \ge p^a q^b r^c.

To show that M=paqbrcM = p^a q^b r^c is sufficient, we proceed by induction on a+b+ca + b + c. The base case is trivial. Assume it holds for all smaller values of a+b+ca + b + c. We group the paqbrcp^a q^b r^c pieces into pp groups of pa1qbrcp^{a-1} q^b r^c pieces each. By the inductive hypothesis, each group can be used to place a piece on (1,0,0)(1, 0, 0). These pp pieces can then be used to place a piece on (0,0,0)(0, 0, 0).

Thus, the smallest positive integer MM such that a piece can always be placed on (0,0,0)(0,0,0) is:
paqbrc. \boxed{p^a q^b r^c}.

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.