wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> easy >> Rubik's Cube
        
(Message started by: alien2 on Mar 8^th, 2019, 10:06am)

Title: Rubik's Cube
Post by alien2 on Mar 8^th, 2019, 10:06am

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.

Title: Re: Rubik's Cube
Post by towr on Mar 8^th, 2019, 11:34pm

[hide]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.[/hide]

Title: Re: Rubik's Cube
Post by alien2 on Mar 9^th, 2019, 9:24am

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.

Title: Re: Rubik's Cube
Post by rmsgrey on Mar 10^th, 2019, 10:02am

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₂₇.

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 [hide]100 steps or 26*H₂₆[/hide]

Title: Re: Rubik's Cube
Post by alien2 on Mar 10^th, 2019, 10:13am

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!

Title: Re: Rubik's Cube
Post by rmsgrey on Mar 11^th, 2019, 9:41am

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 non-independent 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 (n-k)/n, so the expected number of draws to get from k to k+1 is just one over that, or n/(n-k). So for example, when k=0 (you haven't got anything yet), you have an expected time of n/(n-0) = n/n = 1 draw to get a new item. Or when k=n-1 (you're trying to get that last item to complete the set) you have an expected time of n/(n-(n-1)) = 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 26-item 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 26-item 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₂₆ = 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 one-tailed 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).

Title: Re: Rubik's Cube
Post by alien2 on Mar 11^th, 2019, 6:31pm

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

Title: Re: Rubik's Cube
Post by Grimbal on Apr 22^nd, 2019, 8:27am

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?

Title: Re: Rubik's Cube
Post by towr on Apr 22^nd, 2019, 9:26am

on 04/22/19 at 08:27:45, 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.

Title: Re: Rubik's Cube
Post by Grimbal on May 10^th, 2021, 4:53am

I see. I doughnut-shaped cube.

And yes, to some people that makes perfectly sense.