A subset $S$ of positive real numbers is called powerful if for any two distinct elements $a, b$ of $S$, at least one of $a^{b}$ or $b^{a}$ is also an element of $S$. a) Give an example of a four elements powerful set. b) Prove that every finite powerful set has at most four elements.
Problem
Source: Iran National Olympiad - 2014 Second Round - D2P2
Tags: combinatorics unsolved, combinatorics
03.05.2014 21:32
This one speaks about real numbers. Which one is correct?
03.05.2014 21:39
chaotic_iak wrote: This one speaks about real numbers. Which one is correct? sorry i edited it...
03.05.2014 21:50
I. Consider the set $1,\frac{1}{2},\frac{1}{4},\frac{1}{16}$. Note that $\frac{1}{2}^1=\frac{1}{2}$, $\frac{1}{4}^1=\frac{1}{4},\frac{1}{16}^1=\frac{1}{16},\frac{1}{4}^{1/2}=\frac{1}{2},\frac{1}{16}^{1/2}=\frac{1}{4},\frac{1}{16}^{1/4}=\frac{1}{2}$.
03.05.2014 21:51
pi37 wrote: I. Consider the set $1,\frac{1}{2},\frac{1}{4},\frac{1}{16}$. Note that $\frac{1}{2}^1=\frac{1}{2}$, $\frac{1}{4}^1=\frac{1}{4},\frac{1}{16}^1=\frac{1}{16},\frac{1}{4}^{1/2}=\frac{1}{2},\frac{1}{16}^{1/2}=\frac{1}{4},\frac{1}{16}^{1/4}=\frac{1}{2}$. yes thats right now try to prove the $II$ part....
04.05.2014 18:22
we will prove the lemma that if a set $A$ of positive numbers satisfying that condition, $A$ must contain the number $1$. Assume $A$ doesn't contain $1$, and $A={a,b,c,d}$. we consider $S_a={a^b,a^c,a^d}$ and by the way, we have $S_b,S_c,S_d$ Because $a,b,c,d$ are not equal $1$, we have $S_a={b,c,d}$ and similarly with $S_b,...$. WLOG,$a<b<c<d$. We consider two cases. Cases 1. $d<1$. Since $S_d={a,b,c}$ and $a,b,c$ are less than $1$, we have $d<d^a\in {a,b,c}$, a contradiction. Cases 2. $d>1$. $S_d={a,b,c}$, so $ a,b,c >1$. So $d<d^a\in {a,b,c}$, a contradiction, too. So our result is proved. Use this lemma, we easily prove the 2 part.
04.05.2014 23:12
thedarkness wrote: we consider $S_a={a^b,a^c,a^d}$ and by the way, we have $S_b,S_c,S_d$ Because $a,b,c,d$ are not equal $1$, we have $S_a={b,c,d}$ and similarly with $S_b,...$. I don't think we can conclude that $S_a={ b,c,d }$ since only one of ${ a^b, b^a }$ need to be in the powerful set My solution: If there are at least three elements in $A$ greater than $1$, choose the three greatest element $c<b<a$ we can show that $c^b , c^a \in { b,a }$ , $b^a = a$ and $c^b < c^a$ which impiled $c^a = b^a$ contradiction If there are at least four elements in $A$ small than $1$, choose the four greatest element that is lesser than $1$ $d<c<b<a$ we can show that $b^a = a$,$c^a =b$,$c^b=a$, $d^a=c$ which impiled $a=\frac{1}{2}, b=\frac{1}{4},c=\frac{1}{16},d=\frac{1}{256}$ and both $c^d,d^c$ cannot be in $A$ contradiction If there are both number greater and smaller than $1$ in the same set, choose the smallest number lesser than $1$ and the smallest number greater than $1$: $a,b$ we can easily find that both $a^b$,$b^a$ can't be in $A$ So there are at most $2$ elements greater than $1$ there are at most $3$ elements smaller than $1$ there can't be both number greater and smaller than $1$ combine the additional $1$ There can be at most $4$ number in $A$