Dominion Strategy Forum

Please login or register.

Login with username, password and session length
Pages: 1 ... 36 37 [38]  All

Author Topic: Maths thread.  (Read 84046 times)

0 Members and 1 Guest are viewing this topic.

silverspawn

  • Governor
  • *****
  • Offline Offline
  • Posts: 4021
  • Shuffle iT Username: sty.silver
  • ♦ Twilight ♦
  • Respect: +1768
    • View Profile
Re: Maths thread.
« Reply #925 on: November 05, 2017, 03:55:07 am »
0

This is probably an easy problem, but what is

sum(k from 0 to n) [(k+1) * (k out of n)]

I figured it can be rewritten as sum (k from 0 to n (k out of n)) + sum (k from 1 to n (k out of n)) + ... + sum (k from n to n (k out of n)) but couldn't solve that either.

navical

  • Golem
  • ****
  • Offline Offline
  • Posts: 186
  • Respect: +236
    • View Profile
Re: Maths thread.
« Reply #926 on: November 05, 2017, 04:19:32 am »
0

What do you mean by "k out of n"? Is it "n choose k" i.e. n!/(k!(n-k)!)?
Logged

silverspawn

  • Governor
  • *****
  • Offline Offline
  • Posts: 4021
  • Shuffle iT Username: sty.silver
  • ♦ Twilight ♦
  • Respect: +1768
    • View Profile
Re: Maths thread.
« Reply #927 on: November 05, 2017, 04:51:29 am »
0

yes. (In german we say "n over k" because that's how the operator looks, but that's understood as n/k in english, so I used "k out of n" because that's what it counts.)

faust

  • Torturer
  • *****
  • Offline Offline
  • Posts: 1972
  • Shuffle iT Username: faust
  • Respect: +2761
    • View Profile
Re: Maths thread.
« Reply #928 on: November 05, 2017, 08:34:30 am »
0

Well, the sum over all (n choose k) is 2^n, I feel like that should be part of the solution.

Thus, you can rewrite to 2^n+2^n-(n choose 0)+2^n-(n choose 0)-(n choose 1)+... or in other words n*2^n-sum(k from 0 to n-1) (n-1-k)*(n choose k)

Also (n choose k)=(n-1 choose k-1)+(n-1 choose k)

Thus you can rewrite the above sum and should be able to progress in some inductive manner I believe.
Logged
Since the number of points is within a constant factor of the number of city quarters, in the long run we can get (4 - ε) ↑↑ n points in n turns for any ε > 0.

navical

  • Golem
  • ****
  • Offline Offline
  • Posts: 186
  • Respect: +236
    • View Profile
Re: Maths thread.
« Reply #929 on: November 05, 2017, 10:26:15 am »
+1

If you call the original sum S_n then using (n choose k) = (n-1 choose k-1) + (n-1 choose k) you can get a recurrence relation S_n = 2S_{n-1} + 2^{n-1}. This has closed form S_n = (n+2)*2^{n-1} which you can prove by induction.
Logged

heron

  • Jester
  • *****
  • Offline Offline
  • Posts: 988
  • Shuffle iT Username: heron
  • Respect: +1112
    • View Profile
Re: Maths thread.
« Reply #930 on: November 05, 2017, 11:35:12 am »
+2

The given sum is the number of ways to color a group of n points with red, green, and blue such that at most one point is colored red (think of each term as selecting k points to color green, and then choosing either one of those k points or no point to be red, and coloring the rest blue).

The number of ways to color points in that fashion is 2^(n-1) * n + 2^n = 2^(n-1) * (n + 2) as navical computed.
The first term is the number of ways if there is a red point, and the second term is the number of ways if there is no red point.
Logged

silverspawn

  • Governor
  • *****
  • Offline Offline
  • Posts: 4021
  • Shuffle iT Username: sty.silver
  • ♦ Twilight ♦
  • Respect: +1768
    • View Profile
Re: Maths thread.
« Reply #931 on: November 05, 2017, 01:05:54 pm »
+1

Well, the sum over all (n choose k) is 2^n, I feel like that should be part of the solution.

Thus, you can rewrite to 2^n+2^n-(n choose 0)+2^n-(n choose 0)-(n choose 1)+... or in other words n*2^n-sum(k from 0 to n-1) (n-1-k)*(n choose k)
I did try that, but I didn't get any further than the above, because I didn't see how to handle the negative sums any better than the original sum.

The given sum is the number of ways to color a group of n points with red, green, and blue such that at most one point is colored red (think of each term as selecting k points to color green, and then choosing either one of those k points or no point to be red, and coloring the rest blue).

The number of ways to color points in that fashion is 2^(n-1) * n + 2^n = 2^(n-1) * (n + 2) as navical computed.
The first term is the number of ways if there is a red point, and the second term is the number of ways if there is no red point.

That is a really smart and intuitive explanation. Thanks.

It took me a few minutes to figure out how you get from that to the formula but I think I got it. We do 2 cases separately: there is a red point, then first choose that (n) then have 2 choices for any other point (* 2^(n-1)) or there is no red point, then just have 2 choices for each point (+ 2^n). Those cases are disjoint and exhaustive.

sudgy

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3288
  • Shuffle iT Username: sudgy
  • It's pronounced "SOO-jee"
  • Respect: +2522
    • View Profile
Re: Maths thread.
« Reply #932 on: November 05, 2017, 03:15:08 pm »
0

Here's another one:

Say you have a set S of sets, where each subset has size N.  What is the maximum size of S for a given N such that for all pairs of sets in S, they share exactly one element?  My brother and I have figured out that the upper bound is N * (N - 1) + 1, and have verified that that is the case for N = 1, 2, and 3, but haven't found a way to show that that is the answer.

EDIT: Read below, this isn't quite perfect.
« Last Edit: November 05, 2017, 06:32:58 pm by sudgy »
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

Watno

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2688
  • Shuffle iT Username: Watno
  • Respect: +2867
    • View Profile
Re: Maths thread.
« Reply #933 on: November 05, 2017, 04:35:12 pm »
+3

I think you missed some restriction in the question, because you can get an arbitrary size for S when N> 1  (by having each s \in S consist of a common element x_0 and further elements x^s_1, ..., x^s_N, where all the x^M_i are different).
« Last Edit: November 05, 2017, 04:36:30 pm by Watno »
Logged

sudgy

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3288
  • Shuffle iT Username: sudgy
  • It's pronounced "SOO-jee"
  • Respect: +2522
    • View Profile
Re: Maths thread.
« Reply #934 on: November 05, 2017, 06:12:39 pm »
0

I think you missed some restriction in the question, because you can get an arbitrary size for S when N> 1  (by having each s \in S consist of a common element x_0 and further elements x^s_1, ..., x^s_N, where all the x^M_i are different).

Oh crap, you're right.  Each element needs to be in the same number of sets.

EDIT: Now that I think of it, this might not work either.  I feel like saying that each element needs to be in more than one set could work too, but I'm not sure if that stops the infinite answer.
« Last Edit: November 05, 2017, 06:32:41 pm by sudgy »
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

silverspawn

  • Governor
  • *****
  • Offline Offline
  • Posts: 4021
  • Shuffle iT Username: sty.silver
  • ♦ Twilight ♦
  • Respect: +1768
    • View Profile
Re: Maths thread.
« Reply #935 on: November 11, 2017, 08:57:13 am »
0

which theorem (I'm sure it exists but I can't find it) states that for a general triangle split like this



it holds that c^2 = p*(p+q)?

Watno

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2688
  • Shuffle iT Username: Watno
  • Respect: +2867
    • View Profile
Re: Maths thread.
« Reply #936 on: November 11, 2017, 09:10:28 am »
0

I think that statement is false (consider the case where q=0).

In the case of a right triangle, it's an easy consequence of the pythagorean theorem and https://en.wikipedia.org/wiki/Geometric_mean_theorem (Höhensatz in German)
« Last Edit: November 11, 2017, 09:15:56 am by Watno »
Logged

silverspawn

  • Governor
  • *****
  • Offline Offline
  • Posts: 4021
  • Shuffle iT Username: sty.silver
  • ♦ Twilight ♦
  • Respect: +1768
    • View Profile
Re: Maths thread.
« Reply #937 on: November 11, 2017, 09:33:05 am »
0

aw. I needed it to prove that the triangle is a right triangle and I remembered it from somewhere. well in that case that does not work. thanks.

heron

  • Jester
  • *****
  • Offline Offline
  • Posts: 988
  • Shuffle iT Username: heron
  • Respect: +1112
    • View Profile
Re: Maths thread.
« Reply #938 on: November 12, 2017, 10:38:48 am »
0

Logged
Pages: 1 ... 36 37 [38]  All
 

Page created in 0.114 seconds with 20 queries.