0

This is what I mean: I have three numbers $[a,b,c]$ and I can produce a set from the numbers comprised of pairs of $1$ number and the sum of the other two numbers, ie. $\{(a, b+c), (b, a+c), (c, a+b)\}$. With four numbers $[a,b,c,d]$, the set becomes $\{(a, b, c+d), (a, c, b+d), (a, d, b+c), (b, c, a+d), (b, d, a+c), (c, d, a+b)\}$.

Edit: The pairs in the set are unordered, so $(1,2)$ is the same as $(2,1)$

I need to be able to give a general definition of this set for any size of the initial set of numbers. This is for a proof that would involve that set for any size.

For some background, I am trying to prove that for three numbers $[a,b,c]$ no two pairs from the set can contain the same number. For four numbers $[a,b,c,d]$, no two triples from the set can contain two of the same numbers. For five numbers $[a,b,c,d,e]$ no two elements can contain three of the same numbers, etc. I have proved this for $3$ and $4$, but it gets very tedious for $5$. (I am not sure that it works for larger numbers, so if anyone knows that it doesn't (or if there is already a proof like this out there somewhere) please let me know and the question is moot.)

This is how I have started:

For any set of integers $I=(i_1, i_2, i_3, ..., i_n)$ used to generate a set of the form $\{(i_1,\dots, i_{n-2},(i_{n-1}+i_{n})),(i_1,\dots, i_{n-3}, i_{n-1}, (i_{n-2}+i_{n})),\dots)\}$

But I'm not sure how to define the full set, or ever if it can be defined in such a way. I can easily define it in words as "the set of (pairs, triples, etc.) containing all but two of the integers from $I$ and the sum of the remaining two", but this really doesn't help me with my proof at all.

Asaf Karagila
  • 393,674
JPrince
  • 1
  • When you say you have three numbers, $[a, b, c]$, do you mean three distinct numbers, so that $[1,1,1]$ and $[2, 4, 4]$ or even $[3, 4, 3]$ are not allowed? – John Hughes Jun 17 '19 at 19:24
  • @JohnHughes duplicate numbers in the initial numbers are allowed (but that means that the set would be smaller, since there would be some duplicate entries). ie. if the numbers were [1, 1, 1], the set would just be {(1, 2)} – JPrince Jun 17 '19 at 19:27
  • If I start with $[3_1, 4, 3_2]$, where I've used subscripts to "name" the two copies of $3$, the ordered pairs I get are $(3_1, 7), (4, 6), (3_2, 7)$; the first and last of these "contain the same number" (or numbers!), which appears to contradict the claim you're trying to prove. I think I must be misunderstanding something. – John Hughes Jun 17 '19 at 19:31
  • @JohnHughes Those are the right pairs, but since its a set, only one instance of (3,7) would appear. So the final set would be {(3,7), (4, 6)}. (Unless I am mis-remembering my sets) I also forget to mention at first that the pairs are unordered - I have made an edit to include that. – JPrince Jun 17 '19 at 19:39
  • @B.Swan is the j+1 supposed to be a j-1? – JPrince Jun 17 '19 at 19:47
  • $I=(i_1,i_2,...,i_n)$ then your set $S_I={(i_1,...,i_{k−1},i_{k+1},...,i_{j-1}, i_{j+1},...,i_n,i_k+i_j)|1≤k<j≤n}$ – B.Swan Jun 17 '19 at 19:48
  • Yeah I had to delete and and repost my comment because I have missed it and couldnt edit... the "definition" I have given is a little sloppy but I hope its good enough – B.Swan Jun 17 '19 at 19:48
  • Let's look at $(5,0, 3)$. That produces three pairs: $(5,3), (0, 8), (3, 5)$. The number "5" appears in two of those pairs. Isn't that a counterexample? – John Hughes Jun 17 '19 at 20:09
  • @JohnHughes the pairs are unordered, so (5, 3) is the same as (3, 5). I added an edit near the top of the question to clarify. – JPrince Jun 17 '19 at 20:22
  • Perhaps you should use set notation, i.e., ${1, 2, 5}$, which is intrinsically unordered, rather than ordered-tuple notation, $(1, 2, 5)$, which is intrinsically ordered. It's likely to lead to less confusion among your readers. – John Hughes Jun 17 '19 at 20:28
  • So the $n = 3$ case is trivial, for if two pairs share one number, they also share the OTHER number (because the sum of the numbers in a pair is the sum of the three original numbers), and once the pairs share BOTH numbers, they're the same, i.e., they aren't different elements of the set of pairs. – John Hughes Jun 17 '19 at 20:29
  • In fact ... that's really a proof of the general case, too. I know this doesn't answer your notation question (for which I have no good answer), but it at least addresses the overall problem. – John Hughes Jun 17 '19 at 20:32
  • @JohnHughes I think set notation is avoided to allow repetitions in the tuples. For example $(1,1,1,1)$ would give tuples $(2,1,1)$, if that would be a set it would be only ${1,2}$ – B.Swan Jun 17 '19 at 20:43
  • @JohnHughes I hadn't thought of it like that, but you're right, it makes perfect sense. That proves the general case in just a few words. I wrote down about a page of proof for the 4-number case. That's a relief. Thanks for the help! – JPrince Jun 17 '19 at 20:43
  • @B.Swan yes, that is why I originally did't use set notation. Thanks for the help with the notation as well! – JPrince Jun 17 '19 at 20:45

0 Answers0