You are currently browsing the category archive for the ‘Puzzles’ category.
Who doesn’t like self-referential paradoxes? There is something about them that appeals to all and sundry. And, there is also a certain air of mystery associated with them, but when people talk about such paradoxes in a non-technical fashion indiscriminately, especially when dealing with Gödel’s incompleteness theorem, then quite often it gets annoying!
Lawvere in ‘Diagonal Arguments and Cartesian Closed Categories‘ sought, among several things, to demystify the incompleteness theorem. To pique your interest, in a self-commentary on the above paper, he actually has quite a few harsh words, in a manner of speaking.
“The original aim of this article was to demystify the incompleteness theorem of Gödel and the truth-definition theory of Tarski by showing that both are consequences of some very simple algebra in the cartesian-closed setting. It was always hard for many to comprehend how Cantor’s mathematical theorem could be re-christened as a“paradox” by Russell and how Gödel’s theorem could be so often declared to be the most significant result of the 20th century. There was always the suspicion among scientists that such extra-mathematical publicity movements concealed an agenda for re-establishing belief as a substitute for science.”
In the aforesaid paper, Lawvere of course uses the language of category theory – the setting is that of cartesian closed categories – and therefore the technical presentation can easily get out of reach of most people’s heads – including myself. Thankfully, Noson S. Yanofsky has written a nice paper, ‘A Universal Approach to Self-Referential Paradoxes, Incompleteness and Fixed Points’, that is a lot more accessible and fun to read as well.Yanofsky employs only the notions of sets and functions, thereby avoiding the language of category theory, to bring out and make accessible as much as possible the content of Lawvere’s paper. Cantor’s theorem, Russell’s Paradox, the non-definability of satisfiability, Tarski’s non-definability of truth and Gödel’s (first) incompleteness theorem are all shown to be paradoxical phenomena that merely result from the existence of a cartesian closed category satisfying certain conditions. The idea is to use a single formalism to describe all these diverse phenomena.
(Dang, I just found that John Baez had already blogged on this before, way back in 2006!)
Among several things, these days, I have been doing some (serious) reading of literature on psychology, cognitive development, learning, linguistics, philosophy and a few other subjects. Well, the ones I just named happen to be parts of interdisciplinary areas, which are precisely the ones I am interested in. Of course, on many levels those parts also have a lot to do with mathematics, especially mathematical education. Ok, that was just a little background I wanted to provide for the content of today’s post.
I need to do a small (online) experiment in order to test a hypothesis, which will be the subject of my next post. Let me not reveal too much for now. The experiment is in the form of two puzzles that I ask readers (you!) to solve. They are both “multiple choice” puzzles with exactly two correct answers to each. Please bear in mind that this is NOT an IQ test. It is also not meant to test how good you are at solving puzzles individually. I am really interested in “aggregate” results. That is, for testing my hypothesis, I am only interested in what the majority thinks are the right answers. What is more, you won’t be graded, and no one (not even me) will ever know if you got the right answers. Please submit answers to both the puzzles.
Lastly, please don’t cheat or try to look for answers offline or online. As I said, this is NOT a test!
Let us now look at the puzzles.
There are four cards, labelled either X or Y on one side and either 3 or 7 on the other. They are laid out in a row with their top (visible) sides shown like this: X Y 3 7. A rule states: “If X is on one side then there must be a 3 on the other.” Which two cards do you need to turn over to find out if this rule is true?
As you walk into a bar, you see a large sign that reads, “To drink alcohol here you must be over 18.” There are four people in the bar. You know the ages of two of them, and can see what the other two are drinking. The situation is: Alisa is drinking beer; Dymphna is drinking Coke; Maureen is 30 years old; Lauren is 16 years old. Which two people would you need to talk to in order to check that the “over 18 rule” for drinking alcohol is being followed?
If you think you have the answers to those puzzles, then please click here Puzzles to submit your answers. (I couldn’t use PollDaddy to embed the above puzzles in this post because I am not allowed more than 160 characters in a single question. What a pain!) So, please go ahead and click the above link to submit yours answers.
Note: I will keep this “poll” open for a week to collect as much data as possible. Thanks!
Update: It seems many readers weren’t aware of the short duration of the “poll” and that they would have very much liked to participate. So, I am extending the poll till Jan 7, 2010 for them. (Doing so would also help me in collecting more data.)
I thought I would share with our chess-loving readers the following interesting (and somewhat well-known) mathematical chess paradox , apparently proving that , and the accompanying explanation offered by Prof. Christian Hesse, University of Stuttgart (Germany). It shows a curious connection between the well-known Cassini’s identity (related to Fibonacci numbers) and the chessboard ( being a Fibonacci number!). The connection can be exploited further to come up with similar paradoxes wherein any -square can always be “rerranged” to form a -rectangle such that the difference between their areas is either or . Of course, for the curious reader there are plenty of such dissection problems listed in Prof David Eppstein’s Dissection page.
The solutions are in! This problem of the week was interesting for me: the usual pattern has been that I pose problems that I’ve solved myself at some point in the past, giving me a kind of “inside edge” on understanding the solutions that come in. But, as I said in POW-12, the difference this time is that the solution I knew of came from someone else (Arin Chaudhuri). What was interesting for me — and given the circumstances, it was probably inevitable — is that some of the solutions we received forced me to make contact with some mathematics I’d only heard about but never studied. Let me get to that in a minute.
Another interesting thing for me — speaking now with my category theorist’s hat on — is how utterly simple and conceptual Arin’s proof was! I was pleased to see that regular problem solver Philipp Lampe also spotted it. Wait for it…
Solution I by Philipp Lampe, University of Bonn: The answer is 8.
Among the eight neighbors of an arbitrary vertex, all colors of an admissible coloring must occur. Thus, 8 is an upper bound for the maximum number of colors one can use. We have to show that there is an admissible coloring with eight colors.
The vertices of the 8-dimensional cube may be represented by vectors with in , in other words as vectors in , the 8-dimensional vector space over the field with two elements (i.e., the integers modulo 2). Two such vectors are neighbors iff their coordinate vectors differ in exactly one place, in other words if considered modulo 2, where is one of the eight standard basis elements (with -th coordinate 1, and the other coordinates 0).
Now let our “colors” be the 8 elements of , the 3-dimensional vector space over . Let the vertex “coloring”
be the unique -linear map such that ; that is, define the color of a vertex/vector by
Now, if is any vector, the colors of its neighbors are . The colors of these neighbors are all distinct since the are distinct. Hence all 8 colors are represented among the colors of the neighbors of any given vertex , QED.
What I love about this solution it is how natural it is. I’ll say a little more about this in remarks below.
But I also learned a thing or two by studying the next solution. It relies on the theory of Hamming codes, with which I was not conversant. Up to some small edits, here is exactly what Sune Jakobsen submitted:
Solution II by Sune Jakobsen (first-year student), University of Copenhagen: Since each vertex only has 8 neighbors, the answer cannot be greater that 8.
Now we construct such a coloring with 8 colors. An 8-dimensional cube can be represented by the graph with vertices in , and with an edge between them iff the Hamming distance between them is 1. We color a vertex with color 8 if the seven first bits in the vertex is a “correct” Hamming message (cf. Hamming code (7,4)), and color it in color if the first seven bits give a correct Hamming message upon changing bit . This is a well-defined coloring, since each element in is either a correct Hamming message, or is Hamming distance 1 away to exactly one correct Hamming message.
It remains to show that no vertex is neighbor to two vertices of the same color. The Hamming distance between these two vertices is 2, thus the Hamming distance between the first 7 bits of two neighbors must be 1 or 2. If two neighbors had the same color , then by definition one would get two correct Hamming messages by changing bit in both of them, and the Hamming distance between these messages would be the same as before — either 1 or 2. But the distance between any two correct Hamming messages is at least 3. Contradiction.
1. Let me give a little background to Sune’s solution. Mathematically, the Hamming code called “(7, 4)” is the image of injective linear map
given by the matrix
The Hamming code is what is known as an “error-correcting code”. Imagine that you want to send a 4-bit message (each bit being a 0 or 1) down a transmission line, but that due to noise in the line, there is the possibility of a bit being flipped and the wrong message being received. What can you do to help ensure that the intended message is received?
The answer is to add some “parity check bits” to the message. In the code (7, 4), one adds in three parity checks, so that the transmitted message is 7 bits long. What one does is apply the matrix to the 4-vector, to get a 7-vector (remember we’re working modulo 2), and this 7-vector is sent down the line. Assuming only a moderate amount of noise in the transmission line, perhaps the 7-bit message will remain intact or perhaps a single bit will be flipped, more rarely two bits will be flipped (and we’ll assume the event that more than two are flipped has negligible probability). Now, the Hamming encoding is rigged up so that if the 7-bit vector is received as sent, then the parity checks will report 0 errors. If the parity checks report an error, they report precisely where the error occurred if the received vector was off by one bit. (If two flips occurred, then the receiver can still detect from the parity checks that an error occurred. The parity checks can never detect how many bits were flipped, but if the receiver assumes correctly that just one bit got flipped, he can restore the intended message with accuracy. If three or more got flipped, then the receiver got the wrong message, but he would never know it if the parity checks reported back 0 errors.)
How does this work? By having the receiver apply a parity-check matrix to the received message, given by the matrix
In the first place, , and so if the message received belongs to the image of (is a “correct Hamming message” in the terminology of Solution II), which will indeed be the case if there were no errors in the transmission, then applied to the message will produce the zero vector. In the case where one bit got flipped in the transmission, applied to the received vector will return a nonzero 3-vector, but the beauty of the Hamming code is that the 3-vector will spell out in binary the bit the error occurred (for example, if the output vector is , then error occurred in the bit with binary number 011, that is bit 3). In that case, the receiver flips that bit to restore the original message. In these two cases, the original 4 bits are then read off as the 3rd, 5th, 6th, and 7th coordinates of the (possibly corrected) 7-vector.
By the way, Sune reminded us that Hamming codes also came up in a post by Greg Muller over at The Everything Seminar, who used the existence of a Hamming code in every dimension to solve general hat-guessing puzzles.
2. Within minutes of posting the original problem, we received a message from David Eppstein, who reported that the solution of 8 colors is essentially contained in a paper he coauthored with T. Givaris (page 4); his solution is close in spirit to Sune’s.
Arin Chaudhuri also surmised the connection to Hamming codes, and mentions that the problem (in a slightly different formulation) originally came from a friend of a friend, who blogs about a number of related problems on this page. Presumably the author had things like error-correcting codes in mind.
3. Sune and David noted that their solutions generalize to show that on the -dimensional cube (for any ), it is possible to color the vertices with colors (the maximum number possible) so that all of the colors show up as colors of the neighbors of any given vertex.
This is very easy to see by adapting Philipp’s method. Indeed, for each just take the color set to be the -vector space . The set of vertices of the -dimensional cube may identified with the -vector space generated by the set (as basis), and the desired coloring is then just the -linear map that extends the identity function on . As mathematical constructions go, you can’t get much more canonical than that! No fuss, no muss — it’s a purely categorical construction (categorists call it a counit of an adjunction). So then why didn’t I see that myself? 🙂
4. We’re still not sure what the story is in other dimensions. If is the maximum number of admissible colors in dimension , then about all any one of us knows right now is that for , is weakly monotone increasing, and that if is not a power of 2. There’s a conjecture afloat that where is the floor function, but for now that should be treated as a wild guess. If anyone has further information, please let us know!
Solved by Arin Chaudhuri, David Eppstein, Sune Jakobsen, and Philipp Lampe. Thanks to all those who wrote in!
Or, at least, that’s what this blog post at Science and Math Defeated aims to do. Normally, I avoid writing on such a topic but I think the following example could be instructive to a few people, at least, in learning how not to infer from mathematical induction. The author of that blog post sets to “disprove” the foundation of Calculus by showing that the “assumption” leads to a contradiction (which I am sure most of you have seen before.) And this is supposed to be achieved through the use of Mathematical Induction.
Let be the statement for all and .
Claim: is true for all .
Proof: , and so, is true. This takes care of the base case. Now assume is true for some , where . Now, it is easy to show that is true as well (I just skipped some details!). Hence, holds. This takes care of the induction step. (Note that is shown to be true independent of !) And, this proves our claim.
(Erroneous) Conclusion: Hence, .
Notwithstanding the inductive proof (which is correct) above, why is the above conclusion wrong?
Ans. Because “infinity” is not a member of .
(Watch out for Todd’s next post in the ETCS series!)
Time for another Problem of the Week! This one is rather elementary, but is connected with a pet topic of mine which I plan to write a post on soon:
If a baseball player’s batting average is .334, what is the minimum number of times he’s been up at bat?
[Note for those who are not fans of baseball: a player’s batting average is (number of hits made)/(number of times at bat), rounded to three decimal places.]
Please submit solutions to topological[dot]musings[At]gmail[dot]com by Wednesday, July 30, 11:59 pm (UTC); do not submit solutions in Comments. Everyone with a correct solution will be inducted into our Hall of Fame! We look forward to your response.
The solutions are in! There was quite a bit of activity behind the scenes on this one; POW-7 might look intuitively obvious, as if it should succumb to an easy application of the intermediate value theorem, but for a number of people who fought through it, this problem fought back! (And that was true for me too, when I first encountered it.)
This problem appears as problem B-4 from the 1977 Putnam Competition. A couple of readers hit upon the snappy solution proposed by the problem compilers [as given in The American Mathematical Monthly vol. 86 (1979), pp. 749-757]. I’ll give that solution, and follow up with a few remarks on alternate approaches, and on some of the thoughts the problem evoked in our readers. Thanks to all who wrote in!
Composite solution by Kenneth Chan and Paul Shearer: By translation, we may assume that the given point is the origin. Let . It suffices to show that is nonempty, for if belongs to this set, then both and , so that is the midpoint .
The interior regions of intersect (e.g., is in both regions), so if , then by connectedness of the curves , one of them must be contained in the interior of the other. But this is absurd; for example, it is clear that
and so if the sup is realized at a point which is interior to , then the boundary of the nonempty set contains a point of whose distance from the origin exceeds this shared sup, contradiction.
1. One could just as easily observe that the regions are congruent and therefore have the same area, so that one of these regions cannot be strictly contained in the other. Therefore, unless , some of is interior to and some is exterior; since is connected, it must therefore intersect the border of . Similarly, the exterior of must be partly inside and partly outside, so it too must intersect . In other words, some of is interior to and some is exterior to , and so by connectedness of , it must cross , as desired. This argument is substantially the one given by Sune Jakobsen.
2. Assuming is at the origin, a number of people tried to argue that (in polar coordinates) the radius of a point on is a function of its angle , and since sometimes takes non-positive values and sometimes non-negative values, it should take on the value 0 somewhere by the intermediate value theorem. The pitfall though is that is not necessarily a well-defined function of (consider non-convex curves where a radial line meets in more than one point). Some other readers seemed to notice this and tried a surrogate function where along the radial line at angle , you choose the closest distance from to the origin; the trouble there is that this new function might not be continuous (there will typically be a jump discontinuity at angles where the radial line is tangent to ).
3. The obstructions mentioned in remark 2. are of a sort which is ubiquitous in topology, where one would like to construct a continuous choice function (e.g., in the theory of vector bundles or fiber bundles, where one is interested in whether continuous sections of a bundle projection exist). À propos of that, Paul Shearer made an intriguing suggestion (in a comment here), that POW-7 would follow from the stronger conjecture that the space of pairs of points on which “straddle” (i.e., where the points and live on the same line, but the points are on opposite sides of ) should be path-connected. That is, given two pairs , the conjecture is that we can choose a continuous path through which gets us from to . Subsequently, Paul found a counterexample to this conjecture. Can you find one? [Edit: I had invited Paul to comment on this, but then missed the fact that he had already done so! My bad – TT.]
4. Miodrag Milenkovic came up with a related problem which can be posed in any dimension. Consider any -sphere embedded in (POW-7 concerns the case ), and let be a point interior to the embedded sphere. [Note: the complement of such an embedded sphere consists of two connected components, i.e., an “interior” and “exterior”, although this fact isn’t completely trivial; see theorem 36.3 (generalized Jordan curve theorem) in Munkres’s Elements of Algebraic Topology. These regions can be topologically complicated, as we know from the example of the Alexander horned sphere.] Miodrag asks: is it true that there exists a plane through so that is the center of mass (barycenter) of the -dimensional region where the interior intersects the plane?
I am not entirely decided on the answer to this question, although I think I have a nice topological argument that the answer is yes, if we assume some mild smoothness assumption on the embedding. I am frankly a little scared of the problem in full topological generality, due to the pathology one may encounter in the topological category!
POW-7 was also solved by Arin Chaudhuri, Sune Jakobsen, Philipp Lampe, and Peter LeFanu Lumsdaine. Thanks again to all for the stimulating correspondence!
Let be a simple closed curve in the plane, and let be any point strictly in the region interior to . Show there are two points on whose midpoint is .
Please submit solutions to topological[dot]musings[At]gmail[dot]com by Wednesday, July 9, 11:59 pm (UTC); do not submit solutions in Comments. Everyone with a correct solution will be inducted into our Hall of Fame! We look forward to your response.
This week’s problem is offered more in the spirit of a light and pleasant diversion — I don’t think you’ll need any deep insight to solve it. (A little persistence may come in handy though!)
Define a triomino to be a figure congruent to the union of three of the four unit squares in a square. For which pairs of positive integers is an rectangle tileable by triominoes?
Please submit solutions to topological[dot]musings[At]gmail[dot]com by Wednesday, July 3, 11:59 pm (UTC); do not submit solutions in Comments. Everyone with a correct solution will be inducted into our Hall of Fame! We look forward to your response. Enjoy!