Let $a_1, a_2, \ldots, a_n$ be $n$ positive integers, and let $b_1, b_2, \ldots, b_m$ be $m$ positive integers such that $a_1 a_2 \cdots a_n = b_1 b_2 \cdots b_m$. Prove that a rectangular table with $n$ rows and $m$ columns can be filled with positive integer entries in such a way that * the product of the entries in the $i$-th row is $a_i$ (for each $i \in \left\{1,2,\ldots,n\right\}$); * the product of the entries in the $j$-th row is $b_j$ (for each $i \in \left\{1,2,\ldots,m\right\}$).
Problem
Source: German TST 2022, exam 2, problem 1
Tags: number-theory, algebra, factorization, combinatorics
11.03.2022 17:20
Initially write $1$ in all the cells. Pick a prime dividing the common product, say $p | a_i$ and $p | b_j$, replace $a_i, b_j$ with $\frac{a_i}{p}, \frac{b_j}{p}$ and multiply the entry in the cell $(i,j)$ by $p$. Repeatedly do this until the common product is $1$. This works.
16.03.2022 11:47
Associate with each cell $(i,j)$ two multisets $A_{i,j}$ and $B_{i,j}$ which are initially empty. Put into $A_{i,1}, i=1,\dots,n$ all prime factors of $a_i$ with their multiplicities. Put into $B_{1,j},j=1,\dots,m$ the prime factors of $b_j$. Our goal is to equalize $A_{i,j}$ with $B_{i,j}$ through the following operations. 1) We can move a prime number $p$ from $A_{i,j}$ to $A_{i,k}\,,\, i\in[n],j,k\in[m]$ 2) We can move a prime number $p$ from $B_{i,j}$ to $B_{k,j}\,,\, i,k\in[n],j\in[m]$ It can be done by a greedy algorithm. Suppose, for some prime $p$, there are more $p$'s in $A_{i,j}$ than in $B_{i,j}$ (or vise versa). Since the total number of $p$'s in all the sets $A$ equals to the corresponding number for the sets $B$, there exists two multisets $A_{i',j'}$ and $B_{i',j'}$ for which there are more $p$'s in $B_{i',j'}$ than in $A_{i',j'}$. We move one $p$ from $A_{i,j}$ to $A_{i,j'}$ and one $p$ from $B_{i',j'}$ to $B_{i,j'}$. Thus, the discrepancy between the corresponding $A$'s and $B$'s decreases, so doing this operation finitely many times we achieve our goal..
16.03.2022 15:37
dgrozev wrote: We move one $p$ from $A_{i,j}$ to $A_{i,j'}$ and one $p$ from $B_{i',j'}$ to $B_{i,j'}$. What is the loop invariant here? That the product of all elements of all $A_{i,j}$'s for a fixed $i$ is $a_i$, whereas the product of all elements of all $B_{i,j}$'s for a fixed $j$ is $b_j$? EDIT: Ah, yes, that's the loop invariant. Nice algorithm!
06.04.2022 20:52
My solution is based on changing condition of product of numbers to sum of numbers and using induction. Let $rad(a_1a_2\cdots a_n)=p_1p_2\cdots p_t$. Let's create a board $k$ for each $k=1,2,...,t$ such that this board has $n$ rows and $m$ columns and it can be filled with positive integer entries in such a way that * the product of the entries in the $i$-th row is $p_k^{v_{p_k}(a_i)}$ (for each $i \in \left\{1,2,\ldots,n\right\}$); * the product of the entries in the $j$-th row is $p_k^{v_{p_k}(b_j)}$ (for each $i \in \left\{1,2,\ldots,m\right\}$. After creating $1$ board for each $k$, write product of numbers written in cell $(i,j)$ of all boards to cell $(i,j)$ of our initial rectangular table. Obviously it holds both condition. So it means it's enough to take all $a_i,b_i$ as a power of prime $p$. So let $a_i=p^{x_i}$ and $b_i=p^{y_i}$. Now problem is equivalent to this: Let $x_1, x_2, \ldots, x_n$ be $n$non-negative integers, and let $y_1, y_2, \ldots, y_m$ be $m$ non-negative integers such that $x_1+ x_2 \cdots +x_n = y_1+ y_2 \cdots +y_m$. Prove a rectangular table with $n$ rows and $m$ columns can be filled with non-negative integer entries in such a way that * the sum of the entries in the $i$-th row is $x_i$ (for each $i \in \left\{1,2,\ldots,n\right\}$); * the sum of the entries in the $j$-th row is $y_j$ (for each $i \in \left\{1,2,\ldots,m\right\}$. Now let's use strong induction on $m+n$. In $m\times n$ table pick cell $(m,n)$, write here $\min\{y_m,x_n\}=x_n$(WLOG) and write $0$s to all remaining cells of $n$th row. Then remove $n$th row. Since all conditions remained same and $m+n$ decreased by $1$, we need only check $1\times 1$ board, which is obvious. So we are done.