The Ultimate Puzzle and Riddle Site: enjoy puzzles and riddles online!

Solution to: Alien Alert

We take the following abbreviations for the individuals:

F = Federation Officer
A = alien who can fly the spaceship
a = alien who cannot fly the spaceship

Given that the number of Federation officers must be at least equal to the number of aliens on each planet, only the following 16 states are allowed:

State number	Planet 1	Planet 2
1	FFFAaa	-
2	FFFAa	a
3	FFFaa	A
4	FFFA	aa
5	FFFa	Aa
6	FFF	Aaa
7	FFAa	Fa
8	FFaa	FA
9	FA	FFaa
10	Fa	FFAa
11	Aaa	FFF
12	Aa	FFFa
13	aa	FFFA
14	A	FFFaa
15	a	FFFAa
16	-	FFFAaa

Now we make a list of all possible states and flights when the spaceship is on Planet 1 and will fly to Planet 2. Note that we can disregard states where there are no pilots on Planet 1. These are the states numbered 13, 15, and 16.

Note that the possible flights (a maximum of two individuals, with at least one pilot) are as follows: FF, F, FA, Fa, Aa, and A. However, if a flight would result in more aliens than Federation Officers on one of the planets, then that flight is not allowed. For example, in state 1 (all individuals on Planet 1), the flights FF and F are not allowed because they would result in an undesirable state on Planet 1.

We arrive at the following list of possible states and flights when the spaceship (denoted as S) is on Planet 1 and will fly to Planet 2:

Number	State		Possible flights	Resulting state
Number	Planet 1	Planet 2	Possible flights	Planet 1	Planet 2
1	S FFFAaa	-	FA	FFaa	S FA
			Fa	FFAa	S Fa
			Aa	FFFa	S Aa
			A	FFFaa	S A
2	S FFFAa	a	F	FFAa	S Fa
			Aa	FFF	S Aaa
			A	FFFa	S Aa
3	S FFFaa	A	F	FFaa	S FA
4	S FFFA	aa	FF	FA	S FFaa
4	S FFFA	aa	A	FFF	S Aaa
5	S FFFa	Aa	FF	Fa	S FFAa
6	S FFF	Aaa	none possible
7	S FFAa	Fa	FF	Aa	S FFFa
			FA	Fa	S FFAa
			Fa	FA	S FFaa
8	S FFaa	FA	FF	aa	S FFFA
8	S FFaa	FA	Fa	Fa	S FFAa
9	S FA	FFaa	F	A	S FFFaa
9	S FA	FFaa	FA	-	S FFFAaa
10	S Fa	FFAa	F	a	S FFFAa
10	S Fa	FFAa	Fa	-	S FFFAaa
11	S Aaa	FFF	Aa	a	S FFFAa
11	S Aaa	FFF	A	aa	S FFFA
12	S Aa	FFFa	Aa	-	S FFFAaa
12	S Aa	FFFa	A	a	S FFFAa
14	S A	FFFaa	A	-	S FFFAaa

Now we can make the following observations:

State 6 is impossible. Therefore, it can be eliminated.
Every state that is part of the solution must have both an incoming flight and an outgoing flight (except for the initial and final states). This means that for each (intermediate) state, two outgoing flights must be possible: the outgoing flight that is part of the solution and an outgoing flight that is the reverse of the incoming flight of the solution.
Therefore, we can eliminate any (intermediate) state in which only one flight is possible. These are states 3 and 5.
But if we eliminate these states, it means that "S FFFaa" and "S FFFa" can no longer occur as part of the solution. This means that for state 7, one of the three flights is no longer possible, and for state 9, only one possible flight remains. Therefore, state 9 can also be eliminated, which means that "S FA" can no longer occur as part of the solution. This also means that one of the four flights for state 1 becomes impossible.
Flights from the initial state with only one individual are pointless. This is because in the next step, the only possible flight is the return of that individual. Therefore, the flight by A can be eliminated for state 1.
Flights to the final state with only one individual are impossible. That state can only occur if that individual has traveled from Planet 2 to Planet 1 in the previous step, which means that all individuals must have already been on Planet 2 at that time. As a result, state 14 can also be eliminated.
A similar list can be constructed for the states and flights from Planet 2 to Planet 1. We denote those states and flights as 1', 2', 3', ... 14'. For example, state 2 denotes "S FFFaa" on Planet 1 and "a" on Planet 2. Similarly, state 2' denotes "a" on Planet 1 and "S FFFaa" on Planet 2.

When we apply the above observations to the list of possibilities, we get the following:

Number	State		Possible flights	Resulting state		Remarks
Number	Planet 1	Planet 2	Possible flights	Planet 1	Planet 2	Remarks
1	S FFFAaa	-	FA	FFaa	S FA	Eliminated because state 9 ("S FA") has been eliminated
			Fa	FFAa	S Fa	Result is state 10'
			Aa	FFFa	S Aa	Result is state 12'
			A	FFFaa	S A	Eliminated because it is pointless to let only one individual fly from the initial state
2	S FFFAa	a	F	FFAa	S Fa	Result is state 10'
			Aa	FFF	S Aaa	Result is state 11'
			A	FFFa	S Aa	Result is state 12'
3	S FFFaa	A	F	FFaa	S FA	Eliminated because there is only one outgoing flight
4	S FFFA	aa	FF	FA	S FFaa	Result is state 8'
4	S FFFA	aa	A	FFF	S Aaa	Result is state 11'
5	S FFFa	Aa	FF	Fa	S FFAa	Eliminated because there is only one outgoing flight
6	S FFF	Aaa	none possible			Eliminated because this state cannot occur
7	S FFAa	Fa	FF	Aa	S FFFa	Eliminated because state 5 ("S FFFa") has been eliminated
			FA	Fa	S FFAa	Result is state 7'
			Fa	FA	S FFaa	Result is state 8'
8	S FFaa	FA	FF	aa	S FFFA	Result is state 4'
8	S FFaa	FA	Fa	Fa	S FFAa	Result is state 7'
9	S FA	FFaa	F	A	S FFFaa	Eliminated because state 3 ("S FFFaa") has been eliminated
9	S FA	FFaa	FA	-	S FFFAaa	Eliminated because this is the only remaining outgoing flight
10	S Fa	FFAa	F	a	S FFFAa	Result is state 2'
10	S Fa	FFAa	Fa	-	S FFFAaa	Result is the final state
11	S Aaa	FFF	Aa	a	S FFFAa	Result is state 2'
11	S Aaa	FFF	A	aa	S FFFA	Result is state 4'
12	S Aa	FFFa	Aa	-	S FFFAaa	Result is the final state
12	S Aa	FFFa	A	a	S FFFAa	Result is state 2'
14	S A	FFFaa	A	-	S FFFAaa	Eliminated because this state cannot occur

Now we can see the following:

There are two possibilities to go from the initial state (state 1) to state 2:
- 1 → 10' → 2
- 1 → 12' → 2
There are two possibilities to go from state 2' to the final state:
- 2' → 10 → final state
- 2' → 12 → final state
There is exactly one possible way to go from state 2 to state 2':
- 2 → 11' → 4 → 8' → 7 → 7' → 8 → 4' → 11 → 2'

We conclude that there are four possible solutions, which are listed below.

Solution 1

Planet 1          Flight          Planet 2

F F F A a a
                -- F a -->
F F A a                           F a
                <-- F ----
F F F A a                         A a
                -- A a -->
F F F                             A a a
                <-- A ----
F F F A                           a a
                -- F F -->
F A                               F F a a
                <-- F a --
F F A a                           F a
                -- F A -->
F a                               F F A a
                <-- F a --
F F a a                           F A
                -- F F -->
a a                               F F F A
                <-- A ----
A a a                             F F F
                -- A a -->
a                                 F F F A a
                <-- F ----
F a                               F F A a
                -- F a -->
                                  F F F A a a

Solution 2

Planet 1          Flight          Planet 2

F F F A a a
                -- F a -->
F F A a                           F a
                <-- F ----
F F F A a                         A a
                -- A a -->
F F F                             A a a
                <-- A ----
F F F A                           a a
                -- F F -->
F A                               F F a a
                <-- F a --
F F A a                           F a
                -- F A -->
F a                               F F A a
                <-- F a --
F F a a                           F A
                -- F F -->
a a                               F F F A
                <-- A ----
A a a                             F F F
                -- A a -->
a                                 F F F A a
                <-- A ----
A a                               F F F a
                -- A a -->
                                  F F F A a a

Solution 3

Planet 1          Flight          Planet 2

F F F A a a
                -- A a -->
F F F a                           A a
                <-- A ----
F F F A a                         A a
                -- A a -->
F F F                             A a a
                <-- A ----
F F F A                           a a
                -- F F -->
F A                               F F a a
                <-- F a --
F F A a                           F a
                -- F A -->
F a                               F F A a
                <-- F a --
F F a a                           F A
                -- F F -->
a a                               F F F A
                <-- A ----
A a a                             F F F
                -- A a -->
a                                 F F F A a
                <-- F ----
F a                               F F A a
                -- F a -->
                                  F F F A a a

Solution 4

Planet 1          Flight          Planet 2

F F F A a a
                -- A a -->
F F F a                           A a
                <-- A ----
F F F A a                         A a
                -- A a -->
F F F                             A a a
                <-- A ----
F F F A                           a a
                -- F F -->
F A                               F F a a
                <-- F a --
F F A a                           F a
                -- F A -->
F a                               F F A a
                <-- F a --
F F a a                           F A
                -- F F -->
a a                               F F F A
                <-- A ----
A a a                             F F F
                -- A a -->
a                                 F F F A a
                <-- A ----
A a                               F F F a
                -- A a -->
                                  F F F A a a

Back to the puzzle