## combinatorical problem with subsets

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

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

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

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