By Stephen Meskin
“Tiling 2”? If you look back at prior issues of Contingencies, you will not find a puzzle column named “Tiling 1.” However, just a year ago, you’ll find one named “Polyominoes,” in which the first problem asked you “to determine how many distinct ways one can tile a 4×4 square using tetrominoes.” So, we can call that column, “Tiling 1.” (Mathematicians often give new names to old things when they are considered in a new context. For example, what is the difference between a “divisor” and a “factor”?) But don’t worry, you don’t need to know anything about “Tiling 1” to solve the problems in this column.
Problem 1. How many ways can a 1 x N rectangle be tiled by dominoes and monominoes? A domino is a 1 x 2 rectangle, a monomino is a 1 x 1 square—we’ll use square for short. We can visualize a 1 x N rectangle as a board, 1 unit high and N units long running from left to right and call it an N-board for short. Assume the N-board has N-1 vertical lines one unit apart starting 1 unit from the left edge and ending 1 unit before the right edge. A tiling of an N-board is an arrangement of the tiles that exactly covers it so that the ends of the tiles abut each other only at some of the N-board’s vertical lines. Tilings, which need to be turned 180° to be the same, are considered different. For example, there are 5 tilings of a 4-board as shown here along with names/notation which may be useful. Let S and Ꝏ represent a square and domino, respectively.
14: SSSS 212: ꝎSS 121: SꝎS
122: SSꝎ 22: ꝎꝎ
We denote the number of tilings of an N-board fN and define f0 to be 1. I am looking for an equation of the form fN = a function of {fN-1, fN-2, …, f0 |for all N>K} for some K where {fK, fK-1, …, f0} are given. There are a few different answers, but to make it easy for me to review (and as a hint to later problems), partition the tilings of fN into two groups: one group consisting of tilings that end with a domino, the other of tilings that end in a square. If you count correctly, you can justify your formula in just a few words without using mathematical induction. (A purist might say that the induction is just hidden.)
For each of the following problems, write your answer as a function of the fN as in problem 1. And again, you can avoid induction if you do a good job of partitioning.
Problem 2. How many ways can an N-board be symmetrically tiled by dominoes and squares? (There are 3 tilings that are symmetric if N=4: 14, 121, and 22.)
Problem 3. How many ways can an N-board be tiled by dominoes and squares where two tilings, which are the same when turned 180°, are now considered the same? (4 for N=4.)
We now replace the N-board by an N-circle, which is just an N-board with the right end adjacent to the left or by assuming the N-board is made of rubber and bent into a circle. To fit on the N-circle, the tiles would have to be bent into small arcs subtending angles of (360/N)° for squares and (720/N)° for dominoes.
Problem 4. How many ways can an N-circle be tiled by dominoes and squares where tilings, which are only the same when rotated or flipped 180°, are considered different? (7 for N=4, see illustration)
A bracelet is like a circle with beads in place of dominoes and squares. It is easily rotated and flipped over. Assume that the space between the beads on a bracelet is negligible.
Problem 5 (extra credit). How many ways can a bracelet of length N be beaded by beads of lengths 1 and 2? This problem has four subproblems, one is problem 4, the other three are variations on problem 4, which differ in how rotations and flips affect the counts. You only need to solve one of the three variations to get extra credit. As this is being written, I don’t know the full answers to any of the three variations. (For N=4, the answers are 5, 3, and 3; for larger N, the last number can be smaller than the second.)
Solution to Previous Puzzle: Streak for Cash
- Given that people get 60% of their picks correct, what are the odds that someone in a company of 2,000 will get a streak of at least 46?
The probability of someone getting a streak of 46 is (6/10)46. The probability of someone not getting a streak is just 1-(6/10)46. And the probability of 2,000 people not getting a streak is similarly (1-(6/10)46)2,000. Which means the probability of at least one person hitting a streak of 46 is one minus that, or 0.000000125.
- What is the smallest streak so that 9 times out of 10, no one will hit the target streak?
Further working with our results in part 1, now we have the equation (1-(6/10)X)2,000=0.9. When we solve for x, we see that 19 gives us an 88.5% probability, which is too low, and if x=20 we have a probability of 92.95%. Hence the correct answer is 20.
- How do these answers change if the probability of a streak changes to 75%?
If we change 6/10 to 75/100 in both equations in parts one and two, we see that the probability of someone in the office getting a 46-game streak improves to 0.0036, and that management needs to set the length of a streak to 35 games in order for there to be less than a 10% chance of someone getting a streak that long.
- What probability of success will lead to a 25% chance that at least one person in 2,000 will get a streak of at least 46?
Modifying our equation in part 2, we now are trying to solve for Y in the equation (1-(Y)46)2,000=0.75. Solving for Y gives us an answer very close to 82.5%.
Solvers:
Robert Bartholomew, Doug Bass, Israel Bichachi, Mark Billingsley, Bob Byrne, Lois Cappellano, Brendan Cawley, Bob Conger, Andrew Dean, Joshua Durand, Deb Edwards, Bill Feldman, Yan Fridman, Steve Gallancy, Rui Guo, Adam Hudes, David Kausch, Clive Keatinge, Paul Navratil, Dan Onnen, David Promislow, Kathryn Rains-McNally, Anthony Salis, John Snyder, Al Spooner, Zig Swistunowicz, Daniel Wade, Gary Wang.
