Author |
Topic: Random assignment (Read 940 times) |
|
wonderful
Full Member
Posts: 203
|
 |
Random assignment
« on: Jun 16th, 2008, 6:52pm » |
 Quote  Modify
|
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!
|
| « Last Edit: Jun 16th, 2008, 6:54pm by wonderful » |
 IP Logged |
|
|
|
cool_joh
Newbie
Gender: 
Posts: 50
|
|
Re: Random assignment
« Reply #1 on: Jun 16th, 2008, 11:01pm » |
Quote Modify
|
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?
|
|
IP Logged |
MATH PRO
|
|
|
wonderful
Full Member
Posts: 203
|
|
Re: Random assignment
« Reply #2 on: Jun 17th, 2008, 12:31am » |
Quote Modify
|
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!
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Random assignment
« Reply #3 on: Jun 17th, 2008, 1:39am » |
Quote Modify
|
? In the worst case each marble is in the wrong cell, so they all need to be relocated, so it's 50.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
cool_joh
Newbie
Gender:
Posts: 50
|
|
Re: Random assignment
« Reply #4 on: Jun 17th, 2008, 6:37pm » |
Quote Modify
|
If the answer really is 50, I think this is too trivial. 
|
|
IP Logged |
MATH PRO
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Random assignment
« Reply #5 on: Jun 18th, 2008, 12:06am » |
Quote Modify
|
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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Random assignment
« Reply #6 on: Jun 18th, 2008, 6:35am » |
Quote Modify
|
Wouldn't n-1(49) be enough? But may be I realy don't understand wonderful's notation.
|
| « Last Edit: Jun 18th, 2008, 6:39am by Hippo » |
IP Logged |
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Random assignment
« Reply #7 on: Jun 18th, 2008, 7:47am » |
Quote Modify
|
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?"
|
|
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Random assignment
« Reply #8 on: Jun 18th, 2008, 12:59pm » |
Quote Modify
|
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 n-1, since an n-cycle requires n-1 transpositions.
But this doesn't really agree with wonderful's example.
|
| « Last Edit: Jun 18th, 2008, 1:02pm by Eigenray » |
IP Logged |
|
|
|
wonderful
Full Member
Posts: 203
|
|
Re: Random assignment
« Reply #9 on: Jun 18th, 2008, 1:57pm » |
Quote Modify
|
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!
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Random assignment
« Reply #10 on: Jun 19th, 2008, 1:22am » |
Quote Modify
|
What does the move mean ... will there be situations with more marbles in the same square?
|
|
IP Logged |
|
|
|
wonderful
Full Member
Posts: 203
|
|
Re: Random assignment
« Reply #11 on: Jun 19th, 2008, 1:32am » |
Quote Modify
|
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!
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Random assignment
« Reply #12 on: Jun 19th, 2008, 4:57am » |
Quote Modify
|
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, ...)
|
| « Last Edit: Jun 19th, 2008, 5:00am by Hippo » |
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Random assignment
« Reply #13 on: Jun 19th, 2008, 5:22am » |
Quote Modify
|
on Jun 19th, 2008, 1:32am, wonderful wrote:| The marbles can only move to another empty square. |
|
Then the worst case is 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.
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
capricafox
Newbie
Gender:
Posts: 8
|
|
Re: Random assignment
« Reply #14 on: Jul 12th, 2008, 5:35pm » |
Quote Modify
|
I agree with the 75 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.
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.
I would like to mention that there are only 14 blank cells on a chessboard occupied by 50 marbles.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print