Welcome to The Riddler. Every week, I offer up problems related to the things we hold dear around here: math, logic and probability. Two puzzles are presented each week: the Riddler Express for those of you who want something bite-size and the Riddler Classic for those of you in the slow-puzzle movement. Submit a correct answer for either,1 and you may get a shoutout in next week’s column. Please wait until Monday to publicly share your answers! If you need a hint or have a favorite puzzle collecting dust in your attic, find me on Twitter.
Riddler Express
Every weekend, I drive into town for contactless curbside pickup at a local restaurant. Across the street from the restaurant are six parking spots, lined up in a row.
While I can parallel park, it’s definitely not my preference. No parallel parking is required when the rearmost of the six spots is available or when there are two consecutive open spots. If there is a random arrangement of cars currently occupying four of the six spots, what’s the probability that I will have to parallel park?
Riddler Classic
Parking cars is one thing — parking trucks is another thing entirely. Suppose I’m driving a very long truck (with length L) with two front wheels and two rear wheels. (The truck is so long compared to its width that I can consider the two front wheels as being a single wheel, and the two rear wheels as being a single wheel.)
Question 1: Suppose I can rotate the front wheels up to 30 degrees in either direction (right or left), but the rear wheels do not turn. What is the truck’s turning radius?
Question 2: Suppose I can also rotate the rear wheels — independently from the front wheels — 30 degrees in either direction. Now what is the truck’s turning radius?
Solution to last week’s Riddler Express
Congratulations to 👏 Derek Carnegie 👏 of Geneva, Switzerland, winner of last week’s Riddler Express.
Last week, you considered “hip” numbers that could be written as the difference between two perfect squares. For example, the number 40 was hip, since it equals 72−32, or 49−9. But hold the phone, 40 was doubly hip, because it also equals 112−92, or 121−81. Meanwhile, 42 was not particularly hip.
It was then left to you to determine the hipness of the number 1,400 — how many ways could 1,400 be written as the difference of two perfect squares?
You could have tested out lots of square numbers or written code to do it for you, like solver Eero Kuusi from Helsinki, Finland. But most readers recognized that any difference of squares, written as A2−B2, could be factored as (A+B)(A−B). So to find the different possible values of A and B, you had to identify the factor pairs of 1,400 — the greater factor was equal to A+B and the lesser factor was equal to A−B. In other words, A was the average of the two factors, while B was half their difference.
The number 1,400 had a prime factorization of 23×52×71. So for a number to be a divisor of 1,400, it had to have between zero and three powers of 2, between zero and two powers of 5 and zero or one power of 7. That meant 1,400 had a total of 24 factors (four times three times two), or 12 factor pairs. Here they are:
- 1 and 1,400
- 2 and 700
- 4 and 350
- 5 and 280
- 7 and 200
- 8 and 175
- 10 and 140
- 14 and 100
- 20 and 70
- 25 and 56
- 28 and 50
- 35 and 40
At this point, you might have thought the answer was 12. But not so fast! Remember, when it came to the difference of squares, the root of the greater square was the average of the two factors. For this to be a whole number, either both factors had to be even or both factors had to be odd. Among the 12 factor pairs of 1,400, six of them had one even number and one odd number (1×1,400, 5×800, 7×200, 8×175, 25×56 and 35×40). The remaining factors pairs had two even numbers. (Since 1,400 was an even number, it couldn’t have been the product of two odd factors.)
In all, there were six factor pairs with two even numbers, which meant six was the correct answer — 1,400 could be written as the difference of squares in exactly six ways:
- 3512 − 3492 = 123,201 − 121,801 = 1,400
- 1772 − 1732 = 31,329 − 29,929 = 1,400
- 752 − 652 = 5,625 − 4,225 = 1,400
- 572 − 432 = 3,249 − 1,849 = 1,400
- 452 − 252 = 2,025 − 625 = 1,400
- 392 − 112 = 1,521 − 121 = 1,400
For extra credit (which admittedly went well beyond “Riddler Express territory”), you had to find a general approach for determining how many ways a whole number N could be written as the difference of squares. Like the original puzzle, a good first step was to start with the number’s prime factorization, which we could write as N = 2a×3b×5c×7d×….
Again, you wanted to determine the number of unique factor pairs in which both factors were even or both factors were odd. But first, it was helpful to count the total number of odd factors, (b+1)(c+1)(d+1)…, which we’ll call F.
When a was zero, all F of N’s factors were odd. That meant N had F/2 factor pairs. (Okay, technically it was the ceiling of F/2, accounting for cases in which N was a square number.) And when a was one, every factor pair had exactly one even number and one odd number, so there were no ways to write N as a difference of squares.
When a was greater than one, at least one number in each factor pair was even, so you wanted to count the factor pairs in which both numbers were even. There were (a+1)×F/2 total factor pairs, F of which included an odd factor. That meant there were (a−1)×F/2 pairs of even factors, and so this was the number of ways you could write N as a difference of squares. (Again, it was technically the ceiling of (a−1)×F/2, accounting for when N was a square number.) In other words, when N was even and divisible by 4, the answer was the number of factor pairs for N/4.
This math checked out in the case when N was 1,400, or 23×52×71. For this value of N, N/4 was 350, or 21×52×71, which had 12 factors, or six factor pairs — the answer to the Express.
Anyway, no matter your approach, 1,400 was indeed a sextuply hip number.
Solution to last week’s Riddler Classic
Congratulations to 👏 Gary M. Gerken 👏 of Littleton, Colorado, winner of last week’s Riddler Classic.
Last week, I had 10 chocolates in a bag: Two were milk chocolate, while the other eight were dark chocolate. One at a time, I randomly pulled chocolates from the bag and ate them — that is, until I picked a chocolate of the other kind. When I got to the other type of chocolate, I put it back in the bag and started drawing again with the remaining chocolates. I kept going until I had eaten all 10 chocolates.
For example, if I first pulled out a dark chocolate, I ate it. (I always ate the first chocolate I pulled out.) If I pulled out a second dark chocolate, I ate that as well. If the third one was milk chocolate, I did not eat it (yet), and instead placed it back in the bag. Then I started again, eating the first chocolate I pulled out.
What were the chances that the last chocolate I ate was milk chocolate?
But before we get into any analytical solutions, let’s check in with our Monte Carlo-minded friends. Ian Greengross and Kyle Giddon both ran 1 million simulations of the problem, while Josh Silverman ran 10 million simulations. All three of them found the same result: In about half of the simulations, the last chocolate was milk chocolate. Could it be that the answer was simply… a half?
Yes! The answer was precisely a half. What follows is a proof of why this is true, based on the explanation of solver Guy D. Moore:
Suppose there are two chocolates in the bag: one dark and one milk. In this “base case,” they each have a 50 percent chance of being the last (i.e., the second) chocolate you’ll eat.
Next, we’ll take a mathematical leap of faith. Suppose we’ve proven — somehow — that there’s a 50 percent chance the last chocolate is either milk or dark chocolate whenever the total starting number of chocolates is less than some value N. What would happen if I now started with N chocolates?
Well, one of three things could happen. (Again, let’s suppose that d of these N chocolates are dark and m are milk. Note that this implies d+m = N, since every chocolate must be either dark or milk.)
- I go on a “dark” streak and pick out all d dark chocolates first, which means the last chocolate I eat will be milk. This is one of the N choose d total ways to order the chocolates, so the probability this occurs is one divided by N choose d, which is d!(N−d)!/N!, or d!m!/N!, since N−d equals m.
- I go on a “milk” streak and pick out all m milk chocolates first, which means the last chocolate I eat will be dark. Again, this is one of the N choose d ways to order the chocolates, so the probability this occurs is also d!m!/N!.
- I don’t go on either streak. I’ll eat some milk or dark chocolates until I pick out a chocolate of the other kind. At this point, I’m effectively starting over with a bag that has fewer than N chocolates. By my earlier leap of faith, I assumed the probability of now finishing with a milk chocolate was 50 percent.
So then what are the chances of finishing with a milk chocolate when there are N chocolates in the bag? It’s 50 percent! That’s because finishing with dark or milk is equally likely in the third case, and equally likely when you consider the first and second cases together.
Let’s take a final step back to get a bigger picture of what just happened. When there were two chocolates in the bag (one of each type), you had a 50 percent chance of finishing with a milk chocolate. We also showed that if there’s a 50 percent chance for fewer than N chocolates, there’s also a 50 percent chance for N chocolates. Since it was 50 percent when there were two chocolates, it must also be true when there were three. That means it must also be true when there were four. And five. And then six. And so on!
All of this amounts to a proof by induction: showing something is true for a “base case” (here, two), and then using an induction step to show it is true for all higher cases.
Indeed, this was a beautiful problem with an even more beautiful result. No matter how many chocolates of either type you started with — as long as you had at least one of each — the chances of finishing with either were precisely 50 percent.
In a neat little extension, solver Laurent Lessard proved that this was not the case when there were three types of chocolates. So it’s a good thing we left out the white chocolate. (That, and because it’s not even chocolate.)
Want more riddles?
Well, aren’t you lucky? There’s a whole book full of the best puzzles from this column and some never-before-seen head-scratchers. It’s called “The Riddler,” and it’s in stores now!
Want to submit a riddle?
Email Zach Wissner-Gross at riddlercolumn@gmail.com
"car" - Google News
October 09, 2020 at 07:00PM
https://ift.tt/2SCvIFg
Can You Parallel Park Your Car? - FiveThirtyEight
"car" - Google News
https://ift.tt/2SUDZWE
https://ift.tt/3aT1Mvb
Bagikan Berita Ini
0 Response to "Can You Parallel Park Your Car? - FiveThirtyEight"
Post a Comment