A carpet dealer,who has a lot of carpets in the market,is available to exchange a carpet of dimensions $a\cdot b$ either with a carpet with dimensions $\frac{1}{a}\cdot \frac{1}{b}$ or with two carpets with dimensions $c\cdot b$ and $\frac{a}{c}\cdot b$ (the customer can select the number $c$).The dealer supports that,at the beginning he had a carpet with dimensions greater than $1$ and,after some exchanges like the ones we described above,he ended up with a set of carpets,each one having one dimension greater than $1$ and one smaller than $1$.Is this possible? Note:The customer can demand from the dealer to consider a carpet of dimensions $a\cdot b$ as one with dimensions $b\cdot a$.
Problem
Source: 2016 All-Russian Olympiad,Problem 9.1
Tags: Support, combinatorics
07.06.2016 17:50
We will prove that for all times, there always exist carpet with side length $p,q$ such that $(p-1)(q-1)\geq 0$ First step is obvious since $a,b>1$, now suppose that after $k$ steps, there not exist such carpet So in $(k+1)^{th}$ step, such carpet from $k^{th}$ step must be changed, let that carpet have side length $u,v$ If $u,v\geq 1$, then we have $1)$ $(\frac{1}{u}-1)(\frac{1}{v}-1)=\frac{(u-1)(v-1)}{uv}\geq 0$ and $2)$ If $c\geq 1$, then $(c-1)(v-1)\geq 0$ and if $c<1$ then $(\frac{u}{c}-1)(v-1)>0$ Similarly, if $u,v\leq 1$ we easily get that we can't get all carpet with $(p-1)(q-1)<0$ So we get contradiction and our claim is true, then it's immediately finish the problem
30.05.2018 07:19
We show that this is not possible. Proceeding by induction, we start by seeing that the base case is obvious. Now assume that after $n$ moves he has $k$ carpets all of whose dimensions are either both $>1$ or $<1$, and choose any one carpet with dimension $a \cdot b$. WLOG assume $a,b>1$. Then there are two(three in fact) transformations: $\bullet$ $(a,b) \mapsto \left( \tfrac{1}{a},\tfrac{1}{b} \right)$, but then $\tfrac{1}{a}<1$ and $\tfrac{1}{b}<1$. $\bullet$ $(a,b) \mapsto \left(c \cdot b, \tfrac{a}{c} \cdot b \right)$. Since $b>1$, we must have $c<1$. But then $b,\tfrac{a}{c}>1$. $\bullet$ $(a,b) \mapsto \left(c \cdot a, \tfrac{b}{c} \cdot a \right)$. Since $a>1$, we must have $c<1$. But then $a,\tfrac{b}{c}>1$. Hence this is not possible. $\square$