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.

 Samadhi's school help thread Goto page 12345678910111213 Previous  1, 2, 3 ... , 11, 12, 13  Next
Author Message
kevinatilusa
Daedalian Member

 Posted: Fri Sep 14, 2007 1:19 am    Post subject: 441 I think proof by cases is the way to go, because you're trying to show that two things can't be both true at the same time (The two inequalities). This suggests your argument will look like "If __________, then the expression can't be less than 1" If not _________, then the expression can't be greater than -2" where you'll need to figure out what _________ is. To figure out ___________, how can you tell when the fraction will be positive (in which case you want to show that it's at least 1) or negative (in which case you want to show it's at most -2)?
+1

 Posted: Fri Sep 14, 2007 2:25 am    Post subject: 442 Here's the official solution for that one I posted earlier (for those interested). If J contains no positive elements, then it contains no negative elements either (if x ∈J, with x negative, then (-1)x ∈J by (b), which would be positive) and therefore J = {0} since J is nonempty. In this case, J = J 0 . Otherwise, J has at least one positive element, and therefore by the well-ordering of the natural numbers must have a minimal positive element, which we will call m. By (b), all integer multiples of m are in J, and hence J m ⊆J. It remains to show that J ⊆J m . Suppose by way of contradiction that there is some n ∈J but n !∈J m . Using the division algorithm, we divide n by m to get n = qm + r. We know that n ∈J, and qm ∈J (because qm ∈J m , and J m ⊆J), so by (a) we must have r = n - qm ∈J. But the division algorithm guarantees that 0 ≤r < m, which contradicts the fact that m is minimal and positive in J. Hence any element of J must also be in J m , which proves J ⊆J m and hence J = J m . (I got 66% )_________________And he lived happily ever after. Except for the dieing at the end and the heartbreak in between.
+1

 Posted: Mon Sep 17, 2007 4:05 pm    Post subject: 443 Another number theory problem. I'm at the hand waving stage. Let m, n, a, b be integers, with b ≠ 0. Suppose that gcd (m, ab) = 1. Prove that gcd (ma + nb, b) = gcd (a, b). (I haven't proved these steps but they intuitively feel correct....step 1 is the PITA though) 1. gcd (ma + nb, b) = gcd (ma, b) 2. gcd (m, ab) = 1 = gcd (m, a) = gcd (m, b) 3. Since gcd (m, b) = 1, gcd (ma, b) = gcd (a, b) --> gcd (ma + nb, b) = gcd (a, b). Unless I'm daft those are the right steps and I just need to connect the dots. If there's something wrong with my crayon work, please let me know._________________And he lived happily ever after. Except for the dieing at the end and the heartbreak in between.
+1

Posted: Wed Oct 10, 2007 7:32 pm    Post subject: 444

Here are two questions I missed on a recent test in numerical analysis. He hasn't given us the key yet.

 Quote: The value of f(t) = (1+t 3 ) 1/2 -1 is to be computed for t = 10 -6 . Which of the two mathematically equivalent expressions f 1 (t) = (1+t 3 ) 1/2 -1, or f 2 (t) = t 3 /((1+t 3 ) 1/2 +1), should you use? Why?

I said f 1 (t) because it has fewer operations so less precision is lost. I got it wrong.
 Quote: Can you propose another strategy (based on our current "toolbox") which may be successful for computing this value? [Note: propose != execute!]

I had no idea on this. For "toolbox" I'm sure he means the methods we've gone over so far this semester: Newton's Divided Differences, Newton's Method (of root detection), Taylor Expansion (and some others but they have to do with fixed point iteration and roots).

I guess you could use Taylor expansion, but I don't see how that would help.
_________________
And he lived happily ever after. Except for the dieing at the end and the heartbreak in between.
Antrax
ESL Student

 Posted: Wed Oct 10, 2007 7:38 pm    Post subject: 445 (As usual, I don't know the English terms so I'm translating the Hebrew ones) In any case, f2 is better because you don't have the cancellation problem (where you lose meaningful digits because you substract two close numbers). That's also why Taylor expansion would help._________________After years of disappointment with get rich quick schemes, I know I'm gonna get rich with this scheme. And quick!
+1

 Posted: Tue Oct 16, 2007 12:55 am    Post subject: 446 Thanks, I forgot about that aspect of precision. Here's one from my ODE class. Describe the regions in a, b, c-space where the matrix |0 0 a| |0 b 0| |c 0 0| has real, complex, and repeated eigenvalues. I'm not sure what it's asking. The eigenvalues are b, and +- (ac) 1/2 , with the eigenvectors (a, 0, (ac) 1/2 ), (-a, 0, (ac) 1/2 ), (0, 1, 0). That's not what's being asked though. [edit: no c in row 2]_________________And he lived happily ever after. Except for the dieing at the end and the heartbreak in between.Last edited by Samadhi on Tue Oct 16, 2007 1:54 am; edited 1 time in total
Bicho the Inhaler
Daedalian Member

Posted: Tue Oct 16, 2007 1:22 am    Post subject: 447

 Samadhi wrote: Thanks, I forgot about that aspect of precision. Here's one from my ODE class. Describe the regions in a, b, c-space where the matrix |0 0 a| |0 b c| |c 0 0| has real, complex, and repeated eigenvalues. I'm not sure what it's asking. The eigenvalues are b, and +- (ac) 1/2 , with the eigenvectors (a, 0, (ac) 1/2 ), (-a, 0, (ac) 1/2 ), (0, 1, 0). That's not what's being asked though.
I think it just wants you to consider the three cases and describe under what conditions on a, b, and c they occur.
+1

 Posted: Tue Oct 16, 2007 1:58 am    Post subject: 448 That's rather pedestrian. I have a feeling it's more complex than that. I'll ask my teacher at office hours tomorrow. But the answer to that would be: real (b real and a,c either both neg or both pos), complex (b complex, a or c negative not both), repeated (ac = b 2 )  We've been mainly focusing on phase portraits and the like which is why I think something more is required._________________And he lived happily ever after. Except for the dieing at the end and the heartbreak in between.
+1

 Posted: Tue Oct 16, 2007 3:48 am    Post subject: 449 Recent test question that I haven't got back yet. Fix m, n ∈ N with gcd(m,n) = 1. Suppose that R = {r i : 1 ≤ i ≤ m} is a complete residue system modulo m, and that S = {s j : 1≤j≤n} is a complete residue system modulo n. Prove that T = nR + mS = {nr i + ms j : 1≤i≤m, 1≤j≤n} is a complete residue system modulo mn. Two things need to be shown: (1) ∀ t, t' ∈ T if t≡t'(mod mn) then t = t' (2) |T| = mn Pf (2) There are clearly mn elements in the set so showing that each are distinct is sufficient. Assume not. Therefore t = t' where t = nr 1 + ms 1 and t' = nr 2 + ms 2 So nr 1 + ms 1 = nr 2 + ms 2 nr 1 - nr 2 = ms 2 - ms 1 n(r 1 - r 2 ) = m(s 2 - s 1 ) R and S are closed so let r 1 - r 2 = r 3 and s 2 - s 1 = s 3 nr 3 = ms 3 But this implies that they have a gcd ≠ 1, which is a contradiction. Pf (1) t≡t'(mod mn) ⇒ (t - t')/mn = c, c ∈ Z [(nr 1 + ms 1 ) - (nr 2 + ms 2 )]/mn = c (r 1 - r 2 )/m + (s 1 - s 2 )/n = c r 3 /m + s 3 /n = c But gcd(m,n) = 1 so r 3 = s 3 = 0 ⇒ t = t'_________________And he lived happily ever after. Except for the dieing at the end and the heartbreak in between.
+1

 Posted: Tue Nov 06, 2007 2:14 pm    Post subject: 450 dh/dt = -C (h) 1/2 h(0) = 1 Use seperation of variables to find the explicit analytical solution to the initial value problem in terms of t e (when it's zero). [C is an arbitrary constant] I get h 1/2 = -Ct + c, could someone refresh me on what to do next?_________________And he lived happily ever after. Except for the dieing at the end and the heartbreak in between.
+1

 Posted: Fri Nov 09, 2007 5:47 am    Post subject: 451 From a test today: Prove that x 13 ≡x mod(78) for all x. If instead of 78 it were a prime I could have done something. x 13 -x≡0 mod(78) but then?_________________And he lived happily ever after. Except for the dieing at the end and the heartbreak in between.
Antrax
ESL Student

 Posted: Fri Nov 09, 2007 6:06 am    Post subject: 452 Let's look at the subgroup <13> in Z*78. What is its order? So, what does (x^13)^2 equal mod 78? etc._________________After years of disappointment with get rich quick schemes, I know I'm gonna get rich with this scheme. And quick!
+1

 Posted: Fri Nov 09, 2007 7:44 pm    Post subject: 453 If you mean like 13, 26 etc then its order would be 78 since gcd(78,13) = 1. I don't see how that follows to the next._________________And he lived happily ever after. Except for the dieing at the end and the heartbreak in between.
L'lanmal
Daedalian Member

 Posted: Fri Nov 09, 2007 9:10 pm    Post subject: 454 Perhaps you should factor 78.
+1

 Posted: Sat Nov 10, 2007 2:36 am    Post subject: 455 Yeah, I figured that out while I was out. Thanks._________________And he lived happily ever after. Except for the dieing at the end and the heartbreak in between.
+1

 Posted: Mon Nov 12, 2007 7:41 pm    Post subject: 456 Show that dN/dt = rN (1-N/K) - H(N/(A+N)) can be rewritten as dx/dt = x(1-x) - h(x(a+x)). I know I need to do a change of variable but I'm having trouble choosing a good one._________________And he lived happily ever after. Except for the dieing at the end and the heartbreak in between.
+1

 Posted: Tue Dec 11, 2007 5:20 am    Post subject: 457 For the above it should be dx/dτ (that's tau) here's the solution. Let τ = rt --> use chain rule dN/dτ * dτ/dt = r dN/dt Let N(τ) = k x(τ), H = krh, A = ka r dx/dτ = rx(1-x) - (krh)[kx/(ka+kx)] (after some cancelling) dx/dτ = x(1-x) - h(x(a+x)). Pretty straightforward I guess. For this one I'm stumped at where to begin: dg/dt = k 1 s 0 - k 2 g + k 3 g 2 /(k 4 2 + g 2 ) into dx/dτ = s - rx + x 2 /(1+x 2 ) That's a whole heck of a lot of constants. I thought about letting g = k 4 x and s = k 1 s 0 and r = k 2 k 4 but that leaves me with (k 4 )dx/dτ = s - rx + k 3 x 2 /(1+x 2 ) Any suggestions would be appreciated._________________And he lived happily ever after. Except for the dieing at the end and the heartbreak in between.
+1

 Posted: Thu Feb 07, 2008 2:55 am    Post subject: 458 (!A & !B) --> !(A -->!B) & !(B-->!A) So showing the right hand side is sufficient to show that the possibility of the left exists, right?_________________And he lived happily ever after. Except for the dieing at the end and the heartbreak in between.
Antrax
ESL Student

 Posted: Thu Feb 07, 2008 6:24 am    Post subject: 459 Not sure what you're asking, but assuming the exercise is to prove the formula you quoted is a tautology, you'll have to do something along the lines of: "assume (!A & !B) is true, and assume to the contrary that !(A -->!B) & !(B-->!A) is false. This means either (A -->!B) is true or (B-->!A) is true, which according to "-->"s truth table means..." etc etc._________________After years of disappointment with get rich quick schemes, I know I'm gonna get rich with this scheme. And quick!
+1

 Posted: Thu Feb 07, 2008 6:37 am    Post subject: 460 The actual problem is to show that you can choose from 5 people acquaintances such that no three people are mutually acquainted (IE A knows B and C, B knows A and C, C knows A and B) and no three people are mutual strangers (same example just replace know with don't know). Let the former be proposition A, let the latter be proposition B. Show that A and B are both possible individually. Then show that A --> !B and B --> !A are both false, this shows that A and B are possible at the same time. (I'm sure there's a better way to do this.)_________________And he lived happily ever after. Except for the dieing at the end and the heartbreak in between.
Antrax
ESL Student

 Posted: Thu Feb 07, 2008 7:44 am    Post subject: 461 Why not just use the pigeonhole principle?_________________After years of disappointment with get rich quick schemes, I know I'm gonna get rich with this scheme. And quick!
+1

 Posted: Thu Feb 07, 2008 9:25 am    Post subject: 462 I know that the extended pigeonhole principle applies to this, but I'm not allowed to use that theory (unless I prove it). Edit: I think I'm having difficulty with how to apply the theory here. Sets of acquaintances, ok. Sets of strangers, ok. I'm not clear on how to make the connection between those two sets._________________And he lived happily ever after. Except for the dieing at the end and the heartbreak in between.
Antrax
ESL Student

 Posted: Thu Feb 07, 2008 9:36 am    Post subject: 463 Uh, what's to prove about the pigeonhole principle? Assume to the contrary there's no such "hole", and you get a contradictory upper bound to the number of "pigeons"._________________After years of disappointment with get rich quick schemes, I know I'm gonna get rich with this scheme. And quick!
+1

 Posted: Thu Feb 07, 2008 9:41 am    Post subject: 464 Nothing to prove about the basic theory. But with two disparate sets, I have some difficulty defining the 'holes'._________________And he lived happily ever after. Except for the dieing at the end and the heartbreak in between.
ralphmerridew
Daedalian Member

 Posted: Thu Feb 07, 2008 12:38 pm    Post subject: 465 A knows B knows C knows D knows E knows A (and the reverses). Nobody else knows anybody else.
+1

 Posted: Mon Feb 11, 2008 3:52 am    Post subject: 466 (3)27 Prove that n > 3, n! > 2 n . Let P(0) be where n = 4. n! = 24, 2 4 = 16, so P(0) is true. Assuming P(m-1), consider P(m) (n-1)! > 2 (n-1) multiply each side by n. n! > 2 (n-1) * n. Consider 2 (n-1) * n > 2n. Divide each side 2 (n-1) and you have n > 2. This is true (n >3) so therefore n! > 2n. I got 3/5 on that. Does everyone else agree that I missed something?_________________And he lived happily ever after. Except for the dieing at the end and the heartbreak in between.
Zag
Tired of his old title

 Posted: Mon Feb 11, 2008 12:43 pm    Post subject: 467 Yes. This step Consider 2 (n-1) * n > 2n. Divide each side 2 (n-1) and you have n > 2. This is true (n >3) so therefore n! > 2n. You have only shown that it might be true. That is, you've shown that assuming 2 (n-1) * n > 2n leads you to something else you know to be true, which doesn't conclude anything. If you had said that it is true "if and only if" n>2 then you would have had it. That is, in fact, true and it is clear that's where you were headed, but you didn't prove it. p -> q does not mean that q -> p. However p iff q does imply q iff p. It is usually easier to prove something not true. Try this. Assume 2 (n-1) * n <= 2n This leads to n <= 2. However, we know n >3, a contradiction, so the assumption must be incorrect. Therefore, we can conclude that 2 (n-1) * n > 2n. p -> q does mean that ~q -> ~p Edit. You also have to throw in a statement that 2 (n-1) is a positive number, to make dividing by it a safe step without reversing the inequality. (Easy to do, you just need to declare it, I think.)
+1

 Posted: Mon Feb 11, 2008 2:30 pm    Post subject: 468 I took that from word and had to add tags and I missed one sorry. My professor looked at this exact text: _________________And he lived happily ever after. Except for the dieing at the end and the heartbreak in between.
Zag
Tired of his old title

 Posted: Mon Feb 11, 2008 7:46 pm    Post subject: 469 This doesn't change anything. You haven't proven it. Plus a step in your non-proof is wrong. Consider 2 (n-1) * n > 2 n . Divide each side 2 (n-1) and you have n > 2 This step is not true until you assert that 2 (n-1) is a positive number. Inequalities require more careful manipulation. If you have 3x 2 > 9x You cam NOT say 3x > 9 x > 3 You'll notice that x = -1 is a solution to the original problem.
Nsof
Daedalian Member

 Posted: Mon Feb 11, 2008 10:55 pm    Post subject: 470 My way of thinking on what Zag means is that you are considering too much its because n > 2 that (multiply each side by 2 (n-1) ) n * 2 (n-1) > 2 * 2 (n-1) =2 n not the other way around So n! > n * 2 (n-1) > 2 * 2 (n-1) = 2 n _________________Will sell this place for beer
+1

 Posted: Tue Feb 12, 2008 3:26 am    Post subject: 471 It's positive because n > 3 is a requirement of the problem. I've never had to be that ridiculously pedantic before._________________And he lived happily ever after. Except for the dieing at the end and the heartbreak in between.
Zag
Tired of his old title

Posted: Tue Feb 12, 2008 3:18 pm    Post subject: 472

 Samadhi wrote: It's positive because n > 3 is a requirement of the problem. I've never had to be that ridiculously pedantic before.

You're working at being annoyed instead of trying to see the point. In any case, 2 x is positive as long as x is a real number, and I think you are ignoring imaginary numbers for the time being, so you just have to say it.

But that wasn't the critical flaw in your proof, it was only a minor flaw. The critical flaw was that you didn't prove anything. You said, "Let's assume A is true. I do some transformations on it and, given that assumption, we arrive as something else which we know to be true." This is NOT a proof that your assumption was correct. It is the mathematical equivalent of saying "I'll assume all dogs are black. Look! There's a black dog. Therefore, my assumption was correct."

As I said before, you are much better assuming things you know to be false, such that their opposite is what you want to prove. When you show a contradiction, then you know that the assumption was false, so its opposite is proven true. Note how this works in my other case: "I'll assume no dogs are black. Look! There's a black dog. Therefore my assumption was false, so its opposite -- Some dogs are black -- must be true."

By the way, I think Nsof's solution is also an adequate proof. He didn't assume anything, just built up what he wanted to prove from something else that was known to be true.
ralphmerridew
Daedalian Member

 Posted: Tue Feb 12, 2008 4:29 pm    Post subject: 473 For the inequality on the previous page: If xy+yz+xz < 0, then: (x+y+z)^2 >= 0 xx+yy+zz+2xy+2xz+2yz >= 0 xx+yy+zz >= -2(xy+xz+yz) Since xy+yz+xz < 0, dividing by xy+yz+xz reverses the inequality: (xx+yy+zz)/(xy+xz+yz) <= -2 ------- If xy+yz+xz > 0, then: (|x|-|y|)^2 >= 0 |x||x| - 2|x||y| + |y||y| >= 0 xx + yy >= 2|xy| Similarly, xx+zz >= 2|xz|, yy+zz >= 2|yz| Adding those together gives: 2xx + 2yy + 2zz >= 2|xz|+2|yz|+2|xy| >= 2xz + 2yz + 2xy xx + yy + zz >= xz+yz+xy Since xy+xz+yz > 0, dividing by xy+xz+yz leaves the inequality the same: (xx + yy + zz)/(xy+yz+xz) >= 1
+1

 Posted: Wed Feb 13, 2008 1:27 am    Post subject: 474 Zag: Yeah, I saw the error in the logic when you pointed it out. Sorry I didn't say._________________And he lived happily ever after. Except for the dieing at the end and the heartbreak in between.
Zag
Tired of his old title

 Posted: Wed Feb 13, 2008 3:00 am    Post subject: 475 Ok. Sorry for being a little harsh.
+1

 Posted: Wed Feb 13, 2008 4:56 am    Post subject: 476 No worries. I was going for transitive, but ignoring the utter and complete obviousness of 'dividing by positive number' -> 'no change of inequality' , my fault was that I didn't divide all three by the same value. If I'd done that, that step would have been sound. However, it would have required some extra steps to show that the first inequality holds, so PbyC is best._________________And he lived happily ever after. Except for the dieing at the end and the heartbreak in between.
+1

Posted: Sun Mar 02, 2008 3:42 am    Post subject: 477

I'm having a problem with a linked list.
Here's what I'm doing. Create a linked list with x random integers.
Then create two more lists and insert primes into one, non primes into the other.

The first creation is no problem. But it won't insert into the other lists even though I'm using a similar algorithm.

Here's the creation for the first
 Code: List makeRandomList(int size){    List result = emptyList();    int k;    srand(time(NULL));    for (k=0;kdata = x;    result->nextPtr = L;    return result; }

Here's the primes algorithm (I've used just true/false for isPrime and that's not the problem).
 Code: List getPrimes (List L){    if (isEmpty(L)) return L;    List result = emptyList();    List p = L;    int z;    while (!isEmpty(p)){       z = getFirst(p);       if (isPrime(z)) makeList(z, result);       p = getRest(p);    }    return result; } int isEmpty (List L){    return L==NULL; }

For whatever reason, with result it won't insert z. I'm baffled.
_________________
And he lived happily ever after. Except for the dieing at the end and the heartbreak in between.
extro...*
Guest

 Posted: Sun Mar 02, 2008 6:17 am    Post subject: 478 while (!isEmpty(p)){ z = getFirst(p); if (isPrime(z)) makeList(z, result); p = getRest(p); } should be: while (!isEmpty(p)){ z = getFirst(p); if (isPrime(z)) result = makeList(z, result); p = getRest(p); }
extro...*
Guest

 Posted: Sun Mar 02, 2008 6:22 am    Post subject: 479 "makeList" is a pure function, i.e. it doesn't change it's arguments, but returns a value. But you're not doing anything with that value. Also, not sure what IDE you're using (and I haven't programmed in C in many years, so I don't know what IDEs there are), but if you can learn to use a debugger. it will allow you to step through the code, and you should be able to inspect the value of variables at each step, and see where they don't have the values you expect. Even without an IDE, you could write a function/procedure that prints the contents of a list, and insert calls to it in your loop, and you'll get an idea where things are not doing what you expect they should be doing.
+1

 Posted: Sun Mar 02, 2008 6:41 am    Post subject: 480 Your first post nailed it. Just a stupid mistake. I narrowed it all down until I knew that was the problem line. I just couldn't see my mistake. I only included everything else in case I missed something._________________And he lived happily ever after. Except for the dieing at the end and the heartbreak in between.
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year by All usersalphatangoAnonymousAntraxAZuBicho the InhalercasinopeteChuckcloudRunnerCrystyBCzarJDeath MageextropalopakettleGHkevinatilusaL'lanmalLeptonLordKinboteMatthewVmithmps1453NsofralphmerridewSamadhiTalzorThe Ragin' South AsianwormZag Oldest FirstNewest First
 All times are GMTGoto page 12345678910111213 Previous  1, 2, 3 ... , 11, 12, 13  Next Page 12 of 13

 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