TDM
Legend
Oh, that's unfortunate. Yeah, 4th is good.
If you need to get first to get through then I don't think we're going to get through to the next round either ... we don't have anyone from year 13 in our school
Mathematics Thread
- Thread starter IanTheCuber
- Start date
If you need to get first to get through then I don't think we're going to get through to the next round either ... we don't have anyone from year 13 in our school
TDM
Legend
ok so the team maths challenge went even worse than I expected We got 5/10 in the first round, did well in the second and then completely failed the final round. One school got 100% in all three rounds...
We got 5/10 in the first round, did well in the second and then completely failed the final round. One school got 100% in all three rounds...
Ickathu
Veteran
mkay, I need help with my intermediate number theory class. I'm stuck on two proofs. I've gotten some stuff on one of them, and nothing on the other one:
Unfortunately, these forums don't support LaTeX, but I image-ized my work; hopefully the upload works.
And the second one
Any help would be fantastic.
Unfortunately, these forums don't support LaTeX, but I image-ized my work; hopefully the upload works.
Prove that the system x^6+x^3+x^3y+y = 147^{157} x^3+x^3y+y^2+y+z^9 = 157^{147} has no solutions in integers x, y, and z.
Here's what I've got so far. I think I'm really close, but I can't get any more.
Here's what I've got so far. I think I'm really close, but I can't get any more.
And the second one
Show there are infinitely many primes that are equivalent to 1 mod 8.
This one comes with two hints:
Hint #1: For the first half of the solution: Recall the problem from class about x^2 + xy + y^2. Apply the same ideas to numbers of the form x^4 + 1.
Hint #2: For the second half of the solution: How did Euclid show there were infinitely many primes?
This one comes with two hints:
Hint #1: For the first half of the solution: Recall the problem from class about x^2 + xy + y^2. Apply the same ideas to numbers of the form x^4 + 1.
Hint #2: For the second half of the solution: How did Euclid show there were infinitely many primes?
Any help would be fantastic.
Eduard Khil
Regular
- Joined
- Dec 15, 2014
- Messages
- 169
Only in Year 9...
Seanliu
Veteran
chronondecay
Member
Yes! Something that I can actually contribute to the forums
Though I hope I'm not too late...
For the first part, you actually don't need to find the orders at all! You can just simplify using 14^18 = 15^18 = 1 (mod 19).
The factorisation is nice. Now the first thing we want to investigate is the z^9 term: what values can z^9 take (mod 19)?
Now there are two things we can do here: add the two congruences, or subtract them. Try it out! (Hint: one of them solves the question.)
I don't know what you did in class with x^2+xy+y^2, but let's try this.
Let p be a prime that divides x^4+1 for an integer x. In other words, x^4 = -1 (mod p). Now what can the order of x (mod p) be?
Deduce that either p = 2, or p = 1 (mod 8).
For the second half of the proof, we assume like Euclid's proof that there are finitely many primes that are = 1 (mod 8), say {p_1, p_2, ..., p_k}. Now we want to make a number that must have a 1 (mod 8) prime factor, but not divisible by any of p_1, ..., p_k. This would be a contradiction, which is what we want.
How do we make this work? How does the first half link to the second half? How do we rule out the case p=2?
I hope that's enough to get you going. Good luck with your course!
Ickathu
Veteran
Yes! Something that I can actually contribute to the forums
Though I hope I'm not too late...
Thanks, I ended up figuring them both out, using the same(ish) methods as you hinted at.
My class is over now, and it makes me sad because (a) I love math and (b) I love number theory...
chronondecay
Member
My class is over now, and it makes me sad because (a) I love math and (b) I love number theory...
Wow, it isn't everyday that you hear someone say that! :tu
(Though I suppose being on the math thread in a cubing forum helps, lol)
Most number theory beyond the level of your class would probably no longer actually involve numbers... Though I think if you enjoy other parts of higher math (linear algebra? calculus? real analysis? group theory?) you'll enjoy more advanced number theory as well.
Here's my favourite theorem. It's easy to state but its proofs can be very involved:
Let p,q be distinct odd prime numbers. Consider the two congruences
x^2=p (mod q)
y^2=q (mod p),
where x,y are integers. Then either both congruences have a solution, or neither of them do,
unless
p=q=3 (mod 4), in which case exactly one of the congruences has a solution in integers.
x^2=p (mod q)
y^2=q (mod p),
where x,y are integers. Then either both congruences have a solution, or neither of them do,
unless
p=q=3 (mod 4), in which case exactly one of the congruences has a solution in integers.
Shoutout to all math students out there: what's your favourite theorem?
Keroma12
Veteran
- Joined
- Jul 28, 2010
- Messages
- 657
- Location
- Vancouver, BC, Canada
- WCA ID
- 2010MATT02
- YouTube
- Visit Channel
chronondecay
Member
I've always known that theorem as black magic, because 1. I have no idea how its proof goes, and 2. it proves this immediately:
Theorem: There are nonstandard models of first-order Peano arithmetic.
Proof: Consider the theory containing the first-order Peano axioms (P1-P5), and the following infinite set of axioms:
A0: There exists n such that n is not equal to 0.
A1: There exists n such that n is not equal to 1.
A2: There exists n such that n is not equal to 2.
...
Clearly any finite set of axioms in this theory has a model (namely the set of natural numbers). By the compactness theorem, this theory has a model, which clearly cannot be the set of natural numbers. QED.
Proof: Consider the theory containing the first-order Peano axioms (P1-P5), and the following infinite set of axioms:
A0: There exists n such that n is not equal to 0.
A1: There exists n such that n is not equal to 1.
A2: There exists n such that n is not equal to 2.
...
Clearly any finite set of axioms in this theory has a model (namely the set of natural numbers). By the compactness theorem, this theory has a model, which clearly cannot be the set of natural numbers. QED.
Any other takers?
cmhardw
Premium Member
I just did a fun problem, with a neat solution. I post it here for others to have fun with, and potentially for us to compare methods of solution if people are interested.
I am listening to a playlist of songs on grooveshark. There are 18 songs in my playlist, and I have it set to shuffle (play songs in random order). Assuming that the player could potentially repeat a song, what is the expected song play at which I hear my first repeat song? If any song plays for the second time, then I consider it a repeat play.
For example, if there are five songs (A, B, C, D, E) and the player plays them in order:
DCEBC
Then the 5th play was the song C for the second time, and I would say that the 5th play is when the first repeat happened. The question again is which song play is the expected first repeat play of any song, given a playlist of 18 songs?
Have fun
Gödel's (first) incompleteness theorem
I am listening to a playlist of songs on grooveshark. There are 18 songs in my playlist, and I have it set to shuffle (play songs in random order). Assuming that the player could potentially repeat a song, what is the expected song play at which I hear my first repeat song? If any song plays for the second time, then I consider it a repeat play.
For example, if there are five songs (A, B, C, D, E) and the player plays them in order:
DCEBC
Then the 5th play was the song C for the second time, and I would say that the 5th play is when the first repeat happened. The question again is which song play is the expected first repeat play of any song, given a playlist of 18 songs?
Have fun
Gödel's (first) incompleteness theorem
Last edited:
Stefan
Legend
TDM
Legend
I couldn't believe it would be so low, but I found a random letter generator, and ran it 100 times, and got 6.03 as the average. Didn't expect that...
(even though I knew your maths would be right, I didn't want to believe it)
(even though I knew your maths would be right, I didn't want to believe it
)
cmhardw
Premium Member
I got the same answer. My solution was:
I'm still having trouble with LaTeX on this forum, so here's my general solution for n songs
And here's my solution for 18 songs
To be clear, the solution method I used is probably not particularly neat. I found the result neat because for 18 songs, the number in my actual playlist, the result is very nearly a natural number. For n=7 and n=12 songs the expected value is also very close to a natural number, but for n=18 it is closer than the other n values I mentioned. In addition to that, this problem is very similar to the birthday paradox problem, a problem I like. For those two reasons I found this problem to be neat
And here's my solution for 18 songs
To be clear, the solution method I used is probably not particularly neat. I found the result neat because for 18 songs, the number in my actual playlist, the result is very nearly a natural number. For n=7 and n=12 songs the expected value is also very close to a natural number, but for n=18 it is closer than the other n values I mentioned. In addition to that, this problem is very similar to the birthday paradox problem, a problem I like. For those two reasons I found this problem to be neat
Last edited:
Stefan
Legend
Chris: Meh, I wouldn't call this neat. My solution is basically the same, btw (though I admit I originally made the mistake of only going to 18, not 19).
TDM: R is really good at this kind of stuff, I did a big experiment as well before I posted: http://ideone.com/q2li4r
TDM: R is really good at this kind of stuff, I did a big experiment as well before I posted: http://ideone.com/q2li4r
cmhardw
Premium Member
I clarified what I meant by neat within my previous post, but it appears to have been after you made this post.
Stefan
Legend
Ah yes, that edit came too late for me. And I agree it's kinda neat that way. I had actually done my big experiment before my formula and got a number very close to 6, making me wonder whether the correct value is actually exactly 6 (but I highly doubted it).
chronondecay
Member
A slightly neater expression for the answer.
Let P(m) be the probability that the first m songs are distinct. P(m) has a nice expression (the product (18-k)/18 in my answer). Now the probability that the first repetition occurs after exactly m songs is just P(m-1)-P(m), and we can proceed from there.
Let P(m) be the probability that the first m songs are distinct. P(m) has a nice expression (the product (18-k)/18 in my answer). Now the probability that the first repetition occurs after exactly m songs is just P(m-1)-P(m), and we can proceed from there.
I see others have responded, but I haven't looked at any of their spoilers, I promise!
For a playlist of length n, the probability that the xth song will be a repeat of a previously played song is given by
{[n!/(n-x+1)!]/n^(x-1)}[(x-1)/n] for n ≥ x
and [P(x-1)]/(x-2) for n < x
If we graph this equation for n=18, we find that x=5 returns the greatest value, and thus it is more likely that it will be the 5th song than any other single song. (I think you could use the second derivative or something to find out the same thing, but we haven't gotten that far yet in Calculus)
How I arrived at my answer:
I started with n=4
[TABLE="width: 500"]
[TR]
[TD]x[/TD]
[TD]P(x is a repeat given there haven't been any repeats yet) = c[/TD]
[/TR]
[TR]
[TD]1[/TD]
[TD]0 already-played songs to repeat / 4 total = 0/4[/TD]
[/TR]
[TR]
[TD]2[/TD]
[TD]1 already-played songs to repeat / 4 total = 1/4[/TD]
[/TR]
[TR]
[TD]3[/TD]
[TD]2/4[/TD]
[/TR]
[TR]
[TD]4[/TD]
[TD]3/4[/TD]
[/TR]
[TR]
[TD]5[/TD]
[TD]4/4[/TD]
[/TR]
[/TABLE]
But that assumes that none of the previous songs have been repeats. Thus, to find the probability the xth song will be a repeat, we need to multiply c by the probability none of the previous have been repeats (d)
so:
[TABLE="width: 500"]
[TR]
[TD]x[/TD]
[TD]d[/TD]
[/TR]
[TR]
[TD]1[/TD]
[TD]undefined? (there were no previous songs)[/TD]
[/TR]
[TR]
[TD]2[/TD]
[TD]4/4=1[/TD]
[/TR]
[TR]
[TD]3[/TD]
[TD]4/4*3/4=3/4[/TD]
[/TR]
[TR]
[TD]4[/TD]
[TD]4/4*3/4*2/4=3/8[/TD]
[/TR]
[TR]
[TD]5[/TD]
[TD]4/4*3/4*2/4*1/4=3/32[/TD]
[/TR]
[/TABLE]
[TABLE="width: 500"]
[TR]
[TD]x[/TD]
[TD]c*d = P(x)[/TD]
[/TR]
[TR]
[TD]1[/TD]
[TD]0/4*1=0[/TD]
[/TR]
[TR]
[TD]2[/TD]
[TD]1/4*1=1/4[/TD]
[/TR]
[TR]
[TD]3[/TD]
[TD]1/2*3/4=3/8[/TD]
[/TR]
[TR]
[TD]4[/TD]
[TD]3/4*3/8=9/32[/TD]
[/TR]
[TR]
[TD]5[/TD]
[TD]1*3/32=3/32[/TD]
[/TR]
[/TABLE]
But of course this only works with 4 songs. To extrapolate to 18 songs, we need to formulate an equation to describe n=4 that will apply to all values of n.
We continue to separate c and d, because the equation for c is very easy: (x-1)/n.
So what's the equation for d? It definitely has something/n^(x-1) because we see in the table for d that we are always multiplying by a number of fractions with n in the denominator equal to x-1. The numerator, then, is n!/(n-x+1)!
That's how I arrived at {[n!/(n-x+1)!]/n^(x-1)}[(x-1)/n]
I noticed it didn't work for values where x>n, so I generated another equation to solve those values.
any questions?
EDIT: so apparently everyone else understood it to mean the value of x at which the sum of x and all smaller values of x is greater than .5, which I also calculated and found to be 6 using my equation, but the way the question was worded, I thought we were supposed to find the single value of x which had the highest probability of being the first repeat. I used the graph on this page to find that value
{[n!/(n-x+1)!]/n^(x-1)}[(x-1)/n] for n ≥ x
and [P(x-1)]/(x-2) for n < x
If we graph this equation for n=18, we find that x=5 returns the greatest value, and thus it is more likely that it will be the 5th song than any other single song. (I think you could use the second derivative or something to find out the same thing, but we haven't gotten that far yet in Calculus)
How I arrived at my answer:
I started with n=4
[TABLE="width: 500"]
[TR]
[TD]x[/TD]
[TD]P(x is a repeat given there haven't been any repeats yet) = c[/TD]
[/TR]
[TR]
[TD]1[/TD]
[TD]0 already-played songs to repeat / 4 total = 0/4[/TD]
[/TR]
[TR]
[TD]2[/TD]
[TD]1 already-played songs to repeat / 4 total = 1/4[/TD]
[/TR]
[TR]
[TD]3[/TD]
[TD]2/4[/TD]
[/TR]
[TR]
[TD]4[/TD]
[TD]3/4[/TD]
[/TR]
[TR]
[TD]5[/TD]
[TD]4/4[/TD]
[/TR]
[/TABLE]
But that assumes that none of the previous songs have been repeats. Thus, to find the probability the xth song will be a repeat, we need to multiply c by the probability none of the previous have been repeats (d)
so:
[TABLE="width: 500"]
[TR]
[TD]x[/TD]
[TD]d[/TD]
[/TR]
[TR]
[TD]1[/TD]
[TD]undefined? (there were no previous songs)[/TD]
[/TR]
[TR]
[TD]2[/TD]
[TD]4/4=1[/TD]
[/TR]
[TR]
[TD]3[/TD]
[TD]4/4*3/4=3/4[/TD]
[/TR]
[TR]
[TD]4[/TD]
[TD]4/4*3/4*2/4=3/8[/TD]
[/TR]
[TR]
[TD]5[/TD]
[TD]4/4*3/4*2/4*1/4=3/32[/TD]
[/TR]
[/TABLE]
[TABLE="width: 500"]
[TR]
[TD]x[/TD]
[TD]c*d = P(x)[/TD]
[/TR]
[TR]
[TD]1[/TD]
[TD]0/4*1=0[/TD]
[/TR]
[TR]
[TD]2[/TD]
[TD]1/4*1=1/4[/TD]
[/TR]
[TR]
[TD]3[/TD]
[TD]1/2*3/4=3/8[/TD]
[/TR]
[TR]
[TD]4[/TD]
[TD]3/4*3/8=9/32[/TD]
[/TR]
[TR]
[TD]5[/TD]
[TD]1*3/32=3/32[/TD]
[/TR]
[/TABLE]
But of course this only works with 4 songs. To extrapolate to 18 songs, we need to formulate an equation to describe n=4 that will apply to all values of n.
We continue to separate c and d, because the equation for c is very easy: (x-1)/n.
So what's the equation for d? It definitely has something/n^(x-1) because we see in the table for d that we are always multiplying by a number of fractions with n in the denominator equal to x-1. The numerator, then, is n!/(n-x+1)!
That's how I arrived at {[n!/(n-x+1)!]/n^(x-1)}[(x-1)/n]
I noticed it didn't work for values where x>n, so I generated another equation to solve those values.
any questions?
EDIT: so apparently everyone else understood it to mean the value of x at which the sum of x and all smaller values of x is greater than .5, which I also calculated and found to be 6 using my equation, but the way the question was worded, I thought we were supposed to find the single value of x which had the highest probability of being the first repeat. I used the graph on this page to find that value
Last edited:
cmhardw
Premium Member
To be honest I had to do some research on this before replying. My interpretation of your solution is that you figured out the probability mass function for this situation and then picked the mode, the value with the highest probability of occurrence.
I don't claim to be an expert on this, I'm actually taking my first official statistics course this semester in grad school, so take what I say with a grain of salt.
It appears that using the mode to estimate the "most representative" value in a distribution introduces more error than using the "expected value" or "mean" of that distribution.
Here is an article that explains the difference between using the mean and mode. It shows via a demonstration that the mode introduces more error than using the mean.
I also found this article useful (go to the "Comparison of Mean, Median, and Mode section and look at the graphs for the skewed or log normal distributions)
I don't know if this helps point you in the right direction. I had never thought about the mode as compared to the mean for estimating a "representative" value of a distribution, and I definitely learned something new!
I don't claim to be an expert on this, I'm actually taking my first official statistics course this semester in grad school, so take what I say with a grain of salt.
It appears that using the mode to estimate the "most representative" value in a distribution introduces more error than using the "expected value" or "mean" of that distribution.
Here is an article that explains the difference between using the mean and mode. It shows via a demonstration that the mode introduces more error than using the mean.
I also found this article useful (go to the "Comparison of Mean, Median, and Mode section and look at the graphs for the skewed or log normal distributions)
I don't know if this helps point you in the right direction. I had never thought about the mode as compared to the mean for estimating a "representative" value of a distribution, and I definitely learned something new!
