Prove that if the numbers $3,4,5, \dots ,3^5$ are partitioned into two disjoint sets, then in one of the sets the number $a,b,c$ can be found such that $ab=c.$ ($a,b,c$ may not be pairwise distinct)
Problem
Source: BdMO 2022 Secondary P3
Tags: algebra
12.04.2022 06:14
What does disjoint mean?
12.04.2022 06:15
Disjoint sets mean that they have no elements in common.
12.04.2022 06:16
easy u have $3\cdot4=12$ and done
12.04.2022 06:18
Lionking212 wrote: easy u have $3\cdot4=12$ and done What if $3,4$ are in the same set while $12$ is in the other?
12.04.2022 06:20
Oh i didn’t see that.
12.04.2022 06:24
Assume the contrary that there exist a way to partition that doesn't satisfy the condition. Let the two disjoint sets be $A,B$. WLOG, let $3\in A$. $3\cdot 3=9$, so $9\in B$ $9\cdot 9=81$, so $81\in A$ $3\cdot 81=243$, so $243\in B$ $9\cdot 27=243$, so $27\in A$ But $3\cdot 27=81$, a contradiction.
22.06.2022 06:32
Quidditch wrote: Assume the contrary that there exist a way to partition that doesn't satisfy the condition. Let the two disjoint sets be $A,B$. WLOG, let $3\in A$. $3\cdot 3=9$, so $9\in B$ $9\cdot 9=81$, so $81\in A$ $3\cdot 81=243$, so $243\in B$ $9\cdot 27=243$, so $27\in A$ But $3\cdot 27=81$, a contradiction. I thought $a,b,c$ aren't pairwise distinct.
22.06.2022 12:22
jasperE3 wrote: Quidditch wrote: Assume the contrary that there exist a way to partition that doesn't satisfy the condition. Let the two disjoint sets be $A,B$. WLOG, let $3\in A$. $3\cdot 3=9$, so $9\in B$ $9\cdot 9=81$, so $81\in A$ $3\cdot 81=243$, so $243\in B$ $9\cdot 27=243$, so $27\in A$ But $3\cdot 27=81$, a contradiction. I thought $a,b,c$ aren't pairwise distinct. Sorry, I don’t quite understand what you’re trying to say…
18.08.2022 09:01
Let's assume we partitioned the numbers into two disjoint set $A$ and $B$. For the sake of contradiction, we assume that the given condition is false. WLOG, $3 \in A$. Hence, $3^2 \not \in A \implies 3^2 \in B$. So, $3^2 \times 3^2 = 3^4 \not \in B \implies 3^4 \in A$. So, $3^5 \not \in A$. So, $3^5 \in B$. $3^3$ is not in any of the sets as we assumed the given condition is false. So, contradiction.