wu :: forums - Print Page


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

        riddles >> easy >> Similar sets
        
(Message started by: jollytall on Oct 20^th, 2013, 11:33am)

Title: Similar sets
Post by jollytall on Oct 20^th, 2013, 11:33am

For what n, can be found two different sets, A(a1..an) and B(b1..bn) of real numbers, that when we calculate all combinations of ai+aj and place the totals (n*(n-1)/2 sums) into a new set A', and likewise bi+bj into B', then A'=B'?
Two sets are different if at least one element is different.
The sets can have repeated numbers (ai=aj).

Title: Re: Similar sets
Post by jollytall on Oct 21^st, 2013, 7:01am

Sorry, A typo. Both A and B are n elements. I fix it.

Title: Re: Similar sets
Post by rmsgrey on Oct 21^st, 2013, 7:02am

Trivially possible when n=2: for some a,b,c with a not equal to b: A={c+a, c-a}; B={c+b, c-b}; A'=B'={2c}

Title: Re: Similar sets
Post by Grimbal on Oct 21^st, 2013, 7:56am

Hm... the way I understand the question, it is possible to sum the same element. So you would have
a1+a1, a1+a2 (2x) and a2+a2.

By the way, sets normally don't have duplicates. So how does it work? If the ai can be duplicated (ai=aj for i<>j) then it makes sense that you also count duplicates in A' and B' (as I did above). But are A' and B' considered different if the values are the same but the count of some value is different?

PS: oops, the n*(n-1)/2 implies we sum only ai and aj with i<j .

But still, the question remains about whether you count the duplicates in the resulting set.

Title: Re: Similar sets
Post by jollytall on Oct 21^st, 2013, 9:44am

To clarify:
Only ai+aj type sums are in the A' set, i.e. ai+ai is not.
ai+aj and aj+ai is only counted once (no duplicates as such).
But if a1+a4 = a2 + a3 =x then x is twice in A', not only once.
n=2 is a trivial solution indeed, but the real question is for n>5.

Title: Re: Similar sets
Post by Grimbal on Oct 21^st, 2013, 10:29am

For n=4, I get {0,4,6,8} and {1,3,5,9}.

Title: Re: Similar sets
Post by towr on Oct 21^st, 2013, 10:59am

I'll double that to {0, 4, 6, 8, 11, 13, 15, 19} and {1, 3, 5, 9, 10, 14, 16, 18} ;D
And again to {0, 4, 6, 8, 11, 13, 15, 19, 21, 23, 25, 29, 30, 34, 36, 38} and {1, 3, 5, 9, 10, 14, 16, 18, 20, 24, 26, 28, 31, 33, 35, 39}
And again, and again, and again, I'd wager.

So, well, let's say we can do it for any n that is a power of 2. Can we do it for 3? 5? 7?

Title: Re: Similar sets
Post by jollytall on Oct 21^st, 2013, 11:43am

n=3 is always unique. From the total of A' you can get to the total of A. From the largest of A' you know a2+a3, and from the smallest you know a1+a2.

n=4 is actually also doable from the n=2 with the trick from towr: {1,4} {2,3} ===> {1,4,12,13} {2,3,11,14}.

n=5 is like n=3. You know the total of a1+a2, a4+a5, from these you know a3. From the largest and second largest you know a4-a3, and from thereon it is easy.

Title: Re: Similar sets
Post by towr on Oct 21^st, 2013, 12:09pm

on 10/21/13 at 11:43:27, jollytall wrote:

n=4 is actually also doable from the n=2 with the trick from towr: {1,4} {2,3} ===> {1,4,12,13} {2,3,11,14}.

That's actually how I found it, I went from Grimbal's n=4 to n=2, spotted a possible pattern, then tried n=8 and n=16.
{0,4}, {1,3} ===> {0,4,1+5,3+5}, {1,3,0+5,4+5}

Title: Re: Similar sets
Post by jollytall on Oct 21^st, 2013, 12:37pm

Actually, I used +10 and the same sequence, since it is easy to recognise the logic. But also because the sets can have the same elements (ai=aj), it is enough to add 1:
{1,4}{2,3} ===> {1,4,3,4},{2,5,2,3}.

Title: Re: Similar sets
Post by jollytall on Oct 22^nd, 2013, 12:04pm

Any idea about n>5 and n<>2^k? I am especially interested in n=6. Any help would be appreciated. (My son of 14 has this question in school and he cannot solve it, neither can I help.)

Title: Re: Similar sets
Post by towr on Oct 22^nd, 2013, 1:05pm

on 10/22/13 at 12:04:28, jollytall wrote:

(My son of 14 has this question in school and he cannot solve it, neither can I help.)

In what context? Because you don't usually get problems in school where you don't first get the necessary methods and knowledge needed to solve it. Or was it simply a puzzle thrown into the classroom for no particular reason?

Title: Re: Similar sets
Post by Grimbal on Oct 22^nd, 2013, 1:14pm

I didn't see the pattern when I found n=4.

But indeed, the surprising pattern for a power of 2 is that A={positions of 0's in the Thue-Morse sequence}, B={positions of 1's in the Thue-Morse sequence}.

A={0,3,5,6,9,10,12,15,16,19,21,22,25,26,28,31}
B={1,2,4,7,8,11,13,14,17,18,20,23,24,27,29,30}

Title: Re: Similar sets
Post by Grimbal on Oct 22^nd, 2013, 2:43pm

The case n=6 is a bit tedious.

Suppose A={a,b,c,d,e,f}. You know only the 2-sums. Can you find a,b,c,d,e,f?

The sum of all 2-sums is 5*(a+b+c+d+e+f)
The 2 smallest sums are (a+b) and (a+c)
The 2 largest are (e+f) and (d+f)

You can compute
(c+d) = (a+b+c+d+e+f) - (a+b) - (e+f)
(b+e) = (a+b+c+d+e+f) - (a+c) - (d+f)
(a+f) = (a+b) + (a+c) + (d+f) + (e+f) - (a+b+c+d+e+f)
(b+d) = (a+b+c+d+e+f) - (a+c) - (e+f)
(c+e) = (a+b+c+d+e+f) - (a+b) - (d+f)

All of these you can identify among the 2-sums.
The remaining sums are
(b+c), (a+d), (a+e) that are <= (b+e)
(b+f), (c+f), (d+e) that are >= (b+e)

If you sum the first group and subtract (a+b) + (c+d) you get
(b+c) + (a+d) + (a+e) - (a+b) - (c+d) = (a+e).

Then you are almost done:
(f-e) = (a+f) - (a+e)
With (f+e) and (f-e) you can compute e and f.
From this, with the sums you already have the rest is trivial.

Title: Re: Similar sets
Post by Grimbal on Oct 22^nd, 2013, 2:47pm

By the way, who put this in easy?

Title: Re: Similar sets
Post by jollytall on Oct 22^nd, 2013, 9:33pm

Thanks Grimbal.
I put it in easy, though I did (do) not know the answer and wanted to avoid the mistake we see so often, that because one does not know the answer, it is hard.
The original question in school was for n=5,6,8., but I thought to generalise it for n.
I still wonder whether there is an easier logic that works for any n, or at least 5,6,8.
Re towr: It is an extra class's, extra homework. Questions are always from a wide range (numeric, geometry, etc.), so it is not strictly connected to the actual subject, what is btw. at the moment is the full induction. FI does not work, since some n-s are OK, some are not.

Title: Re: Similar sets
Post by rmsgrey on Oct 23^rd, 2013, 5:10am

So we've shown that, given a pair of sets for some n, you can find sets for 2^kn for any integer k>0 and that it's impossible to find a pair of sets for n in {3,5,6}.

Even more trivial than the n=2 case is the n=1 case (where both sets generate the empty set)

The open question is whether sets exist for any other n. A possible line of attack would be to try showing that for any pair of sets, you can decompose them into a pair half the size (so long as there's at least one sum).

Given a pair of sets and the common generated set, the lowest element of either set is then enough to determine the entire set (the lowest sum is the sum of the two lowest, so you can get the second lowest. The lowest remaining sum is the sum of lowest and third lowest, then the lowest remaining sum once you take out all pairs of the three lowest must be lowest and fourth lowest, and so on) so the two sets must have different lowest elements.

Given the difference between the lowest element of each set, the second lowest element has to have the same difference, but the other way around, and the same for the third lowest (by considering the lowest and second lowest pairs). So the sets must be {a,b',c',...} and {a',b,c,...} where x' is x plus the common difference. Consider b+c: in the other set, that has to be made up of something smaller than b (which must be a) and something larger than c' (call it d) so b+c=a+d, and must also be the third smallest sum. What I haven't nailed down is whether the counterpart of b'+c' has to be a'+d', or whether it could be b+c'' or c+b''...

Title: Re: Similar sets
Post by jollytall on Nov 7^th, 2013, 12:20pm

It was confirmed to me that if n<>2^k then there is no solution. The proof I still do not have, but was said that it exists.