Mathematics, applications of mathematics to life in general, and my life as a mathematician.
Archive for the ‘Puzzles’ Category.
We know that tripling the triangular number 1 yields the triangular number 3. The figure shows how we can use this fact to conclude that tripling the triangular number 15 yields the triangular number 45.
Using this new fact, can you modify the figure to find even larger examples of tripling triangles?
This post is inspired by the following problem:
Sleeping Beauty participates in the following experiment. On Sunday she is put to sleep, and a fair coin is flipped. Regardless of the result of the coin flip, she is awakened on Monday and asked whether she thinks the coin was heads or not. If the coin was tails, however, then she is put back to sleep with her memory erased, and awakened on Tuesday and asked the same question again. She knows the protocol. She is awakened one morning: What is her probability that the coin was heads?
Some people argue: asleep or awake, the probability of a fair coin being heads is one half, so her probability should be one half.
Other people, including us, argue that those people didn’t study conditional probability. On the information of the setup to the problem and the information of having awakened, the three situations “Coin was heads and it is Monday”, “Coin was tails and it is Monday”, and “Coin was tails and it is Tuesday” are symmetric and therefore equiprobable; thus the probability that the coin was tails is, on this information, two thirds.
So who is right? We are, of course. A good way to visualize probability judgements is to turn them into bets. Suppose each time Beauty wakes up she is offered the following bet: She pays $600 and gets $1000 if the coin was tails. Should she take it? If her probability of the coin being tails were one half, then obviously not; if her probability of the coin being tails were two thirds, obviously yes. So which is it? Consider the situation from her perspective as of Sunday. She can either always take this bet or always refuse it. If she always refuses, she gets nothing. If she always accepts: If the coin turns up heads, she will be asked the question once and will lose $600. If the coin turns up tails, she will be asked the question twice and will gain $800. So on average she will win, so she should take the bet. By this thought experiment, her probability of tails is clearly not one half.
To make matters more interesting, let’s try another bet. Suppose she is given the above bet just once, in advance, on Sunday. She pays $600, and she gets paid $1000 on Wednesday if the coin was tails. This has nothing to do with sleeping and awakening. If she takes the bet she loses $600 with probability one half and gains $400 otherwise. So she shouldn’t take the bet. Her probability on Sunday that the coin will come up heads is, of course, one half. The point is that just as these two bets are different bets, the sets of information Beauty has on Sunday vs at awakening are different, and lead to different conclusions. On Sunday she knows that the next time she wakes up it will be Monday, but when she then wakes up, she doesn’t know that it’s Monday.
Parting thought: The phenomenon of predictably losing information leads to the phenomenon of predictably changing one’s assessments. Suppose for some reason she decided to take that unprofitable bet on Sunday. When she wakes up during the experiment, should she feel happy or sad? From her perspective during the experiment, the odds of gaining $400 vs losing $600 are two to one, so she should be happy. Given that she knows on Sunday how she will (with complete certainty!) feel about this bet on Monday, should she take it, even given her Sunday self’s assessment that it’s a bad bet?
Share:
My e-friend and coauthor, Konstantin Knop, designed the following problem for the 2011 All-Russia Olympiad:
Some cells of a 100 by 100 board have one chip placed on them. We call a cell pretty if it has an even number of neighboring cells with chips. Neighbors are the cells that share a side. Is it possible for exactly one cell to be pretty?
The problem is not easy. Only one person at the Olympiad received full credit for it.
Share: I recently had the following chat with a particular calculator:
It seems odd to me that putting a few more e’s down the bottom should result in it thinking there were the same number of extra 10s at the bottom. In fact, I’ve never seen a calculator answer in this form at all. I’m especially intrigued that the final power of ten seems to be the same in all three cases, so it can’t even just be estimating. Do you have any thoughts on what screwy counting could be behind these particular answers?
Share: I met Leon Vaserstein at a party. What do you think I do at parties? I bug people for their favorite problems, of course. The first riddle Leon gave me is a variation on a famous problem I had already written about. Here’s his version:
The hypotenuse of a right triangle is 10 inches, and one of the altitudes is 6 inches. What is the area?
When Leon told me that he had designed some problems for the Soviet Olympiads, naturally I wanted to hear his favorite:
Share:A closed polygonal chain has its vertices on the vertices of a square grid and all the segments are the same length. Prove that the number of segments is even.
I wonder what the largest number is that can be represented with one character. Probably 9. How about two characters? Is it 99? What about three or four?
I guess I should define a character. Let’s have two separate cases. In
the first one you can only use keyboard characters. In the second one
you can use any Unicode characters.
I’m awaiting your answers to this.
Share: The Moscow Math Olympiad has a different set of problems for every grade. Students need to write a proof for every problem. These are the 8th grade problems from this year’s Olympiad:
Problem 1. There were 6 seemingly identical balls lying at the vertices of the hexagon ABCDEF: at A — with a mass of 1 gram, at B — with a mass of 2 grams, …, at F — with a mass of 6 grams. A hacker switched two balls that were at opposite vertices of the hexagon. There is a balance scale that allows you to say in which pan the weight of the balls is greater. How can you decide which pair of balls was switched, using the scale just once?
Problem 2. Peter was born in the 19th century, while his brother Paul was born in the 20th. Once the brothers met at a party celebrating both birthdays. Peter said, “My age is equal to the sum of the digits of my birth year.” “Mine too,” replied Paul. By how many years is Paul younger than Peter?
Problem 3. Does there exist a hexagon which can be divided into four congruent triangles by a single line?
Problem 4. Every straight segment of a non-self-intersecting path contains an odd number of sides of cells of a 100 by 100 square grid. Any two consecutive segments are perpendicular to each other. Can the path pass through all the grid vertices inside and on the border of the square?
Problem 5. Denote the midpoints of the non-parallel sides AB and CD of the trapezoid ABCD by M and N respectively. The perpendicular from the point M to the diagonal AC and the perpendicular from the point N to the diagonal BD intersect at the point P. Prove that PA = PD.
Problem 6. Each cell in a square table contains a number. The sum of the two greatest numbers in each row is a, and the sum of the two greatest numbers in each column is b. Prove that a = b.
Share: A mathematician is someone who pauses when asked “How much is two and two?”
Indeed, the answer might be:
As you might have guessed from the title, this essay is about domino tilings.
Suppose a subset of a square grid has area N, and the number of possible domino tilings is T. Let’s imagine that each cell is contributing a factor of x tilings to the total independently of the others. Then we get that xN = T. This mental exercise suggests a definition: we call the nth root of T the degree of freedom per square for a given region.
Let’s consider a 1 by 2k rectangle. There is exactly one way to tile it with dominoes. So the degree of freedom per square of such a rectangle is 1. Now consider a 2 by k rectangle. It has the same area as before, and we know that there should be more than one tiling. Hence, we expect the degree of freedom to be larger than the one in the previous example. The number of tilings of a 2 by k rectangle is Fk-2, where Fk is kth Fibonacci number. So the degree of freedom for large k will be approximately the square root of the golden ratio, which is about 1.272.
You might expect that squares should give larger degrees of freedom than rectangles of the same area. The degree of freedom for a large square is about 1.3385. You can find more information in the beautiful paper Tilings by Federico Ardila and Richard P. Stanley.
Let’s move from rectangles to Aztec diamonds. They are almost like squares but the side of the diamond is aligned with diagonals of the dominoes rather than with their sides. See the sample diamonds in the picture above, which Richard Stanley kindly sent to me for this essay.
It is easier to calculate the degree of freedom for Aztec diamonds than for regular squares. The degree is the fourth root of 2, or 1.1892…. In the picture below created by James Propp’s tiling group you can see a random tiling of a large Aztec diamond.
Look at its colors: horizontal dominoes are yellow and blue; vertical ones are red and aquamarine. You might wonder what rule decides which of the horizontal dominoes are yellow and which are blue. I will not tell you the rule; I will just hint that it is simple.
Back to freedom. As you can see from the picture, freedom is highly non-uniform and depends on where you live. Freedom is concentrated inside a circle called the arctic circle, perhaps because the areas outside it are frozen for lack of freedom.
Now I would like to expand the notion of freedom to give each cell its own freedom. For a large Aztec diamond, I will approximate freedom with a function that is one outside the arctic circle and is uniform inside. The Aztec diamond AZ(n) consists of 2n(n+1) squares, shaped like a square with side-length n√2. So the area of the circle is πn2/2. Hence we can calculate the freedom inside the circle as the πth root of 2, which is about 1.247. This number is still much less than the degree of freedom of a cell in a large square.
Share:
Jorge Tierno sent me a link to the following puzzle:
There is a certain country where everybody wants to have a son. Therefore, each couple keeps having children until they have a boy, then they stop. What fraction of the children are female?
If we assume that a boy is born with probability 1/2 and children do not die, then every birth will produce a boy with the same probability as a girl, so girls will comprise half of all children.
Now, I wonder why everyone would want a boy? Y-chromosomes are much shorter than X-chromosomes. If a man wants to pass his genes to the next generation, a daughter should be preferable as she keeps more genes from the father. I am a mother of two boys, so my granddaughters will have my X-chromosome while my grandsons will have my ex-husband’s Y-chromosome, so to keep my genes in the pool I should be more interested in granddaughters.
But I digress. I started writing this essay because in the original puzzle link the answer was different from mine. Here is how the other argument goes:
Half of all families have zero girls, a quarter have 1/2 girls, 1/8 have 2/3 girls, and so on. If we sum this up the expected ratio of girls to boys is (1/2)0 + (1/4)(1/2) + (1/8)(2/3) + (1/16)(3/4) + … which adds to 1 − ln 2, which is about 30%.
What’s wrong with this solution?
Share: 