1
$\begingroup$

I recently run into a question that asked me to find a number $n$ if for $k$ times, $n$ has been halved and subtracted $0.5$ and, at the end, $n$ becomes $0$. I don't know if this is of any relevance but the question was about people in a bus and in every stop, half of the people plus half a person would leave the bus until the bus is empty.

Given $k$, the answer was just $2^{k-1}$, I don't quite understand how to get there, the only thing I got was:

$$\left(\sum_{i=1}^{k}\frac{n+1-2^{i-1}}{i^2}\right)+\frac{k}{2}=n$$

I would appreciate any help.

P.D.: I'm positive this is very basic to almost all of you, but I'm trying to get started in the mathematical world as I've found it to be extremely interesting.

$\endgroup$
0

3 Answers 3

Reset to default
8
$\begingroup$

If we count an extra person to the people in the bus, who never gets off (say, the bus driver), then we observe that exactly half of the people get off. Then it should be clearer that - including the bus driver - the numbers are always powers of two.

$\endgroup$
3
  • $\begingroup$ Great answer I think! Note that if $u_n$ is the number at step $n$, we have $u_{n+1}=\frac{u_n}{2}-\frac{1}{2}$ and we look for $u_0$ knowing that $u_k=0$. To find a closed form for $u_n$, the usual method is to consider the fixed point $a$ of $f(x)=\frac{x}{2}-\frac{1}{2}$, and show that $v_n=u_n$ is geometric. Here, $a=-1$, so adding the driver is a very nice illustration of the general method! $\endgroup$
    – Taladris
    May 12, 2014 at 15:44
  • $\begingroup$ Very nice observation, really. Thanks for the answer! @Taladris thanks for the explanation! $\endgroup$
    – probablynotfranco
    May 12, 2014 at 15:58
  • $\begingroup$ I cannot edit my comment. $v_n$ should be defined as $v_n=u_n-a$. $\endgroup$
    – Taladris
    May 12, 2014 at 16:04
0
$\begingroup$

We will find a recurrence relation to solve the problem.

$n(k)/2 -0.5=n(k-1)$,

So,$n(k)=2n(k-1)+1$ and $n(1)=1$

Solving, we get $n(k)=2^k-1$

$\endgroup$
1
  • $\begingroup$ Nice solution, thank you very much. If we take the number of people we start with for k iterations, halve it and substract one, we are left with the number of people with start for k-1 iterations. $\endgroup$
    – probablynotfranco
    May 12, 2014 at 16:11
0
$\begingroup$

For $k=1$, you just work backwards. Let the number of people for $k$ operations be $p(k)$. For $p(1)$, we are told $\frac 12p(1)-\frac 12=0$ and discover that $p(1)=1$ Now we use induction. I claim that for $k$ operations we start with $2^k-1$ people. I have shown it is true for $k=1$ Now assume it is true for $k$, that we start with $2^k-1$ people. Then $\frac 12p(k+1)-\frac 12=2^k-1$ and we can solve it to find $p(k+1)=2^{k+1}-1$

$\endgroup$
2
  • $\begingroup$ Thanks for the answer. I have a doubt as to how did you come up with 2^k-1. Did you choose it because you see it works for 2^1-1 = 1? $\endgroup$
    – probablynotfranco
    May 12, 2014 at 16:00
  • $\begingroup$ I've seen this one. To find $2^k-1$ initially, I would calculate for the first few $k$'s. Getting $1,3,7,15$ (and probably not waiting for the $15$) would convince me to try an prove it. I would then prove it this way. $\endgroup$
    – Ross Millikan
    May 12, 2014 at 21:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .