Dominion Strategy Forum

Please login or register.

Login with username, password and session length
Pages: 1 ... 27 28 [29] 30 31 ... 47  All

Author Topic: Maths thread.  (Read 307329 times)

0 Members and 1 Guest are viewing this topic.

sudgy

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3431
  • Shuffle iT Username: sudgy
  • It's pronounced "SOO-jee"
  • Respect: +2706
    • View Profile
Re: Maths thread.
« Reply #700 on: November 06, 2016, 06:21:03 pm »
0

So, there's this game that my mom has for piano students, and a problem came up that I feel like should have a simple answer but I can't think of it.  To make it simpler, I'll turn the game into this:  You start at 0.  You roll a die with n sides.  If the number on the die is greater than the number you are at, you move to that number.  If the number on the die is less than the number you are at, you win.

So, my question is, how many turns on average does it take to win, as n tends towards infinity?  This game seems horribly unbalanced in that it should only take a couple turns to win, but what would this average be?  It seems like the type of problem where e would sneak up on you but I can't think of any way to actually solve 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

schadd

  • Jester
  • *****
  • Offline Offline
  • Posts: 892
  • Shuffle iT Username: schadd
  • Respect: +1266
    • View Profile
Re: Maths thread.
« Reply #701 on: November 06, 2016, 09:01:50 pm »
0

lower bound: 1
Logged
I thought you thought it was a slip because I said 'Jake's partners' instead of 'Roadrunner7671.'

sudgy

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3431
  • Shuffle iT Username: sudgy
  • It's pronounced "SOO-jee"
  • Respect: +2706
    • View Profile
Re: Maths thread.
« Reply #702 on: November 06, 2016, 10:53:53 pm »
0

lower bound: 1

It's actually two.  You can't win in one turn because no dice roll is less than zero.
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

schadd

  • Jester
  • *****
  • Offline Offline
  • Posts: 892
  • Shuffle iT Username: schadd
  • Respect: +1266
    • View Profile
Re: Maths thread.
« Reply #703 on: November 06, 2016, 11:21:29 pm »
0

i meant 1 after the first one
Logged
I thought you thought it was a slip because I said 'Jake's partners' instead of 'Roadrunner7671.'

pacovf

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3499
  • Multiediting poster
  • Respect: +3838
    • View Profile
Re: Maths thread.
« Reply #704 on: November 06, 2016, 11:59:03 pm »
+2

If you are rolling an n-sided die. Let's call a_k the average number of (extra) throws you need to satisfy the given condition, if the highest number you've rolled is a k. Then you have:

-> a_n = (n-1)/n + (1+a_n)/n -> a_n = n/(n-1)

-> a_k = (k-1)/n + sum_(h>=k){(1+a_h)/n}

which uh I am sure you can solve by induction, but it's late.

EDIT: a_k = n(1-1/(n-1)^(1+n-k))/(n-2), I believe, so you just do the average of all the possibilities (and add 1) to get the answer. Or replace k by 0, which is the same:

A = n(1-1/(n-1)^(n+1))/(n-2)

which tends to 1 as n->inf, which feels weird? I might be wrong.

EDIT:

Actually I was wrong, a_k = (n/(n-1))^(1+n-k)

so A = (n/(n-1))^(n+1)
« Last Edit: November 07, 2016, 12:47:19 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.

ehunt

  • Torturer
  • *****
  • Offline Offline
  • Posts: 1528
  • Shuffle iT Username: ehunt
  • Respect: +1856
    • View Profile
Re: Maths thread.
« Reply #705 on: November 07, 2016, 04:43:03 am »
+1

If you are rolling an n-sided die. Let's call a_k the average number of (extra) throws you need to satisfy the given condition, if the highest number you've rolled is a k. Then you have:

-> a_n = (n-1)/n + (1+a_n)/n -> a_n = n/(n-1)

-> a_k = (k-1)/n + sum_(h>=k){(1+a_h)/n}

which uh I am sure you can solve by induction, but it's late.

EDIT: a_k = n(1-1/(n-1)^(1+n-k))/(n-2), I believe, so you just do the average of all the possibilities (and add 1) to get the answer. Or replace k by 0, which is the same:

A = n(1-1/(n-1)^(n+1))/(n-2)

which tends to 1 as n->inf, which feels weird? I might be wrong.

EDIT:

Actually I was wrong, a_k = (n/(n-1))^(1+n-k)

so A = (n/(n-1))^(n+1)

nice! then A tends to e -- put n-1 = m to get

A = (1 + 1/m)^(m+2);

(the + 2 in the exponent doesn't affect the limit since lim (1+1/m)^2 is 1).
Logged

sudgy

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3431
  • Shuffle iT Username: sudgy
  • It's pronounced "SOO-jee"
  • Respect: +2706
    • View Profile
Re: Maths thread.
« Reply #706 on: November 29, 2016, 01:17:49 am »
0

Didn't somebody way earlier talk about factoring a negative exponent?  For instance, I was doing a problem that involved the expression "6sqrt(1+x^-2) + sqrt(1 + x^2)" and by factoring x^-2 from the first sqrt I was able to simplify it a lot.
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

SirPeebles

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3249
  • Respect: +5459
    • View Profile
Re: Maths thread.
« Reply #707 on: December 29, 2016, 12:07:37 pm »
0

Kirian is probably referring to the result from https://en.wikipedia.org/wiki/Euler_product#Notable_constants



Edit: Looks like an explanation that generalizes requires more math than I know. An easier justification is at http://www.cut-the-knot.org/proofs/AfterEulerProduct.shtml. The idea is that you start with the Leibniz formula, and note that every odd number equal to 1 mod 4 must be the product of an even number of (not necessarily distinct) primes that are 3 mod 4.


Another connection is that the Riemann Zeta function may be expressed in terms of primes, and when evaluate at s=2 you get (pi^2)/6
Logged
Well you *do* need a signature...

silverspawn

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 5301
  • Shuffle iT Username: sty.silver
  • Respect: +3191
    • View Profile
Re: Maths thread.
« Reply #708 on: December 29, 2016, 12:18:54 pm »
0

By the way, is it just me or is pi as 3,1516... a really unlikely definition and 6,303... would be more practical for most purposes, and most likely what would be done if it were defined today?

SirPeebles

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3249
  • Respect: +5459
    • View Profile
Re: Maths thread.
« Reply #709 on: December 29, 2016, 12:38:03 pm »
0

By the way, is it just me or is pi as 3,1516... a really unlikely definition and 6,303... would be more practical for most purposes, and most likely what would be done if it were defined today?

I wouldn't use either of those  ;)

But more seriously, I think that tau is often more useful for theoretical work, but for practicality it sure is a lot more convenient to measure the diameter of a circle than it is to measure the radius. Hell, even finding the center of a circle can be a pain.
« Last Edit: December 29, 2016, 12:42:23 pm by SirPeebles »
Logged
Well you *do* need a signature...

Watno

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2745
  • Shuffle iT Username: Watno
  • Respect: +2982
    • View Profile
Re: Maths thread.
« Reply #710 on: December 29, 2016, 01:08:04 pm »
0

The analytical definition actually defines pi/2.
Logged

Mic Qsenoch

  • 2015 DS Champion
  • *
  • Offline Offline
  • Posts: 1709
  • Respect: +4329
    • View Profile
Re: Maths thread.
« Reply #711 on: December 29, 2016, 01:11:18 pm »
+3

The analytical definition actually defines pi/2.

Which is a real pain because you have to add up that infinite series twice just to figure out what pi is!
Logged

SirPeebles

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3249
  • Respect: +5459
    • View Profile
Re: Maths thread.
« Reply #712 on: December 29, 2016, 01:17:50 pm »
0

The analytical definition actually defines pi/2.

Which definition are you thinking of? One of the simplest analytical definitions for "pi" that I can think of is that it is the period of any (nonzero) solution to y'' = -y. This definition yields tau.
Logged
Well you *do* need a signature...

Watno

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2745
  • Shuffle iT Username: Watno
  • Respect: +2982
    • View Profile
Re: Maths thread.
« Reply #713 on: December 29, 2016, 01:23:27 pm »
0

I was thinking of the smallest nonnegative zero of cosine.
Logged

SirPeebles

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3249
  • Respect: +5459
    • View Profile
Re: Maths thread.
« Reply #714 on: December 29, 2016, 02:48:00 pm »
0

I was thinking of the smallest nonnegative zero of cosine.

Sure, but cosine is a somewhat arbitrary function to start with. Well, it's the even part of e^x, which is kind of special.
Logged
Well you *do* need a signature...

pacovf

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3499
  • Multiediting poster
  • Respect: +3838
    • View Profile
Re: Maths thread.
« Reply #715 on: December 29, 2016, 02:57:18 pm »
+1

...are you back, or just terribly bored? Because... Welcome back!
Logged
pacovf has a neopets account.  It has 999 hours logged.  All his neopets are named "Jessica".  I guess that must be his ex.

sudgy

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3431
  • Shuffle iT Username: sudgy
  • It's pronounced "SOO-jee"
  • Respect: +2706
    • View Profile
Re: Maths thread.
« Reply #716 on: January 16, 2017, 02:12:32 am »
0

Say you are trying to prove that all natural numbers have a certain property.  You find an infinite sum where each term is a fraction of the natural numbers (and all of the numbers one fraction gives the property to only get it from that one fraction).  The sum of this infinite series of fractions is one.  Is that proof that all natural numbers have that property, or just that almost all of them do?
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 #717 on: January 16, 2017, 10:47:34 am »
0

Say you are trying to prove that all natural numbers have a certain property.  You find an infinite sum where each term is a fraction of the natural numbers (and all of the numbers one fraction gives the property to only get it from that one fraction).  The sum of this infinite series of fractions is one.  Is that proof that all natural numbers have that property, or just that almost all of them do?

What do you mean each term is a fraction of the natural numbers?  Do you mean each term is rational and positive? 

I'd be inclined to say (without giving much thought) that it depends on the property.

Edit: Err, actually no.  You only have one sequence.  Say you have sum(1/2^n, n>=2), which converges to 1.  All numerartors and denominators are of the form 2^n , but every natural number is not.

You may mean something different though.  It's hard to understand what you're trying to say.
« Last Edit: January 16, 2017, 10:52:43 am by Witherweaver »
Logged

Haddock

  • Minion
  • *****
  • Offline Offline
  • Posts: 725
  • Shuffle iT Username: Haddock
  • Doc Cod
  • Respect: +558
    • View Profile
Re: Maths thread.
« Reply #718 on: January 16, 2017, 12:43:25 pm »
0

You may mean something different though.  It's hard to understand what you're trying to say.
Logged
The best reason to lynch Haddock is the meltdown we get to witness on the wagon runup. I mean, we should totally wagon him every day just for the lulz.

M Town Wins-Losses (6-2, 75%): 71, 72, 76, 81, 83, 87 - 79, 82.  M Scum Wins-Losses (2-1, 67%): 80, 101 - 70.
RMM Town Wins-Losses (3-1, 75%): 42, 47, 49 - 31.  RMM Scum Wins-Losses (3-3, 50%): 33, 37, 43 - 29, 32, 35.
Modded: M75, M84, RMM38.     Mislynched (M-RMM): None - 42.     Correctly lynched (M-RMM): 101 - 33, 33, 35.       MVPs: RMM37, M87

sudgy

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3431
  • Shuffle iT Username: sudgy
  • It's pronounced "SOO-jee"
  • Respect: +2706
    • View Profile
Re: Maths thread.
« Reply #719 on: January 16, 2017, 01:18:13 pm »
0

Okay, for a really simple example, say you find that something gives half the numbers the property, then half of the remaining numbers that property, then half of those remaining numbers, and so on.  In this case it seems pretty obvious that all numbers have the property, so I'm wondering if that works for any infinite sum that sums to one.
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

SirPeebles

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3249
  • Respect: +5459
    • View Profile
Re: Maths thread.
« Reply #720 on: January 16, 2017, 01:23:37 pm »
+4

Okay, for a really simple example, say you find that something gives half the numbers the property, then half of the remaining numbers that property, then half of those remaining numbers, and so on.  In this case it seems pretty obvious that all numbers have the property, so I'm wondering if that works for any infinite sum that sums to one.

This would still not imply that all natural numbers have the property. Mostly because there isn't really a useful definition of "half" of a countably infinite set.
Logged
Well you *do* need a signature...

Watno

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2745
  • Shuffle iT Username: Watno
  • Respect: +2982
    • View Profile
Re: Maths thread.
« Reply #721 on: January 16, 2017, 01:29:45 pm »
+4

However, if you have a sequence of subsets of of N that covers N, and you prove a statement for each such subset, it holds for all natural numbers.
Logged

Witherweaver

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 6476
  • Shuffle iT Username: Witherweaver
  • Respect: +7861
    • View Profile
Re: Maths thread.
« Reply #722 on: January 16, 2017, 01:30:52 pm »
0

You're also making the set of numbers for which you have the property smaller... if all numbers in a set have a given property, then certainly any subset satisfies it.

Oh.. remaining.. nevermind.

But yeah, finite sure, infinitely countable it depends on what you mean.
« Last Edit: January 16, 2017, 01:32:39 pm by Witherweaver »
Logged

SirPeebles

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3249
  • Respect: +5459
    • View Profile
Re: Maths thread.
« Reply #723 on: January 16, 2017, 01:31:19 pm »
+3

This might be a more useful response. It seems that what you really want to do is put what it called a "measure" on the set of natural numbers. A measure is a way of assigning a size to each subset of numbers in such a way that the size of a disjoint union is just the sum of the sizes of of the individual subsets. In your example, you would want the measure of the full set of natural numbers to equal one, which is sometimes called a probability measure.

In this case, if you have a disjoint union of subsets whose measures sum up to one, then your subsets will indeed include all but a subset of measure zero. Now, it depends on the measure you use, but you can indeed have a nonempty set with measure zero. However, the phrase "almost all" is frequently used by mathematicians in a very precise sense to mean "all but a set of measure zero".

tl;dr

rephrasing your question in measure theoretic terms, almost all natural numbers will have your property.
Logged
Well you *do* need a signature...

sudgy

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3431
  • Shuffle iT Username: sudgy
  • It's pronounced "SOO-jee"
  • Respect: +2706
    • View Profile
Re: Maths thread.
« Reply #724 on: January 16, 2017, 01:32:37 pm »
0

Okay, for a really simple example, say you find that something gives half the numbers the property, then half of the remaining numbers that property, then half of those remaining numbers, and so on.  In this case it seems pretty obvious that all numbers have the property, so I'm wondering if that works for any infinite sum that sums to one.

This would still not imply that all natural numbers have the property. Mostly because there isn't really a useful definition of "half" of a countably infinite set.

Say first is that all even numbers have the property.
Next, all numbers 4n+1 have the property.
Next, all numbers 8n+3 have the property.
Next, all numbers 16n+7 have the property.
Next, all numbers 32n+15 have the property.

And so on.  You can represent this as 1/2 + 1/4 + 1/8 + 1/16 + 1/32 + ..., which is one.
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
Pages: 1 ... 27 28 [29] 30 31 ... 47  All
 

Page created in 0.265 seconds with 21 queries.