By Josh Feldman
I still remember my introduction to the internet as if it happened yesterday. As a sophomore in college, I had an assignment to run a regression and write a paper about the results, and I had no clue what dataset to use, or even how to find a dataset. As desperation started to creep in, a fellow classmate told me to search the web for data. Of course, in early 1995 I had no clue what the heck the web was!
Fortunately, my classmate gave me a quick tour, which resulted in more frustration than anything else. This of course was before the days of AltaVista, let alone Google, and finding useful things online was not easy. By the end of this quick show-and-tell, I thought for sure I would never use this tool again. (Fair to say, this wouldn’t be the only time I would make an incorrect prognostication.)
Just a couple of months later at a summer job, someone else mentioned the mysterious World Wide Web again. However, unlike a few months ago, everyone was mesmerized as what the web could do. The trick was that instead of searching out boring datasets, we looked up sports scores. And back then one sports website was clearly superior to all the others: ESPN. Thanks to ESPN, I must admit that it wasn’t the most productive of summers for me, but could you blame me? This was the most revolutionary thing I’d seen in years!
That autumn as I headed back to college, I couldn’t wait to tell all my friends and classmates about this new technology. I so wanted to see their expressions at this new marvel. But something strange happened … magically EVERYONE learned about the web that summer! In my whole life I have never seen anything catch on so quickly.
Over my final two years in college, I think I looked at the ESPN website 20 times a day, which was impressive given that I didn’t own a computer. It didn’t matter if I wrote a paper or checked my email or did anything else on a computer, I would always have ESPN open in the background.
Alas, for various (nonpolitical) reasons, ESPN doesn’t have the clout it once had. Heck, I currently frequent a different website that starts with the letters “ES” more than ESPN! But there are still a few things that the Worldwide Leader does well, and one is the Streak For Cash contest.
In Streak For Cash, your goal is to correctly pick the correct side of a sporting contest without getting one wrong. You keep playing until you pick a losing side. Whoever has the longest streak of the most consecutive correct guesses at the end of the month wins a prize.
Just a few weeks ago, Streak For Cash made national news when someone had a 46-win streak go to dust when he picked the Wizards to beat the Hawks in an NBA game. As my friend Big T from our nation’s capital would say, never trust the Wizards with anything valuable, let alone a long Streak!
But this got me thinking—if the games were truly random 50/50 affairs, picking 46 games in a row would have near insurmountable odds. Even if everyone in North America played this game, the probability of someone getting a 46 game streak would be close to zero. And unlike a bookmaker, ESPN wants people to get big streaks, as this makes the game more fun. Besides, ESPN gives the same prizes whether the winning streak is 10 or 100, so they have little incentive to make every matchup an even-probability affair. This concept leads to this issue’s puzzle…
Assume all 2,000 people at my company have one chance to play Streak For Cash. Assume the probability of success for each win is 60%, and that there is no correlation between successive picks, or between picks of individual employees. What is the probability that one or more of the employees will get a streak of at least 46 games?
Management wants to give a prize to any employee who has a streak at or above a certain amount. Yet, management is also cheap, so they want to configure the game so that 9 times out of 10, no employee will hit the target score. Assuming the same conditions as in problem 1, what is the smallest streak that meets these criteria?
How do the answers to problems 1 and 2 change if the probability of success changes from 60% to 75%?
What probability of success will lead to a 25% chance that at least one of the 2,000 employees will get a streak of at least 46 games long?
Solutions to Previous Puzzle: How High Can You Go?
Let {a1, a2, … , an} be a non-empty set of relatively prime positive integers. All except a finite number of positive integers are non-negative (integer) linear combinations of {a1, a2, … , an}. The largest of that finite number of exceptions is denoted Similarly, all except a finite number of positive integers are non-negative (integer) linear combinations of {a1, a2, … , an} in at least two different ways. The largest of that finite number of exceptions is denoted g1(a1, a2, … , an).
Problem 1. Find g0(3,8) and prove it is.
Answer: g0(3,8) = 13
Proof: 14 = 2 × 3 + 1 × 8, 15=5 × 3 + 0 × 8, and 16 = 0 × 3 + 2 × 8. By adding enough 3’s to each identity we can express every integer >13 as non-negative (integer) linear combinations of 3 and 8. But 13 cannot be so expressed, so it is the largest.
Problem 2. Find g0(6,10,15) and prove it is.
Answer: g0(6,10,15) = 29
Proof: Like problem 1 – 30 = 5 × 6 + 0 × 10 + 0 × 15, 31 = 1 × 6 + 1 × 10 + 1 × 15 etc. up to 35. By adding 6’s to each identity we can express every integer >29 as non-negative (integer) linear combinations of 6, 10, and 15. But 29 cannot be so expressed. This is not as obvious as in #1. But the coefficient of 15 must be 1 because 29 is odd. Subtracting 15 from both sides reduces the problem to trying to express 14 as a non-negative (integer) linear combinations of 6 and 10, which can’t be done.
Problem 3. Find g1(3,8) and prove it is.
Answer: g1(3,8) = 37
Proof: This could be (and was) done like problems 1 and 2, but here’s another approach based on one sent in by David Promislow. Let N(3,8) = the set of all integers n = 3a + 8b, for non-negative integers a and b. If a > 7 then n = 3a + 8b = 3(a – 8) + 8(b + 3). And if b > 2 then n = 3a + 8b = 3(a + 8) + 8(b – 3). Thus the only possible members of N(3,8) to have unique coefficients are those with a ≤ 7 and b ≤ 2. The largest of these is 3 × 7 + 8 × 2 = 37. To show that these coefficients (7 and 2) are unique let 37 = 3a + 8b also. Then 3(7 – a) = 8(b – 2). But a ≤ 7 → LHS ≥ 0 and b ≤ 2 → RHS ≤ 0 so both sides must = 0 → a = 7 and b = 2.
Notes: g0(a,b) = ab – a – b.There doesn’t seem to be a general formula for g0(a,b,c).
For more information, search for The Coin Problem, The McNugget Number, or the Frobenius Number, or see: https://cs.uwaterloo.ca/~shallit/Talks/frob14.pdf.
Solvers
Bob Alps, Robert Bartholomew, Bob Byrne, Bob Conger, Andrew Dean, Bill Feldman, Yan Fridman, Rui Guo, Clive Keatinge, David Lovit, Michael Manos, John Pauly, David Promislow, Tomasz Serbinowski, Lenny Shteyman, John Snyder, Al Spooner, Elliott Steiner, Doug Szper, and Daniel Wade
Solutions may be emailed to cont.puzzles@gmail.com.
In order to make the solver list, your solutions must be received by April 1, 2018.