If this sounds familiar, it's because I used a similar puzzle before.
There is a common theme with these two puzzles: parity. Parity is the property of being odd or even.
See the solutions
Monday, August 9, 2010
A pair of parity puzzles
If this sounds familiar, it's because I used a similar puzzle before.
There is a common theme with these two puzzles: parity. Parity is the property of being odd or even.
See the solutions
Subscribe to:
Post Comments (Atom)
11 comments:
The first is easy.
I'll have to think more about the second. The parity is not so obvious.
Ah... I think I've got #2. I'll wait until you post the answer to see if I'm right.
Agree, the first is straightforward.
The solution to the second has to do with pairing up the single-square ends of the N piece, since the thinnest projection ("sticky-out bit") of any shape made from O pieces will be two squares thick. I'll leave out further detail until others have had a look.
Ok, it's been a week.
With the first puzzle, number the
columns from 1 to 7 along the bottom starting at the left, and number the rows 1 to 7 up the side starting at the bottom. The square at the lower left is thus (1,1), the missing piece is (1,4), and the upper right square is (7,7).
Any square whose coordinates sum to an even number such as (1,1) or (2,6) is considered to be of "even" parity, with the remaining squares (with odd-number sums) being "odd" parity. This will produce an alternating pattern like a checkers/draughts board.
It can then be seen that the original full 7x7 grid consists of 25 "even" squares and 24 odd. The missing piece is (1,4) which is "odd" so there are now 25 "even" and 23 "odd" squares.
Any domino correctly placed on the squares must cover exactly one "even" and one "odd" square. Therefore, the best that can be achieved is to place 23 dominoes covering 46 "odd"-"even" pairs, with two "even" squares left over.
The second puzzle also does not seem possible but a clear eloquent proof escapes me.
The best that I can do is to note that the ends of the 'N' piece consist of a single square, each of which must be paired up at some point (ie they don't have to be adjacent) with another single-square end somewhere above or below it (in the orientation you have shown it).
The pieces can only be rotated in multiples of 90°. If the original 'N' piece's two ends are paired with the ends of two different pieces, there will still be two unpaired single-square ends. Therefore, the original 'N' piece's ends must pair with the ends of another single piece. No matter how many other 'N' pieces make up the final structure, each one must be paired (but not necessarily adjacent) with another, such that the ends are in line with each other. Thus the total number of pieces must be even.
Secret Squïrrel: With the first puzzle...
Nice. I got it wrong: I can't count.
My answer to #2 is the same as yours, but I'm not convinced it's correct.
Depending on the orientation of the N tetra, the ends have the same horizontal or vertical parity (the parity of the x or y coordinate alone). Therefore, with an odd number of N's, there's always an excess of vertical or horizontal parity.
I'm not convinced by this proof either. If each end needs to be paired, and each piece contributes two ends, why can't we have an odd number of pieces?
I did have an elegant proof in mind for this one, but it's not the first proof I thought of. I may give a hint later.
Interestingly, the same can be proven for any pair of tetrominoes.
Hmm... wait, now I see where your proof is going. If developed more, I think it should work.
(It would be easier if we were all in he same room and I could just move some tetronimoes around on a table).
What I mean is that if the 'N' piece (in the horizontal orientation you have depicted it) has its ends paired with the ends of two different horizontally oriented 'N' pieces, the unpaired ends of the two new pieces are "outliers" at the far left and right of the nascent structure. You can't then daisy-chain two (or 4, 6, etc) more horizontal 'N' pieces above or below them to pair them up.
Vertically oriented 'N' pieces can't alter the pairing (vertical parity) of horizontally oriented pieces (and vice versa). If used in the structure, they are subject to the same restrictions as horizontally oriented pieces and must also be paired.
I know it's a bit clunky but it's all I got right now.
By "paired" you just mean that the ends are in the same column (or, for vertical Ns, in the same row).
Yes, I think that proof works. It is clunky, but proofs often start out that way. Often, a really clever proof seems to come out of nowhere, but that's just because the clunky scaffolding has been removed.
You got it. Nice graphic analogy btw. Altho', sometimes when I remove the scaffolding the whole thing comes tumbling down!
Post a Comment