Let $a, b, c, p, q, r$ be positive integers with $p, q, r \ge 2$. Denote \[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 $Q$, with a total of $M$ pieces. Then, one can perform the following three types of operations repeatedly: (1) Remove $p$ pieces on $(x, y, z)$ and place a piece on $(x-1, y, z)$ ; (2) Remove $q$ pieces on $(x, y, z)$ and place a piece on $(x, y-1, z)$ ; (3) Remove $r$ pieces on $(x, y, z)$ and place a piece on $(x, y, z-1)$. Find the smallest positive integer $M$ such that one can always perform a sequence of operations, making a piece placed on $(0,0,0)$, no matter how the pieces are distributed initially.
Problem
Source: 2022 China TST, Test 1, P3 (posting for better LaTeX)
Tags: combinatorics, invariant, algorithm
CANBANKAN
26.03.2022 22:40
Note: This seemingly easy problem is actually very hard. This is only a partial solution. I have yet to work out other details.
The answer is $p^aq^br^c$. Let $f(x,y,z)$ be the number of pieces on the lattice point $(x,y,z)$. For sets $X,Y,Z$, let $X\times Y\times Z = \{ (m,n,t) | m\in X, n\in Y, t\in Z\}$
I first show $M\ge p^aq^br^c$. Let $$N=\sum\limits_{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}$$
Note $N$ is an invariant. In the end, $f(0,0,0)\ge 1$. Therefore, if $M<p^aq^br^c$, setting $f(a,b,c)=M$ gives $N<1$, contradiction.
Now I show $p^aq^br^c$ always works. We proceed by strong induction, and we will use the inductive hypothesis very strongly. The key intuition is that almost all the pieces must be on $(a,b,c)$ while there must be a piece on $x=0$. Combining these two gives a way to place a cell in $(0,0,0)$.
Case 1: there are no pieces with $x=0$. We group the $p^aq^br^c$ pieces into $p$ random groups of $p^{a-1}q^br^c$ pieces. Each move uses pieces in the same group only. By inductive hypothesis on $(a-1,b,c)$ on $\{1,\cdots,a\} \times \{0,\cdots,b\} \times \{0,\cdots, c\}$, each group of $p^{a-1}q^br^c$ piece can result in one piece on $(1,0,0)$. Now there are $p$ pieces on $(1,0,0)$, we can use these to get one piece on $(0,0,0)$.
Case 2: There is a piece with $x=0$, a piece with $y=0$ and a piece with $z=0$.
Claim: There are at most $(b+1)(c+1)-2$ pieces in $\{0,\cdots,a-1\} \times \{0,\cdots,b\} \times \{0,\cdots,c\}$.
Proof: We can move $\lfloor \frac{f(a,n,t)}{p} \rfloor$ pieces from $(a,n,t)$ to $(a-1,n,t)$. After transferring all cells from $(a,n,t)$ to $(a-1,n,t)$ for $0\le n\le b, 0\le t\le c$.
Let $A$ be the number of pieces in $\{0,\cdots,a-1\} \times \{0,\cdots,b\} \times \{0,\cdots,c\}$. If $A+\sum\limits_{0\le n\le b, 0\le t\le c} \lfloor \frac{f(a,n,t)}{p} \rfloor \ge p^{a-1}q^br^c$, by inductive hypothesis on $(a-1,b,c)$, we can place a cell on $(0,0,0)$. Therefore, it suffices to handle the case where $A+\sum\limits_{0\le n\le b, 0\le t\le c} \lfloor \frac{f(a,n,t)}{p} \rfloor \le p^{a-1}q^br^c-1$ (1)
We also have $A+\sum\limits_{0\le n\le b, 0\le t\le c} f(a,n,t) =p^aq^br^c$ (2) because there are a total of $p^aq^br^c$ pieces on the board.
$p(1)-(2)$ gives $(p-1)A - \sum\limits_{0\le n\le b, 0\le t\le c} R(f(a,n,t),p) \le -p$
It follows that $(p-1)A - \sum\limits_{0\le n\le b, 0\le t\le c} (p-1) \le -p$ so $A\le (b+1)(c+1)-2$.
Using similar arguments, we can see that the number of stones in $\{0,\cdots,a\} \times \{1,\cdots,b\} \times \{0,\cdots,c\}$ is at most $(a+1)(c+1)-2$ and the number of stones in $\{0,\cdots,a\} \times \{0,\cdots,b\} \times \{1,\cdots,c\}$ is at most $(a+1)(b+1)-2$. This means the number of stones not in $(a,b,c)$ is at most $(a+1)(b+1)+(b+1)(c+1)+(c+1)(a+1)-6$, so the number of stones in $(a,b,c)$ is at least $p^aq^br^c -(a+1)(b+1)+(b+1)(c+1)+(c+1)(a+1) + 6$.
Let $X=(0,k,l)$ be a square with at least one cell. If I can transfer $q^kr^l-1$ stones to $X$, I win by inductive hypothesis on $a=0, b=k, c=l$. To transfer $q^kr^l-1$ stones to $X$, I need $(q^kr^l-1)(p^aq^{b-k}r^{c-l}) = p^aq^br^c - p^aq^{b-k}r^{c-l} \le p^aq^br^c-p^a$. Therefore, if $p^a\ge (a+1)(b+1)+(b+1)(c+1)+(c+1)(a+1)-6$ I am done. Similarly, if $q^b, r^c\ge (a+1)(b+1)+(b+1)(c+1)+(c+1)(a+1)-6$ I am also done.
It remains to handle small cases?
qwqwq
30.03.2022 11:58
Official solution:
turmax2005
28.04.2022 18:12
Very nice problem! There is my solution,i hope that there are no mistakes in it.
Answer is $p^{a}q^{b}r^{c}$,to the lowerbound place $p^{a}q^{b}r^{c}-1$ pieces in (a;b;c).
Now we will proof that if we have $p^{a}q^{b}r^{c}$ pieces we can make a piece placed in (0;0;0).
Let f(x;y;z) be the count of pieces in the (x;y;z)
Firstly let we solve problem for a path,instead of cube.(Path may be not straight,but it must be lowered).
In this case,by induction we can show that there is a soluiton if and only if $\sum(f(x;y;z)*p^{-x}q^{-y}r^{-z})>=1$
Secondly,let we solve a problem for square (z=0).
For each lowered path from (a;b) to (0;0) we choose its probability p ($\sum p=1$) ,such that we have cell (i;j) in our path with probability 1/(a+b-i-j+1)
we can reach it,moving from diagonal to diagonal and choose a probability of going from (i;j) to (i;j-1) and to (i-1;j)
So let the value of a path will be $\sum(f(x;y)*p^{-x}q^{-y})$ by taking all paths with probabilities as below we have an average path value $\sum((f(x;y)*p^{-x}q^{-y})/(a+b-x-y+1))$
This is at least 1,because $p^{a-x}q^{b-y}>=(a+b-x-y+1)$
So for square we are done
Now we will solve a problem for a cube.Let we say that $r^{c}>=q^{b}>=p^{a}$
Let we try to move by induction from (a;b;c) to (a;b;c-1).(with base min(a;b;c)=0 for square).
Firstly while there is (x;y;c) such that f(x;y;c)>=r we will (will try) decrease f(x;y;c) by r and increase f(x;y;c-1) by 1.
If now there is at least $p^{a}q^{b}r^{c-1}$ pieces with $0<=x<=a,0<=y<=b,0<=z<=c-1$,then we are done.
But if it is wrong then initially ((number of (x;y;c) that is not empty) > (pieces count with $0<=x<=a,0<=y<=b,0<=z<=c-1$)) (because "we are losing" at most c-1 for nonempty (x;y;c) and "we are winning" c-1 for each piece with $0<=x<=a,0<=y<=b,0<=z<=c-1$).
So if we cannot reduce by induction we have (number of pieces in cells (x;y;c) + number of nonempty cells (x;y;c))>$p^{a}q^{b}r^{c}$
Now we will proof that we can move at least $r^{c}$ pieces to the (0;0;c).
Let we will do a steps placing piece in a (0;0;c) one-by-one.
(Now i will write (u;v;c) as (u;v))
In each move if we have a path from (a;b) to (0;0) with value>=1 we will choose such path with at least one non-empty cell except (a;b) (for example,a path with maximal value).
Let we move by path from (0;0) to (a;b) while our value will not be =1.And from this pieces we will form one piece at (0;0).
So (number of pieces in cells (x;y;c) + number of nonempty cells (x;y;c)) decrease to at most $p^{a}q^{b}r^{c}+1$ by step
But it decreases to at most $p^{a}q^{b}r^{c}-2$+count of cell in (a;b),(a;b-1),(a-1;b) that become empty exactly after this step.
So after k moves we have a (number of pieces in cells (x;y;c) + number of nonempty cells (x;y;c))>$p^{a}q^{b}r^{c}-k*p^{a}q^{b}+2*k-3$
We want to do at least $r^{c}$ moves.What can resist us? Firstly,the path with the maximal value can be the path with only one nonempty square (a;b).But in this case the only nonempty square is (a;b),and count of pieces in it is at least $p^{a}q^{b}r^{c}-k*q^{b}r^{c}+2*k-4$ (in fact more than this) we want to prove that this is at least $p^{a}q^{b}$.
With $k=r^{c} - 1$ we have $p^{a}q^{b}+2*r^{c}-6$ the only case when we lose is p=q=r=2,a=b=c=1,but in this case we do =1 step and we can't get (a;b) empty (by the definition of case),and move to each (a;b-1) and (a-1;b).So in this case $p^{b}q^{b}+2*r^{c}-4>=p^{a}q^{b}$.
But there is another obstacle for us.We can fail to find a path with value>=1.In this case $\sum((f(x;y)*p^{-x}q^{-y})/(a+b-x-y+1))<1$
$\sum((f(x;y)*p^{a-x}q^{b-y})/(a+b-x-y+1))<p^{a}q^{b}$
but (number of pieces in cells (x;y;c) + number of nonempty cells (x;y;c))>=$p^{a}q^{b}+2*r^{c}-1-(number of empty cells from (a;b),(a;b-1),(a-1;b))$ (-1,not -2 because we had strict inequality)
But $\sum((f(x;y)*p^{a-x}q^{b-y})/(a+b-x-y+1))$>=(number of pieces in cells (x;y;c) + number of nonempty cells (x;y;c))-(2/3)*3 -number of nonempty cells from (a;b),(a;b-1),(a-1;b) ).
((-2/3)*3 is for (a+b-x-y=2)).
$\sum((f(x;y)*p^{a-x}q^{b-y})/(a+b-x-y+1))$>=(number of pieces in cells (x;y;c) + number of nonempty cells (x;y;c))-(2/3)*3 -number of nonempty cells from (a;b),(a;b-1),(a-1;b))>=$p^{a}q^{b}+2*r^{c}-6$.
If $2*r^{c}>=6$ we are done.(We have at least $r^{c}$ pieces in (0;0;c) so we can make a piece in (0;0;0))
The only case we must check is p=q=r=2 and a=b=c=1,but in this case probability that path (that we choose) goes to (0;0) is not (1/3) but 1,so we remove (2/3)*3,and have $2*r^{c}>=4$.
Now we are done!
Joider
02.08.2023 18:50
We said that $f(a,b,c) =M$ the number of pieces in $(a,b,c)$ or M are all pieces in every points????
Joider
03.08.2023 20:17
Any answer???
aspalapati75
03.11.2024 00:00
bro how are yall so smart