4
$\begingroup$

Given $a$ apples and $b$ mangoes, where $a$ and $b$ can be non negative numbers, we can convert one apple to mango or vice versa in one move. What is the expected number of moves after which only one kind of fruit will be left, i.e, one of the following condition satisfies:

  1. #apples = $a$+$b$ and #mangoes = 0
  2. #apples = 0 and #mangoes = $a$+$b$

My attempt: I thought of recurrence relation $E(a,b) = 1 + \tfrac12 E(a-1,b+1) + \tfrac12 E(a+1,b-1)$ (thanks @henry for correcting it) but could not moved further from this. Also, I thought that expected number of moves will only depend on max($a$,$b$). I am not sure but I have strong intuition that this is correct.

Question Link: https://my.newtonschool.co/playground/code/crm33y2jcf/

$\endgroup$
3
  • $\begingroup$ For context, this question was asked in one of the programming contest I was giving few days back. $\endgroup$
    – Vivek
    Jul 13, 2021 at 10:15
  • 1
    $\begingroup$ It is worth working this out for small $a$ and $b$, spotting the multiplication pattern, and then proving by induction $\endgroup$
    – Henry
    Jul 13, 2021 at 10:19
  • $\begingroup$ @Henry If a=$0$ or b = $0$, expected moves will be obviously 0. For $a$ = 1 and $b$ = 1, expected moves will be 1. For $a$=1 and $b$=2, expected moves will be 2. I was not able to calculate for further numbers. $\endgroup$
    – Vivek
    Jul 13, 2021 at 10:25

1 Answer 1

Reset to default
4
$\begingroup$

Hints:

  • Except when $a=0$ or $b=0$, you will have $$E[N_{a,b}]=1+\tfrac12 E[N_{a-1,b+1}]+\tfrac12 E[N_{a+1,b-1}]$$

  • As you have spotted, $$E[N_{a,0}]=E[N_{0,b}]=0$$

  • It is worth working $E[N_{a,b}]$ out for small $a$ and $b$, spotting the multiplication pattern, and then proving by induction

$\endgroup$
8
  • $\begingroup$ Okay, my recurrence relation was wrong. Updated in question. But how will we calculate further states from this relation? For calculating $E[N_{a,b}]$ we need future as well as past state. $\endgroup$
    – Vivek
    Jul 13, 2021 at 10:48
  • $\begingroup$ Is the result $ab$? $\endgroup$
    – Snoop
    Jul 13, 2021 at 10:51
  • 3
    $\begingroup$ It is, though you might want to prove (a) it satisfies the recurrence and (b) nothing else will $\endgroup$
    – Henry
    Jul 13, 2021 at 10:52
  • $\begingroup$ @Snoop No. For reference question link: my.newtonschool.co/playground/code/crm33y2jcf $\endgroup$
    – Vivek
    Jul 13, 2021 at 10:57
  • 2
    $\begingroup$ @VivekMoar In order to calculate the states from the relation, you have to solve a system of linear equations. You have $a+b+1$ variables $E[N_{k,a+b-k}],\;k\in\{0,\ldots,a+b\}$ and $a+b+1$ equations, which are $E[N_{0,a+b}]=0,$ $E[N_{a+b,0}]=0$ and $a+b-1$ equations of the type $-\frac{1}{2} E[N_{a-1,b+1}] + E[N_{a,b}] - \frac{1}{2} E[N_{a+1,b-1}] = 1.$ $\endgroup$
    – Reinhard Meier
    Jul 13, 2021 at 11:27

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.