Author |
Topic: Similar sets (Read 4052 times) |
|
jollytall
Senior Riddler
Gender: 
Posts: 585
|
 |
Similar sets
« on: Oct 20th, 2013, 11:33am » |
 Quote  Modify
|
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).
|
| « Last Edit: Oct 21st, 2013, 7:02am by jollytall » |
 IP Logged |
|
|
|
jollytall
Senior Riddler
Gender:
Posts: 585
|
|
Re: Similar sets
« Reply #1 on: Oct 21st, 2013, 7:01am » |
Quote Modify
|
Sorry, A typo. Both A and B are n elements. I fix it.
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: Similar sets
« Reply #2 on: Oct 21st, 2013, 7:02am » |
Quote Modify
|
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}
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Similar sets
« Reply #3 on: Oct 21st, 2013, 7:56am » |
Quote Modify
|
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.
|
| « Last Edit: Oct 21st, 2013, 7:59am by Grimbal » |
IP Logged |
|
|
|
jollytall
Senior Riddler
Gender:
Posts: 585
|
|
Re: Similar sets
« Reply #4 on: Oct 21st, 2013, 9:44am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Similar sets
« Reply #5 on: Oct 21st, 2013, 10:29am » |
Quote Modify
|
For n=4, I get {0,4,6,8} and {1,3,5,9}.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Similar sets
« Reply #6 on: Oct 21st, 2013, 10:59am » |
Quote Modify
|
I'll double that to {0, 4, 6, 8, 11, 13, 15, 19} and {1, 3, 5, 9, 10, 14, 16, 18} 
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?
|
| « Last Edit: Oct 21st, 2013, 11:03am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
jollytall
Senior Riddler
Gender:
Posts: 585
|
|
Re: Similar sets
« Reply #7 on: Oct 21st, 2013, 11:43am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Similar sets
« Reply #8 on: Oct 21st, 2013, 12:09pm » |
Quote Modify
|
on Oct 21st, 2013, 11:43am, 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}
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
jollytall
Senior Riddler
Gender:
Posts: 585
|
|
Re: Similar sets
« Reply #9 on: Oct 21st, 2013, 12:37pm » |
Quote Modify
|
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}.
|
|
IP Logged |
|
|
|
jollytall
Senior Riddler
Gender:
Posts: 585
|
|
Re: Similar sets
« Reply #10 on: Oct 22nd, 2013, 12:04pm » |
Quote Modify
|
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.)
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Similar sets
« Reply #11 on: Oct 22nd, 2013, 1:05pm » |
Quote Modify
|
on Oct 22nd, 2013, 12:04pm, 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?
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Similar sets
« Reply #12 on: Oct 22nd, 2013, 1:14pm » |
Quote Modify
|
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}
|
| « Last Edit: Oct 22nd, 2013, 1:22pm by Grimbal » |
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Similar sets
« Reply #13 on: Oct 22nd, 2013, 2:43pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Similar sets
« Reply #14 on: Oct 22nd, 2013, 2:47pm » |
Quote Modify
|
By the way, who put this in easy?
|
|
IP Logged |
|
|
|
jollytall
Senior Riddler
Gender:
Posts: 585
|
|
Re: Similar sets
« Reply #15 on: Oct 22nd, 2013, 9:33pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: Similar sets
« Reply #16 on: Oct 23rd, 2013, 5:10am » |
Quote Modify
|
So we've shown that, given a pair of sets for some n, you can find sets for 2kn 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''...
|
|
IP Logged |
|
|
|
jollytall
Senior Riddler
Gender:
Posts: 585
|
|
Re: Similar sets
« Reply #17 on: Nov 7th, 2013, 12:20pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print