Author 
Topic: Rubik's Cube (Read 14175 times) 

alien2
Uberpuzzler
Gender:
Posts: 6953


Rubik's Cube
« on: Mar 8^{th}, 2019, 10:06am » 
Quote Modify

You are trapped inside a Rubik’s Cube levitating a mile up in the air so that it is possible to get to the roof only outside the cube. The 27 rooms, each with six accessible doors centered on each side, are often changing their location randomly by means of quantum teleportation, more precisely, each time you enter another room. You are allowed to break free if you make a valid assertion, that is to say, that you have been in every room. After how many entering from one room to another it is advised making your assertion? It will be warm and you will be properly fed, though you’ll have to sleep on the floor, while your feces and urine will disintegrate immediately before hitting the floor.


IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: Rubik's Cube
« Reply #1 on: Mar 8^{th}, 2019, 11:34pm » 
Quote Modify

If the room randomly teleport around, and you can't mark them, then there's no telling if you've been in every room. The room you're in can always be teleported to the opposite corner from a room you've never been in, and so you can never get there.


IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



alien2
Uberpuzzler
Gender:
Posts: 6953


Re: Rubik's Cube
« Reply #2 on: Mar 9^{th}, 2019, 9:24am » 
Quote Modify

Thanks for illustrating the point Towr. As per "random" teleportation AND probability, is there really no number You could offer, say, is a thousand times, possibly, advised after which time to make your assertion? Math is not my strong suit, much to my everlasting shame.


IP Logged 



rmsgrey
Uberpuzzler
Gender:
Posts: 2861


Re: Rubik's Cube
« Reply #3 on: Mar 10^{th}, 2019, 10:02am » 
Quote Modify

So you're looking at a modified version of the collector problem  rather than entering a random room at each step, you enter a random different room at each step. It's also a random walk on K_{27}. There are two steps to getting a proper answer to this problem: 1) working out the numbers to get the probability of having visited all rooms after n steps A) deciding what the threshold probability you want is If you just want the expected time to visit all rooms, it's 100 steps or 26*H_{26}

« Last Edit: Mar 11^{th}, 2019, 8:33am by rmsgrey » 
IP Logged 



alien2
Uberpuzzler
Gender:
Posts: 6953


Re: Rubik's Cube
« Reply #4 on: Mar 10^{th}, 2019, 10:13am » 
Quote Modify

And rmsgrey saves the day! Does he? Of course He does! Still not that good at math . . . All that math and jazz you throw at me, hitting me with advanced math stuff with an analogy being a monkey being hit by bananas. Bananas I like. Math, perhaps. Aw! The shame! But at least I know what is 2 + 2! When I put two and two together, baby, there is nooooooooo stopping me!

« Last Edit: Mar 10^{th}, 2019, 10:40am by alien2 » 
IP Logged 



rmsgrey
Uberpuzzler
Gender:
Posts: 2861


Re: Rubik's Cube
« Reply #5 on: Mar 11^{th}, 2019, 9:41am » 
Quote Modify

More detailed breakdown (not going to bother hiding since it doesn't solve the general question, and my previous post gives enough keywords people can just google it themselves anyway): The "collector problem" (or "coupon collector problem") is a standard problem in probability theory, where you have a set of collectibles, say, baseball cards, or stickers for a sticker album, which are available as individual random draws from a very large pool (so each draw has the same chance of getting a given item) and where each item has the same probability of being drawn. The question is what the expected time to draw a complete set is. That is, if you went through the process of collecting a complete set through random draws a large number of times (starting from scratch each time), what's the mean number of draws needed to get the complete set? Because the expected time for event A then event B to happen is the expected time for event A to happen plus the expected time for event B to happen following event A (a property known as "linearity of expectation" which is true for both independent and nonindependent events). After you have k different items out of the set of n, the probability of getting a new one on the next draw is (nk)/n, so the expected number of draws to get from k to k+1 is just one over that, or n/(nk). So for example, when k=0 (you haven't got anything yet), you have an expected time of n/(n0) = n/n = 1 draw to get a new item. Or when k=n1 (you're trying to get that last item to complete the set) you have an expected time of n/(n(n1)) = n/1 = n draws. In between, you have n/2, n/3, n/4, n/5, etc. If you take out the common factor of n, you get that the total expected time is n*H_{n} where H[/sub]n[/sub] is the nth "harmonic number" or the sum of the reciprocals of the integers 1 to n. To convert the collector problem into this problem, you need to account for the fact that each step is to one of 26 different rooms, not to one of 27 different rooms (every step changes which room you're in), and for the fact that you start in a room. Those two changes combine to make the cube problem equivalent to the 26item collector problem: at each step, you're "drawing" from 26 rooms, of which k are new, so you have a k/26 chance of stepping into a new room at each step. A way of simulating the problem that makes the equivalence to the 26item collector problem even clearer is as follows: Take a standard deck of 52 playing cards. Take the Clubs and Diamonds, and use them to label the 26 rooms apart from the start room. For each step, draw one of the 26 remaining cards (the Spades and Hearts)  if you draw a Spade, the move is to the corresponding Club; a Heart moves to the corresponding Diamond. So, for example, if your first draw was the Ace of Spades, the first move would be to the room labelled by the Ace of Clubs. If you draw the room you're currently in, then move to the start room instead. Drawn cards are shuffled back into the pack immediately, so you're always drawing 1 of 26 cards, each moving you to a different 1 of the 26 rooms you're not currently in. Because you start in the start room, and the first time you draw a given card, you'll visit the matching room, you will have visited every room after exactly the same number of steps as it takes to draw every card at least once. So, if you had a million people trapped inside the cube, on average it would take them 26*H_{26} = 100 steps to visit every room for the first time. That's not the same as having a 50% chance of visiting every room in the first 100 steps  it's actually going to be more than 50% because of the onetailed shape of the distribution  you can't possibly visit all the rooms in fewer than 26 steps, but you can still have not yet visited them all after a billion steps  and one run of a billion steps contributes has more effect on the mean than ten million runs of 26 steps, so the mean is going to end up above the median. Working out the probability of having visited all 27 rooms after n steps is a different matter, but you can take the 100 step figure as a rule of thumb, and take, say, 500 steps as giving a safe margin (you'll have a significantly better than 97% chance of having visited all rooms by then  if there were an exactly 50% chance of visiting all rooms in 100 steps, and you had to visit all rooms in a single block of 100 steps, then you'd have a 96.75% chance of having done so in at least one of the five blocks  because the probability is greater than 50% in the first 100 steps, and you carry over previously visited rooms, the probability of success grows much faster than that).

« Last Edit: Apr 23^{rd}, 2019, 5:33am by rmsgrey » 
IP Logged 



alien2
Uberpuzzler
Gender:
Posts: 6953


Re: Rubik's Cube
« Reply #6 on: Mar 11^{th}, 2019, 6:31pm » 
Quote Modify

You're not an uberpuzzler for nothing. Well done.


IP Logged 



Grimbal
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 7523


Re: Rubik's Cube
« Reply #7 on: Apr 22^{nd}, 2019, 8:27am » 
Quote Modify

A few questions:  What stops you from claiming "I have been in all rooms" every day and just wait for the assertion to become valid?  What if you make the valid assertion on the 1st day "I have not been in all rome"?  If the cube is hovering miles above the ground, do you really want to break free?  How is it possible to arrange 27 cubical rooms so that all 6 doors lead to other cubes? Or can you accidentally reach the outside?  What is that roof you can access from outside the cube?


IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: Rubik's Cube
« Reply #8 on: Apr 22^{nd}, 2019, 9:26am » 
Quote Modify

on Apr 22^{nd}, 2019, 8:27am, Grimbal wrote: How is it possible to arrange 27 cubical rooms so that all 6 doors lead to other cubes? 
 They teleport around so you're effectively always in a room in the center of the cube.


IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



Grimbal
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 7523


Re: Rubik's Cube
« Reply #9 on: May 10^{th}, 2021, 4:53am » 
Quote Modify

I see. I doughnutshaped cube. And yes, to some people that makes perfectly sense.


IP Logged 



