wu :: forums - Print Page


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

        riddles >> medium >> Random assignment
        
(Message started by: wonderful on Jun 16^th, 2008, 6:52pm)

Title: Random assignment
Post by wonderful on Jun 16^th, 2008, 6:52pm

There are 50 cells numbered from 1 to 50 and 50 marbles also numbered from 1 to 50. These 50 marbles are randomly assigned to the 50 cells.

What is the maximum number of re-allocations you need to make so that each marble is assigned to the cell with the same corresponding number?

Have A Great Day!

Title: Re: Random assignment
Post by cool_joh on Jun 16^th, 2008, 11:01pm

In one re-allocation, do you interchange the positions of two marbles or do you move a marble to another cell?

Maximum means minimum upper bound right?

Title: Re: Random assignment
Post by wonderful on Jun 17^th, 2008, 12:31am

Let's say, marble 3 in cell 5; marble 5 in cell 7; and marble 7 in cell 3. Then, by 3 re-allocations: 3-3, 5-5, and 7-7 we have the desired outcomes for marbles 3, 5, and 7.

Have A Great Day!

Title: Re: Random assignment
Post by towr on Jun 17^th, 2008, 1:39am

? In the worst case each marble is in the wrong cell, so they all need to be relocated, so it's 50.

Title: Re: Random assignment
Post by cool_joh on Jun 17^th, 2008, 6:37pm

If the answer really is 50, I think this is too trivial. ???

Title: Re: Random assignment
Post by towr on Jun 18^th, 2008, 12:06am

That's what I was thinking as well. But no matter how I look at the puzzle that's the only thing that comes up.

Title: Re: Random assignment
Post by Hippo on Jun 18^th, 2008, 6:35am

Wouldn't n-1(49) be enough? But may be I realy don't understand wonderful's notation.

Title: Re: Random assignment
Post by Sir Col on Jun 18^th, 2008, 7:47am

I don't think he meant you empty out all the marbles in wrong positions and re-allocate them to the correct cells. So I wonder if he meant us to perform a "bubble" swap? I've used his example below with the pairs representing (cell number,marble number).

(3,7) (5,3) (7,5)
move marble 3 to cell 3
(3,3) (5,7) (7,5)
move marble 5 to cell 5
(3,3) (5,5) (7,7)

However, this would stretch his definition of "3 re-allocations" to include the initial position. Also a bubble sort is also rather trivial for a "medium" problem; a "worst case scenario" sort requiring up to n(n-1)/2 swaps. Unless he meant thinking outside the basic algorithm. For example, the following initial configuration would require the maximum three swaps usnig a blind sort, but can be done in one if you pick the right pair:
(3,7) (5,5) (7,3)

So now I'm not sure either?

"wonderful, where are you?"

Title: Re: Random assignment
Post by Eigenray on Jun 18^th, 2008, 12:59pm

Any permutation is a product of transpositions (swaps). The only reasonable (non-trivial) interpretation I can think of would be: what is the smallest number k such that any permutation on n elements can be written as a product of at most k transpositions. So the answer should be [hide]n-1, since an n-cycle requires n-1 transpositions[/hide].

But this doesn't really agree with wonderful's example.

Title: Re: Random assignment
Post by wonderful on Jun 18^th, 2008, 1:57pm

Thanks guys for pointing out some shortcomings of the original question. I appreciate it. I have revised the question as follows:

There are 50 cells numbered 1- 50 in a chess board. Fifty marbles numbered 1-50 are randomly assigned in these cells. What is the maximal number of moves you need to re-assign each marbles to the cell which has the same number.

Have A Great Day!

Title: Re: Random assignment
Post by Hippo on Jun 19^th, 2008, 1:22am

What does the move mean ... will there be situations with more marbles in the same square?

Title: Re: Random assignment
Post by wonderful on Jun 19^th, 2008, 1:32am

Thanks Hipo for this clarifying question. The marbles can only move to another empty square. For simplicity, we also assume that they can jump e.g., 1=>3 is ok as long as 3 is empty even 2 is occupied by some marble. Also, please remember that the chessboard is a standard one.

Have A Great Day!

Title: Re: Random assignment
Post by Hippo on Jun 19^th, 2008, 4:57am

OK, it's much valuable to answer questions to someone who knows what is he asking for.

... with these rules the original question has no solution at all (no possible move) ...

P.S.: All these questions are trivial, the only nontriviality is to correctly guess what do you intend to ask ... may be special category should be introduced for such a case (not hard, not medium, ...)

Title: Re: Random assignment
Post by SMQ on Jun 19^th, 2008, 5:22am

on 06/19/08 at 01:32:02, wonderful wrote:

The marbles can only move to another empty square.

Then the worst case is [hide]75 moves. It takes n+1 moves to resolve a cycle involving n marbles, so if the marbles are swapped in pairs it will take 25(2+1) moves to sort them.[/hide]

--SMQ

Title: Re: Random assignment
Post by capricafox on Jul 12^th, 2008, 5:35pm

I agree with the [hide]75[/hide] but that is if the marbles are all in pairs.

Now, can you give the minimum moves if all marbles were all in wrong places? Explain your data as part of your solution.

[hide]The fastest way, I think, presumes that all marbles are forming a unique big chain of 50 nodes, no pairs, no triplet, etc... Removing 1 marble allows the marble of the free cell to move in, freeing another cell for another marble, but never the initial marble until the very end. In that case, 1+49+1=51 moves.[/hide]

I would like to mention that there are only 14 blank cells on a chessboard occupied by 50 marbles.