Yes, inquriing minds would like to see the answer to this.
Printable View
Yes, inquriing minds would like to see the answer to this.
Do you mean "n number of switches are toggled" ? You could toggle the same switch a trillion times. :eek:Quote:
Originally Posted by SolarFlare
Yeah. Well, I'll try to solve this now, two ways.Quote:
Originally Posted by Sahir
Method 1
I am looking for L(n,k), the number of lights on after n toggles of k switches. I will treat k as a constant, since it doesn't change once it has been selected, so I may use the notation L_n to mean L(n,k).
Suppose we know L_n. It is fairly simple to find the expected value L_(n+1) recursively:
L_(n+1) = L_n + (probability next lightswitch is turned on) - (probability next lightswitch is turned off) = L_n + p_on - p_off.
Well, p_on and p_off depend on the number of lights that are currently on (L) and the number of total lights (k):
p_off = L_n/k
p_on = (k-L_n)/k
So L_(n+1) = L_n + (k-L)/k - L/k = L_n + (k-2L_n)/k = (k+L_n*(k-2))/k.
Also it should be clear intuitively that L_0 = 0 (no lights are on at the beginning), and L_1 = 1 (you will always have one light on after one toggle), establishing a base case and completing the recursive formula.
That only helps a little, since the solution is supposed to be in closed form. So I have to escape recursion somehow. This is a little tricky. Consider what a graph of L vs n would look like. It would start off at 0, climb rapidly at first and then slow down, until it approached approximately k/2, because for n>>k, about half of the lights should be on. This sounds a lot like what an exponential graph does, so perhaps our formula can be modeled by an exponential formula.
Let L_n = k/2-b^n for some b.
Now k/2 - b^(n+1) = L_(n+1) = (k+L_n*(k-2))/k = (k+(k/2 - b^n)*(k-2))/k
k^2/2 - kb^(n+1) = k+(k/2 - b^n)*(k-2)
k^2/2 - kb^(n+1) = k + k^2/2 - k - kb^n +2b^n
- kb^(n+1) = - kb^n +2b^n
kb = k-2
b = (k-2)/k
Thus we have L_n = k/2 - ((k-2)/k)^n satisfying the recursion.
But does it satisfy the base case as well? L_0 = k/2 - ((k-2)/k)^0 = k/2 - 1 != 0 and we can see that it does not. So, let's tweak the proposed formula a little to see if that helps.
Let L_n = k/2-a*b^n for some a, b.
The 'a's fall out leaving the same solution for b, so L_n = k/2 - a((k-2)/k)^n.
Solving for a using the known base case (L_0=0), 0 = L_0 = k/2 - a((k-2)/k)^0 = k/2 - a, so a=k/2.
Putting it all together gives L_n = k/2 - k/2((k-2)/k)^n = k/2 * [ 1 - ((k-2)/k)^n ] as the final solution, which satisfies both the recursion and the base case.
Method 2
Suppose k=2. Once one of the switches is turned on, the expected value is always 1, since there is an equal chance of a light being turned off as it is being turned on. Using this fact, we can group pairs of lights for other values of k.
Now suppose k is arbitrary, as per the guidelines of the question. Consider the first two lightbulbs. The probability that neither has been turned on after n toggles is ((k-2)/k)^n. So the probability that at least one has turned on (giving the pair an expected value of 1) is 1 - ((k-2)/k)^n.
In exactly half these circumstances, the first lightbulb is on. This means the expected value for the first bulb is (1 - ((k-2)/k)^n)/2.
Since the first bulb is symmetric with all other bulbs, the expected value for all the bulbs is the sum of each bulb's expected value, or L = E_total = sum(E_i) = k*E_i = k*(1 - ((k-2)/k)^n)/2 = k/2 * (1 - ((k-2)/k)^n), as above.
==========
Notice that the solutions are radically different in both length, method, and the number of assumptions it asks you to believe.
Suppose k = 2 and n = 2 let the switches be s1, s2Quote:
Originally Posted by SolarFlare
if you toggle s1 twice you have 0 lights on
if you toggle s1 and s2 once each you have 2 lights on
If this is a challenge to my solution, then perhaps the meaning of Expected Value has been misunderstood.Quote:
Originally Posted by Sahir
In the instance of k=n=2, there is a 1/2 chance that no lights will be on and a 1/2 chance that both lights will be on, so E = (1/2)*(0) + (1/2)*(2) = 1.
hhmm...... okay i think that was is far over my head. I know It is not my turn but
I would like to ask a question any way. I prolly won't be here long enough for
the points to matter.
It has been a while since i read this last, and the wording may be a little off. ICode:Gertrude entered a Boeing 707 (I don't know if this is a real plane or not, it
doesn'tmatter either way.) which seated 300 people, it is full. No one saw
Gertrude get on. Gertrude exited the plane. No one saw Gertrude exit the plane.
Gertrude killed 300 people. How did she do it?
Note: You do NOT need any knowledge about jet liners aside from what you
would learn by 6th grade. Or anything else for that matter. A logic problem not a
technical problem.
hope it is close enough that some one could answer it.
Gertrude is a rocket!
Qaueda operative with a parachute?Quote:
Originally Posted by Sravoff
Either that or it's an odorless and colorless gas of some sort that knocked out the pilot.
How about everybody ;)Quote:
Originally Posted by YourSurrogateGod
/Hypoxia
The thing with the gas is not stupid. Maybe the gas or fuelt vault is called Gertrude. Or she is a Re'Tu
It was either that or a huge flame wreck :) . At the very least the pilot would have to go :) .Quote:
Originally Posted by Mick
[edit]
I take it that it was CO?
/ahh... carbon monoxide... wait a sec!
Loss of cabin pressure.Quote:
Originally Posted by YourSurrogateGod
Gertrude is a goose that flew through the jet engine.
Goose is to jet engine as apple pie is to ............ ?
Gertrude is some kind of ariborne virus ?