wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Unsolvable subsets
        
(Message started by: Earendil on Mar 13^th, 2004, 11:58pm)

Title: Unsolvable subsets
Post by Earendil on Mar 13^th, 2004, 11:58pm

Divide the set of positive real numbers into three subsets, such that the equation "a + b = 5c" is not solvable in any of the subsets, i.e. the equation does not hold, for any three numbers a, b, c, that come from the same subset. Can this be done for the equation "a + b = 3c", maybe by using more subsets?

Title: Re: Unsolvable subsets
Post by Barukh on Mar 19^th, 2004, 11:59pm

[smiley=blacksquare.gif][hide]
Let q = [sqrt]5, and define the subsets as follows: S_i = [smiley=bigcup.gif] [q^3k+i, q^3k+i+1), k [in] [bbz]. To put it differently, x [in] S_i if [ log_qx ] = i mod 3.

By symmetry considerations, we may assume a, b [in] S₀ and a [ge] b. Then a = q^3k+e, e [in] [0,1), and c > a/5 = aq^-2 = q^3k+e-2 [ge] q^3k-2,c [le] 2a/5 = 2q^3k+e-2 < 2q^3k-1 < q^3k,
which implies that c [in] S₁ or c [in] S₂.

For the second question, I think the answer is yes: take q = 3^1/3, and divide into 4 subsets.
[/hide] [smiley=blacksquare.gif]

Title: Re: Unsolvable subsets
Post by Icarus on Mar 21^st, 2004, 2:27pm

on 03/13/04 at 23:58:53, Earendil wrote:

Can this be done for the equation "a + b = 3c", maybe by using more subsets?

As stated, it can easily be done for any equation. Just make each set a singleton! But I suppose you meant do it with a finite number of sets.

Title: Re: Unsolvable subsets
Post by Barukh on Mar 21^st, 2004, 11:18pm

on 03/21/04 at 14:27:47, Icarus wrote:

As stated, it can easily be done for any equation. Just make each set a singleton!

Except the equation 'a+b=2c', of course! ;)

Title: Re: Unsolvable subsets
Post by Icarus on Mar 22^nd, 2004, 4:07pm

Okay - I'll grant that one! So, what's true is that setting each set to be a singleton will work for any equation which has no solution with all the variables equal. And for equations which have at least one such solution, every partition will have at least one set containing a solution.

Still, the real challenge is: Can it be done with a finite partition?

Title: Re: Unsolvable subsets
Post by Barukh on Mar 23^rd, 2004, 12:38am

on 03/22/04 at 16:07:33, Icarus wrote:

Still, the real challenge is: Can it be done with a finite partition?

Consider the equation a+b = kc, k [in] [bbr]⁺. If the partitions are made as in my proposed solution, it can be shown that q must satisfy the following conditions:
k^1/(P-1) [le] q [le] k/2,
where P is the number of partitions. So, for k > 2 it suffices to make P = log(k²/2) / log(k/2) partitions.