Instead of looking at strings themselves, I'd look at the lengths of the runs and the first value of the string. Since it's binary, you know that it's just switching back and forth between 0 and 1.

I think that in this situation it is easier to count the valid strings instead of trying to count the invalid strings.

Is this possible to do with just a CFG and no special rules?

An example of a CFG is this, u always start with S and use rules ...
So this CFG below accepts the string abcc and it also accepts the string abcccc. to get abcccc you have A go to a A and that A goes to empty, B goes to b B and that B goes to empty, C goes to cc C and that C goes to cc C and that C goes to empty

S -> ABC
A -> a A | empty
B -> b B | empty
C -> cc C | empty

LONG POST, CLIFFNOTES AT END

has anybody heard about and directly solved the "alien extinction problem"? it's one of those typical "the setup is everything" kinda riddles and i got to the correct setup, but then couldn't solve the stupid equation that i ended up with.

i looked EVERYWHERE to get a step by step explanation of how to get to the roots and none of the sites i found would give me one for free (one site would but i had to pay for it, which is stupid). they just gave me a million different ways to EXPRESS the problem, which didn't help.

so the problem, if you haven't heard it, is that there's 1 alien. every day, one of 4 equally likely things happen. either a) he dies, b) nothing happens and there's still 1 alien, c) he duplicates himself, so there's 2 aliens, or d) he triples himself and there's 3 aliens.

so the question is, what is the probability that the alien race dies out starting from that one alien?

the setup is pretty standard where we get P(alien dies out) = 1/4*the events in terms of P (i started out with P(alien doesn't die out) but that proved to be clunky so i switched it to P(alien dies out)). so the first event is just a 1 (100% aliens die out. 2nd event is just P (probability that aliens die out since nothing changed). 3rd event is P^2 (first alien has to die out and second alien has to die out). 4th event is P^3 (now 1 and 2 and 3 all have to die out).

so we get P = 25%*(1+P+P^2+P^3). now i tried rearranging this into a bunch of different ways to try to get something like 0 = some stuff to see the roots, and i couldn't do it (after much trying i gave up and found looked up the answers/roots and STILL COULDN'T figure out how to get from this equation to the roots).

here's what i did initially:

if we do it out we get P = .25 + .25P+.25P^2+.25P^3

we can subtract P and get: 0=.25-.75P+.25P^2+.25P^3

i then tried to figure out a way to get the 3 P terms into one of those foiling situations (a+b)(c+d) etc. i first divided by .25 to clear everything up and i got:

0 = 1-3P+P^2+P^3, which setup better is P^3+P^2-3P+1=0. and i still couldn't get this into a foiling situation so i tried to get a subset into a foiling situation (P^2-3P+1).

(P-3P)(P+0): P^2+ P-3p^2+0. then i tried:

(P^2-3P)(1+0): P^2+0-3P+0 = P^2-3P, which is close but we're missing the one.

0= P^2-3P would give us P=3, but that's only for one set of the equation (we still have P^3 to deal with and the other powers of P lol), and it would mess up the equation above without the 1.

so back to P^3+P^2-3P+1=0, and i'm out of ideas. i tried then just substituting a few numbers, starting with 1 ofc and 1 worked lol. i tried a few others but none satisfied the equation, nor gave me a logical pattern as to where to look if i didn't know the answer.

1+1-3+1=0. so we know 1 is a root, but that's not the solution (b/c i know the answer is 41.4% or Sqrt(2)-1, but also b/c we should know that it's not possible that the alien dies EVERY time in a situation where he triples himself 1/4 of the time, doubles himself 1/4 of the time and stays himself 1/4 of the time). and the answer has to be a clean kind of expression to get Sqrt(2)-1 as the correct root.

out of desperation i then tried newton's root finding method. that is:

xn+1 = xn+f(xn)/f'(xn)

i started with 0.5 and it just got bigger (i got for xn=0.5, xn+1=0.6), so i tried 2 and it got bigger again (xn=2, xn+1=2.5833333). so i gave up (i'd thought that newtons method gets you closer to the root each time but these two didn't get me closer to what i knew was the answer (.414), so i was either doing something wrong and was too tired/stupid to figure out what, or that method doesn't work here, either way at that point i just gave up).

i thought maybe i'd sleep on it for a bit, but that didn't work, so here you go lol. how do i get the answer to this problem??

CLIFFNOTES:

Since you have already identified one root of your equation, p=1, factoring the rest of it is pretty simple. You can just do some expanding of your equation so that you can factor out a (p-1)

start with:
p^3 + P^2 - 3p + 1 = 0
Then you can add and substract to get
p^3 - p^2 + 2p^2 - 2p - p + 1 = 0
Group this as
(p^3 - p^2) + (2p^2 - 2p) - (p + 1) = 0
So then you have
p^2(p-1) + 2p(p-1) - 1(p-1) = 0
(p-1)(p^2 + 2p - 1) = 0

From there finding the other 2 roots (sqrt(2)-1 and -1-sqrt(2)) is pretty trivial. Clearly the answer isn't the 3rd root since the extinction probability must live between 0 and 1. The longterm extinction probability is going to be 1 if the expected number of aliens tomorrow is fewer than the expected number of aliens today, but the expected number of aliens in the next period is 3/2 so the long-run extinction probability cannot be 1 (if you had some other distribution where the alien died more and tripled less, it could easily be 1). This eliminates 2 of our roots and we are left with sqrt(2)-1 which you already identified as the long run extinction probability.

Completely lost on how to do this question, have tried various strategies, but I'm not arriving at the answer.

You're trying to decide whether to buy an energy-efficient, 225 -W refrigerator for $1150 or a standard, 425 -W model for $850. The standard model will run 20% of the time, but better insulation means the energy-efficient model will run 11% of the time.

If electricity costs 9.5cent/kW⋅h, how long would you have to own the energy-efficient model to make up the difference in cost?

This can be thought of as two y=mx+b equations that you find the intersection of.

With these equations:
y = total cost
x = hours owned (plugged in)
m = the running cost per hour
b = the base cost



For the standard model:



For the energy efficient model:



Set them equal to each other, solve for x, and that is the number of hours.

The answer I come up with is approximately

You're correct. I didn't think about it this way since it's a physics course, so I tried doing it in other 'ways'.

Thank you.

Physics is all about understanding the problem and equation setup. You'll need to use all kinds of things you've learned over the years in various math classes in order to be successful in Physics.

Slow pony, but I randomly came across this today:

https://www.youtube.com/watch?v=A5-Q2GdD5xw

thanks reno, sorry it's taken me a bit to get back to this. i do still have a few questions.

first, how did you complete this first step:

i.e. what did you add/subtract here to both sides?

from there:
this made sense.

HOWEVER, what would i do if i hadn't known one of the roots was 1, i.e. so i wouldn't be able to knowingly factor out (p-1)? that was one of my main goals in asking this: how to find these roots without knowing any of them?

did you try the newton's method? i'm surprised that got farther away from .414 each time i tried it (though there is a larger root, so i can't really say it's necessarily not going there, but it didn't seem to from the first iteration using 2 x0s).

thanks again!

In general, there is no easy way to factor a polynomial. But sometimes, you get lucky.

https://en.wikipedia.org/wiki/Rational_root_theorem

then how was this given as an "interview question" lol? i mean, they can't expect one to factor polynomial roots left and right i'd assume? maybe that's a bad assumption, but i think once you get to the setup of the problem, that should theoretically be the hard part (and i was quite pleased i got that part completely right only to be foiled, no pun, by the general solution)

There's a whole range of interview questions that have been thrown at people. Factoring a polynomial is one of the easier things that might have been thrown at you.

The goal of the interviewer may not be the same as the goal of the interviewee. You think the goal is to get the answer. They are probably less interested in that.

Figuring out that 1 is a solution isn't impossible or unreasonable. It's a monic polynomial whose constant term is 1. You can literally figure out in a couple seconds whether or not 1 or -1 is a root by just evaluating it for p=1 and p=-1 to see if you get a zero.

I was just looking to factor out the given root. I knew that (p-1) was a factor of p^3 + p^2 - 3p + 1 because you pointed that out, so I knew it would work to block this as a bunch of things times (p-1) so I could factor it out to (p-1) times some quadratic polynomial.

I just started with the p^3. In order to factor out (p-1) I needed (p^3 - p^2) so I subtracted p^2 which meant I then had to add it also so now I've got p^3 - p^2 + 2p^2 - 3p + 1. Then I needed to split the 3p into -2p and -p and then I was done.

If I didn't know that a root was 1 I'd probably guess and check because in these recursive survival problems x=1 is almost always a root. I don't have a good answer beyond that.

Newton's method works fine, you just have it wrong. It is xn+1 = xn-f(xn)/f'(xn). You were using xn+1 = xn+f(xn)/f'(xn) so the fact that it went the wrong way isn't too surprising. Once you correct that mistake, it will converge to the 3 roots of this problem depending on where you seed the starting value

true re: interview problems. ones i've had in the past were much more interested in the logical thinking behind it and if you understood the explanation once given and could implement similar thinking.

ty for correcting newton's method. i had to be doing something wrong there. highly unlikely a tried and true method was giving incorrect answers. now it seems both of my original seeds would have headed towards .414 and 1 respectively.

also true re: trying the obvious roots (0, -1, 1, -2, 2 etc.).

man this was a tricky brain teaser for sure.

You probably know that you can also do "long division" to help factor a polynomial if you already know one root.

Here you can simply "long divide" p-1 into p^3+p^2-3p+1 to get p^2+2p-1.

I think you completely missed the point.

Having a hard time coming up with an answer to this:

"Masses m and 3m approach at the same speed v and collide head-on. Find the final speed of mass 3m, while mass m rebounds at speed 2v."

So I know it's an elastic collision, but I'm unsure of which equation to use/how to approach it. Thank you.

This phrase tells you that momentum and energy are both conserved. You should start by writing down the equations that correspond to the before/after momentum and set them equal to each other, and then write down the equations that correspond to the before/after energy and set those equal to each other.

Then do algebra.

So is it:

1/2m1v1i^2 + 1/2m2v2i^2 = 1/2m1v1f^2 + 1/2m2v2f^2

That's one of them. Do you know which one it is and where it came from? (And don't say "it came from the book." That you would write this formula with this notation makes it feel very much like you just grabbed a formula from the right section of the book, but you really aren't sure what it's saying.)

It's not that I just got it from the book, I know it's the equation for elastic collisions (conserved momentum and KE).

I used it before, however, I wasn't arriving at the answer...

Ah got it, it was 0. I really over think these problems.

No. That's not what that equation says at all. You're going to step in it deep in this class if you keep playing the equation-hunter game.

The equation presented is merely the conservation of energy equation. The initial energy (which consists of the energy of two moving objects) is equal to the final energy (which consists of the energy of two moving objects).

You're right, honestly I haven't taken physics in 4 years so it's a bit hard getting my head around everything (only reason I'm taking it is because I need it as a pre-req for professional school).

Anyways, why is it that when I just used the conservation of energy equation, I arrived at the correct answer?