wu :: forums
« wu :: forums - Rubik's Cube »

Welcome, Guest. Please Login or Register.
Jun 23rd, 2021, 7:20am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   easy
(Moderators: ThudnBlunder, towr, Eigenray, Grimbal, SMQ, Icarus, william wu)
   Rubik's Cube
« No topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Rubik's Cube  (Read 13747 times)
alien2
Uberpuzzler
*****






   


Gender: male
Posts: 6930
Rubik's Cube  
« on: Mar 8th, 2019, 10:06am »
Quote Quote Modify 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: male
Posts: 13729
Re: Rubik's Cube  
« Reply #1 on: Mar 8th, 2019, 11:34pm »
Quote Quote Modify 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: male
Posts: 6930
Re: Rubik's Cube  
« Reply #2 on: Mar 9th, 2019, 9:24am »
Quote Quote Modify 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
*****





134688278 134688278   rmsgrey   rmsgrey


Gender: male
Posts: 2840
Re: Rubik's Cube  
« Reply #3 on: Mar 10th, 2019, 10:02am »
Quote Quote Modify 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 K27.
 
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*H26
« Last Edit: Mar 11th, 2019, 8:33am by rmsgrey » IP Logged
alien2
Uberpuzzler
*****






   


Gender: male
Posts: 6930
Re: Rubik's Cube  
« Reply #4 on: Mar 10th, 2019, 10:13am »
Quote Quote Modify 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 10th, 2019, 10:40am by alien2 » IP Logged


rmsgrey
Uberpuzzler
*****





134688278 134688278   rmsgrey   rmsgrey


Gender: male
Posts: 2840
Re: Rubik's Cube  
« Reply #5 on: Mar 11th, 2019, 9:41am »
Quote Quote Modify 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 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*Hn 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*H26 = 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).
« Last Edit: Apr 23rd, 2019, 5:33am by rmsgrey » IP Logged
alien2
Uberpuzzler
*****






   


Gender: male
Posts: 6930
Re: Rubik's Cube  
« Reply #6 on: Mar 11th, 2019, 6:31pm »
Quote Quote Modify Modify

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


Grimbal
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 7515
Re: Rubik's Cube  
« Reply #7 on: Apr 22nd, 2019, 8:27am »
Quote Quote Modify 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: male
Posts: 13729
Re: Rubik's Cube  
« Reply #8 on: Apr 22nd, 2019, 9:26am »
Quote Quote Modify Modify

on Apr 22nd, 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: male
Posts: 7515
Re: Rubik's Cube  
« Reply #9 on: May 10th, 2021, 4:53am »
Quote Quote Modify Modify

I see.  I doughnut-shaped cube.
 
And yes, to some people that makes perfectly sense.
IP Logged
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« No topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board