Prev: The Tuesday boy problem.
Next: Godels theorem ends in paradox-simple proof
From: Larry on 26 May 2010 23:59
On May 26, 4:22 pm, "Peter Webb"
<webbfam...(a)DIESPAMDIEoptusnet.com.au> wrote:
> "Larry" <larry.free...(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.

Thanks, Peter. That really helps.

-Larry
From: Larry on 27 May 2010 00:00
On May 26, 4:29 pm, Bastian Erdnuess <earth...(a)web.de> wrote:
> 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

Thanks, Bastian!

-Larry
From: Maarten Bergvelt on 27 May 2010 10:05
On 2010-05-26, Larry <larry.freeman(a)gmail.com> wrote:
> Assume that we have n unfilled slots which are named 0, 1, 2, ..., n

Very funny!


--
Maarten Bergvelt
From: hagman on 27 May 2010 10:36
On 27 Mai, 06:00, Larry <larry.free...(a)gmail.com> wrote:
> On May 26, 4:29 pm, Bastian Erdnuess <earth...(a)web.de> wrote:
>
>
>
> > 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
>
> Thanks, Bastian!
>
> -Larry

You would have saved you some trouble anyway if you had started with
one slot for every natural number (not including 0!).
a) no laughs for your off-by-one-error
b) statement true for all c>=0, not only 0 <= c < ld n
c) simpler statement simpler proof: After c >= 0 rounds, the
remaining slots are exactly the multiples of 2^c

-hagman
First  |  Prev  | 
Pages: 1 2
Prev: The Tuesday boy problem.
Next: Godels theorem ends in paradox-simple proof