A blind old man loves jigsaw puzzles. He starts them by picking a piece at random and putting it down. He then picks another piece at random and tries to attach it to each side of the piece he started with (trying all four rotations and flipping it over) and repeats until the piece fits. Then he picks another piece at random and tries to attach it to the part of the puzzle he already has. He continues doing this until the puzzle is solved. What is the expected number of pieces he will try in order to solve an m by n puzzle?
Welcome to BrainDen.com - Brain Teasers Forum
|Welcome to BrainDen.com - Brain Teasers Forum. Like most online communities you must register to post in our community, but don't worry this is a simple free process. To be a part of BrainDen Forums you may create a new account or sign in if you already have an account.
As a member you could start new topics, reply to others, subscribe to topics/forums to get automatic updates, get your own profile and make new friends.
Of course, you can also enjoy our collection of amazing optical illusions and cool math games.
If you like our site, you may support us by simply clicking Google "+1" or Facebook "Like" buttons at the top.
If you have a website, we would appreciate a little link to BrainDen.
Thanks and enjoy the Den :-)
Blind man's jigsaw puzzle
Posted 06 February 2013 - 09:08 PM
Posted 08 February 2013 - 01:22 AM
Spoiler for Answer
Technically, you're right. What i mean to ask though is how many times will he pick up a piece.
Note: When a piece does not fit, he puts it back into the pile and may pick it up again immediately. If so, it still counts as picking up another piece.
The solution I found is recursive. I have closed forms for m=1 and m=2. I'm still working on generalizing it.
Posted 09 February 2013 - 10:43 PM
Edited by phil1882, 09 February 2013 - 10:44 PM.
Posted 10 February 2013 - 01:40 AM
The solution would be straightforward, but...
Past prime, actually.
Posted 10 February 2013 - 03:31 AM
Actually, it's more complicated. Like Phil1882 noted.
Past prime, actually.
Posted 22 February 2013 - 04:56 PM
Below are closed-form expressions for 1xn and 2xn cases
0 user(s) are reading this topic
0 members, 0 guests, 0 anonymous users