# Dominion Strategy Forum

• August 12, 2020, 05:06:18 am
• Welcome, Guest

### News:

DominionStrategy Wiki

Pages: 1 ... 36 37 [38] 39 40 ... 46  All

0 Members and 1 Guest are viewing this topic.

#### silverspawn

• Governor
• Offline
• Posts: 4407
• Respect: +2068
« 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.
Logged

#### navical

• Golem
• Offline
• Posts: 193
• Respect: +256
« 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
• Posts: 4407
• Respect: +2068
« 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.)
Logged

#### faust

• Margrave
• Offline
• Posts: 2688
• Respect: +3753
« 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
• Posts: 193
• Respect: +256
« 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

• Saboteur
• Offline
• Posts: 1040
• Respect: +1160
« 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
• Posts: 4407
• Respect: +2068
« 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.
Logged

#### sudgy

• Cartographer
• Offline
• Posts: 3431
• It's pronounced "SOO-jee"
• Respect: +2695
« 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
• Posts: 2740
• Respect: +2970
« 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
• Posts: 3431
• It's pronounced "SOO-jee"
• Respect: +2695
« 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
• Posts: 4407
• Respect: +2068
« 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)?
Logged

#### Watno

• Margrave
• Offline
• Posts: 2740
• Respect: +2970
« 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
• Posts: 4407
• Respect: +2068
« 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.
Logged

#### heron

• Saboteur
• Offline
• Posts: 1040
• Respect: +1160
« Reply #938 on: November 12, 2017, 10:38:48 am »
0
Logged

#### silverspawn

• Governor
• Offline
• Posts: 4407
• Respect: +2068
« Reply #939 on: October 15, 2018, 06:06:34 pm »
+2

Here's something I've been thinking about again recently

So, a while ago I tried to prove that the derivative of sin is cos using the limit calculation, that's lim h->0 [sin(x + h) - sin(x)] / h. After finishing it, I realized that I used the rule of L'hopital, so I used the fact that sin' = cos in order to prove that sin' = cos. And ofc logically speaking, sin' = cos => sin' = cos is a tautology, so it doesn't prove anything. But then I realized that it's actually still pretty strong evidence – certainly it would be strong rational evidence if you didn't know what the derivative of sin was – because if you postulate an incorrect derivative, the same calculation will most likely get you a contradiction. For example, if you postulate that sin(x)' cos(x)' = x, then what you prove is that sin'(x) = cos'(x) = x => sin(x) = 0, which is a contradiction, so it does give you a valid proof that sin(x)' or cos(x)' does not equal x.

This made me think that perhaps the correct result is the only result that would not yield a contradiction in this way. If that were true and you could somehow prove it to be true, then the tautological proof of sin' = cos would actually become a legit proof. It turns out that's not true, though, because I found two counterexamples: sin' = cos' = 0 and sin' = sin, cos' = cos both return tautologies rather than contradictions. this keeps being true if you also plug them into the limit calculation for cos(x). But I still suspect that the class of contradictions is quite small. maybe that's wrong.

It also made me think about whether this is a formally stateable question. You may not be able to ask "is there another function f such that if sin(x)' = f(x), you get a stable result doing the limit calculation with l'hopital", because if sin(x)' = f(x) for f(x) ≠ cos(x), you would have a contradiction and then everything follows, so it probably would be possible to do the calculation and conclude that sin(x)' = x => sin(x)' = x. This is the general problem of reasoning about logical uncertainty. But at the same time, it is a question that's pretty easy to understand informally. Maybe you could formulate it if you restricted the operations that are allowed, but that sounds weird.
Logged

#### ConMan

• Saboteur
• Offline
• Posts: 1377
• Respect: +1663
« Reply #940 on: October 15, 2018, 06:27:41 pm »
0

Not quite the same thing, but in one applied maths course I took the lecturer solved a problem, but at one step he pointed out that there are a bunch of conditions you're meant to check before you do it, and said "We can leave that to the pure mathematicians, we'll just get an answer and check that it works". And he did - once he reached an answer, he proved it was a solution to the original problem, and never bothered to confirm that the process he used to reach it was valid.
Logged

#### infangthief

• Moneylender
• Offline
• Posts: 151
• Respect: +315
« Reply #941 on: October 16, 2018, 04:20:41 am »
+1

I think what you're saying here is addressed by the concept of logical completeness. I'm a bit rusty on this, but here's what I recall:

A set of axioms may be complete or incomplete. Now consider throwing in a new axiom (say sin' = cos).

If the original set of axioms is complete, then the new axiom will either cause a contradiction, or the new axiom will turn out to be derivable from the other axioms.

If the original set of axioms is incomplete, then it would be possible for the new axiom to be unprovable and yet not cause a contradiction.

So what you're effectively asking is: are my axioms for limit calculation, trig functions, derivatives etc complete?
If they are complete, then any result will either be correct or can be used to generate a contradiction.
Logged
Three different people now have quotes from me as their sigs. I guess I’m quite quotable!

#### faust

• Margrave
• Offline
• Posts: 2688
• Respect: +3753
« Reply #942 on: October 16, 2018, 04:45:19 am »
+1

Then of course, for the question of completeness, we need to consider Gödel's incompleteness theorem, which states that any consistent system with arithmetic cannot be complete. The axioms of limit calculation probably need to include arithmetic rules, so your system will be incomplete; thus, it is guaranteed that there are other axioms you could add (though of course it is unclear that any of them will be of the form sin' = f).
« Last Edit: October 16, 2018, 09:50:39 am by faust »
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.

#### pacovf

• Cartographer
• Offline
• Posts: 3441
• Multiediting poster
• Respect: +3778
« Reply #943 on: October 16, 2018, 09:43:06 am »
+1

I mean, if we are getting to that point, the question is, how do you define “sin(x)”?
Logged
pacovf has a neopets account.  It has 999 hours logged.  All his neopets are named "Jessica".  I guess that must be his ex.

#### fisherman

• Steward
• Offline
• Posts: 27
• Respect: +33
« Reply #944 on: October 16, 2018, 09:56:03 am »
0

This made me think that perhaps the correct result is the only result that would not yield a contradiction in this way. If that were true and you could somehow prove it to be true, then the tautological proof of sin' = cos would actually become a legit proof.

This definitely cannot work without an independent argument showing that sin is differentiable.

For comparison, you can often argue that if a given sequence approaches a limit, then the limit has a certain value. In some cases, this will in fact be the correct limit, while in others the limit will not actually exist.
Logged

#### theorel

• Spy
• Offline
• Posts: 86
• Respect: +57
« Reply #945 on: October 16, 2018, 10:28:36 am »
+3

Here's something I've been thinking about again recently

So, a while ago I tried to prove that the derivative of sin is cos using the limit calculation, that's lim h->0 [sin(x + h) - sin(x)] / h. After finishing it, I realized that I used the rule of L'hopital, so I used the fact that sin' = cos in order to prove that sin' = cos. And ofc logically speaking, sin' = cos => sin' = cos is a tautology, so it doesn't prove anything. But then I realized that it's actually still pretty strong evidence – certainly it would be strong rational evidence if you didn't know what the derivative of sin was – because if you postulate an incorrect derivative, the same calculation will most likely get you a contradiction. For example, if you postulate that sin(x)' cos(x)' = x, then what you prove is that sin'(x) = cos'(x) = x => sin(x) = 0, which is a contradiction, so it does give you a valid proof that sin(x)' or cos(x)' does not equal x.

The other replies are good for the general question, but this specific question seems to have some interesting points in it.
First: note that applying l'Hopital to the general derivative rule produces a tautology:
lim h->0 f(x+h)-f(x)/h=lim h->0 f'(x+h)/1=f'(x).

If you restrict yourself to using the derivative of sin, then you'll get the tautology.  The reason your problem gets wonky is because you're involving the derivative of cos as well, because of the other steps involved in finding the actual solution.
Trying to solve the limit, I assume you used the addition rule for sin, and got to:
sin'(x) = lim h->0 (sin(x)*(cos(h)-1)/h)+ (cos(x)*(sin(h)/h))
Now what's interesting here is that the parts of this equation involving the limit are in fact derivatives at 0.  i.e. lim h->0 (cos(h)-1)/h=cos'(0) and lim h->0 sin(h)/h=sin'(0).
So, applying l'Hopital here is no longer a tautology, it's in fact not changing the equation at all.  So, we have an equation that tells us a relationship between sin'(x) and sin'(0) and cos'(0).  To simplify the form of the relationship let's suppose sin'(x)=f(x) and cos'(x)=g(x) we get:

f(x)=g(0)*sin(x)+f(0)*cos(x).

Now, if we evaluate this at 0 we see that f(0)=g(0)*0+f(0)*1=f(0).  So we can choose any values for f(0) and g(0) and it's valid.  So we get the full set of all solutions:
f(x)=C*sin(x)+D*cos(x).
Note that g(x) does not depend at all on f(x), so it can be whatever you want as long as you choose it first, rather than trying to arbitrarily choose both at the same time.

So, in the end it's funny because using l'Hopital on the derivative rule produces a tautology, but using it on this modified form does not produce a tautology, but actually just expresses what's already true.  The "tautology" element comes from the f(0) evaluation above, but the produced equation is actually a pretty tight constraint on the form of sin'(x).
« Last Edit: October 16, 2018, 10:32:47 am by theorel »
Logged

#### gamesou

• Apprentice
• Offline
• Posts: 291
• Respect: +337
« Reply #946 on: November 13, 2018, 07:15:02 am »
+3

A quick math riddle involving fruits

Logged
Designer of Chronos Conquest

#### silverspawn

• Governor
• Offline
• Posts: 4407
• Respect: +2068
« Reply #947 on: November 13, 2018, 09:37:15 am »
0

Disclaimer: the riddle is very hard and the smallest correct numbers have 20+ digits. Far fewer than 5% of all people could solve this.
Logged

#### Iridium

• Swindler
• Offline
• Posts: 18
• Respect: +7
« Reply #948 on: November 13, 2018, 04:27:04 pm »
0

How would you even start solving it? I haven't graduated high school yet, but I know at least up through Calc II, so I figured I would be qualified to post in this thread.

But still, I have no idea how to even start.
« Last Edit: November 13, 2018, 06:58:42 pm by Iridium »
Logged

#### ThetaSigma12

• Torturer
• Offline
• Posts: 1681
• Respect: +1790