combinatorical problem with subsets

Polinomi, disuguaglianze, numeri complessi, ...
Rispondi
timothy6
Messaggi: 18
Iscritto il: 12 set 2007, 21:03

combinatorical problem with subsets

Messaggio da timothy6 »

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 $ .
Alex89
Messaggi: 366
Iscritto il: 29 gen 2006, 16:57

Messaggio da Alex89 »

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 $
darkcrystal
Messaggi: 706
Iscritto il: 14 set 2005, 11:39
Località: Chiavari

Messaggio da darkcrystal »

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 :)
"Solo due cose sono infinite: l'universo e la stupidità dell'uomo, e non sono tanto sicuro della prima" - Einstein

Membro dell'EATO
Sepp
Messaggi: 87
Iscritto il: 01 gen 1970, 01:00
Località: Vicenza

Re: combinatorical problem with subsets

Messaggio da Sepp »

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 $ .
Stavolta si è pure sforzato di cambiare le lettere! :P
http://www.om.edu.pl/ 59. OM I: dal 13 Nov al 10 Dic
Rispondi