combinatorical problem with subsets
combinatorical problem with subsets
There is integer number $ x\geqslant 2 $ . Find the smallest integer number$ y\geqslant x $, such that for every division of set$ \lbrace x, x+1, ..., y\rbrace $ into two subsets at least one of thease subsets contains such numbers $ m, n, p $ (not necessarily different), such that $ mn=p $ .
Si scrive [/tex] e non [\tex] !! -- EG
I'm sorry because I wrote a wrong solution.
Now I'll try to correct it:
Ok let's write the (hoped) solution.
We have that $ n=c $; in fact, if $ n>c $, we can have a set of $ {m,m+1,...,c} $ that can also be divided into two subset as requested. So to find the smallest n we must suppose n=c.
In both subsets we have numbers $ a_1,a_2 $ and $ b_1,b_2 $ such as $ a_1a_2=b_1b_2=c $. Infact if we haven't those numbers in both subsets, we can place c in one of them such as a and b are in one subset and c in the other one.
Now we have that $ b_1 $ or $ b_2 $ can't be in the first subset because if they can, we can place one of them in the subset and the product will change. Then we have that
$ a_1,a_2,b_1,b_2 $ are all related to a same prime number; in fact, if they aren't, we have that there is a division in two subset such as $ a_1a_2 $ is different from $ b_1b_2 $
So we have that $ a_1,a_2,b_1,b_2 $ are:
$ a_1=a $
$ a_2=a^4 $
$ b_1=a^3 $
$ b_2=a^2 $
and $ c=a^5. $
So the minimum value are: $ a=m $ and $ n=c=m^5 $
I'm sorry because I wrote a wrong solution.
Now I'll try to correct it:
Ok let's write the (hoped) solution.
We have that $ n=c $; in fact, if $ n>c $, we can have a set of $ {m,m+1,...,c} $ that can also be divided into two subset as requested. So to find the smallest n we must suppose n=c.
In both subsets we have numbers $ a_1,a_2 $ and $ b_1,b_2 $ such as $ a_1a_2=b_1b_2=c $. Infact if we haven't those numbers in both subsets, we can place c in one of them such as a and b are in one subset and c in the other one.
Now we have that $ b_1 $ or $ b_2 $ can't be in the first subset because if they can, we can place one of them in the subset and the product will change. Then we have that
$ a_1,a_2,b_1,b_2 $ are all related to a same prime number; in fact, if they aren't, we have that there is a division in two subset such as $ a_1a_2 $ is different from $ b_1b_2 $
So we have that $ a_1,a_2,b_1,b_2 $ are:
$ a_1=a $
$ a_2=a^4 $
$ b_1=a^3 $
$ b_2=a^2 $
and $ c=a^5. $
So the minimum value are: $ a=m $ and $ n=c=m^5 $
-
- Messaggi: 706
- Iscritto il: 14 set 2005, 11:39
- Località: Chiavari
Well, it should be $ x^5 $
Obviously it works: let's call A and B the subsets. wlog $ x \in A \rightarrow x^2 \in B \rightarrow x^4 \in A \rightarrow x^3 \in B $, and wherever we put $ x^5 $ we have (m,n,p) s.t. mn=p by choosing only powers of x.
Let's show we can't do anything better. We must show two subsets which partition $ {x,...,x^5-1} $ in a good way. But this is easy: let's choose $ A=x \leq n \leq x^2-1 \bigcup x^4 \leq n \leq x^5-1 $ and $ B=x^2 \leq n \leq x^4-1 $.
It's easy to see that the product of any two elements in each subsets is not in that subset for reasons of "size".
I hope this is right...
Bye
Obviously it works: let's call A and B the subsets. wlog $ x \in A \rightarrow x^2 \in B \rightarrow x^4 \in A \rightarrow x^3 \in B $, and wherever we put $ x^5 $ we have (m,n,p) s.t. mn=p by choosing only powers of x.
Let's show we can't do anything better. We must show two subsets which partition $ {x,...,x^5-1} $ in a good way. But this is easy: let's choose $ A=x \leq n \leq x^2-1 \bigcup x^4 \leq n \leq x^5-1 $ and $ B=x^2 \leq n \leq x^4-1 $.
It's easy to see that the product of any two elements in each subsets is not in that subset for reasons of "size".
I hope this is right...
Bye
"Solo due cose sono infinite: l'universo e la stupidità dell'uomo, e non sono tanto sicuro della prima" - Einstein
Membro dell'EATO
Membro dell'EATO
Re: combinatorical problem with subsets
Stavolta si è pure sforzato di cambiare le lettere!timothy6 ha scritto:There is integer number $ x\geqslant 2 $ . Find the smallest integer number$ y\geqslant x $, such that for every division of set$ \lbrace x, x+1, ..., y\rbrace $ into two subsets at least one of thease subsets contains such numbers $ m, n, p $ (not necessarily different), such that $ mn=p $ .
http://www.om.edu.pl/ 59. OM I: dal 13 Nov al 10 Dic