Prev: The Tuesday boy problem.
Next: Godels theorem ends in paradox-simple proof
From: Larry on 26 May 2010 19:02
Assume that we have n unfilled slots which are named 0, 1, 2, ...,
n-1.

We go through a series of rounds to fill the slots. On round 0, we
fill the first empty slot (0), skip the next empty slot (1), fill the
next empty slot (2) and so on until the end of list.

On round 1, we fill the first empty slot (1), skip the next empty slot
(3), fill the next empty slot (5) and so on until the end of the list.

I am looking to prove that for any round c (starting from round 0),
the first empty slot is (2^c)-1.

For round 0, the first empty slot was (2^0)-1= 0. For round 1, the
first empty slot was (2^1)-1 = 1 and so on.

For some reason, proving what appears to be a simple proof is harder
than I realized. Any help or corrections is greatly appreciated! :-)

-Larry
From: Gerry Myerson on 26 May 2010 19:06
In article
<feba3128-3217-4fed-8f25-a09bd91f03fe(a)11g2000prv.googlegroups.com>,
Larry <larry.freeman(a)gmail.com> wrote:

> Assume that we have n unfilled slots which are named 0, 1, 2, ..., n

So, one of the slots has two names?

> Any help or corrections is greatly appreciated! :-)

Glad to oblige.

--
Gerry Myerson (gerry(a)maths.mq.edi.ai) (i -> u for email)
From: Larry on 26 May 2010 19:22
Hi Gerry,

Absolutely correct. I realized my mistake after I hit "send". I
tried to reedit but instead sent out a correction just after it.

Cheers,

-Larry

On May 26, 4:06 pm, Gerry Myerson <ge...(a)maths.mq.edi.ai.i2u4email>
wrote:
> In article
> <feba3128-3217-4fed-8f25-a09bd91f0...(a)11g2000prv.googlegroups.com>,
>
>  Larry <larry.free...(a)gmail.com> wrote:
> > Assume that we have n unfilled slots which are named 0, 1, 2, ..., n
>
> So, one of the slots has two names?
>
> >  Any help or corrections is greatly appreciated!  :-)
>
> Glad to oblige.
>
> --
> Gerry Myerson (ge...(a)maths.mq.edi.ai) (i -> u for email)

From: Peter Webb on 26 May 2010 19:22

"Larry" <larry.freeman(a)gmail.com> wrote in message
news:6a089cb4-7b51-4128-a679-014b48c6e624(a)s4g2000prh.googlegroups.com...
> Assume that we have n unfilled slots which are named 0, 1, 2, ...,
> n-1.
>
> We go through a series of rounds to fill the slots. On round 0, we
> fill the first empty slot (0), skip the next empty slot (1), fill the
> next empty slot (2) and so on until the end of list.
>
> On round 1, we fill the first empty slot (1), skip the next empty slot
> (3), fill the next empty slot (5) and so on until the end of the list.
>
> I am looking to prove that for any round c (starting from round 0),
> the first empty slot is (2^c)-1.
>
> For round 0, the first empty slot was (2^0)-1= 0. For round 1, the
> first empty slot was (2^1)-1 = 1 and so on.
>
> For some reason, proving what appears to be a simple proof is harder
> than I realized. Any help or corrections is greatly appreciated! :-)
>
> -Larry

Proof by induction.

Assume that step n we have 2^(n-1)-1 filled slots, an empty slot, 2^(n-1)-1
filled slots, an empty slot, and then the pattern repeats.

Fill in every second empty slot in the manner described above.

You will get the same pattern but with (2^n) - 1 filled slots, then an empty
slot, etc.

Now show its true for n=1 and you are finished.






From: Bastian Erdnuess on 26 May 2010 19:29
Larry wrote:

> Assume that we have n unfilled slots which are named 0, 1, 2, ...,
> n-1.
>
> We go through a series of rounds to fill the slots. On round 0, we
> fill the first empty slot (0), skip the next empty slot (1), fill the
> next empty slot (2) and so on until the end of list.
>
> On round 1, we fill the first empty slot (1), skip the next empty slot
> (3), fill the next empty slot (5) and so on until the end of the list.
>
> I am looking to prove that for any round c (starting from round 0),
> the first empty slot is (2^c)-1.
>
> For round 0, the first empty slot was (2^0)-1= 0. For round 1, the
> first empty slot was (2^1)-1 = 1 and so on.
>
> For some reason, proving what appears to be a simple proof is harder
> than I realized. Any help or corrections is greatly appreciated! :-)
>
> -Larry

Show indctively that before the k-th round the filled/unfilled-pattern of
the slots is 2^k-periodic where only the last slot of each period is
unfilled.

Cheers,
Bastian
 |  Next  |  Last
Pages: 1 2
Prev: The Tuesday boy problem.
Next: Godels theorem ends in paradox-simple proof