Problem 648. Cumulative probability of finding an unlikely combination

Created by Doug Hull

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>This is a supplemental problem to the</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://www.mathworks.com/matlabcentral/cody/problems/621-cryptomath-addition\"><w:r><w:t>CryptoMath</w:t></w:r></w:hyperlink><w:r><w:t> problem. If you solve the problem methodically or randomly matters for expected solution time. This calculates the difference in techniques. My reference solution has some commented out graphics code to visualize the timing differences.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>---</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>If you have N possible combinations to a lock you can calculate the likelihood of opening the lock as a percentage given X attempts.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>There are two ways to figure out the combination to try:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>Try a random one, possibly trying an old one again</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>Methodically doing them in order</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Choosing a random combination is very fast and easy. No record keeping needed. Choosing a methodical way of trying them all is a little slower on each attempt, and incurs a fix cost before the first attempt is made.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>If you have:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>Goal of</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>G%</w:t></w:r><w:r><w:t> cumulative probability of opening the lock</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>Fixed cost of</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>F</w:t></w:r><w:r><w:t> seconds to start the methodical style</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>TR</w:t></w:r><w:r><w:t> seconds per random attempt</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>TM</w:t></w:r><w:r><w:t> seconds per methodical attempt</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>N</w:t></w:r><w:r><w:t> equally likely combinations</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Which technique should you use to get to your goal chance fastest?</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>0</w:t></w:r><w:r><w:t> for random</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>1</w:t></w:r><w:r><w:t> for methodical</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>--- Note for the curious: The really short solution is gaming the system and just choosing randomly. Eventually one of the solutions will guess right on all the test suite.</w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

This is a supplemental problem to the <a href="http://www.mathworks.com/matlabcentral/cody/problems/621-cryptomath-addition">CryptoMath</a> problem. If you solve the problem methodically or randomly matters for expected solution time. This calculates the difference in techniques. My reference solution has some commented out graphics code to visualize the timing differences.---If you have N possible combinations to a lock you can calculate the likelihood of opening the lock as a percentage given X attempts.There are two ways to figure out the combination to try:<ul><li>Try a random one, possibly trying an old one again</li><li>Methodically doing them in order</li></ul>Choosing a random combination is very fast and easy. No record keeping needed. Choosing a methodical way of trying them all is a little slower on each attempt, and incurs a fix cost before the first attempt is made.If you have:<ul><li>Goal of G% cumulative probability of opening the lock</li><li>Fixed cost of F seconds to start the methodical style</li><li>TR seconds per random attempt</li><li>TM seconds per methodical attempt</li><li>N equally likely combinations</li></ul>Which technique should you use to get to your goal chance fastest?<ul><li>0 for random</li><li>1 for methodical</li></ul>---
Note for the curious: The really short solution is gaming the system and just choosing randomly. Eventually one of the solutions will guess right on all the test suite.

Solve

Solution Stats

109 Solutions
29 Solvers

Last Solution submitted on Aug 19, 2020

Last 200 Solutions

Problem Comments

2 Comments

2 Comments

@bmtran (Bryant Tran) on 2 May 2012

bah, my lack of knowledge of probability fails me again

Peter Wittenberg on 18 Aug 2012

A very interesting probability problem applicable across a lot of areas underlies the solution. It isn't obvious at first glance. The solution is fairly short, but it takes a lot of thought to get it. I can't wait to see the length 14 solution!

Solution Comments

Solution 85685

3 Comments

3 Comments

@bmtran (Bryant Tran) on 4 May 2012

ironic solution ftw!

Doug Hull on 8 May 2012

I should have known! :) Next problem is, how many times can you expect to submit that solution! :)

Peter Wittenberg on 18 Aug 2012

OK. You've gamed the solution. The author shouldn't have to beef up the test suite to prevent this sort of solution.

Problem Recent Solvers29

Problem Tags

ml101

Problem 648. Cumulative probability of finding an unlikely combination

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers29

Suggested Problems

More from this Author52

Problem Tags

Problem 648. Cumulative probability of finding an unlikely combination

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers29

Suggested Problems

More from this Author52

Problem Tags

Players