Creative Problem Solving

[akorn]

Re: Creative Problem Solving

2. If you divide a prime number by 30, is the remainder necessarily prime?

Basically the question is -> if n(30)+x is prime, then x is a prime number for x<30.

If x is a multiple of 2, 3 or 5, n(30)+x is not prime since n(2*3*5)+2x/3x/5x is always a multiple of 2, 3 or 5.

If x is not a multiple of 2, 3 or 5, it is a prime number.

Therefore, if n(30)+x is prime, x is not a multiple of 2, 3 or 5 and x is a prime number.

So yes.

[T0rajir0u]

Re: Creative Problem Solving

1. TRICK QUESTION O SNAP.

p^2 + 2 is only prime for p = 3

for every other prime it's divisible by 3

3. (31^{11})/(17^{14}) < (34^{11})/(17^{14}) = (2^{11})/(17^3) < (2^{11})/(16^{3}) = 1/2

so 17^{14} is bigger

[Kilgamayan]

Re: Creative Problem Solving

1 is correct although I'd like to see a proof of your claim to make sure you didn't just decide 3 was the only applicable prime >_>

2 is incorrect

3 is correct but there's an easier way to do it

[T0rajir0u]

Re: Creative Problem Solving

1. DA PROOF

if p = 3 we have **** that works

if p isn't 3 then either p \equiv 1 \bmod 3 or p \equiv 2 \bmod 3

then p^2 + 2 \equiv 0 \bmod 3 either case (in other words, 1 is the only nonzero quadratic residue mod 3)

OR IF YOU DON'T LIKE THIS HARDCORE NUMBER THEORY

p^2 + 2 = (p^2 - 1) + 3 = (p+1)(p-1) + 3 so for p not equal to 3 we have either p+1 or p-1 is divisible by 3

2. TRICKY TRICKY 1 ISN'T A PRIME LULZ

[akorn]

Re: Creative Problem Solving

Well, I guess I made the problem harder that what it was supposed to be, since for some reason I thought that 1 was a prime... although answering 31-->1(not a prime!) seems dumb seeing as how when you ignore that 1 isn't a prime it's much harder to work it out. So I might as well make something out of it:

If you divide a prime number by N, for what values of N is the remainder necessarily prime or 1?

[T0rajir0u]

Re: Creative Problem Solving

4
6
8
(10 don't work cuz 9 is a remainder)
12
18
24
30

(yeah we want multiples of 6, but 36 doesn't work because 25 is a viable remainder)

there's probably some bounding argument i could use to prove that no others exist but i'm way too lazy

edit: CLAIM: no numbers larger than 30 work

we need multiples of 30. otherwise, either 4, 9, or 25 are viable remainders

however if we try 60 then 49 is a viable remainer so we need multiples of 210

but then 121 is a viable remainder etc

the sequence of products of primes here that we need grows faster than the sequence of squares of primes (WAY too lazy to prove this) so nothing above 30 works

[akorn]

Re: Creative Problem Solving

Yep, that's correct. You just missed one answer, which is n=1, but that's kind of a silly solution

[church_pk]

Re: Creative Problem Solving

u guyz awr nerds mang

[Kilgamayan]

Re: Creative Problem Solving

although answering 31-->1(not a prime!) seems dumb seeing as how when you ignore that 1 isn't a prime it's much harder to work it out.

Not math's fault you forgot 1 wasn't prime. >_>

It's not terribly hard to work out even if you forget that: given you're dividing a prime number by 30, the only possible remainders are 1, 7, 11, 13, 17, 19, 23 and 29 (at which point you SHOULD notice that 1 isn't a prime), and it's really easy to prove this.

[Kilgamayan]

Re: Creative Problem Solving

Revitval because of midterm exams. Got mine back today, 100'd, etc.

It was surprisingly easy - the only thing you needed for it that you wouldn't have learned in high school was induction. Here's the entire thing.

1. What is the sum of the first n consecutive odd positive integers? Justify your answer.

2. Simplify (1+3)(1+9)(1+81)(1+(3^8))...(1+(3^512)).

3. There are 8 white socks, 10 black socks and 6 grey socks in a drawer. What is the smallest number of socks you have to take from the drawer to guarantee that you have a matching pair?

4. Prove that the sum of the distances from a point inside an equilateral triangle to its sides does not depend on the position of the point.

---

In addition, we got the second of three "really ****ing hard" problems on Tuesday, and I solved it today. Your goal is to prove that (nC0)² + (nC1)² + (nC2)² + ... + (nCn)² = (2n)Cn. In order from easiest to hardest, the three ways you can do this are combinatorically, geometrically (!) and via induction. ap, Tass, t0ra, I'm looking at you for this one.

[T0rajir0u]

Re: Creative Problem Solving

1. n^2, induction (n^2 - (n-1)^2 = 2n-1 hmm dat luks liek da nth odd numbr 2 me lulz)
2. hehe multiply by 1 - 3 for an secret
3. after 3 draws you either have a pair or one of each so 4 draws ps this problem is stupidly easy
4. hehe add up da areas

lemme think about dat uthr wun

[Kilgamayan]

Re: Creative Problem Solving

Pigeonhole Principle problems tend to be pretty easy >_>

If you can, find the geometric proof for the last question, because apparently it's really cool. I got the combinatorial one and while it was pretty cool as well it was also really tedious to write out.

[T0rajir0u]

Re: Creative Problem Solving

lmao i got it after 2 mins in the shower

and what are you talking about the combinatorial argument is hella easy but i got trixxed thinking about the squares

anyway

(nCk)^2 = (nCk)(nC(n-k))

RHS is the number of ways to pick n objects out of 2n objects

you can do this by picking k objects out of the first n objects and then n-k objects out of the second n for k = 0... n and that gets you the LHS

induction is retarded 4 dis problerm LETS NOT EVEN GO THERE

and geometry wtf i will keep thinking about that

EDIT: lmao 5 more minutes trying to fall asleep and i have another counting argument

this time its path counting

basically we're tracing paths down pascal's triangle (easy way to think about it) and every entry in the triangle tells you how many paths there are from the top to that entry

we want to find the number of paths to the middle entry in the 2nth row

so we trace out all the possible paths to the nth row and then there's a nice symmetry between the first n rows of the journey and the second n rows that lets us conclude that the number of paths to the 2nth row passing through the kth entry of the nth row is just (nCk)^2 (there are nCk paths to the kth entry of the nth row and because the 2nth row and 0th row are symmetric about the nth row there are nCk paths from the kth entry of the nth row to the nth entry of the 2nth row)

sum it up etc

pretty similar to the other argument but i don't think pathcounting = geometry so lemme think about it some more

[Kilgamayan]

Re: Creative Problem Solving

Well, yeah, the question you ask is adurdurdurr because of the RHS >_>

The trick is thinking about how to mainpulate the squares and about the division of the 2n-set into two n-sets

And then writing out the whole thing is a pain

[Omeganitros]

Re: Creative Problem Solving

Yeah, somehow I think if the answers were written and drawn out on paper, it would a make a lot more sense to me.

PS I havent had a "Prove yadda yada" problem since Sophmore year.