Printable View
hmm here is my shot ...
starting is n=0 and num of lights on is also 0, both even,
n=1, numLightsOn = 1
n=2, numLightsOn = 0 / 2
n=3, numLightsOn = 1 / 3
n=4, numLightsOn = 0 / 2 / 4
so,
if n is even, number of lightss on is all even numbers less than k and less than n
if n is odd, number of lightss on is all oddnumbers less than k and less than n
so..
numLightsOn = 0+(n%2) , 2+(n%2) , 4+(n%2) ... k+(n%2)
so, how? is it right..?
Ever heard of Pascal pyramid? It looks like this:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
....
C(n,0) C(n,1) C(n,2) ... C(n,n)
First colum and last are always 1. The others are computed this way
a1
a21 a22
a31 a32 a33
a41 a42 a43 a44
a32 = a21 + a22
a42 = a31 + a32 ; a43 = a32 + a33
...
a[i][j] = a[i-1][j-1] + a[i-1][j]
where C(n,k) mean k combination taken from n. (well, I'm not very good at math in english but I hope I'll make it as clear as possible)
if you want to see how you can get the pyramid, compute (x+y)^n. Here ^ means power.
(x + y)^0 = 1
(x + y)^1 = 1*x + 1*y
(x + y)^2 = 1*x^2 + 2*xy + 1*y^2
(x + y)^3 = 1*x^3 + 3*xy^2 + 3*yx^2 + 1*y^3
...
and so on
What does it have to do with our problem? Well, it is the answer. At least almost.
Let me explain. we have k switches, all OFF. That means at the beginning the number of ON switches is 0. After each step you can either have increase the number of ON swtiches with 2 or have it unmodified. In the first phase consist of a turning one switch ON. That only applies to the OFF switches, ON switches are not affected in this phase. In the second phase you can either turn another OFF switch to ON, or toggle and ON switch to OFF, in which case you have returned to a previous configuration (only the number of ON switches counts, not their position in the row).
So, after step 1 you can either have 2 switches ON or none. That is
1:0 1:2
No, we go to the second step (n=2). If after the first step we had 0 ONs, after step 2 we can have either 2 ONs or 0. If after the first step we had 2 ONs, after the second we can have 2 ONs or 4ONs. To summarize:
1:0 2:2 1:4
Getting back to Pascal's pyramid:
step = 0 1:0
step = 1 1:0 1:2
step = 2 1:0 2:2 1:4
step = 3 1:0 3:2 3:4 1:6
step = 4 1:0 4:2 6:4 4:6 1:8
....
step = n C(n,0):0 C(n,1):2 C(n,k')
if k is odd, than k' = k-1
if k is even than k' = k
Note that the fact k is odd or even does not matter. Proof:
k = 5
n = 0
00000
n=1
00000 , 11000
n = 2
00000 , 11000 , 11000 , 11110
n = 3
00000 , 11000, 11000 , 11110 , 11000 , 11110 , 11110
end
11110 from step 2, can only generate 11110, because there is only 1 OFF switch that will be set to ON in phase1. in phase 2 any of the 5 ON switches (position doesn't matter) will be turned OFF.
k = 4
n = 0
0000
n = 1
0000 , 1100
1:0 1:2
n = 2
0000 , 1100 , 1100 , 1111
1:0 2:2 2:4
n = 3
0000 , 1100 , 1100 , 1111 , 1100 , 1111
1:0 3:2 2:4
n = 4
0000 , 1100 , 1100 , 1111 , 1100 , 1111 , 1100 , 1111
1:0 4:2 3:4
If you experiment with k=6, k=8, etc (I told you that the parity is unimportant) you will observe that Pascal's pyramid must be cut after (k+2)/2 colums.
Here is an example for K=6:
1
1 1
1 2 1
1 3 3 1
1 4 6 3
1 5 10 6
I hope you noticed that when the pyramid is cut, the last element is not 1, but is a copy of the upper-left element.
So the answer is that Pascal's Pyramid (sometimes cut) gives the probability.
Cheers! :wave:
read more about Pascal's pyramid
long post hurt brain.
Find a single formula - no summation or Pascal's triangle references (although it can probably be achieved that way - what a great triangle). It also turns out that the formula is independent of whether k is odd or even.
Is that so?Quote:
Originally Posted by Joe Nellis
I'll give it a shot and say that the answer is 63 2/11.
:D
let
- P(i) be the probability that 2*i switches are ON (there can be only even number of ON switches)
- k' be k/2 if k = 2*j (i.e. k even) and (k-1)/2 is k = 2*j+1 (i.e. k odd)
- C(n,i) i combinations of n
P(i) = C(n, i), if n<=k'
P(i) = C(n, i), if n>k' and i<k'
P(i) = C(n-1, i-1), if n>k' and i=k'
Of course you can put it simplier as
P(i) = C(n, i), if i<k'
P(i) = C(n-1, i-1), if i=k'
[QUOTE=cilu]there can be only even number of ON switches[\QUOTE]
???
Bad english? :o Sorry. Or you don't understand why there can only be 0,2,4, etc. switches turned ON? If so, please read my first post. It's obvious. :cool:
k=1, n=3. guarantees one switch on after your "step 1"Quote:
Originally Posted by cilu
Cilu, your method explores possibility instead of probability and if I'm not mistaken, assumes k>>n.
To clarify, the solution is an equation for the expected value (defined as "The weighted average of a probability distribution"), and the assumption that k>n is invalid.
Here's a montecarlo solution to check your answers.
Absolutely not! How did you get that!? :eek: n can take values between [1,k]. n can be as great as k.Quote:
Originally Posted by SolarFlare
And what do you mean with posibility vs. probability? After all, they are the same thing. And yes, I was talking in terms of probability.
If my formula is wrong please prove it. Please don't make assumption just because you didn't read my posts carefully.
Regards. :wave:
Your formula does not conform to the standards I have requested.Quote:
Originally Posted by cilu
It's possible that a helicopter just landed on your roof.Quote:
Originally Posted by cilu
Proof that I have not adequately explained the problem. A random lightswitch is toggled, and this act is repeated n-1 times for a total of n times. I sure hope your house isn't built such that you can only turn on each lightswitch once.Quote:
Originally Posted by cilu
When you say turn on a switch. That means the switch MUST be OFF. An ON switch cannot be turned ON. So, in the first phase of each step, only OFF switches can be turned ON. That's why you can always have only EVEN numbers of ON switches. If we start withQuote:
Someone turns on one of the lightswitches randomly. Then they toggle another lightswitch randomly (if it's the same one as the first one, the light goes off. This process is repeated n times (so that n total toggles are made).
00000
and in Step1, phase 1 turn a switch ON we get
10000
in Step 2, phase 1 (n=1), we toggle a switch. Than can only lead either to
00000 or to 11000
(position is not important 11000 is the same with 10001).
If in the first step, we got 11000, in step 2 (n=2), phase 1, we can only select one of the three OFF switches. So it can lead us to either
11110 or 11000
+
00000 or 11000 from configuration 00000 at the end of step 1.
NOW I SEE THAT I MISUNDERSTOOD THE PROBLEM. Well, SolarFlare, next time please be less ambiguous. :DQuote:
Proof that I have not adequately explained the problem. A random lightswitch is toggled, and this act is repeated n-1 times for a total of n times. I sure hope your house isn't built such that you can only turn on each lightswitch once.
NEW ANSWER will come soon.
PS: I have a new pyramid, but I'm looking for the formula.
1
0 1
1 0 1
0 2 0 1
2 0 3 0 1
0 5 0 4 0 1
5 0 9 0 5 0 1
...
I give up. :( There were too many exceptions thrown in my brain, I can't handle them anymore. :D