Dominion Strategy Forum

Please login or register.

Login with username, password and session length
Pages: 1 ... 3 4 [5] 6 7 ... 41  All

Author Topic: Maths thread.  (Read 96213 times)

0 Members and 2 Guests are viewing this topic.

SirPeebles

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3247
  • Respect: +5447
    • View Profile
Re: Maths thread.
« Reply #100 on: May 10, 2014, 02:09:25 pm »
0

Here's a question.  When is the next year in which the corresponding variant of heron's problem would have a unique answer?
Logged
Well you *do* need a signature...

pacovf

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3382
  • Multiediting poster
  • Respect: +3716
    • View Profile
Re: Maths thread.
« Reply #101 on: May 10, 2014, 02:15:39 pm »
0

Here's a question.  When is the next year in which the corresponding variant of heron's problem would have a unique answer?

Somehow I doubt that there is a smart way to answer this.
Logged
pacovf has a neopets account.  It has 999 hours logged.  All his neopets are named "Jessica".  I guess that must be his ex.

heron

  • Saboteur
  • *****
  • Offline Offline
  • Posts: 1022
  • Shuffle iT Username: heron
  • Respect: +1147
    • View Profile
Re: Maths thread.
« Reply #102 on: May 10, 2014, 02:27:27 pm »
+2

Fortunately it does not take very many years; 2020 = 2*2*5*101 so the answer is 2019.
Logged

SirPeebles

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3247
  • Respect: +5447
    • View Profile
Re: Maths thread.
« Reply #103 on: May 10, 2014, 02:28:20 pm »
0

Fortunately it does not take very many years; 2020 = 2*2*5*101 so the answer is 2019.

What if the roots are distinct negative integers?

edit:  It's not that much more interesting, so I'll just post it.  2030 = 2*5*7*29, so it would be in 2029.
« Last Edit: May 10, 2014, 02:29:33 pm by SirPeebles »
Logged
Well you *do* need a signature...

dnkywin

  • Scout
  • ****
  • Offline Offline
  • Posts: 43
  • Respect: +57
    • View Profile
Re: Maths thread.
« Reply #104 on: May 12, 2014, 12:09:47 am »
0

Heh, as someone who's working behind the scenes, it's nice to see HMMT problems being discussed here.

Here's one of my favorite math competition problems of all time (bonus points if you can find the source):

We have a sequence of real numbers a(0), a(1), a(2), ... that satisfies a(n) = r * a(n-1) + s * a(n-2) for some real numbers r,s. Is it possible that a(n) is never 0, but for any positive real number x we can find integers i and j such that |a(i)|< x < |a(j)| ?
« Last Edit: May 12, 2014, 12:12:10 am by dnkywin »
Logged

DStu

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2627
  • Respect: +1487
    • View Profile
Re: Maths thread.
« Reply #105 on: May 12, 2014, 02:22:48 am »
+2

Heh, as someone who's working behind the scenes, it's nice to see HMMT problems being discussed here.

Here's one of my favorite math competition problems of all time (bonus points if you can find the source):

We have a sequence of real numbers a(0), a(1), a(2), ... that satisfies a(n) = r * a(n-1) + s * a(n-2) for some real numbers r,s. Is it possible that a(n) is never 0, but for any positive real number x we can find integers i and j such that |a(i)|< x < |a(j)| ?
my guess is    no   
as

For this to be true, you need a subsequence which converges to 0, and a subsequence that convergece to +inf or -inf.  But the recursion formula should lead to an exponential behaviour like with the Fibonacci sequence (write it in 2d linear recursion, find the eigenvalues/vectors) which leads to exponential behaviour (as long as the absolute value of all eigenvalues does not equal 1. In which case you might have oscillating behaivour depending of the second eigenvalue, but the absolute value stays constant).
In any case you can write a(n) as sum of two complex exponetials, and I don't see how this sum can have both subsequences converging to 0 and to +-inf.

Maybe I'm missing something without writing it down, but in this case this method is exactly what you need to find how it is possible.
Logged

Ozle

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3625
  • Sorry, this text is personal.
  • Respect: +3349
    • View Profile
Re: Maths thread.
« Reply #106 on: May 12, 2014, 02:40:45 am »
+4

Heh, as someone who's working behind the scenes, it's nice to see HMMT problems being discussed here.

Here's one of my favorite math competition problems of all time (bonus points if you can find the source):

We have a sequence of real numbers a(0), a(1), a(2), ... that satisfies a(n) = r * a(n-1) + s * a(n-2) for some real numbers r,s. Is it possible that a(n) is never 0, but for any positive real number x we can find integers i and j such that |a(i)|< x < |a(j)| ?

Moat?
Logged
Try the Ozle Google Map Challenge!
http://forum.dominionstrategy.com/index.php?topic=7466.0

Sullying players Enjoyment of Innovation since 2013 Apparently!

pacovf

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3382
  • Multiediting poster
  • Respect: +3716
    • View Profile
Re: Maths thread.
« Reply #107 on: May 12, 2014, 05:53:44 am »
+1

Heh, as someone who's working behind the scenes, it's nice to see HMMT problems being discussed here.

Here's one of my favorite math competition problems of all time (bonus points if you can find the source):

We have a sequence of real numbers a(0), a(1), a(2), ... that satisfies a(n) = r * a(n-1) + s * a(n-2) for some real numbers r,s. Is it possible that a(n) is never 0, but for any positive real number x we can find integers i and j such that |a(i)|< x < |a(j)| ?
my guess is    no   
as

For this to be true, you need a subsequence which converges to 0, and a subsequence that convergece to +inf or -inf.  But the recursion formula should lead to an exponential behaviour like with the Fibonacci sequence (write it in 2d linear recursion, find the eigenvalues/vectors) which leads to exponential behaviour (as long as the absolute value of all eigenvalues does not equal 1. In which case you might have oscillating behaivour depending of the second eigenvalue, but the absolute value stays constant).
In any case you can write a(n) as sum of two complex exponetials, and I don't see how this sum can have both subsequences converging to 0 and to +-inf.

Maybe I'm missing something without writing it down, but in this case this method is exactly what you need to find how it is possible.


Had arrived to the same conclusion as DStu, but hadn't thought about complex solutions, for some reason. If both "eigenvalues" (e1, e2) have same absolute value larger than one, but their arguments cannot be transformed from one to the other by multiplication by a rational number, it should work.

The idea is that sometimes e1^n and e2^n will have a very similar argument, and hence a(n) will have a very high absolute value, and sometimes their argument will differ by more or less Pi, and hence they will mostly cancel each other, and can get arbitrarily close to zero in absolute value.

EDIT: or maybe not. The absolute value of ei^n might grow fast enough that it can't be cancelled by the nearly opposing arguments. Don't know how to prove it either way.


Scratch that, a(n) has to be real. I agree with DStu, then.
« Last Edit: May 12, 2014, 06:21:48 am by pacovf »
Logged
pacovf has a neopets account.  It has 999 hours logged.  All his neopets are named "Jessica".  I guess that must be his ex.

SirPeebles

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3247
  • Respect: +5447
    • View Profile
Re: Maths thread.
« Reply #108 on: May 12, 2014, 06:18:56 am »
+1

I agree with pacovf that it may be possible.  You can get a(n) to look something like (2^n)*cos(n).  But I'm not sure whether such a sequence will have a subsequence converging to zero or not.  I seem to recall this question coming up in my thesis, and I think I abandoned it for a different approach.
Logged
Well you *do* need a signature...

pacovf

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3382
  • Multiediting poster
  • Respect: +3716
    • View Profile
Re: Maths thread.
« Reply #109 on: May 12, 2014, 10:19:11 am »
+1

Been thinking about it for a while. My gut instinct tells me that minn<N [cos(n)] ~ 1/N, but I can't manage to prove it. I've been working around the fact that cos(x+e) ~ e when cos(x) = 0, so the question is how "quickly" n approaches N*Pi, but I've only managed to compare it to things that go slower, not faster...
« Last Edit: May 12, 2014, 10:24:34 am by pacovf »
Logged
pacovf has a neopets account.  It has 999 hours logged.  All his neopets are named "Jessica".  I guess that must be his ex.

SirPeebles

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3247
  • Respect: +5447
    • View Profile
Re: Maths thread.
« Reply #110 on: May 12, 2014, 10:23:09 am »
0

Been thinking about it for a while. My gut instinct tells me that minn<N [cos(n)] ~ 1/N, but I can't manage to prove it

Yeah, that's what I've been thinking too.
Logged
Well you *do* need a signature...

SirPeebles

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3247
  • Respect: +5447
    • View Profile
Re: Maths thread.
« Reply #111 on: May 12, 2014, 10:38:33 am »
+1

Been thinking about it for a while. My gut instinct tells me that minn<N [cos(n)] ~ 1/N, but I can't manage to prove it. I've been working around the fact that cos(x+e) ~ e when cos(x) = 0, so the question is how "quickly" n approaches N*Pi, but I've only managed to compare it to things that go slower, not faster...

So here's my line of reasoning.  Let's say the cosine has a frequency f.  Instead of looking at cos(2*pi*f*n), let's look at the points traced out on the unit circle and see how close they get to the y-axis.  Well, if f is rational then there are only finitely many points, so assume f is irrational.  Then they form a dense subset of the unit circle.  In fact, I suspect that for large N, the first N points should be close to uniformly distributed around the unit circle.  If so, then we would expect that for large N, the point closest to the y-axis is off by an angle of about 2pi/N, which would give a value for cosine of about 2pi/N.
Logged
Well you *do* need a signature...

pacovf

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3382
  • Multiediting poster
  • Respect: +3716
    • View Profile
Re: Maths thread.
« Reply #112 on: May 12, 2014, 11:14:24 am »
0

Been thinking about it for a while. My gut instinct tells me that minn<N [cos(n)] ~ 1/N, but I can't manage to prove it. I've been working around the fact that cos(x+e) ~ e when cos(x) = 0, so the question is how "quickly" n approaches N*Pi, but I've only managed to compare it to things that go slower, not faster...

So here's my line of reasoning.  Let's say the cosine has a frequency f.  Instead of looking at cos(2*pi*f*n), let's look at the points traced out on the unit circle and see how close they get to the y-axis.  Well, if f is rational then there are only finitely many points, so assume f is irrational.  Then they form a dense subset of the unit circle.  In fact, I suspect that for large N, the first N points should be close to uniformly distributed around the unit circle.  If so, then we would expect that for large N, the point closest to the y-axis is off by an angle of about 2pi/N, which would give a value for cosine of about 2pi/N.

Ah, this should be true, and constitute a proof if using the proper formalism.

The points should be distributed uniformly on the circle for N large enough, I think three years ago one of my teachers did a 10 minute aside to kinda prove it, but I don't remember how he did it... I think it's a bit tricky to demonstrate rigourously.
« Last Edit: May 12, 2014, 11:16:58 am by pacovf »
Logged
pacovf has a neopets account.  It has 999 hours logged.  All his neopets are named "Jessica".  I guess that must be his ex.

Cuzz

  • Minion
  • *****
  • Offline Offline
  • Posts: 548
  • Shuffle iT Username: Cuzz
  • Respect: +900
    • View Profile
Re: Maths thread.
« Reply #113 on: May 12, 2014, 03:08:34 pm »
0

Been thinking about it for a while. My gut instinct tells me that minn<N [cos(n)] ~ 1/N, but I can't manage to prove it. I've been working around the fact that cos(x+e) ~ e when cos(x) = 0, so the question is how "quickly" n approaches N*Pi, but I've only managed to compare it to things that go slower, not faster...

So here's my line of reasoning.  Let's say the cosine has a frequency f.  Instead of looking at cos(2*pi*f*n), let's look at the points traced out on the unit circle and see how close they get to the y-axis.  Well, if f is rational then there are only finitely many points, so assume f is irrational.  Then they form a dense subset of the unit circle.  In fact, I suspect that for large N, the first N points should be close to uniformly distributed around the unit circle.  If so, then we would expect that for large N, the point closest to the y-axis is off by an angle of about 2pi/N, which would give a value for cosine of about 2pi/N.

I don't think any irrational value gives a dense orbit, but a full measure set should. In fact I think a full-measure set of f will give you uniform distribution by the Birkhoff ergodic theorem.
Logged

soulnet

  • Mountebank
  • *****
  • Offline Offline
  • Posts: 2142
  • Respect: +1746
    • View Profile
Re: Maths thread.
« Reply #114 on: May 12, 2014, 03:35:03 pm »
+1

This is one of the best pure-math (i.e., no computability or algorithmic considerations) problems I have encountered:

Are there polynomials in two variables p,q such that given f(x,y) = (p(x,y),q(x,y)) f's range is R^2 - {(0,0)}?
Logged

SirPeebles

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3247
  • Respect: +5447
    • View Profile
Re: Maths thread.
« Reply #115 on: May 12, 2014, 03:38:18 pm »
0

Been thinking about it for a while. My gut instinct tells me that minn<N [cos(n)] ~ 1/N, but I can't manage to prove it. I've been working around the fact that cos(x+e) ~ e when cos(x) = 0, so the question is how "quickly" n approaches N*Pi, but I've only managed to compare it to things that go slower, not faster...

So here's my line of reasoning.  Let's say the cosine has a frequency f.  Instead of looking at cos(2*pi*f*n), let's look at the points traced out on the unit circle and see how close they get to the y-axis.  Well, if f is rational then there are only finitely many points, so assume f is irrational.  Then they form a dense subset of the unit circle.  In fact, I suspect that for large N, the first N points should be close to uniformly distributed around the unit circle.  If so, then we would expect that for large N, the point closest to the y-axis is off by an angle of about 2pi/N, which would give a value for cosine of about 2pi/N.

I don't think any irrational value gives a dense orbit, but a full measure set should. In fact I think a full-measure set of f will give you uniform distribution by the Birkhoff ergodic theorem.

The unit circle is compact.  If the frequency is irrational, then the orbit never repeats, and there will be an infinite subset of the unit circle, and therefore it will have an accumulation point.  This means that for any positive epsilion, one can find two points in the orbit whose angles differ by less than epsilon.  But one of these points comes sooner than the other, so this means that there is some N(epsilon) such that if you take a point in the orbit and move forward N(epsilion) steps, then you will have moved forward by this same angle less than epsilon.  It follows that the orbit is dense.
Logged
Well you *do* need a signature...

Cuzz

  • Minion
  • *****
  • Offline Offline
  • Posts: 548
  • Shuffle iT Username: Cuzz
  • Respect: +900
    • View Profile
Re: Maths thread.
« Reply #116 on: May 12, 2014, 03:51:27 pm »
0

Been thinking about it for a while. My gut instinct tells me that minn<N [cos(n)] ~ 1/N, but I can't manage to prove it. I've been working around the fact that cos(x+e) ~ e when cos(x) = 0, so the question is how "quickly" n approaches N*Pi, but I've only managed to compare it to things that go slower, not faster...

So here's my line of reasoning.  Let's say the cosine has a frequency f.  Instead of looking at cos(2*pi*f*n), let's look at the points traced out on the unit circle and see how close they get to the y-axis.  Well, if f is rational then there are only finitely many points, so assume f is irrational.  Then they form a dense subset of the unit circle.  In fact, I suspect that for large N, the first N points should be close to uniformly distributed around the unit circle.  If so, then we would expect that for large N, the point closest to the y-axis is off by an angle of about 2pi/N, which would give a value for cosine of about 2pi/N.

I don't think any irrational value gives a dense orbit, but a full measure set should. In fact I think a full-measure set of f will give you uniform distribution by the Birkhoff ergodic theorem.

The unit circle is compact.  If the frequency is irrational, then the orbit never repeats, and there will be an infinite subset of the unit circle, and therefore it will have an accumulation point.  This means that for any positive epsilion, one can find two points in the orbit whose angles differ by less than epsilon.  But one of these points comes sooner than the other, so this means that there is some N(epsilon) such that if you take a point in the orbit and move forward N(epsilion) steps, then you will have moved forward by this same angle less than epsilon.  It follows that the orbit is dense.

Ahh, of course, nevermind. You're talking about circle rotation (theta -> theta + alpha), and I was thinking of angle k-tupling instead for some reason (theta -> k*theta).
Logged

SirPeebles

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3247
  • Respect: +5447
    • View Profile
Re: Maths thread.
« Reply #117 on: May 12, 2014, 03:57:42 pm »
0

Yeah, I'm thinking of the powers of e^(i*alpha).
Logged
Well you *do* need a signature...

SirPeebles

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3247
  • Respect: +5447
    • View Profile
Re: Maths thread.
« Reply #118 on: May 12, 2014, 05:02:37 pm »
0

This is one of the best pure-math (i.e., no computability or algorithmic considerations) problems I have encountered:

Are there polynomials in two variables p,q such that given f(x,y) = (p(x,y),q(x,y)) f's range is R^2 - {(0,0)}?

That is a nice one.  I like topological proofs.
Logged
Well you *do* need a signature...

soulnet

  • Mountebank
  • *****
  • Offline Offline
  • Posts: 2142
  • Respect: +1746
    • View Profile
Re: Maths thread.
« Reply #119 on: May 12, 2014, 05:38:22 pm »
0

That is a nice one.  I like topological proofs.

The only proof I know is not topological.
Logged

SirPeebles

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3247
  • Respect: +5447
    • View Profile
Re: Maths thread.
« Reply #120 on: May 12, 2014, 06:25:57 pm »
0

That is a nice one.  I like topological proofs.

The only proof I know is not topological.

Oh, I see that I made a mistake.
Logged
Well you *do* need a signature...

pacovf

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3382
  • Multiediting poster
  • Respect: +3716
    • View Profile
Re: Maths thread.
« Reply #121 on: May 12, 2014, 08:10:41 pm »
0

This is one of the best pure-math (i.e., no computability or algorithmic considerations) problems I have encountered:

Are there polynomials in two variables p,q such that given f(x,y) = (p(x,y),q(x,y)) f's range is R^2 - {(0,0)}?

Does this work? I tend to skip stuff with multivariate problems...

By reductio at absurdo

Let's define F(x,y) = p(x,y)^2+q(x,y)^2

There exists R such that for x^2+y^2 > R^2, F(x,y) > 1. We study the restriction of F to (x,y) such that x^2+y^2 =< R^2

F (restricted) is continuous over a closed space, and admits values arbitrarily close to 0. Hence it reaches 0 at some point, contradiction.

Hence there aren't any such polynomials.


Will we ever get a problem where we actually get to find a counter-example?  :P
« Last Edit: May 12, 2014, 08:37:20 pm by pacovf »
Logged
pacovf has a neopets account.  It has 999 hours logged.  All his neopets are named "Jessica".  I guess that must be his ex.

florrat

  • Minion
  • *****
  • Offline Offline
  • Posts: 542
  • Shuffle iT Username: florrat
  • Respect: +748
    • View Profile
Re: Maths thread.
« Reply #122 on: May 12, 2014, 08:41:00 pm »
+1

There exists R such that for x^2+y^2 > R^2, F(x,y) > 1.
Why?
Logged

soulnet

  • Mountebank
  • *****
  • Offline Offline
  • Posts: 2142
  • Respect: +1746
    • View Profile
Re: Maths thread.
« Reply #123 on: May 12, 2014, 09:07:30 pm »
0

Will we ever get a problem where we actually get to find a counter-example?  :P

I won't answer that, but I will just say, your proof is wrong.
Logged

pacovf

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3382
  • Multiediting poster
  • Respect: +3716
    • View Profile
Re: Maths thread.
« Reply #124 on: May 12, 2014, 09:13:40 pm »
0

There exists R such that for x^2+y^2 > R^2, F(x,y) > 1.
Why?

Now that you mention it, that is indeed harder to prove than I thought at first (my idea was that even polynomials tend towards infinity, but that doesn't trivially imply what I wrote). Hmmm...

Will we ever get a problem where we actually get to find a counter-example?  :P

I won't answer that, but I will just say, your proof is wrong.

Hmmm... indeed. So, the answer is yes, such a polynomial exists, right?  ;)
I guess that my mistake was the one pointed by florrat?
« Last Edit: May 12, 2014, 09:16:27 pm by pacovf »
Logged
pacovf has a neopets account.  It has 999 hours logged.  All his neopets are named "Jessica".  I guess that must be his ex.
Pages: 1 ... 3 4 [5] 6 7 ... 41  All
 

Page created in 0.116 seconds with 21 queries.