• Welcome to the Speedsolving.com, home of the web's largest puzzle community!
    You are currently viewing our forum as a guest which gives you limited access to join discussions and access our other features.

    Registration is fast, simple and absolutely free so please, join our community of 40,000+ people from around the world today!

    If you are already a member, simply login to hide this message and begin participating in the community!

Mathematics Thread

What is the hardest math you learned?

  • Calculus (specify in comments)

    Votes: 67 35.6%
  • Trigonometry

    Votes: 24 12.8%
  • (Enriched) Geometry

    Votes: 17 9.0%
  • Equations (specify)

    Votes: 7 3.7%
  • Graphing Equations (specify)

    Votes: 4 2.1%
  • Basic Algebra (specify)

    Votes: 9 4.8%
  • I can do better!

    Votes: 47 25.0%
  • What kind of math is that?!

    Votes: 13 6.9%

  • Total voters
    188

TDM

Member
Joined
Mar 7, 2013
Messages
7,006
Location
Oxfordshire, UK
WCA
2013MEND03
YouTube
Visit Channel
You pretty much need to come first and sometimes they let you through if you're second, so sadly no, but out of 30 it's definitely a good result.
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 :p
 

TDM

Member
Joined
Mar 7, 2013
Messages
7,006
Location
Oxfordshire, UK
WCA
2013MEND03
YouTube
Visit Channel
ok so the team maths challenge went even worse than I expected :p 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

Member
Joined
May 20, 2011
Messages
1,406
Location
Virginia
WCA
2011MERT03
YouTube
Visit Channel
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.

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. INTWeek10Problem8.png

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?


Any help would be fantastic.
 

chronondecay

Member
Joined
Feb 10, 2015
Messages
16
Location
Singapore
WCA
2015SHEN02
mkay, I need help with my intermediate number theory class.

Yes! Something that I can actually contribute to the forums :p

Though I hope I'm not too late...

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.

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

Show there are infinitely many primes that are equivalent to 1 mod 8.

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!
 

chronondecay

Member
Joined
Feb 10, 2015
Messages
16
Location
Singapore
WCA
2015SHEN02
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.

Shoutout to all math students out there: what's your favourite theorem?
 

chronondecay

Member
Joined
Feb 10, 2015
Messages
16
Location
Singapore
WCA
2015SHEN02

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.


Shoutout to all math students out there: what's your favourite theorem?

Any other takers?
 

cmhardw

Premium Member
Joined
Apr 5, 2006
Messages
4,115
Location
Orlando, Florida
WCA
2003HARD01
YouTube
Visit Channel
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 :)

Shoutout to all math students out there: what's your favourite theorem?

Gödel's (first) incompleteness theorem
 
Last edited:

TDM

Member
Joined
Mar 7, 2013
Messages
7,006
Location
Oxfordshire, UK
WCA
2013MEND03
YouTube
Visit Channel
About 6.007? My solution isn't neat at all, though, so I'm interested in yours.
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 :p)
 

cmhardw

Premium Member
Joined
Apr 5, 2006
Messages
4,115
Location
Orlando, Florida
WCA
2003HARD01
YouTube
Visit Channel
About 6.007? My solution isn't neat at all, though, so I'm interested in yours.

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 :)
 
Last edited:

cmhardw

Premium Member
Joined
Apr 5, 2006
Messages
4,115
Location
Orlando, Florida
WCA
2003HARD01
YouTube
Visit Channel
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

I clarified what I meant by neat within my previous post, but it appears to have been after you made this post.
 

Stefan

Member
Joined
May 7, 2006
Messages
7,280
WCA
2003POCH01
YouTube
Visit Channel
I clarified what I meant by neat within my previous post, but it appears to have been after you made this post.

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
Joined
Feb 10, 2015
Messages
16
Location
Singapore
WCA
2015SHEN02
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.
 

lerenard

Member
Joined
Sep 5, 2014
Messages
274
Location
Tennessee
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
xP(x is a repeat given there haven't been any repeats yet) = c
10 already-played songs to repeat / 4 total = 0/4
21 already-played songs to repeat / 4 total = 1/4
32/4
43/4
54/4
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:
xd
1undefined? (there were no previous songs)
24/4=1
34/4*3/4=3/4
44/4*3/4*2/4=3/8
54/4*3/4*2/4*1/4=3/32

xc*d = P(x)
10/4*1=0
21/4*1=1/4
31/2*3/4=3/8
43/4*3/8=9/32
51*3/32=3/32
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
Joined
Apr 5, 2006
Messages
4,115
Location
Orlando, Florida
WCA
2003HARD01
YouTube
Visit Channel
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.

...

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

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