Help with Search
 
 
Picture of Peter Ryan
Kings Switches Pow
by Peter Ryan - Sunday, January 6, 2008, 06:44 PM
 
If anyone needs any help with the PoW, I will probably be on AIM until around 10 tonight, but I may not be able to help that much. Spedlyf is my AIM.
Picture of Doug McG
Re: Kings Switches Pow
by Doug McG - Sunday, January 6, 2008, 10:56 PM
 
Thanks for offering to help folks, Peter. We did do a fair amount of work on the POW in class on Friday. I'm going to try to summarize some of what we did.

First, I posted a table of values for the number of moves needed. In this table an stands for the number of moves needed with n switches:

n
an
1
1
2
2
3
5
4
10
5
21
6
42
7
85
8
170

Next, I gave the hint that there are two rules for this table - one for when n is odd and a different one for when n is even.

We noticed that you can state these rules as:
When n is odd an+1 = 2an
When n is even an+1 = 2an+1

I mentioned that these are recursive rules and what you are really looking for are non-recursive rules that will tell you an just as a function of n, without having to know any previous value.

The final hint I gave was the these non-recursive rules can be written as:
Big hint

Skip Navigation

Navigation