Welcome to The Riddler. Every week, I offer up problems related to the things we hold dear around here: math, logic and probability. There are two types: Riddler Express for those of you who want something bite-size and 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. If you need a hint or have a favorite puzzle collecting dust in your attic, find me on Twitter.
Quick announcement: Have you enjoyed the puzzles in this column? If so, I’m pleased to tell you that we’ve collected many of the best, along with some that have never been seen before, in a real live book! It’s called “The Riddler,” and it will be released in October — just in time for loads of great holidays. It’s a physical testament to the mathematical collaboration that you, Riddler Nation, have helped build here, which in my estimation is the best of its kind. So I hope you’ll check out the book, devour the puzzles anew, and keep growing our nation by sharing the book with loved ones.
And now, to this week’s puzzles!
Riddler Express
From Steven Pratt, welcome to Riddler City:
You are a delivery person for the finest peanut butter and jelly sandwich restaurant in Riddler City. City streets are laid out in a grid, and your restaurant is on the corner of 20th Street and Avenue F. The city has 61 east-west streets, numbered 1st to 61st, and 21 north-south avenues, named A to U.
While traveling on a given street or avenue, you can drive at 20 mph, and the blocks are all 0.1 miles long. The exception is Avenue U, also known as the Ultra-Speed Trafficway, upon which you can drive at 200 mph. (You don’t need to worry about slowing down for traffic or turns.)
What are the parts of the map for which it’s helpful to use the Ultra for your deliveries, assuming you always start at 20th and F?
Riddler Classic
From Samuel Oppenheim, welcome to the desert:
You know the following things about the delicate ecology of scorpions and meerkats:
- If there were no meerkats, the population of the scorpions would double every month.
- If there were no scorpions, the population of the meerkats would halve every month.
- If you had exactly 20 scorpions and five meerkats, both populations would not change at all.
What is the number of meerkats when the desert has as many scorpions as possible?
What is the number of meerkats and the number of scorpions when the meerkat population is increasing by four meerkats per month and the scorpion population is decreasing by two scorpions per month?
These questions rely on the Lotka-Volterra model of predators and prey. That model makes certain assumptions, including that the prey (the scorpions here) always find ample food, the predators (the meerkats) have limitless appetite, and the rate of change of a population is proportional to its size.
Extra credit: If you start with 100 scorpions and 10 meerkats, what is the maximum number of meerkats you can have and how long would it take for both populations to return to their starting states?
Solution to last week’s Riddler Express
Congratulations to 👏 David Kravitz 👏 of Santa Monica, California, winner of last week’s Riddler Express!
Last week brought some international bracket math: Assuming we don’t know anything about the strengths of the teams in the tournament, what are the chances that any pair of teams in a 32-team World Cup plays each other twice? (Their first encounter would be in the round-robin, three-game group stage, with their second encounter in the final or the third-place game.)
The chances are 7/32, or about 22 percent.
Solver Jakub Onufry Wojtaszczyk provided the following very nice explanation:
If the teams are all of equal strength, then the results of the group matches don’t matter. Two teams will exit each of the eight groups, and they will have already played each other. Now, it doesn’t matter which team gets into the finals from the left half of the bracket, since it’s all symmetric — assume they’re from Group A. Given the way the bracket is organized, if the Group A representative makes it, teams on the left side from Groups B, C and D will have been eliminated from the tournament. One of the other four teams on the left side of the bracket will get into the third-place game for losing to A’s team in the semifinals — let’s make it E (again, symmetry).
The probability that the other team from A, on the right side of the bracket, makes the finals is ⅛, because all teams are indistinguishable. The probability of the other team from E getting into the third-place game is also ⅛ (again, symmetry). The probability of both these things happening together is (¼)(¼)(½) — A has to win the “ABCD” bracket, E has to win the “EFGH” bracket, and E has to lose to A. Therefore, the total probability (by the inclusion-exclusion principle) is ⅛ + ⅛ – (¼)(¼)(½) = 7/32, or a bit less than 22 percent.
For extra credit, I asked what these odds would have been using FiveThirtyEight’s pre-tournament projections. According to the simulations of solver Andrew Brady and others, the odds were actually slightly higher in real life, at about 28 percent. There still remain two pairs of teams that could play each other twice this year: Russia-Uruguay from Group A and England-Belgium from Group G.
Solution to last week’s Riddler Classic
Congratulations to 👏 Richard Barnes 👏 of Arlington, Virginia, winner of last week’s Riddler Classic!
Last week you stood outside a locked gate, badly wanting to enter. The gate required a specific passcode entered into a 10-digit keypad (buttons numbered 0-9) to open it. You didn’t know the code, but you knew it was four digits long. Also, you knew that this particular keypad never resets: If you enter the correct four digits in order at any time, the gate will open. For example, you could press the numbers “12345” and you would have attempted the codes “1234” and “2345.” What’s the smallest number of buttons you’d need to press to make sure you open the gate?
You’d need at most 10,003 presses. This is much better than the 40,000 you’d need if the keypad did reset with every code attempted!
There are 10,000 (\(10^4\)) possible passcodes. So 10,003 presses is the smallest number of presses you could conceivably require, because your first code attempt comes on your fourth press — the first three presses will not attempt any code. The only question is if there’s a way to try every code in as few presses as possible.
And indeed there is, and not just one of them. Solver Adam Wagner explained it thus:
Any four-digit number, ABCD, has nine “siblings” — that is, numbers whose first three digits are the same as the original number’s last three digits. And since any three-digit string ABC has 10 possible digits that can precede it and 10 possible digits that can come after it, there will always be at least one digit that can come after any four-digit string to create a sibling that has never been attempted before — every number you add can result in one new permutation. So the answer is just \(10^4\), plus the first three digits (which don’t create unique combinations since there aren’t enough digits yet), which is 10,003.
Gary Gerken found his 10,003-digit sequence using a greedy algorithm, while Bill Tressler chose a backtracking algorithm. Michael Hogan pointed out that this puzzle is related to mathematical objects called de Bruijn sequences.
For extra credit, I asked how the answer would change if you didn’t remember the length of the passcode. The answer above generalizes easily. If the passcode were N digits long, for example, you’d need at most \(10^N + (N-1)\) presses.
In case you do ever find yourself standing outside of a locked, four-digit passcode gate like the one described above, desperately needing to enter, here, as a public service, is an efficient 10,003-digit sequence submitted by our winner, Richard:
6503243022979499445496081341386044103411676421216956335398337764846850521051391331590022607275717945579421401474931926576625103322637555024831807554381576091682560125964987794061884648081880876501127748169078159946887166595278658032888373527452010145230838711383461367625582661911864337904874285530078219839201431557334881686011038688432670016258820167144797985474543281372884426050533429949830164008722779638586135384065563869489578612626131521865078783586837216853725643597994079747401638377453745878063195018431316146950432052975584820461635424284131793809783833965400345939751295196586551185512865928520567589119952472141513182642621029884048801825435358924013647964292915742568342325926341018327902053510256502242677322955148412172749953768567699959832848985644204824185180964496778079960547018065056073197329425275529983562684152384529826065323024765726995805745091435608701778596369271380123032732040851903553486329938649136313996133690459846305121270113244647510124224508533160965797888947376978944335287825765207171887728039427308243142331294386765301937220334011941842581739415332024417302870646029317029492243995669147117968494790793623010881556150232116438847009453566372444146190090404716745996533310102097461037616151896986893220629812797673013405640343962834163075338253494100673103658797245127314377709909713620025311170385756559423736427253559325240399744696756903967392860325571409682341945850705720611910199044378270826857213257918102300315309191246347980771691390210397933727671154996955653973863827988882514590724105684606223593675966338873978799277343114651168968652921284552520061603749050643224877740029194372678802204910926656859477417116024275371397409586336611114182772615588909104554159235673426458692035119545146009318715873657856045898918684732751611332896339343574928175509245654190252869160077367722383517344050172662816508274181840928449333810170082829632542112096340905734141454161775243740276228812696248887931588488758401278834972702229860941274072635084857684344453373240530457696352175758582920010534601480628728499939121974558367127121550503055010424071538766153759162270911395360603569825263335405880954174459577828833846233210410778166654918019875617538190942686820289992610575401960310935710846606839051791715592417281104818086392226647100494699750027103023476707929629784579063689803694907383043172125876755385691596040745724860285667332585925295209125725522194006679836388185705989729419562254734985777898827541327193831546201951473375305370445261717587177126792887218817724626698836157820687203403085215071148671746802681072504035806728796618955352496565895659676776288214833575065225079038209208223206513309026447051074080243278244786609806490361927350617658344861490297439593750953136558998001210962067991059518120322160430789237151710606689120416585404427921394955277733193012218589454521173811654675224424570286104352280039389592063972821188634958104064059178687984935203061971463731565665126838186356345399488585267539326311829049612396116683260951582461873594617204475990552424989260859827268803791227919533052481714556667260279652891963011106279486624219154088741247413035004129834078642518529090663223094655595554971723150662221296101591493235703485037886443421874809293200321361255459625755707768707854122466623948705436343893395477187618693110217168061457398898149502836545465847935456610979600811291261804330021536883976434828311968083242098151412345223762653443009594847889529480473950593880684023133585520604687635961839444429710284031205406882470947526408405576497951742005537989626477719059439828713392471824897399881157756797118158388231162854423991310861841759595822577473056196459452805492506863645642346835058162747802088070477046041889146706342559742287749829459290586684215471994351572965975930998205042312137340218025115813014689500583006300438380236053826380580155316348371781052274821337833600527336833376557701206911094970156148784379249567829393611233049295969721525087143030008031348901297258496699075922738509076646215110558129254147920587431856886906455965532646360364826124591872305901429805625977901375689752727217353364614247850893990062695392398428106826293821207577351932927249018549526569981893008588317335618141350483899667131499023886538967900353203813298931232482387700444779584411122995132253730448938142079152261156271707497563067406241260485651980996431655001740499327757442291748623100917742106573848308620395872513686775591085025003723939817970240638178903148921159863140428935887084583986574358379417803874498486861936690531516499161821820774382423549494835479933862673546428805599781439456398734513079525488429340869602586414052027711985246716083595325124480502734724343390985931623662997005761524450545802123530272853806658153470730702706801444889976323797702022590426599376344717613493849041190899470417705259491290748830299060866402901669464367411426917366819462866174712408123703208654851448438750810317507641342214259542386692199733985049574795383968897159414362846154287494045033651783993501408314622676661699197209522908309334308472799017372013387373793480100709609950777293632452539402555134775940823371949349164222473568699369370879234992806958966263207846912367849591280895443107517767947872714217779371817252209432914588851701381252135999791071925748791416836253888139307475722111512380489496407071054412838299214385598788555521672343684810839516294673636212256749156930265540770761289460762377130989534155575329007502134548347154553672076743346680051494516881966827808845681704547292671979753544404674278776928370582598510030927932835233890464921891651696831667470391729778307695463286738084366771013287694054254531276387817681214661211080982409971962138983128222898216454271853400532278581929840015038948258936500882842435075450295350991272385976170903391933021476635378990855062502639466571101653183780498042166272987689056527150864873171981385138414277036374858330158439331449769801607969022336260344920425306216591145175628029282697346310664953089135137998666631570923174148599170658862114986273907791387049772571957000566205186678183323816366535906818285165610089062351822414416603370071488221782306547560936851228590819890246084106715647025466952830368245845009757967851563218467224040984540918235291898698386514007289000130259355682268920746240201287590921078017122239019481288531050805234415795574192029648152933272007982202397189403622059954936092582158009229689434781248530311722827362789511743739639924495484225804524136015153578004220842660898416474324973613969967489601862563514346296070060712319446331152795403262348447483231694472549069005073487647264375788497495125163787521450677758146411805391551664886652668751509670261657598160176406783104794401035268217456038471475564676106358113702339775319987003317603989413927525832093417693591585361732857836418034731304051510589070371079431982322839167095098645191661388385236430179872902809387946395232667549886811187021922862249179957286473822930814066047891500741543122369748480307326878738726518835528506942064244364483931478411713446791163911788109151977149782284338539558561275867576763903738854295613779999457152886164836641939436521243604270400983752395680516737472262213005410816444355587030486979220722271641202163303469268046676807370988760204750360756607434504567240048491481352566855461189930669616874510641046384306097730692215736992264179560699411501693649430509374413344213126308789707529672599209998445154189084981183058511130579259130886080600036732144575704807180086852847765934646829575183196710994248027564968145629223427683064460901090040189289278345553960633296602210115390825012649303925624402693351605515548724257061299622947135657760493784871208755104909925562090956924840739142833135434060135542037514223186077511407580948557233474761958573096650976670420556026004627597809134659030388925194227504708174969321567746780597055449985841992307235020316466393733080131136669342080026630957986114706614102674603018131914432323404158629061027840873334962778440897853282895885713711193564507205772193475831382804137672913265245365600245517678637646947426367016845327072958357357717316813691901575281931022812265439708859503548646544069392161321907132362468624773188527651082100235846536396645781192179270357621763712935120084485255039043492328076866365377208154827645307165251724791632746643929735578423041969666056363020666440970698719192469011751952195590274241505192365944250349001875343250555697097312492648917668856316793957162454481472832937754461201544736082976088964782650632694501928732392692944875731124191752045112666864043706021131378197546938546057870932464094015208929233503190659802818167513587737855671834819996873001918500648656232950605921597303306370701496379623823614772737787104403807429409304698987959722551878695109550744822761403701076317847464527002820007656416219617909390675057125094490874635504657019786003836957636108771571861787629106130689929990329704391844494418790528249977776655231419843541107086727763341253399915314534581877887852222017857930548991835342801161073380069758239103233307723741692536600685807832532475433261446621492743097262825533558080721197654226981001184763047232769080449112569599899554783743616208343760526909614321626249396415664202627053640175426199345694160676061568775013980820366389102494282378628976243844625445508376601904760788298535362954304290342465237588148291116984753698558605113434186795732561176276001411357278133394720200993132011442863037739353177981959054681560584274476888418384201882672108942916976828680908832225235519963184845184924296910000656708360237299115526252578934458281440002070620436964644197031897410987477867050009694331819137423687184597128587548114336357997236337465637708961947644561663467797375476207358208548007368035927669716167874033598804022722924333241121836816198678965159336185919914028893795088800047444684439008334574057080856218117738979086064769188867440760106969238922515260161220045386159564854371417085746977611005968545779262025737163125402416770670333367961589774438033832170569650414919885015321265827112815044650
Want to submit a riddle?
Email me at oliver.roeder@fivethirtyeight.com.