Samadhi's school help thread

[kevinatilusa]

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)?

[Samadhi]

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 ₀ .

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.

[Samadhi]

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.

[Samadhi]

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

[Antrax]

(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!

[Samadhi]

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.

[Bicho the Inhaler]

[Samadhi]

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 ² )

[edit]
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.

[Samadhi]

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 ₁ + ms ₁ and t' = nr ₂ + ms ₂
So
nr ₁ + ms ₁ = nr ₂ + ms ₂
nr ₁ - nr ₂ = ms ₂ - ms ₁
n(r ₁ - r ₂ ) = m(s ₂ - s ₁ )
R and S are closed so let r ₁ - r ₂ = r ₃ and s ₂ - s ₁ = s ₃
nr ₃ = ms ₃
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 ₁ + ms ₁ ) - (nr ₂ + ms ₂ )]/mn = c
(r ₁ - r ₂ )/m + (s ₁ - s ₂ )/n = c
r ₃ /m + s ₃ /n = c
But gcd(m,n) = 1 so r ₃ = s ₃ = 0 ⇒ t = t'
_________________
And he lived happily ever after. Except for the dieing at the end and the heartbreak in between.

[Samadhi]

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.

[Samadhi]

From a test today:
Prove that x ¹³ ≡x mod(78) for all x.

If instead of 78 it were a prime I could have done something.
x ¹³ -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]

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!

[Samadhi]

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]

Perhaps you should factor 78.

[Samadhi]

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.

[Samadhi]

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.

[Samadhi]

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 ₁ s ₀ - k ₂ g + k ₃ g ² /(k ₄ ² + g ² )

into

dx/dτ = s - rx + x ² /(1+x ² )

That's a whole heck of a lot of constants. I thought about letting g = k ₄ x and s = k ₁ s ₀ and r = k ₂ k ₄ but that leaves me with
(k ₄ )dx/dτ = s - rx + k ₃ x ² /(1+x ² )

Any suggestions would be appreciated.
_________________
And he lived happily ever after. Except for the dieing at the end and the heartbreak in between.

[Samadhi]

(!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]

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!

[Samadhi]

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]

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!

[Samadhi]

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]

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!

[Samadhi]

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]

A knows B knows C knows D knows E knows A (and the reverses). Nobody else knows anybody else.

[Samadhi]

(3)27 Prove that n > 3, n! > 2 ⁿ .
Let P(0) be where n = 4. n! = 24, 2 ⁴ = 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]

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.)

[Samadhi]

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]

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 ⁿ . 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 ² > 9x

You cam NOT say

3x > 9
x > 3

You'll notice that x = -1 is a solution to the original problem.

[Nsof]

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 ⁿ
not the other way around

So
n! > n * 2 ^(n-1) > 2 * 2 ^(n-1) = 2 ⁿ
_________________
Will sell this place for beer

[Samadhi]

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]

[ralphmerridew]

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

[Samadhi]

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]

Ok. Sorry for being a little harsh.

[Samadhi]

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.

[Samadhi]

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

[extro...*]

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...*]

"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.

[Samadhi]

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.