1
$\begingroup$

While working on a mathematical model we have come across a problem that seems easy yet has a bunch of intelligent, mathematically trained people start doubting themselves :).

Riddle us this...

Planet Elian is inhabited by flying elves. There are two islands, Sun and Moon. On island Sun live 250 elves, on island Moon 750. Each month a boat leaves from Sun to Moon and back, with room for 25 elves. The boat is always full and is the only way of transport between the islands (the elves don't fly off the islands). One day a black wizard visits Elian and curses the elves. Until the end of time 200 of the elves will be unable to fly... Luckily the non-flying elves have a 1 in 10 chance each month to be able to fly again. Unfortunately, because of the curse, the same amount of flying elves will have their wings cut.

Knowing that the chance to have your wings cut is twice as high on island Sun than on Moon, we would like to know the following:

  1. How many of the 200 elves that can't fly live on Moon?
  2. How many of those elves can fly back every month?
  3. How many elves have their wings cut on Sun?
  4. How many flying elves are on the boat from Sun to Moon and how many on the way back?

(Solving this will require non-integer numbers. This is ofcourse no problem.)

Basically we think it comes down to finding the state transition probabilities for the following Markov Model:

enter image description here

The person who can solve this will have our eternal respect and will be mentioned in the credits of the model!

Thanks and good luck!

$\endgroup$
  • 3
    $\begingroup$ Are you looking for the stationary distribution of the corresponding Markov model? $\endgroup$ – Michael Burr Mar 24 '15 at 11:15
  • $\begingroup$ Yeah probably, we haven't looked at it as being a Markov model! I added a visualization of the model, we are looking for the state transition probabilities. Is it possible to find them based on the data we supplied? The problem might be that we overdetermined the system. $\endgroup$ – Mindbytes Mar 24 '15 at 12:02
  • $\begingroup$ Points of clarification: There are 200 non-flying elves at any time. Do exactly 10 percent of them (i.e., 20) regain the ability to fly at a given point in time each month, or do they regain it in continuous time? When one regains the ability, is there a corresponding elf that loses the ability at the same time? When you say that Sun elves are twice as likely to lose the ability to fly, does that mean that the curse picks a randomly chosen Sun elf with probability 2/3, or do you mean that a given Sun elf is twice as likely to lose the ability as a given Moon elf? $\endgroup$ – Brian Tung Mar 24 '15 at 23:04
0
$\begingroup$

All changes happen indeed at a given point in time and a single Elf can only move once from one state to the other during this month. Regarding probability, the probability is indeed relative on Sun versus Moon. As an example, if the probability to be cursed would be 8% on Moon, it would be 16% on Sun.

$\endgroup$
  • $\begingroup$ You should probably have posted this as a comment rather than as an answer. So we can treat this as a problem in discrete time, and I will assume (unless contradicted) that each month, when 20 of the non-flying elves regain the ability to fly, an entirely disjoint 20 of the flying elves lose it. $\endgroup$ – Brian Tung Mar 26 '15 at 16:51
  • $\begingroup$ I also assume that the boat selects 25 elves randomly from each island to transport to the other island, without regard to their ability to fly. $\endgroup$ – Brian Tung Mar 26 '15 at 16:53
0
$\begingroup$

I'm not sure we can assume that all changes take place at the same time. It seems to me that we have to separate the boat exchange from the flight/non-flight exchange.

Case I. Let us suppose, arbitrarily, that the boat exchange takes place before the flight/non-flight exchange. At the beginning of the cycle, there are $750$ elves on M, of which $n$ are non-flying, and $250$ elves on S, of which $200-n$ are non-flying. During the boat exchange, $1/30$ of the elves on M switch places with $1/10$ of the elves on S. On M, therefore, we finish the boat exchange with

$$ n-\frac{n}{30}+\frac{200-n}{10} = \frac{300+13n}{15} $$

non-flying elves, and on S, we finish with

$$ 200-n-\frac{200-n}{10}+\frac{n}{30} = \frac{2700-13n}{15} $$

non-flying elves. Next, let us execute the flight/non-flight exchange. Given the above numbers of non-flying elves on each island, there must be $(10950-13n)/15$ flying elves on M, and $(1050+13n)/15$ flying elves on S. Let $p$ be the proportion of flying elves on M that lose the ability to fly; then $2p$ is the proportion of flying elves on S that lose that ability. The total number of flying elves that lose the ability to fly must be equal to the number of non-flying elves that regain it, which in turn is $1/10$ of the number of non-flying elves, or $20$. Therefore,

$$ \frac{(10950-13n)p}{15} + \frac{(1050+13n)(2p)}{15} = 20 $$ $$ 13050+13n = \frac{300}{p} $$ $$ p = \frac{300}{13050+13n} $$

Now, consider the situation on M. After the boat exchange, there are $(300+13n)/15$ non-flying elves. Of those, one-tenth, or $(300+13n)/150$, regain the ability to fly, but $(10950-13n)p/15 = (219000-260n)/(13050+13n)$ of the flying elves lose that ability. Therefore, at the end of the cycle, we have a grand total of

$$ \frac{9(300+13n)}{150}+\frac{219000-260n}{13050+13n} = \frac{507n^2+507650n+22695000}{650n+652500} $$

non-flying elves on M. At equilibrium, this must be equal to the number of non-flying elves at the beginning of the cycle—namely, $n$. We then end up with the quadratic equation

$$ 143n^2+144850n-22695000 = 0 $$

which yields the (positive) solution

$$ n = \frac{125\sqrt{543409}-72425}{143} \doteq 137.90455 $$

Case II. Now, let us consider the situation when the boat exchange takes place after the flight/non-flight exchange. We start with $n$ non-flying and $750-n$ flying elves on M, and $200-n$ non-flying and $50+n$ flying elves on S. We again let $p$ be the proportion of the flying elves that lose the ability to fly on M (and $2p$ be the proportion that lose it on S). Then

$$ (750-n)p + (50+n)(2p) = 20 $$ $$ 850+n = \frac{20}{p} $$ $$ p = \frac{20}{850+n} $$

and the number of non-flying elves on M after the flight/non-flight exchange must be

$$ \frac{9n}{10} + \frac{20(750-n)}{850+n} = \frac{9n^2+7450n+150000}{10n+8500} $$

The number of non-flying elves on S after the flight/non-flight exchange can be derived similarly, or alternatively as $200$ minus the above, or

$$ 200 - \frac{9n^2+7450n+150000}{10n+8500} = -\frac{9n^2+5450n-1550000}{10n+8500} $$

Next, let us execute the boat exchange, which exchanges $1/30$ of the elves on M with $1/10$ of the elves on S. On M, we end up with

$$ \frac{29(9n^2+7450n+150000)}{30(10n+8500)} + \frac{9n^2+5450n-1550000}{10(10n+8500)} = \frac{117n^2+99850n+4500000}{150n+127500} $$

Again, this must be equated with $n$, at equilibrium, which yields the quadratic equation

$$ 33n^2+27650n-4500000 = 0 $$

which has the (positive) solution

$$ n = \frac{25\sqrt{543409}-13825}{33} \doteq 139.51728 $$

As you see, the order of the operations makes a small but non-zero difference. They are in some sense conjugates of each other; the state at the middle of one is the same as the state at the ends of the other. You can pick one or the other with equal reason, I think.

$\endgroup$

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.