mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2007-04-02, 17:23   #1
davar55
 
davar55's Avatar
 
May 2004
New York City

108B16 Posts
Default 2n+1 Integers

Let a1,a2,...,a2n+1 be a collection of integers such that if any one element in the collection is removed, the remaining ones can be separated into two collections of n integers with equal sums.

Prove a1 = a2 = ... = a2n+1.
davar55 is offline   Reply With Quote
Old 2007-04-03, 03:01   #2
axn
 
axn's Avatar
 
Jun 2003

24·7·47 Posts
Default


1. If one of the numbers is odd, then all the numbers are odd. Similarly, if one of them is even, then all of them are even.

Proof: Suppose that there is atleast one odd and one even number in the collection. If you can make equal sums while leaving out the odd number, then you can't do the same while leaving out the even (change of parity).

2. If the given set of numbers, a[1]..a[2n+1] is a solution, then so is a[1]+c..a[2n+1]+c. (ie all numbers added/subtracted by a constant integer). Similarly a[1]*c..a[2n+1]*c (where c is a constant _real_ number) is also a solution, assuming that the results of multiplication/division are all integers.

3. Since LSB of all the numbers must be the same (by 1), we can say that (a[1]-LSB)/2 .. (a[2n+1]-LSB)/2 (ie all numbers right-shifted by 1) will also be a solution to the problem (by 2).

4. Repeat 1 & 3 until all the bits are shown to be equal, starting from LSB to MSB.
axn is online now   Reply With Quote
Old 2007-04-03, 07:45   #3
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

11001010010102 Posts
Default

I don't see that (2) is true unless the two groups
each contain n numbers.

Last fiddled with by davieddy on 2007-04-03 at 07:54
davieddy is offline   Reply With Quote
Old 2007-04-03, 08:39   #4
axn
 
axn's Avatar
 
Jun 2003

122208 Posts
Default

Quote:
Originally Posted by davieddy View Post
I don't see that (2) is true unless the two groups
each contain n numbers.
Quote:
Originally Posted by davar55 View Post
the remaining ones can be separated into two collections of n integers with equal sums.


Without it, 1,1,3,3,5 is a trivial counter-example:

Leaving out 5: 3+1 = 3+1
Leaving out 3: 5 = 3+1+1
Leaving out 1: 5+1 = 3+3

Last fiddled with by axn on 2007-04-03 at 08:49
axn is online now   Reply With Quote
Old 2007-04-03, 08:46   #5
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

647410 Posts
Default

THX. At least I have demonstrated that this stipulation was necessary.
davieddy is offline   Reply With Quote
Old 2007-04-03, 10:53   #6
S485122
 
S485122's Avatar
 
"Jacob"
Sep 2006
Brussels, Belgium

2×887 Posts
Default

The two groups had to be of n integers :
Quote:
Originally Posted by davar55 View Post
Let a1,a2,...,a2n+1 be a collection of integers such that if any one element in the collection is removed, the remaining ones can be separated into two collections of n integers with equal sums.

Prove a1 = a2 = ... = a2n+1.
S485122 is online now   Reply With Quote
Old 2007-04-03, 12:18   #7
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

153010 Posts
Default

Quote:
Originally Posted by davar55 View Post
Let a1,a2,...,a2n+1 be a collection of integers such that...
It is also true for (2*n+1) real numbers.
R. Gerbicz is offline   Reply With Quote
Old 2007-06-05, 15:58   #8
m_f_h
 
m_f_h's Avatar
 
Feb 2007

24×33 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
It is also true for (2*n+1) real numbers.
Proof: its true for a collection of rationals, which can be converted to integers by multiplying by the common denominator.

The extension to reals follows by.... "continuity" ?
Another (simpler(?)) proof ?
m_f_h is offline   Reply With Quote
Old 2007-06-06, 13:24   #9
victor
 
victor's Avatar
 
Oct 2005
Fribourg, Switzerlan

3748 Posts
Default

Quote:
Originally Posted by m_f_h View Post
Another (simpler(?)) proof ?
I agree. A different and simpler proof would be welcome
victor is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
rational integers wildrabbitt Math 17 2015-06-15 08:47
integers of the form (2 ^ t +1) / (2 ^ p + x) allasc Math 10 2011-01-26 18:43
Integers = sums of 2s and 3s. 3.14159 Miscellaneous Math 12 2010-07-21 11:47
Integers in a grid Unregistered Homework Help 1 2010-05-06 20:09
Given a set of R integers... Joshua2 Puzzles 19 2009-11-08 00:36

All times are UTC. The time now is 17:54.


Mon Jan 17 17:54:41 UTC 2022 up 178 days, 12:23, 0 users, load averages: 1.00, 1.24, 1.32

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔