Coin conundrum
Source: Australian Mathematical Society Gazette Puzzle Corner
Problem: There are coins of various sizes on a table, with some touching others. As often as you wish, you may choose a coin, then turn it over, along with every other coin that it touches. If all coins start out showing heads, is it always possible to change them to all tails using these moves?
Update (Nov 15, 2010):
Solution: Solution from the gazette author posted by me in comments! Interesting linear algebra solution posted by Siddhant Agarwal (EE, Senior Undergraduate, IITB) in comments!
Problem: There are coins of various sizes on a table, with some touching others. As often as you wish, you may choose a coin, then turn it over, along with every other coin that it touches. If all coins start out showing heads, is it always possible to change them to all tails using these moves?
Update (Nov 15, 2010):
Solution: Solution from the gazette author posted by me in comments! Interesting linear algebra solution posted by Siddhant Agarwal (EE, Senior Undergraduate, IITB) in comments!
To rephrase the problem:
ReplyDeleteGiven a simple graph can you "colour" a subset of its vertices such that
1. Each coloured vertex has an even "colored degree"
2. Each non-coloured vertex has an odd "coloured degree"
where a "coloured degree" is defined as the number of edges going to coloured vertices.
Define a subgraph as selecting a subset of the vertices and joining all the edges between them which were there in the original graph .Proof would be to consider the largest subgraph such that every vertex in that subgraph has an even degree and colour all vertices in that subgraph.
Anyone outside the subgraph will have an odd "coloured degree" as if it happened to have an even "coloured degree" it would be a part of the subgraph thus violating maximality of the subgraph.
I hope this soln is correct, but its definitely not elegant.
ReplyDeleteNo the vertices from 1 to n. Construct the adjacentcy matrix A of the graph.(i.e a(ij)=1 iff ai and aj are connected. generally a(ii)=0 is used) so S=A+I contains the diagonal entries as 1. (I is the identity matrix).
Let x = (x1,x2..xn) where xi=no of times the ith coin "is" flipped.
so this means
Sx=y = (y1,y2...yn) where yi=no of times the ith coins "gets" flipped. This construction proves that the order in which the coins are flipped is immaterial.
Now we want to find an x such that y has all elements odd. So taking modulo 2 on all sides.
Sx(mod 2) = S(x mod 2) = y mod 2 {as S has all elements either 0 or 1}
i.e we want to find an x (whose all elements are 0 or 1) s.t
Sx=(1,1..1)
This shows that if there exists a flipping scheme to invert all the coins then there exists a scheme to invert all coins such that no coin "is" flipped more that once.
hence the problem is this. If S is a symmetric matrix with entries from the finite field F2 with diagonal entries 1, then there exits a vector x (with entries belonging to F2) s.t
Sx=(1,1..1)
clearly if det(S)!=0 (i.e det(S)=1) then S is invertible and x = inv(S)*(1,1..1)
{corollary: if det(S)=1 then there is a soln to Sx=y for any y.. i.e we can get any arrangement of heads and tails)
So let det(S)=0; we use induction:
let n be even and the claim is true till n-1. let Si be the matrix obtained from S by removing the ith row and column. So applying the claim to Si 1<=i<=n. We can generate (0,1,1,1..1) and (1,0,1,...1) etc. {if one Si gives (1,1,..1) then the proof ends there} =>we can generate (1,1..1) {add all of them}
so let n be odd. so we can generate (0,1,..1) and (1,0,1..1) by earlier argument. note that out of there n vectors (n-1) are independent. Also det(S)=0 => every column of S can be written as a linear combination of (0,1..1),(1,0,1,,1) etc.
Now that is a contradiction coz any vector that is a linear combination of those vectors has an odd no of zeroes. So as n is odd the no of zeroes in S is odd. But S is symmetric matrix with diagonal entries 1. Contradiction!!!
Solution taken from austms gazette:
ReplyDeleteThe answer is yes, it is always possible to flip every coin.
First let us define a hyper-flip.
A hyper-flip on coin X is a combination of moves
that flips every coin in the arrangement except coin X.
This is a proof by induction. Assume that any arrangement of n-1 coins can be flipped using an appropriate sequence of moves. This means that for any subset of size n-1 of our n coins, there exists a sequence of moves that flips this subset.
This sequence might flip the nth coin or it might not. If the sequence of moves does flip the nth coin (for any one of the (n-1)-coin subsets), then we are done.
It suffices to consider the cases where it’s possible to perform a hyper-flip about any arbitrary coin.
If n is even, we simply perform a hyper-flip on each coin successively. As a result, each coin is flipped n-1 times.
If n is odd, then at least one coin is touching an even number of other coins. This is because the total of adjacencies summed over all coins, which equals to twice the total number of adjacent pairs of coins, is even. Let X be a coin with 2k neighbours. Perform a hyper-flip on X, plus a hyper-flip on each of the neighbours
of X. Then finish with an ordinary flip on X. Each coin was flipped exactly 2k+1 times.
In both cases, every coin was flipped an odd number of times, hence from head to tail. This completes the proof.
above soln is simply awesome! Still let me clarify my soln:
ReplyDeletefirst we convert the problem to this: Does there exist a vector x such that Sx = (1,1,..,1) for all symmetric S with diagonal entries 1 and entries of x and S are 0 and 1.
Next we show that if Det(S)!=0 then it has a soln.
So now suppose Det(S)=0. We use induction to show that it has soln for this case. Consider two cases, n even and n odd.
For n=even we show that if the conjecture is true for n-1 then it is true for n. (by generating vectors (0,1,1..,1),(1,0,1,..,1))
For n=odd we assume it is true for n-1=even. Now we assume that the conjecture is false for n and derive a contradiction. The contradiction comes as follows: we use a linear algebra argument to say that det(S)=n-1. Then we say that the number of 0 entries in each column of S is odd. As n is odd => total number of 0 entries in S is odd. But S is a symmetric matrix and has 1's on the diagonal. => S has even number of 0 entries. This is a contradiction.
@Siddhant.. Thanks a lot. :) Now I got it. :)
ReplyDelete