# The Grey Labyrinth is a collection of puzzles, riddles, mind games, paradoxes and other intellectually challenging diversions. Related topics: puzzle games, logic puzzles, lateral thinking puzzles, philosophy, mind benders, brain teasers, word problems, conundrums, 3d puzzles, spatial reasoning, intelligence tests, mathematical diversions, paradoxes, physics problems, reasoning, math, science.

 math 201 Goto page Previous  1, 2
Author Message
mikegoo
Daedalian Member

 Posted: Sun Mar 09, 2003 10:40 pm    Post subject: 41 Since some smarter folks than myself might look at this here. Regarding Newton-Raphson Method (or just Newton's Method) for approximating zeros of a function: Xn+1 = Xn - f(Xn)/ f'(Xn) (too incompetent to get subscripts) Does anyone have any insights into the convergence or divergence of the resulting series. I've been doing a bit of reading and have found very little...other than a couple of things that involve knowing the value of the zero (seems rather silly to me) or a test for convergence where failure does not mean divergence. Any help would be appreciated.
mith
Pitbull of Truth

 Posted: Sun Mar 09, 2003 10:55 pm    Post subject: 42 Regarding the injection thing (we call it 1-1), yeah, if I remember correctly, you can only prove that with the AoC or an equivalent (we used Well Ordering, I think). If you have that, you can basically just do what CB said.
Bicho the Inhaler
Daedalian Member

 Posted: Mon Mar 10, 2003 12:52 am    Post subject: 43 mikegoo - From Rudin, Principles of Mathematical Analysis, 3rd ed. (p. 118): "Suppose f is twice differentiable on [a, b], f(a) < 0, f(b) > 0, f'(x) >= d > 0 (for some positive constant d), and 0 <= f''(x) <= M (for some positive constant M) for all x in [a, b]. Let x be the unique point in (a, b) at which f(x) = 0. ... Choose x_1 in (x, b) and define {x_n} by ... x_(n+1) = x_n - f(x_n)/f'(x_n). ... x_(n+1) < x_n and lim(as n -> infinity)x_n = x." In other words, the sequence is guaranteed to converge to the zero of f if your initial guess x_1 falls in an interval [a, b] containing x on which f satisfies those properties. By symmetry, of course, it doesn't matter if your initial guess is greater than or less than the actual root. It doesn't involve knowing exactly where the zero is, but your initial guess has to conform to a certain standard. I've never heard of a test for divergence; maybe someone else has.
extropalopakettle
No offense, but....

 Posted: Mon Mar 10, 2003 1:57 am    Post subject: 44 quote:Regarding Newton-Raphson Method (or just Newton's Method) for approximating zeros of a function: Xn+1 = Xn - f(Xn)/ f'(Xn) (too incompetent to get subscripts) Does anyone have any insights into the convergence or divergence of the resulting series. Not sure what you're looking for, but I do know this much: it's chaotic. Years ago I wrote some programs to plot which of multiple zeroes different starting points (X0) led to (using complex numbers). If there are three zeroes, let's say, you color the complex plain three colors, each point colored to indicate which of the three zeroes the Newton-Raphson method ends up at with that as a starting point. The borders between the colored regions are "infinitely complex" - you can magnify them and get more and more detail. A quich Yahoo search on "Newton-Raphson fractals" will get you lot's of pictures on what I'm talking about (as well as better explanations, I'm sure).
extropalopakettle
No offense, but....

 Posted: Mon Mar 10, 2003 3:29 am    Post subject: 45 Here's a really cool animation, from this page, graphing the results of Newton-Raphson for a 3-zeroed polynomial, as the zeroes move along a continuous curve (i.e. each frame of the animation is for a slightly different polynomial).
CrystyB
Misunderstood Guy

 Posted: Mon Mar 10, 2003 5:32 am    Post subject: 46 i might be a bit thick, but where does the second dimension come from??
extropalopakettle
No offense, but....

 Posted: Mon Mar 10, 2003 2:12 pm    Post subject: 47 Complex numbers - the real an imaginary component. You have an orthogonal real and imaginary axis, and each point on the plane maps to a unique complex number. For each point, use it as the starting value in Newton-Raphson (with a polynomial with known zeroes), and iterate until you reach one of the zeroes. Color the original point according to which zero you end up at (maybe also shade it according to how many iterations it took). Then for the animations, each frame is for a different polynomial, where the polynomials are generated by first picking some points at which they'll evaluate to zero, and moving these along some continuous path for the different polynomials for the different frames.
CrystyB
Misunderstood Guy

 Posted: Tue Mar 11, 2003 5:46 am    Post subject: 48 so the polynom used in this particular case is thought to be C->C?... Bah, i guess i never really had to decompose polynoms which have complex roots!
extropalopakettle
No offense, but....

 Posted: Tue Mar 11, 2003 5:54 am    Post subject: 49 Still, I think for a polynomials in the strictly real domain, you'll still get fractals, though 1-dimensional. Say the polynomial has three zeroes. Color the real line three colors according to which zero each point on the line leads to with Newton-Raphson. I think the boundaries between different colored regions of the line won't be sharp, but will have infinitely many infinitely small alternating segments of different colors. I think.
mikegoo
Daedalian Member

 Posted: Fri Mar 14, 2003 3:51 am    Post subject: 50 Thanks...I completely forgot that there is no such thing as a divergence test for N-R.... I knew there was a reason I didn't like this the last time I looked at it... yet even this makes no sense since I looked into the fractals resulting from this... my brain just isn't what it used to be.
borschevsky
Chessnut

 Posted: Fri Mar 14, 2003 3:59 pm    Post subject: 51 quote:Define the sequence a(n) as a(1) = 1 a(n + 1) = 4*a(n) + 1 for finite positive integers n. (No problems here because surreal addition and multiplication are easy.) Let L be the set { a(n)*4^-n such that n is a finite positive integer } and let R be the set { (a(n) + 1)*4^-n such that n is a finite positive integer }. {L | R} is a valid surreal number and has all of the properties we associate with 1/3. Yeah, that does look like an easier way to do it. Any sequences that go to 1/3 from below and above should work, though, right? We could use my L & R and throw out all the elements that aren't "close" to 1/3, or we could use your sequences and throw out the first 1000 elements, or all the even-numbered elements, etc. How are other numbers (sqrt(2), pi, e) defined? I think the definition I was using should work for any number; just use that number instead of 1/3 in the definition.
mith
Pitbull of Truth

 Posted: Fri Mar 14, 2003 6:56 pm    Post subject: 52 For pi you could use: L={(4-4/3) , (4-4/3+4/5-4/7) , (4-4/3+4/5-4/7+4/9-4/11) , ...} R={4 , (4-4/3+4/5) , (4-4/3+4/5-4/7+4/9) , ...}
CrystyB
Misunderstood Guy

 Posted: Sun Jun 01, 2003 1:28 am    Post subject: 53 Solve     x ( yz ) = ( xy )z,     where x,y,zÎN*, i.e. integers ³1. [This message has been edited by CrystyB (edited 05-31-2003 09:31 PM).]
Lucky Wizard
Daedalian Member

 Posted: Sun Jun 01, 2003 4:47 am    Post subject: 54 By one of the laws of exponents, (xy)z = xyz. Hence, xyz = x(yz). Taking the logarithm in base x of both sides gives yz=yz. I can't prove it, but the only natural numbers for which this could be true are z=1 (in which case y could be any natural number) and z=2 (in which case y could only be 2). So these are both solutions: x=anything; y=anything; z=1 x=anything; y=2; z=2
CrystyB
Misunderstood Guy

 Posted: Mon Jun 02, 2003 3:22 am    Post subject: 55 grade: C (let's not forget this is 201...) You can take the log only if the base is <> 1. That's why you missed a whole class of solutions: 1/anything/anything. And proving z=yz-1 for z>1 => y=z=2 is easy, either by induction or by noticing one is linear and the other exponential... [This message has been edited by CrystyB (edited 06-01-2003 11:23 PM).]
Bicho the Inhaler
Daedalian Member

 Posted: Tue Jun 24, 2003 7:06 am    Post subject: 56 x^(y^z) = (x^y)^z is equivalent to x^(y^z) = x^(yz) Because everything is positive, take the natural log of both sides without losing any information: (y^z)log x = (yz)log x This would be true if log x = 0, i.e., if x = 1. This is one class of solutions ({(1, y, z) for any legal y, z}). If log x <> 0, divide by it to get: y^z = yz y^(z - 1) = z. Note that this will be satisfied if z = 1. This is another class of solutions. Now suppose z > 1, so z - 1 > 0. In this case we can take the (z - 1)-th root of both sides, so now we have y = z^(1/(z - 1)). Let the function f be defined with domain N* and co-domain reals by f(z) := z^(1/(z - 1)). First, note that f(2) = 2, which is another solution to the equation. Shortly, we'll prove that there are no more solutions. Second, suppose f(z) = 1. Then we take the natural logarithm to get: 0 = log(z)/(z - 1) (remembering that z - 1 > 0). But now we must have log(z) = 0, implying z = 1, which is definitely not true. Therefore f never attains 1 on our domain. Third, we prove that f is strictly decreasing on our domain. All we really need to show is that f(a) > f(a + 1) for all integers a >= 2. f(a) = a^(1/(a - 1)) f(a + 1) = (a + 1)^(1/a) Note that (f(a)/(f(a + 1))^((a)(a - 1)) > 1 iff f(a)/f(a + 1) > 1 iff f(a) > f(a + 1). (f(a)/f(a + 1))^((a)(a - 1)) = a^a/(a + 1)^(a - 1) = (a + 1)a^a/(a + 1)^a. Let's look at (a + 1)^a. By the binomial theorem we expand this to a^a + (a)*a^(a - 1) + (1/2)(a)(a - 1)*a^(a - 2) + ... + (1/a!)(a!)*a^(a - a) < a^a + (a)*a^(a - 1) + (1/2)(a)(a)*a^(a - 2) + ... + (1/a!)(a)^a (here, all we did was note that if for each term of the sum, we replace all the factors of form (a - i) that we get by applying the binomial theorem with (a), the result will be greater than the original.) = a^a + a^a + 1/2*a^a + ... + 1/a!*a^a (combined powers of a in each term) = a^a(1 + 1 + 1/2 + ... + 1/a!) < a^a*e (remembering the definition of e as 1 + 1 + 1/2! + 1/3! + 1/4! + ...) Therefore, (a + 1)a^a/(a + 1)^a > (a + 1)a^a/(a^a*e) = (a + 1)/e. Noting that 2 < e < 3, for any a >= 2, (a + 1)/e > 1. Therefore, (a + 1)a^a/(a + 1)^a > 1, therefore, f(a)/f(a + 1) > 1, therefore, f(a) > f(a + 1) for any a >= 2. Now we combine our three results: f(2) = 2; f is never equal to 1; and f is strictly decreasing. For any other solution to the original equation, we would have to find some z > 2 for which f(z) is a positive integer, but this integer would have to be less than 2 by the first and third results, and it can't be 1 by the second result, so we've run out of positive integers. There are no more solutions. Therefore, all the solutions in N*×N*×N* to the original equation are: x = 1; (y and z unrestricted) z = 1; (x and y unrestricted)b y = 2, z = 2. (x unrestricted). CrystyB, I'm sure your method was more elegant than mine, but I had fun anyway.
CrystyB
Misunderstood Guy

 Posted: Wed Jun 25, 2003 4:39 am    Post subject: 57 i knew there was a reason i wouldn't like being a teacher! (besides my psychological abilities) if you say the f has "domain N*", why "z = 1, which is definitely not true"? The rest is worthy of immortalisation. [This message has been edited by CrystyB (edited 06-25-2003 01:01 AM).]
Bicho the Inhaler
Daedalian Member

 Posted: Wed Jun 25, 2003 5:38 am    Post subject: 58 CrystyB - You're right, that's not correct. The domain is supposed to be positive integers >= 2 (I said "Now suppose z > 1" and then miswrote the domain). In fact, there's no way z = 1 could be in the domain because we divide by z - 1 in the exponent. That's actually what I was thinking when I wrote "definitely not true": I just saw the 1/(z - 1) in the expression and thought "contradiction."
Bicho the Inhaler
Daedalian Member

 Posted: Fri Jul 11, 2003 5:10 am    Post subject: 59 Heh. I don't know how many more times I'll get to use the fact that e < 3 in a proof. Anyway, CrystyB, I hope you don't mind if I submit a problem. I saw this posted a while ago on the Straight Dope Message Board, and it is also posed as an exercise somewhere in Rudin's Principles of Mathematical Analysis. It's a nice little problem, IMO. Let f be continuous and differentiable on the nonnegative reals. If 1) f' is increasing on the positive reals, and 2) f(0) = 0 Prove that the function g(x) := f(x)/x is increasing on the positive reals.
Vinny
Promiscuous enough

 Posted: Thu Sep 25, 2003 2:13 am    Post subject: 60 Hey, i have a quick question for you math type. Let's say I borrowed \$1000 from a bank (Face Value). And the interest rate is 15% for a duration of 18 months. That means that the interest I owed is \$1000 x .15 x 1.5 = \$225. And what I actually get is \$775 (not \$1000). This is fine if I only needed \$775, but what if I needed \$1000? How do I calculate the initial face value if I were given a) How much I need (\$1000) b) interest rate (.15) c) duration (18 months) ?
Vinny
Promiscuous enough

 Posted: Thu Sep 25, 2003 2:19 am    Post subject: 61 nm, i figured it out.
Vinny
Promiscuous enough

 Posted: Thu Sep 25, 2003 2:31 am    Post subject: 62 Dang, my solution only worked if the amount of interest owed is less than the amount I needed. It get's negative and all confusing if the interest rate or duration gets too high. Someone help me out?
extropalopakettle
No offense, but....

 Posted: Thu Sep 25, 2003 2:56 am    Post subject: 63 I think there's information missing, and your math is wrong. quote:Let's say I borrowed \$1000 from a bank (Face Value). And the interest rate is 15% for a duration of 18 months. That means that the interest I owed is \$1000 x .15 x 1.5 = \$225 I assume you're multiplying by 1.5 because it's one and a half years. But how often is interest compounded? Compounded annualy, after one year you'd owe \$1150. After that, you're paying interest on \$1150, not on \$1000. If it's 15% compounded quarterly, then every three months you owe 15%/4 = 3.75% more than what you owed three months before. The more frequently it's compounded, the more you owe (but there's a limit). Next problem: You can't just subtract the interest you would pay on \$1000 to get the amount you would borrow to end up paying \$1000 at that rate. If the total accumulated interest you would pay is X%, then you'll owe 1+(X/100) times what you borrowed. So if you want to end up owing D (for debt), divide D by 1+(X/100) to get the amount you'd borrow. For instance, if you're going to end up paying 20% (over the life of the loan), and want to end up owing \$1000, then you'd borrow \$1000/1.2 or \$833.33. You don't subtract 20% of \$1000.
Vinny
Promiscuous enough

 Posted: Thu Sep 25, 2003 3:59 pm    Post subject: 64 How about if I don't care how much I end up owing, I just need \$1000. So the amount I actually borrowed (amount needed plus interest), call it FaceValue, would be higher than \$1000. I need a formula to figure that out. i.e. Given Amount Needed (\$1000), InterestRate (.15), and Duration (18 months), how do I get the FaceValue that will give me \$1000. I thought the formula is FaceValue - (FaceValue * InterestRate * Duration) = Amount Needed and I can solve the formula for FaceValue. But things get weird if InterestRate * Duration is higher than 1.
mathgrant
A very tilted cell member

 Posted: Fri Sep 26, 2003 3:26 am    Post subject: 65 A problem from the Putnam Exam: Let f be a function with continuous third derivative. Prove that there exists a real number a such that f(a)*f'(a)*f''(a)*f'''(a)>0.
Bicho the Inhaler
Daedalian Member

 Posted: Fri Sep 26, 2003 8:52 pm    Post subject: 66 Okay. Suppose what you say is false. Then the negation must be true, i.e., for all real a, f(a)f'(a)f''(a)f'''(a) < 0. 1) None of f, f', f'', or f''' can ever change sign on the real line, i.e., each one is either always positive or always negative. This is because all of f, f', f'', and f''' are continuous (we are given that f''' is continuous, and differentiability implies continuity for the other three), so the intermediate value theorem on the real line implies that if for any one of the four (call it g), there are two real numbers b and c for which g(b) > 0 and g(c) < 0, there must be some a between b and c for which g(a) = 0, since 0 is between g(b) and g(c). However, none of the four functions can ever be 0, because if any one is 0 at some point a, then the product f(a)f'(a)f''(a)f'''(a) = 0 > 0, contradicting our assumption that the proposition was false. Therefore, each one of f, f', f'', and f''' is either always positive or always negative. 2) Suppose f'' is positive for some real argument. By the previous observation, f'' is always positive. This means that f' is monotonically increasing on the real line. Now look at f'. If f'(x) = A > 0 for some x, then since f' is monotonically increasing, for y > x, f(y) > f(x) + A(y - x), so if y > x - f(x)/A, then f(y) > 0, so f > 0 everywhere. On the other hand, suppose f'(x) = B < 0 for some x. In this case, since f' is monotonically increasing, for y < x, f(y) > f(x) + B(y - x), so if y < x - f(x)/B, f(y) > 0, so f > 0 everywhere. (The inequalities I used to get this can easily be derived using the fundamental theorem of the calculus, but because I think they're fairly clear anyway, I'm omitting the proofs.) In both cases, we see that if f'' > 0, then f > 0. If f'' < 0, apply the above argument to -f, -f', and -f'' to see that -f > 0 everywhere, i.e., f < 0 everywhere. Thus, in all cases, f and f'' must have the same sign everywhere. Therefore, f(x)f''(x) > 0 for all real x. Now, by the above result, f'(x)f'''(x) > 0 for all real x, as well (because the above argument is a lemma that applies equally well to both f and f' here). But this is a contradiction, because it implies that f(x)f''(x)f'(x)f'''(x) > 0, so f(x)f'(x)f''(x)f'''(x) > 0, contradicting our assumption that the product was always negative. Therefore, for some real a, f(a)f'(a)f''(a)f'''(a) > 0, which was to be shown.
Interest
Guest

 Posted: Wed Oct 01, 2003 10:35 am    Post subject: 67 But Vinny, you would loan exactly \$1000. The interest is what you'd pay ABOVE when returning the sum. Until the deadline you'd have full use of the \$1000... And extro is right about compounding the interest. Over 18 periods of a month (which is pretty common for interest computing IMO), you'd owe \$1250.5774... PS Bicho, this thread is for math, not for me showing off as good at it... CrystyB, but i can't log on here and now
mathgrant
A very tilted cell member

 Posted: Thu Oct 02, 2003 10:40 pm    Post subject: 68 A very simple problem I made up. Let there be infinitely many languages L1, L2, L3, . . . Ln, . . . . Each language consists of D's and S's. S is a phrase in L1. If x is a phrase in Ln, then xS is in Ln+1. If Sx is a phrase in Ln, so is Dx. If xDSSy is a phrase in Ln, so is xSDy. In what language would you find the phrase SDDSSSDDDDSSSSSDDDDDD? [This message has been edited by mathgrant (edited 10-02-2003 06:41 PM).]
ChienFou

 Posted: Fri Oct 17, 2003 3:04 am    Post subject: 69 Let x= 0.999999.... Then 10x= 9.999999999... therefore 9x=9, all the surreal nonsense is a waste of time.
math geek
Guest

 Posted: Fri Dec 19, 2003 4:19 pm    Post subject: 70 mg, am i to assume that L1 consists only of S and D?
Lucky Wizard
Daedalian Member

 Posted: Fri Dec 19, 2003 10:40 pm    Post subject: 71 I couldn't figure it out when you first posted it, but I think I've figured it out now. Quick question: Is it safe to assume that the logical converse of those three statements is true? If so, then I think the answer is [Language 11583].
math geek
Guest

 Posted: Sat Dec 20, 2003 5:47 pm    Post subject: 72 yes, if all the Ln sets are to be created only by the given rules, you're right, in both statements. ...and to think i was going to determine all the Ln sets! i would've had to reach 11583'rd iteration!!
Hitchhiker
Finally got a ride.

 Posted: Thu Mar 18, 2004 11:36 pm    Post subject: 73 Bump
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year by All usersAgamemnonAnonymousBeartalonBicho the InhalerborschevskyChienFouChuckCoyoteCrystyBextropalopakettleHitchhikerjeepLucky WizardmathgrantmikegooMikkomithrobichelliVinnyVinnyQ Oldest FirstNewest First
 All times are GMTGoto page Previous  1, 2 Page 2 of 2

 Jump to: Select a forum Puzzles and Games----------------Grey Labyrinth PuzzlesVisitor Submitted PuzzlesVisitor GamesMafia Games Miscellaneous----------------Off-TopicVisitor Submitted NewsScience, Art, and CulturePoll Tournaments Administration----------------Grey Labyrinth NewsFeature Requests / Site Problems
You cannot post new topics in this forum
You can reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum