Author |
Topic: odd coins (Read 676 times) |
|
Aryabhatta
Uberpuzzler
Gender: 
Posts: 1321
|
I tried searching but could not find this on the site.
You are given 2n+1 coins such that if you remove any coin, the rest of the 2n coins can be split into two sets of n coins each such that the sum of weights of the coins of the first set is equal to the sum of weights of the coins of the second set.
Show that each coin must have the same weight.
The solution I know requires undergraduate math. But that does not mean there might be other elementary solutions, so I am posting this to the hard section instead of the putnam section.
|
|
 IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
 |
Re: odd coins
« Reply #1 on: Jul 3rd, 2004, 6:50am » |
 Quote  Modify
|
on Jul 3rd, 2004, 6:10am, Aryabhatta wrote:I tried searching but could not find this on the site.
|
|
Ok.
I found in the medium riddles page under "COINS SAME WEIGHT".
Sorry. 
|
|
IP Logged |
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: odd coins
« Reply #2 on: Jul 3rd, 2004, 4:42pm » |
Quote Modify
|
I couldn't find a thread by that name anywhere.
|
|
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: odd coins
« Reply #4 on: Jul 4th, 2004, 10:47am » |
Quote Modify
|
(i thought the following isn't something which needs to be hidden since it is rather incomplete)
let w1,w2,...,w[2n+1] be the weights.
if w1 is removed, i see that,
w2+/-w3+/-......+/-w[2n+1] = 0
(equal no of + and - in the above equation)
from the above problem 2n+1 such linear equations can be obtained.
It is quite evident that w1=w2=w3=...=w[2n+1] is one non-trivial solution. Now the important thing to be proven is that this is unique.
Only way i can think of doing this is showing that the rank of the matrix W is equal to 2n+1 or det(W)!=0 ... I have not been able to prove any of these ... (hence incomplete!)
[edit]
duh! it is obvious that det(W)==0!! hence the rank is definitely not 2n+1. As i see and now realise it shouldn't have been 2n+1 anyways then the only possible solution would have been all w's equal to 0 (  ).
now if we are looking for non-zero solutions then it is to be proved that rank is 2n  (duh!maybe i am talkin non-sense here)
[/edit]
|
| « Last Edit: Jul 4th, 2004, 10:58am by TenaliRaman » |
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: odd coins
« Reply #5 on: Jul 5th, 2004, 10:42pm » |
Quote Modify
|
on Jul 4th, 2004, 10:47am, TenaliRaman wrote:
duh! it is obvious that det(W)==0!! hence the rank is definitely not 2n+1. As i see and now realise it shouldn't have been 2n+1 anyways then the only possible solution would have been all w's equal to 0 ( ).
now if we are looking for non-zero solutions then it is to be proved that rank is 2n (duh!maybe i am talkin non-sense here)
|
|
What you talk makes perfect sense. The rank must be 2n.
if it was any lesser, then there would be a solution with not all weights equal. The reverse holds too. If the rank is 2n, then the only solutions are all weights equal.
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: odd coins
« Reply #6 on: Jul 10th, 2004, 9:12am » |
Quote Modify
|
Is this thread dead?
|
|
IP Logged |
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: odd coins
« Reply #7 on: Jul 10th, 2004, 10:36am » |
Quote Modify
|
Just solved it today!
A minor hint : wi,j=1(mod 2) where i!=j
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: odd coins
« Reply #8 on: Jul 10th, 2004, 12:58pm » |
Quote Modify
|
on Jul 10th, 2004, 10:36am, TenaliRaman wrote:
Can you please post your approach? I am afraid your 'minor' hint does not give any idea as to your approach.
Here is the sketch of a proof i had in mind:
Let N = 2n+1.
We have an NxN matrix W with
wij = 1 or -1 if i [ne] j
wii = 0.
Consider P(t) = det(W -tI), the characteristic polynomial of W.
Consider the coefficient of t. We can show that the coefficient of t is the sum of ND terms, each term being 1 or -1 and D being the number of derangements of N-1 numbers. We can also show D is odd. So coefficient of t is non-zero as it is a sum of odd number of 1's and -1's.
Which implies rank(W) [ge] 2n. Since det(W) = 0, rank(W) = 2n.
[]
|
| « Last Edit: Jul 10th, 2004, 12:59pm by Aryabhatta » |
IP Logged |
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: odd coins
« Reply #9 on: Jul 10th, 2004, 2:28pm » |
Quote Modify
|
Very Nice Proof Aryabhatta!
::
wi,j = 1 (mod 2) where i!=j ...(1)
If i remove a row and column, i would be getting a matrix W2n.
Let D be a dummy matrix which consists of all 1's.
Then from (1) i can write that,
W2n=(D2n-I2n)(mod 2)
W2n2=I2n(mod 2)
det(W2n)=1(mod 2)
hence det(W2n)!=0
::
|
| « Last Edit: Jul 10th, 2004, 2:29pm by TenaliRaman » |
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: odd coins
« Reply #10 on: Jul 11th, 2004, 12:27pm » |
Quote Modify
|
on Jul 10th, 2004, 2:28pm, TenaliRaman wrote:wi,j = 1 (mod 2) where i!=j ...(1)
If i remove a row and column, i would be getting a matrix W2n.
Let D be a dummy matrix which consists of all 1's.
Then from (1) i can write that,
W2n=(D2n-I2n)(mod 2)
W2n2=I2n(mod 2)
det(W2n)=1(mod 2)
hence det(W2n)!=0
:: |
|
Elegant!
This works because we are only dealing with integers and we have that xy mod 2 = ((x mod 2) (y mod 2)) mod 2 and (x+y) mod 2 = ((x mod 2) + (y mod 2)) mod 2.
Pretty neat!
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print