3
$\begingroup$

We must order the elements A, B, C, D, and E. We are told about the ordering

A B C D E

None of the elements are in their correct positions and none of the elements above correctly follow their immediate predecessor

On the ordering of

D A E C B

We are told that two of the elements are in their correct position and two of the elements correctly follows their immediate predecessor.

What is the correct ordering of the set

I was just looking for some hints and not the correct answer as this is a homework problem

$\endgroup$
2
$\begingroup$

Hints:
There are $44$ derangements of a permutation of $5$ objects ($11$ starting with each of B, C, D, E), you could just write them out and inspect each in turn for the properties that need to hold.

Answer:

The single (expected) answer is
EDACB

However this relies on an interpretation of "two of the elements" as "exactly two of the elements", which is probably what was expected since it asks for "the correct ordering of the set"; a strict interpretation would also allow a second ordering of
DAECB
(the second ordering used in the question itself).

Of course writing a program, which is what I did to check there were no more solutions, is easier and less error prone than writing out and inspecting the derangements (and is what is wanted if it's computing homework).

More hints for hand written solutions:
If we assume "exactly" is implied, it's easier to start with the second sequence DAECB
We know that there are two correct pairs from DA, AE, EC, and CB.
There are $\binom{4}{2}=6$ such combinations, three yielding a triple (e.g. DAE) and three yielding two pairs (e.g. DA and EC).
If we try to place them, along with the other $2$ or $1$ item(s) (respectively) such that the completed ordered set has exactly $2$ places in common with DAECB we find $4$ ordered sets (a triple must be offset from the original to not have $3$ in common leaving no way for the remaining two to be placed, and two pairs must remain in order and have one aligned and one unaligned with the original, making for light work).
Inspecting these for aligned positions of ABCDE leaves $2$, and inspecting those for existence of the pairs AB, BC, CD, and DE leaves only $1$.

|improve this answer|||||
$\endgroup$
-3
$\begingroup$

E D A C B. Relating to the second guess, C and B are in their correct position, B and A follow the correct predecessor.

|improve this answer|||||
$\endgroup$
  • $\begingroup$ Thanks. How did you arrive at that conclusion though. Did you guess, or did you logically deduce it? $\endgroup$ – The_Questioner Jun 14 '16 at 2:10
  • $\begingroup$ I'd like to say I deduced it somehow, but it was mostly just guess-and-check. Also, I didn't fully understand your final statement about just wanting a hint until just now; sorry for spoiling :/ $\endgroup$ – kayzeroshort Jun 14 '16 at 2:45
  • $\begingroup$ It's alright. I think I figured out a way to deduce it logically $\endgroup$ – The_Questioner Jun 14 '16 at 3:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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