7
$\begingroup$

You're a cosmonaut dedicated to exploring and understanding strange new worlds. The latest world you've arrived on has a species with a very strange mating dance. After careful observation, you determine the rules for this dance are:

  1. All aliens on the planet are ordered by height and given a number. Number 1 for the shortest, number 2 for the next shortest, etc. There are no ties.
  2. The aliens get into a line in a randomized order.
  3. The alien at the front of the line checks its number, finds the alien at that place in line, and trades place with them. Ex: if the front alien has number 5, it trades places with the fifth alien in line (itself being the first). They repeat this step indefinitely.
  4. If the shortest alien is at the front of the line, the dance ends and the orgy begins. These aliens will not stop dancing until this happens.

You start to wonder: how can this species exist? Surely given enough time, the random arrangement would result in a never-ending dance and, unable to mate, the species would die off. After pondering and observing a while, inspiration strikes. Now satisfied that this is impossible, you leave the planet in search of more interesting puzzles.

How did you know this species can't die off?

Improve this question
$\endgroup$
1
  • $\begingroup$ Never-ending? Seems more likely that eventually No. 1 would be at the front of the line and the dance would stop dead without any outcome. $\endgroup$
    – jhabbott
    Commented Feb 25, 2016 at 23:07

3 Answers 3

Reset to default
28
$\begingroup$

Note that once an alien is in the spot matching its number, it will never swap with another alien again. Every step, one alien moves into its spot, so the number of aliens in the right spot increases by 1 every step. This number can't exceed the number of aliens, which is finite, so there must be a finite number of steps.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Formally, we can represent the aliens-at-the-front as a directed list as opposed to a directed graph (which could potentially contain a loop). $\endgroup$
    – corsiKa
    Commented Feb 26, 2016 at 0:47
  • $\begingroup$ This answer isn't actually complete. It seems quite concise, but seems to assert that the list will get fully sorted in a finite number of steps. Obviously, once 1 gets to the front of the list, it stops the sorting. If the dance continued, then an infinite number of steps would be taken, without increasing the number of aliens in the right spot. $\endgroup$
    – Lacklub
    Commented Feb 26, 2016 at 16:05
2
$\begingroup$

The number of moves it takes in order for the shortest alien to be at the front of the line is O(n). Therefore, they keep dancing until enough aliens die off that the dance converges in a reasonable time.

Improve this answer
$\endgroup$
1
$\begingroup$

Obviously, the aliens can cheat.

Another solution is that the population is very small, or gets very small during the mating dance (aliens die during the dance and thus get removed from the line). It also makes sense to assume that the aliens are hermaphrodites.

The line also does not need to be straight, which can reduce the travel time from one position to another.

Edit: this assumes that "aliens" mean the inhabitants of the planet in question, not aliens from the inhabitants' point of view (that would be you, and the orgy would start when the shortest visiting cosmonaut arrived at the first position - not necessarily participating in the orgy).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.