Dominion Strategy Forum

Please login or register.

Login with username, password and session length
Pages: 1 ... 11 12 [13] 14 15 ... 47  All

Author Topic: Maths thread.  (Read 307122 times)

0 Members and 4 Guests are viewing this topic.

qmech

  • Torturer
  • *****
  • Offline Offline
  • Posts: 1918
  • Shuffle iT Username: qmech
  • What year is it?
  • Respect: +2320
    • View Profile
Re: Maths thread.
« Reply #300 on: February 19, 2015, 03:39:24 am »
+2

In the version I'm familiar with I think you probably need to see the infinite half of the line, but the set up is slightly different here as the guesses aren't made simultaneously.

Here's a variant that I hopefully haven't posted before.  You still have countably infinitely many people, who will be lined up along the natural numbers facing towards infinity.  Everybody guesses their hat colour simultaneously, but doesn't know which position they will be placed in.  Can they ensure that only finitely many people guess incorrectly?
Logged

Watno

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2745
  • Shuffle iT Username: Watno
  • Respect: +2982
    • View Profile
Re: Maths thread.
« Reply #301 on: February 19, 2015, 09:31:01 am »
0

Ok, that's right I guess. You still only need a weakened form of choice, since there are <=|P(N)| classes.
Logged

Witherweaver

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 6476
  • Shuffle iT Username: Witherweaver
  • Respect: +7861
    • View Profile
Re: Maths thread.
« Reply #302 on: February 19, 2015, 09:40:26 am »
+3

Just accept the Axiom of Choice, you bloody heathens. 
Logged

Kirian

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 7096
  • Shuffle iT Username: Kirian
  • An Unbalanced Equation
  • Respect: +9411
    • View Profile
Re: Maths thread.
« Reply #303 on: February 19, 2015, 09:55:07 am »
0

Just accept the Axiom of Choice, you bloody heathens. 

I choose not to!
Logged
Kirian's Law of f.DS jokes:  Any sufficiently unexplained joke is indistinguishable from serious conversation.

heron

  • Saboteur
  • *****
  • Offline Offline
  • Posts: 1055
  • Shuffle iT Username: heron
  • Respect: +1183
    • View Profile
Re: Maths thread.
« Reply #304 on: February 19, 2015, 03:31:11 pm »
+1

Also, how can you know in which class you are if you can just see the hats in front of you, but not the infinitely many behind? Or can you?

Well, there are only finitely many hats behind you, so this is not an issue. I guess for my solution you still need to know how many hats are behind you though. It's not clear whether the prisoners know that or not.
Logged

sudgy

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3431
  • Shuffle iT Username: sudgy
  • It's pronounced "SOO-jee"
  • Respect: +2706
    • View Profile
Re: Maths thread.
« Reply #305 on: February 19, 2015, 04:23:11 pm »
0

Uh, how in the world does 1 + x + x2 + x3 + ... equal 1/(1-x)?
Logged
If you're wondering what my avatar is, watch this.

Check out my logic puzzle blog!

   Quote from: sudgy on June 31, 2011, 11:47:46 pm

Witherweaver

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 6476
  • Shuffle iT Username: Witherweaver
  • Respect: +7861
    • View Profile
Re: Maths thread.
« Reply #306 on: February 19, 2015, 04:26:03 pm »
+2

Uh, how in the world does 1 + x + x2 + x3 + ... equal 1/(1-x)?

Formally set

F(x) = 1+x + x^2 + ...

then

xF(x) = x+x^2 + x^3 + ...

so

F(x) -xF(x) = 1,

or

F(x)(1-x) = 1,

or

F(x) = 1/(1-x).

Now this cheats a little as it's only a formal computation and doesn't deal with convergence.  But that's not hard to deal with.  I'll do it in the next post.
Logged

Witherweaver

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 6476
  • Shuffle iT Username: Witherweaver
  • Respect: +7861
    • View Profile
Re: Maths thread.
« Reply #307 on: February 19, 2015, 04:31:13 pm »
+2

A series x_0+x_1+x_2+x_3+... converges if the sequence of partial sums

{x_0, x_0+x_1, x_0+x_1+x_2, x_0+x_1+x_2+x_3, ....}

converges.  That is, if the sequence S_N = \sum_{n=0}^N x_n converges.  Each partial sum S_N is just a finite sum, so nothing confusing.  For this, x_n = x^n.  So

S_N = \sum_{n=0}^N x^n = 1+x+x^2+x^3+...+x^N

Then by the same trick,

xS_N = x+x^2+...+x^{N+1},

so

S_N - xS_N = 1- x^{N+1}, or

S_N (1-x) = 1-x^{N+1}, os

S_N = 1/(1-x) - x^{N+1}/(1-x).

Now take limits as N->\infty.  It's not hard to see that

S_N -> 1/(1-x) as long as \abs{x} < 1.

Hooray.
Logged

Witherweaver

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 6476
  • Shuffle iT Username: Witherweaver
  • Respect: +7861
    • View Profile
Re: Maths thread.
« Reply #308 on: February 19, 2015, 04:41:43 pm »
+1

While we're at it, let's suppose you have the following problem.

You have a function, but you really like polynomials.  You wish the function was a polynomial instead.  So approximate it by one, but which one?  Well, it depends on what kind of shape you want.  Maybe you only need the approximation near a point (say x=0).  So what to do?  Well, make sure the functions match.  But the shape should stay the same, too.  So the derivatives should match as well.  What degree of polynomial?  Well, however many derivatives you want to match.  If you want to match all the derivatives, then you need a polynomial of all the degrees (i.e., a series).

How do you match up a series with a function such that all the derivatives agree at a single point?  Well do the obvious calculation, and you get the Taylor series, and low and behold the Taylor series for 1/(1-x) is just 1+x+x^2+...

I'll put details when I'm back from phone posting.\

Edit:

Let f:R->R be a smooth (infinitely differentiable) function and fix some x0 in R.  Consider the power series

F(x) = a_0+a_1 (x-x0)+ a_2 (x-x0)^2 + ... + a_n(x-x0)^n + ...

We want F to be the "best" approximation to f "near" x0, in the sense that F agrees with f at x0 in function value and in all derivatives of arbitrary order.  Then we simply require:

F(x0) = f(x0)
F'(x0) = f'(x0)
F''(x0) = f''(x0)
...
F^[n](x0) = f^[n](x0), (this means nth derivative)
...

Well, what is F(x0)?  It's just

F(x0) = a_0 + a_1(x0-x0)+ a_2(x0-x0)^2 + .... = a_0 + 0 = a_0

What is F'(x0)?

F'(x) = a_1 + 2a_2(x-x0) + 3a_3(x-x0)^2 + ... + na_n (x-x0)^(n-1) + ...
F'(x0) = a_1 + 2a_2(x0-x0) + 3a_3(x0-x0)^2 + ... + na_n (x0-x0)^(n-1) + ... = a_1 + 0 = a_1

Continuing,

F''(x) = 2a_2 + 6a_3(x-x0) + ... + n(n-1)a_n (x-x0)^(n-2) + ...
F''(x0) = 2a_2+ 0 + 0 + ... = 2a_2

And in general

F^[n](x) = n! a_n + ((n+1)!/1!) a_{n+1}(x-x0) + ((n+2)!/2!) a_{n+2}(x-x0)^2 + ...
so that
F^[n](x0) = n! a_n.


Then we simply require

F(x0) = a_0 = f(x0)
F'(x0) = a_1 = f'(x0)
F''(x0) = 2a_2 = f''(x0)
F'''(x0) = 6a_3 = f'''(x0)
...
F^[n](x0) = n!a_n = f^[n](x0)
...

So in general,

a_n = f^[n](x0)/n!.

Then the series F is

F(x) = \sum_{n=0}^\infty  (f^[n](x0)/n!) (x-x0)^n

Now, when f(x) = 1/(1-x) and x0 = 0, what are the derivatives?  Well,

f(0) = 1
f'(x)= -(1-x)^(-2)*(-1) = (1-x)^(-2), f'(0) = 1
f''(x) = 2(1-x)^(-3), f''(0) = 2
f'''(x) = 6 (1-x)^(-4), f'''(0) = 6,
...

pattern is you multiply by 1,2,3,4, ...., etc. (every derivative has an extra -1 from the chain rule applied to (1-x)), so you just end up with

f^[n](x) = n! (1-x)^(-(n+1)),

so

f^[n](0) = n!

Then

a_n = (f^[n](x0)/n!)  = n!/n! = 1,

so

F(x) = \sum_{n=0}^\infty x^n

is the Taylor series approximation of 1/(1-x).

Then you can prove that indeed convergence occurs (and is uniform) for \abs{x} < 1.
« Last Edit: February 19, 2015, 04:57:06 pm by Witherweaver »
Logged

sudgy

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3431
  • Shuffle iT Username: sudgy
  • It's pronounced "SOO-jee"
  • Respect: +2706
    • View Profile
Re: Maths thread.
« Reply #309 on: February 19, 2015, 05:19:55 pm »
0

I understand these formal proofs, but more what I'm wondering is that, for example, the infinite sum 1 + 2 + 4 + 8 + 16 + 32 + ... (which is x = 2 for this sum) doesn't converge.  So, how does it equal -1?
Logged
If you're wondering what my avatar is, watch this.

Check out my logic puzzle blog!

   Quote from: sudgy on June 31, 2011, 11:47:46 pm

Witherweaver

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 6476
  • Shuffle iT Username: Witherweaver
  • Respect: +7861
    • View Profile
Re: Maths thread.
« Reply #310 on: February 19, 2015, 05:23:11 pm »
0

I understand these formal proofs, but more what I'm wondering is that, for example, the infinite sum 1 + 2 + 4 + 8 + 16 + 32 + ... (which is x = 2 for this sum) doesn't converge.  So, how does it equal -1?

It doesn't.  Convergence only holds for -1 < x < 1.

But move to the complex plane, analytic continuation, blah blah blah, didn't we talk about this before?
Logged

liopoil

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2587
  • Respect: +2479
    • View Profile
Re: Maths thread.
« Reply #311 on: February 19, 2015, 05:36:52 pm »
+2

So, uh, Witherweaver, hate to break it to you, but LateX doesn't work here... no matter how much syntax you put in.
Logged

pacovf

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3499
  • Multiediting poster
  • Respect: +3838
    • View Profile
Re: Maths thread.
« Reply #312 on: February 19, 2015, 05:39:01 pm »
0

I understand these formal proofs, but more what I'm wondering is that, for example, the infinite sum 1 + 2 + 4 + 8 + 16 + 32 + ... (which is x = 2 for this sum) doesn't converge.  So, how does it equal -1?

The relevant (prettified) formula:

SN = 1/(1-x) - xN+1/(1-x)

This is as far as you can get without making any assumptions about your real x =/= 1. To keep going, you need xN+1 to converge when N -> inf. That's only true for |x| < 1.
Logged
pacovf has a neopets account.  It has 999 hours logged.  All his neopets are named "Jessica".  I guess that must be his ex.

Witherweaver

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 6476
  • Shuffle iT Username: Witherweaver
  • Respect: +7861
    • View Profile
Re: Maths thread.
« Reply #313 on: February 19, 2015, 05:39:20 pm »
+1

So, uh, Witherweaver, hate to break it to you, but LateX doesn't work here... no matter how much syntax you put in.

It makes it the most readable, I think.  It's pretty standard among everyone I know to use pseudo LaTeX code when writing out math in a generic editor (like email).
Logged

Witherweaver

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 6476
  • Shuffle iT Username: Witherweaver
  • Respect: +7861
    • View Profile
Re: Maths thread.
« Reply #314 on: February 19, 2015, 05:44:58 pm »
0

For reference on summing this divergent series: http://en.wikipedia.org/wiki/1_%2B_2_%2B_4_%2B_8_%2B_%E2%8B%AF

Edit:

Oh, and of course there's a similar kind of trick:

Pretend S = 1+2 +4 + 8 + ....

Then

S = 1+2(1+2+4+8+...
   = 1+2(S),

so S must be -1.

Of course it's not true that the series converges in the regular sense of convergent series (i.e., limits of partial sums), BUT if you were going to define a notion of convergence of this series, this calculation shows you should get -1.  (That is, if it obeys regular arithmatic stuff, like linearity.) 
« Last Edit: February 19, 2015, 05:48:01 pm by Witherweaver »
Logged

sudgy

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3431
  • Shuffle iT Username: sudgy
  • It's pronounced "SOO-jee"
  • Respect: +2706
    • View Profile
Re: Maths thread.
« Reply #315 on: February 19, 2015, 05:48:16 pm »
0

Oh yeah, just so you know, I could barely read what you were typing with the LateX, but still got the general gist of it...

I'm more surprised because I saw something that generally doesn't like any types of summing divergent series (or even 1 - 1 + 1 - 1 + ...) state this.
Logged
If you're wondering what my avatar is, watch this.

Check out my logic puzzle blog!

   Quote from: sudgy on June 31, 2011, 11:47:46 pm

sudgy

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3431
  • Shuffle iT Username: sudgy
  • It's pronounced "SOO-jee"
  • Respect: +2706
    • View Profile
Re: Maths thread.
« Reply #316 on: February 19, 2015, 05:49:48 pm »
0

More, what I'm trying to say is, I thought this couldn't be one of those analytical continuations or whatever because of the place I read it.
Logged
If you're wondering what my avatar is, watch this.

Check out my logic puzzle blog!

   Quote from: sudgy on June 31, 2011, 11:47:46 pm

Witherweaver

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 6476
  • Shuffle iT Username: Witherweaver
  • Respect: +7861
    • View Profile
Re: Maths thread.
« Reply #317 on: February 19, 2015, 05:52:32 pm »
0

More, what I'm trying to say is, I thought this couldn't be one of those analytical continuations or whatever because of the place I read it.

Oh, no, it's definitely one of those.  I mean, the person that brought it up may not have been thinking of it that way, or they could have just been stating something that's wrong, but it's definitely implicit in the standard treatment of it.
Logged

qmech

  • Torturer
  • *****
  • Offline Offline
  • Posts: 1918
  • Shuffle iT Username: qmech
  • What year is it?
  • Respect: +2320
    • View Profile
Re: Maths thread.
« Reply #318 on: February 20, 2015, 02:28:43 am »
0

1 - 1 + 1 - 1 + ...

The algebraists and geometers sometimes get up to something a bit like this.
Logged

qmech

  • Torturer
  • *****
  • Offline Offline
  • Posts: 1918
  • Shuffle iT Username: qmech
  • What year is it?
  • Respect: +2320
    • View Profile
Re: Maths thread.
« Reply #319 on: February 20, 2015, 02:49:52 am »
0

Ok, that's right I guess. You still only need a weakened form of choice, since there are <=|P(N)| classes.

If you reject choice then this is a slightly problematic statement.  With choice, given any two sets S and T, either S injects into T or T injects into S, but that needn't hold if choice is false.  So it's not always obvious which sets have cardinality below that of the continuum.

I find set theory slightly disturbing.  I'm not entirely comfortable with what it means for ZFC to have a countable model yet.  (Today's best guess is that theories that we can write down tend not to capture our intent.)
Logged

DStu

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2627
  • Respect: +1490
    • View Profile
Re: Maths thread.
« Reply #320 on: February 20, 2015, 02:59:15 am »
+3

Ok, that's right I guess. You still only need a weakened form of choice, since there are <=|P(N)| classes.
You can probably weaken it a bit further by only having choice if you are standing in a line trying to guess the color of your hat to prevent getting murdered.
Logged

Witherweaver

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 6476
  • Shuffle iT Username: Witherweaver
  • Respect: +7861
    • View Profile
Re: Maths thread.
« Reply #321 on: February 20, 2015, 09:57:42 am »
0

Ok, that's right I guess. You still only need a weakened form of choice, since there are <=|P(N)| classes.
You can probably weaken it a bit further by only having choice if you are standing in a line trying to guess the color of your hat to prevent getting murdered.

You can reject the Axiom of Choice all you want, but gun to your head, you're going to believe it.
Logged

pacovf

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3499
  • Multiediting poster
  • Respect: +3838
    • View Profile
Re: Maths thread.
« Reply #322 on: February 20, 2015, 10:06:14 am »
+1

Ok, that's right I guess. You still only need a weakened form of choice, since there are <=|P(N)| classes.
You can probably weaken it a bit further by only having choice if you are standing in a line trying to guess the color of your hat to prevent getting murdered.

You can reject the Axiom of Choice all you want, but gun to your head, you're going to believe it.

Some would say that they leave you no choice.
Logged
pacovf has a neopets account.  It has 999 hours logged.  All his neopets are named "Jessica".  I guess that must be his ex.

Polk5440

  • Torturer
  • *****
  • Offline Offline
  • Posts: 1708
  • Respect: +1788
    • View Profile
Re: Maths thread.
« Reply #323 on: February 20, 2015, 10:34:48 am »
+2

I get the feeling that those uncomfortable with the axiom of choice are really just uncomfortable with infinities. It sometimes goes against "intuition" but really, what is intuition? It's mostly learned. What's intuitive to us is very different than what was intuitive to a mathematician 500 years ago and is different than what will be intuitive for a mathematician 500 years from now.

Also, to really be uncomfortable with the axiom of choice, don't you have to be equally uncomfortable with all of the equivalent statements? Are you really also so uncomfortable with assumption that the Cartesian product of any family of nonempty sets is nonempty? 
Logged

Witherweaver

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 6476
  • Shuffle iT Username: Witherweaver
  • Respect: +7861
    • View Profile
Re: Maths thread.
« Reply #324 on: February 20, 2015, 10:44:03 am »
+3

I get the feeling that those uncomfortable with the axiom of choice are really just uncomfortable with infinities. It sometimes goes against "intuition" but really, what is intuition? It's mostly learned. What's intuitive to us is very different than what was intuitive to a mathematician 500 years ago and is different than what will be intuitive for a mathematician 500 years from now.

Also, to really be uncomfortable with the axiom of choice, don't you have to be equally uncomfortable with all of the equivalent statements? Are you really also so uncomfortable with assumption that the Cartesian product of any family of nonempty sets is nonempty?

Let's take this to the man on the street.
Logged
Pages: 1 ... 11 12 [13] 14 15 ... 47  All
 

Page created in 0.198 seconds with 21 queries.