What's new
Fantasy Football - Footballguys Forums

This is a sample guest message. Register a free account today to become a member! Once signed in, you'll be able to participate on this site by adding your own topics and posts, as well as connect with other members through your own private inbox!

Math Puzzles (from FiveThirtyEight - new puzzle every Friday) (1 Viewer)

New puzzle and solution to last week's.

You are the CEO of a space transport company in the year 2080, and your chief scientist comes in to tell you that one of your space probes has detected an alien artifact at the Jupiter Solar Lagrangian (L2) point.

You want to be the first to get to it! But you know that the story will leak soon and you only have a short time to make critical decisions. With standard technology available to anyone with a few billion dollars, a manned rocket can be quickly assembled and arrive at the artifact in 1,600 days. But with some nonstandard items you can reduce that time and beat the competition. Your accountants tell you that they can get you an immediate line of credit of $1 billion.

You can buy:

  • Big Russian engines. There are only three in the world and the Russians want $400 million for each of them. Buying one will reduce the trip time by 200 days. Buying two will allow you to split your payload and will save another 100 days.
  • NASA ion engines. There are only eight of these $140 million large-scale engines in the world. Each will consume 5,000 kilograms of xenon during the trip. There are 30,000 kg of xenon available worldwide at a price of $2,000/kg, so 5,000 kg costs $10 million. Bottom line: For each $150 million fully fueled xenon engine you buy, you can take 50 days off of the trip.
  • Light payloads. For $50 million each, you can send one of four return flight fuel tanks out ahead of the mission, using existing technology. Each time you do this, you lighten the main mission and reduce the arrival time by 25 days.
What’s your best strategy to get there first?

 
Buy two really big engines and all the xenon in the world for 860 million and send two fuel tanks out early.   That will save you 350 days and the most a competitor could save is 300 with one really big engine and sending four fuel tanks out early.  You could get there even faster by buying 25000 kg xenon and sending 3 fuel tanks early - 375 days - but you'd allow a competitor to get there in 350.  

 
Buy two really big engines and all the xenon in the world for 860 million and send two fuel tanks out early.   That will save you 350 days and the most a competitor could save is 300 with one really big engine and sending four fuel tanks out early.  You could get there even faster by buying 25000 kg xenon and sending 3 fuel tanks early - 375 days - but you'd allow a competitor to get there in 350.  
Interesting - I was just trying to max out my own trip.  I had a plan to get there 425 days early, but it left enough inventory for someone else the same thing.

 
Buy two really big engines and all the xenon in the world for 860 million and send two fuel tanks out early.   That will save you 350 days and the most a competitor could save is 300 with one really big engine and sending four fuel tanks out early.  You could get there even faster by buying 25000 kg xenon and sending 3 fuel tanks early - 375 days - but you'd allow a competitor to get there in 350.  
You have this backward. The 375 and 350 are days saved off of the 1600-day trip, not days to get there.  So you'd still get there 25 days ahead of the competitor.

Your first option: Spend $860M, get there in 1250 days, nobody else could get there in less than 1600

Second option: Spend $1B, get there in 1225 days, nobody else could get there in less than 1250

Is getting there 25 days sooner worth the $140M?

 
No,  I get that,  I just meant one way you'd beat your competitor there by 50 days and the other by 25.  If the only priority is getting there first then buying all the xenon would be 25 days better for you even though you yourself would get there later too.

 
No,  I get that,  I just meant one way you'd beat your competitor there by 50 days and the other by 25.  If the only priority is getting there first then buying all the xenon would be 25 days better for you even though you yourself would get there later too.
Ah, got it.  So the question is, once you can be assured of getting there first, which is most important: (a) minimize cost; (b) minimize time; (c) maximize time advantage over competition? 

 
There's no indication that your competitors are limited to a $1B budget

I agree that the fastest that you can get there knocks 425 days off the trip

I think my strategy is

<####, how do you do spoilers on the new board?>

 
There's no indication that your competitors are limited to a $1B budget

I agree that the fastest that you can get there knocks 425 days off the trip

I think my strategy is

<####, how do you do spoilers on the new board?>
True, but BFred's approach means that they can't get there faster, no matter how much money they have. There are only 3 big Russian engines and only 30,000 kg of xenon in the world, so unless they have another way to reduce the 1600-day trip outside the constraints of the problem, they're stuck with our leftovers.

 
The fastest way that I've found to get there cuts 425 days off my travel time (1 big Russian engine saves 200 days, 3 NASA ion engines w. 15,000 kg of xenon save 150 days, 3 return flight fuel tanks save 75 days). However, it allows a wealthy competitor who buys up everything else to cut 475 days off their travel time (2 big Russian engines save 300 days, 3 NASA ion engines w. 15,000 kg of xenon saves 150 days, 1 return flight fuel tank saves 25 days).

Another approach can cut 400 days off my travel time, while only allowing the wealthy competitor to cut 300 days off their travel time. I buy

1 big Russian engine (saves 200 days for $400M) + 2 NASA ion engines w. 10,000 of xenon (saves 100 days for $300M) + the remaining 20,000 kg of xenon (saves 0 days for $40M) + 4 return flight fuel tanks (saves 100 days for $200M), for a total price of $940M. My wealthy competitor can only buy 2 big Russian engines (saves 300 days), and useless NASA ion engines without xenon to fuel them.

This seems like the best approach both for maximizing my lead (100 days), and for getting there as quickly as possible while having a lead (400 days saved).

This is assuming that the list includes all equipment that my competitor could get their hands on (e.g., if there are more return flight fuel tanks out there, and the cap is at 4 only because it's not feasible to use more than 4 on one mission, then the optimal strategy might be different).

 
The fastest way that I've found to get there cuts 425 days off my travel time (1 big Russian engine saves 200 days, 3 NASA ion engines w. 15,000 kg of xenon save 150 days, 3 return flight fuel tanks save 75 days). However, it allows a wealthy competitor who buys up everything else to cut 475 days off their travel time (2 big Russian engines save 300 days, 3 NASA ion engines w. 15,000 kg of xenon saves 150 days, 1 return flight fuel tank saves 25 days).

Another approach can cut 400 days off my travel time, while only allowing the wealthy competitor to cut 300 days off their travel time. I buy

1 big Russian engine (saves 200 days for $400M) + 2 NASA ion engines w. 10,000 of xenon (saves 100 days for $300M) + the remaining 20,000 kg of xenon (saves 0 days for $40M) + 4 return flight fuel tanks (saves 100 days for $200M), for a total price of $940M. My wealthy competitor can only buy 2 big Russian engines (saves 300 days), and useless NASA ion engines without xenon to fuel them.


This seems like the best approach both for maximizing my lead (100 days), and for getting there as quickly as possible while having a lead (400 days saved).

This is assuming that the list includes all equipment that my competitor could get their hands on (e.g., if there are more return flight fuel tanks out there, and the cap is at 4 only because it's not feasible to use more than 4 on one mission, then the optimal strategy might be different).
Was swamped all weekend and finally just got around to looking at this, but I agree with this as one of the two best solutions.  The only other reasonable interpretation, I think, would be optimizing for cost instead of speed/margin of victory, in which case it would be this solution minus one NASA ion engine.  Then you still win the race (albeit by not as many days) but only spend $800M.  

There are a few other combinations of resources that would let us win the race as well, but I don't think any are cheaper and/or faster than these two.

 
The fastest way that I've found to get there cuts 425 days off my travel time (1 big Russian engine saves 200 days, 3 NASA ion engines w. 15,000 kg of xenon save 150 days, 3 return flight fuel tanks save 75 days). However, it allows a wealthy competitor who buys up everything else to cut 475 days off their travel time (2 big Russian engines save 300 days, 3 NASA ion engines w. 15,000 kg of xenon saves 150 days, 1 return flight fuel tank saves 25 days).

Another approach can cut 400 days off my travel time, while only allowing the wealthy competitor to cut 300 days off their travel time. I buy

1 big Russian engine (saves 200 days for $400M) + 2 NASA ion engines w. 10,000 of xenon (saves 100 days for $300M) + the remaining 20,000 kg of xenon (saves 0 days for $40M) + 4 return flight fuel tanks (saves 100 days for $200M), for a total price of $940M. My wealthy competitor can only buy 2 big Russian engines (saves 300 days), and useless NASA ion engines without xenon to fuel them.


This seems like the best approach both for maximizing my lead (100 days), and for getting there as quickly as possible while having a lead (400 days saved).

This is assuming that the list includes all equipment that my competitor could get their hands on (e.g., if there are more return flight fuel tanks out there, and the cap is at 4 only because it's not feasible to use more than 4 on one mission, then the optimal strategy might be different).
This is my interpretation of the problem.  There is no limit on the number of available fuel tanks as there is on the other components.

 
This is assuming that the list includes all equipment that my competitor could get their hands on (e.g., if there are more return flight fuel tanks out there, and the cap is at 4 only because it's not feasible to use more than 4 on one mission, then the optimal strategy might be different).
This is my interpretation of the problem.  There is no limit on the number of available fuel tanks as there is on the other components.
In that case, bostonfred's original post has the best solution:

Buy two really big engines and all the xenon in the world for 860 million and send two fuel tanks out early.   That will save you 350 days and the most a competitor could save is 300 with one really big engine and sending four fuel tanks out early.

 
New puzzle is up

The misanthropes are coming. Suppose there is a row of some number, N, of houses in a new, initially empty development. Misanthropes are moving into the development one at a time and selecting a house at random from those that have nobody in them and nobody living next door. They keep on coming until no acceptable houses remain. At most, one out of two houses will be occupied; at least one out of three houses will be. But what’s theexpected fraction of occupied houses as the development gets larger, that is, as N goes to infinity?

 
Didn't look at last week's but I think you could set it up in Solver as a pretty straightforward optimization problem that minimizes the travel time (or minimizes the cost), and includes a constraint that says our elapsed time less our competitor's elapsed time < 0.

 
Last edited by a moderator:
Not sure what mathematical approach would be, but empirically, it seems to settle in around 43.25%.  I tested up to 4000 houses.

An interesting variation would be to make it a two-dimensional neighborhood, with the misanthropes either OK or not with neighbors behind and/or across the street.

 
Thanks for bumping, didn't get a chance to post it this morning. :thumbup:

I figured out a recurrence relation for it, but I'm too rusty to figure out how to convert that into a closed-form solution.  Basically, if f(n) is the expected number of people who move into a street of length n, then:

f(n) = [ 2f(n-2) + (n-1)f(n-1) + 1 ] / n

where f(0) = 0 and f(1) = 1.

That's the number of people living on the street, so for the proportion of people you'd need to divide by n again.  

Just plugging that into Excel, for N = 100,000 you get 0.432335329.  So pretty close to what you guys have already posted.  Still just trying to work out how to solve for it analytically from the recurrence above.  

 
Basically, if f(n) is the expected number of people who move into a street of length n, then:

f(n) = [ 2f(n-2) + (n-1)f(n-1) + 1 ] / n

where f(0) = 0 and f(1) = 1.
Never did figure out a closed-form solution to this, but I saw someone else's solution and this is the right recurrence.  I wouldn't have worked out the rest, it's the kind of math I did years ago and have long forgotten.  

Just wanted to add the reasoning for how I ended up with the above.  When the first person randomly chooses a house to live in, they split the street into one or two parts, each of which is just a smaller version of the same problem.  For example, let N = 7.  If the first person moves into...

  • ...the first house, they leave the case N=5.
  • ...the second house, they leave the case N=4.
  • ...the third house, they leave the cases N=1 and N=3.
  • ...the fourth house, they leave the cases N=2 and N=2.
  • ...the fifth house, they leave the cases N=3 and N=1.
  • ...the sixth house, they leave the case N=4.
  • ...the seventh house, they leave the case N=5.
Note that each of those rows happens with probability 1/7 (or more generally, 1/N).  And in total, they account for every case from N = 1 up to N-2, twice each.  So the total number of expected residents on a street of size N is 1 (for the first resident) plus 2/N times (the sum of the expected residents for all cases from N=1 to N-2).  From there it's pretty straightforward to get to the recurrence relation I posted above.

As I mentioned, there is a closed-form solution to this but I wouldn't have gotten it, at least not without digging out some old math textbooks.  But it works out that the solution for the limit as N goes to infinity is (1 - e-2)/2, which is 0.432332...

 
New puzzle and solution to last week's.

It’s Friday and that means it’s party time! A group of N people are in attendance at your shindig, some of whom are friends with each other. (Let’s assume friendship is symmetric — if person A is friends with person B, then B is friends with A.) Suppose that everyone has at least one friend at the party, and that a person is “proud” if her number of friends is strictly larger than the average number of friends that her own friends have. (A competitive lot, your guests.)

Importantly, more than one person can be proud. How large can the share of proud people at the party be?

 
I think I got this one, and it's not too mathy.  Pretty easy to just work it out via intuition (assuming my answer is right).  I'll wait a bit before posting my reasoning to see if anyone else chimes in with thoughts first.

 
Yep, that's what I came up with as well.  My reasoning:

Why it's possible for N-2 people to be proud: Assume the first N-2 people are friends with each other.  Also assume that some of them are friends with person N-1, and the rest of them are friends with person N.  Then each of the N-2 people is friends with N-2 others, but the average of their friends' friends is less than N-2.

Why it's not possible for N-1 (or N) people to be proud:  In order to be proud, you need to have at least one friend who has fewer friends than you do.  Also, because everyone has at least 1 and at most N-1 friends, that means that at least two people have the same number of friends.  Because of this, it's not possible to create an arrangement where all but one of the guests is proud.  For example, let persons A and B each have two friends, and person C have one friend.  In order for A and B to both be proud, they both need to be friends with C.  But C only has one friend, so that's a contradiction.  
 
My reasoning:

Here's how you can get N-2 proud people: If everyone is friends with everyone else, except for one pair of people who are not friends with each other, then everyone besides that pair is proud. Because (if you are one of those N-2 who is friends with everyone), most of your friends have the same number of friends as you, and 2 of your friends each have 1 fewer friend than you do, so you are above average relative to your friends.

Here is why you can't get N proud people: the person with the fewest friends is not proud (even if they are tied with others for fewest friends), because every single one of their friends has at least as many friends as they do. (e.g., In the case where everyone is friends with everyone, no one is proud.)

Here is why I don't think you can get N-1 proud people: I tried it with N=7 and couldn't get it to work. The basic problem is that you can't make things work by just having one person with fewer friends than everyone else, because you still need to do something to make the person(s) who isn't friends with them also be proud. e.g., With N=7, if 6 people each have 5 friends and 1 person has 4 friends, then the 4 friends guy is not proud and the 2 people who aren't friends with the 4 friends guy are also both non-proud. (This is not yet a proof.)
 
This week was pretty simple.  The explanations by ZWK and IE above were great - as always!  I just thought of it as a graph theoryish problem with a complete graph minus a single edge.  That way, there are always two people (the vertices of the subtracted edge) that are friends with everyone else but not each other.  That guarantees n-2 proud people and also shows why n-1 is impossible.

 
I don't know if this is worth a new thread but Presh Talwalkar puts some interesting puzzles on his mindyourdecisions.com 

This one has me stuck...2 glasses is easy enough but my attempts to generalize have been wrong. He has a video solution but I want to figure it out on my own.

A game starts with 6 empty glasses in a row numbered 1 to 6. You roll a standard die. If the number for the glass is empty, then the glass is filled up. If the number for the glass is full, then you drink that glass so it becomes empty.

There is a special rule when 5 glasses are full. If you roll the number for the lone empty glass, then the final glass gets filled and you have to drink all 6 glasses. At this point the game ends.

From the start of the game, what is the average number of rolls until the game ends?

 
I don't know if this is worth a new thread but Presh Talwalkar puts some interesting puzzles on his mindyourdecisions.com 

This one has me stuck...2 glasses is easy enough but my attempts to generalize have been wrong. He has a video solution but I want to figure it out on my own.

A game starts with 6 empty glasses in a row numbered 1 to 6. You roll a standard die. If the number for the glass is empty, then the glass is filled up. If the number for the glass is full, then you drink that glass so it becomes empty.

There is a special rule when 5 glasses are full. If you roll the number for the lone empty glass, then the final glass gets filled and you have to drink all 6 glasses. At this point the game ends.

From the start of the game, what is the average number of rolls until the game ends?
I would set it up as:

a Markov chain with 7 states. You start at the state with 0 glasses full. When you're in the state with 0 glasses full, there is a 100% chance that you go to the state with 1 glass full. When you're in the state with 1 glass full, there is a 1/6 chance that you go the state with 0 glasses full and a 5/6 chance that you go to the state with 2 glasses full. When you're in the state with 2 glasses full, there is a 2/6 chance that you go to the state with 1 glass full and a 4/6 chance that you go to the state with 3 glasses full. And so on. The state with 6 glasses full is an absorbing state.

There is standard math for Markov chains which gets you the answer (the expected number of state changes) and should be googleable, but I don't know it offhand.
 
Last edited by a moderator:
I would set it up as:

a Markov chain with 7 states. You start at the state with 0 glasses full. When you're in the state with 0 glasses full, there is a 100% chance that you go to the state with 1 glass full. When you're in the state with 1 glass full, there is a 1/6 chance that you go the state with 0 glasses full and a 5/6 chance that you go to the state with 2 glasses full. When you're in the state with 2 glasses full, there is a 2/6 chance that you go to the state with 1 glass full and a 4/6 chance that you go to the state with 3 glasses full. And so on. The state with 6 glasses full is an absorbing state.

There is standard math for Markov chains which gets you the answer (the expected number of state changes) and should be googleable, but I don't know it offhand.
I think this is how I'd go about it as well, but I don't remember the math, exactly.  Should be pretty easily googleable though.  Out of curiosity I just simulated it a bunch of times in Python and got something very close to:

83.3333... = 500/6


as the average number of rolls needed to fill all 6 glasses. 

I wrote up what I believe is an original puzzle here a few years ago, but I can't find it now.  Very similar to this one, though.  The gist of it is you have a box with N balls, each painted a different color.  On each turn, you randomly select two balls from the box, one in each hand.  Whatever color the left ball is, you paint the right ball, and then put them both back in.  What's the expected number of turns until all N balls are painted the same color?

I know the solution for small values of N, and suspect it holds for all N, but I tried to generalize using the same approach you described and was never able to get it.  

 
Last edited by a moderator:
New puzzle and solution to last week's.

In a building’s lobby, some number (N) of people get on an elevator that goes to some number (M) of floors. There may be more people than floors, or more floors than people. Each person is equally likely to choose any floor, independently of one another. When a floor button is pushed, it will light up.

What is the expected number of lit buttons when the elevator begins its ascent?

 
E = A / B, where:

A = the total number of lit buttons for all permutations of people and floors.  Still working out the math expression for this, but for example, with 2 people and 2 floors, A = 6; with 3 people and 3 floors, A = 60.

B = M^N 
 
E = A / B, where:

A = the total number of lit buttons for all permutations of people and floors.  Still working out the math expression for this, but for example, with 2 people and 2 floors, A = 6; with 3 people and 3 floors, A = 60.

B = M^N 
For your numerator, I'm thinking that you need to change the word 'permutation' for 'combination' since the order doesn't count... 2 people and 2 floors, with the assumption that everyone hits exactly one floor, the possibilities are: 11, 12, 21, 22... but 12 and 21 yields the same result (i.e. both floors lit)  

 
JayMan said:
For your numerator, I'm thinking that you need to change the word 'permutation' for 'combination' since the order doesn't count... 2 people and 2 floors, with the assumption that everyone hits exactly one floor, the possibilities are: 11, 12, 21, 22... but 12 and 21 yields the same result (i.e. both floors lit)  
But if you collapse those two, then you also need to treat 11 and 22 as identical in order to get the correct result.  

The EV is (total buttons lit for all the different ways that people could possibly hit the buttons) / (total number of ways people could push the buttons). For M=N=2, there are 2 ways to have 1 floor lit, and 2 ways to have 2 floors lit, for an EV of 1.5 floors lit.  

 
I was getting different numbers, but then it just registered that nobody is going to get on the elevator on the first floor and press "1".

:bag:

 
Are we assuming the height of the cone is equal to the radius of it's "top"?  Does it matter?
No idea.  Also seems like it might matter whether p is measured up the side of the glass, or vertically?  I'm overseas for work so I won't have much time, if any, to work on this week's puzzle but it seems like there's some ambiguity.  

 
No idea.  Also seems like it might matter whether p is measured up the side of the glass, or vertically?  I'm overseas for work so I won't have much time, if any, to work on this week's puzzle but it seems like there's some ambiguity.  
There's also some calculus if I'm visualizing it correctly.  With that, I'm likely out.  I'm not sure how to find out the volume of an "offset cone" (where it's not a circular base, bur rather some oval type shape)

 
I assumed that the largest cross section of the first cone had the same area as the largest cross section of the second "cone."  Then, the areas would be

A1= (.5p^2)sin(base angle) and A2 = .5(answer)sin(base angle)

So, p^2...?  Makes sense but I think I over simplified it.
 
New puzzle and solution to last week's.

A video game requires you to slay monsters to collect gems. Every time you slay a monster, it drops one of three types of gems: a common gem, an uncommon gem or a rare gem. The probabilities of these gems being dropped are in the ratio of 3:2:1 — three common gems for every two uncommon gems for every one rare gem, on average. If you slay monsters until you have at least one of each of the three types of gems, how many of the most common gems will you end up with, on average?

 
Wrote a simulator, ran it up to a million trials

I'm getting around 3.65 common gems on average.  Curious to see what the math is behind it.
 
We can set this up as

a Markov chain with 8 states, where a state is defined by which types of gems you have any of. For example, there is a state where you have at least one common gem, no uncommon gems, and at least one rare gem. And there is a 1/3 chance of transitioning from this state into the absorbing state where you have at least one of each of the three types of gems.

We can calculate the expected number of steps using matrix math. While googling to figure out the details of that matrix math, I came across this writeup of essentially the same problem which has the formula for the expected number of steps written out. Taking that shortcut, I plugged in the numbers and found that the expected number of steps is 7.3.

That means that, on average, you can expect to collect 7.3 gems if you play until you have at least one of each type.

Since half of the gems are common, you can expect to end up with 7.3/2 = 3.65 common gems on average.
 
New puzzle and solution to last week's.

Assume you have a sport (let’s call it “baseball”) in which each team plays 162 games in a season. Assume you have a division of five teams (call it the “AL East”) where each team is of exact equal ability. Specifically, each team has a 50 percent chance of winning each game. What is the expected value of the number of wins for the team that finishes in first place?

 
I've been totally absent from this thread the past few weeks due to travel and work stuff, and today is shaping up to be the same for me, but this looks like a fun puzzle and I'm going to try to work on it and participate in the discussion over the weekend. :thumbup:

 
Seems like incomplete data.

Do we assume they play all 162 games against division opponents?  Or 76 games against division opponents and 86 against non-division opponents?  Do they have a 50% chance of winning games against non-division opponents?  Home field advantage?

 
Seems like incomplete data.

Do we assume they play all 162 games against division opponents?  Or 76 games against division opponents and 86 against non-division opponents?  Do they have a 50% chance of winning games against non-division opponents?  Home field advantage?
I think the answer is 50% in every game they play.

But I agree that the phrasing is awkward.  The expected value for all 5 teams is 81 games.  So that's arguably the answer.

If the question is what's the most likely answer it would be significantly higher.  

But I think the big clue for what they're going for is that

the winner can never have fewer than 81 wins.  That changes the expected value.  

If you and I flip a coin where the winner gets 100 bucks and the loser gets nothing,  the ev for the coin flip is 50 bucks,  but the ev for the winner is 100.  

If we flip two coins for 50 bucks each,  the ev for the coin flip is still 50 but the ev for the winner is 75 bucks.  That's because half the time it comes up heads heads or tails tails and the winner gets 100 bucks, and half the time we split and each get 50.  

If we flip 3 coins for 33.33 each, the expected value is 1/4 (100) + 3/4 (66.66), or 75.  

The more coins we flip, though,  the smaller the winner's ev becomes - but it never becomes less than half. Because as the odds of a clean sweep go down,  the expected value contains a much greater percentage of ties or one more win than yous.  By 162 coin flips, the ev for any of the five teams ought to approach 81.

That's the first part,  anyways. The problem is they're not exactly flipping against each other and there's not just 2 opponents.  But the ev for the winner of the division should be greater than 81, even though it seems like it shouldn't be 
 
According to twitter the schedule thing is ambiguous, so you can make whatever reasonable assumption you want about scheduling and solve it that way.  Next week's column will apparently have multiple solutions to account for different schedule formats. :shrug:

 

Users who are viewing this thread

Back
Top