Pagina **1** di **1**

### combinatorical problem with subsets

Inviato: **04 nov 2007, 16:37**

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 $ .

Inviato: **04 nov 2007, 17:47**

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 $

Inviato: **04 nov 2007, 18:03**

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

### Re: combinatorical problem with subsets

Inviato: **05 nov 2007, 13:02**

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!

http://www.om.edu.pl/ 59. OM I: dal 13 Nov al 10 Dic