Dominion Strategy Forum

Please login or register.

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

Author Topic: Maths thread.  (Read 96483 times)

0 Members and 1 Guest are viewing this topic.

Watno

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2729
  • Shuffle iT Username: Watno
  • Respect: +2947
    • View Profile
Re: Maths thread.
« Reply #75 on: May 10, 2014, 09:49:09 am »
+9

We should petition theory to enable Latex code for this thread :P
« Last Edit: May 10, 2014, 09:53:09 am by Watno »
Logged

qmech

  • Torturer
  • *****
  • Offline Offline
  • Posts: 1918
  • Shuffle iT Username: qmech
  • What year is it?
  • Respect: +2314
    • View Profile
Re: Maths thread.
« Reply #76 on: May 10, 2014, 09:57:29 am »
0

Unicode has an ℝ, but it doesn't look right without serifs...
Logged

pacovf

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3386
  • Multiediting poster
  • Respect: +3719
    • View Profile
Re: Maths thread.
« Reply #77 on: May 10, 2014, 11:10:01 am »
0

Is the solution constructive?
Logged
pacovf has a neopets account.  It has 999 hours logged.  All his neopets are named "Jessica".  I guess that must be his ex.

qmech

  • Torturer
  • *****
  • Offline Offline
  • Posts: 1918
  • Shuffle iT Username: qmech
  • What year is it?
  • Respect: +2314
    • View Profile
Re: Maths thread.
« Reply #78 on: May 10, 2014, 11:19:20 am »
+1

Is the solution constructive?

Good question.
Logged

sitnaltax

  • Apprentice
  • *****
  • Offline Offline
  • Posts: 275
  • Respect: +469
    • View Profile
Re: Maths thread.
« Reply #79 on: May 10, 2014, 11:25:22 am »
0

My attempts to use pennies, pen, and notebook to come up with a counterexample say yes, but I'll keep working on it. Because clearly if the answer is yes, the follow-up is to find the smallest number of marks/disks for which the answer is no.
Logged

heron

  • Saboteur
  • *****
  • Offline Offline
  • Posts: 1023
  • Shuffle iT Username: heron
  • Respect: +1147
    • View Profile
Re: Maths thread.
« Reply #80 on: May 10, 2014, 11:28:28 am »
0

My attempts to use pennies, pen, and notebook to come up with a counterexample say yes, but I'll keep working on it. Because clearly if the answer is yes, the follow-up is to find the smallest number of marks/disks for which the answer is no.

If you have one more mark than disks, you will not always be able to cover all of the marks since they could be really far apart.
Logged

DStu

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2627
  • Respect: +1487
    • View Profile
Re: Maths thread.
« Reply #81 on: May 10, 2014, 11:45:53 am »
+1

Is the solution constructive?

Obviously not, because
Quote
The solution is a very neat trick which is tremendously useful when doing real maths.
Logged

blueblimp

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2784
  • Respect: +1507
    • View Profile
Re: Maths thread.
« Reply #82 on: May 10, 2014, 12:26:40 pm »
+1

Love this solution, but I think there is a minor bug:

When picking X and Y, they can't just be any two points on the convex hull. For example, consider a convex hull that's a large regular polygon, where X and Y are adjacent. Then the line perpendicular to XY, passing through X, would also pass through the interior of the convex hull. Putting some requirement about X and Y being "opposite" points (whatever that means) would work, but I think there's an easier fix that also more easily handles the case of two points on the line.

In the case where all points on the convex hull are red, sort the points by (ascending) x-coordinate, breaking ties by (ascending) y-coordinate. Observe that the first and last points in this ordering are on the convex hull, and thus both red. Also observe that, for any division of this ordering into a prefix and suffix, the convex hull of the prefix does not intersect the convex hull of the suffix. (I don't know a great way to prove this formally, but it's pretty obvious given the ordering we chose.)

Then, use the same sweeping argument. The prefix of length 1 has more red points than orange points, and the prefix of length 2n-1 has more orange points than red points. Hence there exists a prefix with an equal number of red points and orange points, which means the corresponding suffix has an equal number of each colour too. That falls into the inductive case.

One reason that I like your solution because it gives an algorithm that's obviously polynomial time. Computing the convex hull and sweeping is O(n log n). Because we don't have control over how we split the point set for induction, the overall algorithm can be O(n^2 log n). (It's easy to construct an example where the prefix is length 2 for most of the recursive steps.)
Logged

sitnaltax

  • Apprentice
  • *****
  • Offline Offline
  • Posts: 275
  • Respect: +469
    • View Profile
Re: Maths thread.
« Reply #83 on: May 10, 2014, 12:51:04 pm »
0

My attempts to use pennies, pen, and notebook to come up with a counterexample say yes, but I'll keep working on it. Because clearly if the answer is yes, the follow-up is to find the smallest number of marks/disks for which the answer is no.

If you have one more mark than disks, you will not always be able to cover all of the marks since they could be really far apart.

Of course. I took it as a given that the number of marks and disks is the same. (In fact, I assume that the limited number of disks is a sort of red herring w.r.t. the interesting part of the riddle, and the key is to find the smallest number of points that cannot be covered with any number of disks.)
Logged

liopoil

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2587
  • Respect: +2476
    • View Profile
Re: Maths thread.
« Reply #84 on: May 10, 2014, 12:58:53 pm »
0

well having more circles can't possibly help you...
Logged

Polk5440

  • Torturer
  • *****
  • Offline Offline
  • Posts: 1708
  • Respect: +1782
    • View Profile
Re: Maths thread.
« Reply #85 on: May 10, 2014, 01:02:04 pm »
+4

Discs and tablecloth: Oscar needs more than 10 points to thwart me. The circles can jiggle around too much.

Is that a mathy enough answer for ya'?

No? Ok.

Here's the outline of my proof:

0) Oscar secretly places the points on the table trying to thwart me. I have no idea where they are.
1) I tile the table with infinite number of discs such that they are maximally dense and give the tiling a good spin so that what I've covered is uniformly random.
2) Let Ei be the event that I covered point i (i = 1,2,...,10).
3) I have covered all ten points with probability Pr(E1 & E2 & E3 & ... & E10).
3a) Pr(E1 & E2 & E3 & ... & E10) = 1 - Pr(notE1 or notE2 or notE3 or ... or notE10) >= 1 - Pr(notE1) - Pr(notE2) - ... - Pr(notE10) > 0 (see detail)
4) The probability I have covered the 10 points is positive, so there is some way to cover those 10 points no matter how Oscar places them (pick one and call it the special tiling).
5) What, so we're only allowed to use 10 discs? Remove discs from the special tiling which do not cover a point. We must be left with 10 or fewer discs.

Detail: Pr(notEi) = 1 - pi/(2*sqrt(3)) or approximately .09. To see this, draw equilateral triangles over the circle tiling such that the center of the circles are the vertices of the triangles. Each triangle has area  sqrt(3)*r^2. Each triangle is covered by half a circle, area pi*r^2/2. The ratio is pi/(2*sqrt(3)). The ratio of empty space to covered space in the tiling is thus 1 - pi/(2*sqrt(3)).


I should not have spent my morning on this.....
Logged

heron

  • Saboteur
  • *****
  • Offline Offline
  • Posts: 1023
  • Shuffle iT Username: heron
  • Respect: +1147
    • View Profile
Re: Maths thread.
« Reply #86 on: May 10, 2014, 01:05:01 pm »
0

I think that that does not work because The probabilities are not independent.
Logged

Kirian

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 7089
  • Shuffle iT Username: Kirian
  • An Unbalanced Equation
  • Respect: +9359
    • View Profile
Re: Maths thread.
« Reply #87 on: May 10, 2014, 01:05:04 pm »
0

My attempts to use pennies, pen, and notebook to come up with a counterexample say yes, but I'll keep working on it. Because clearly if the answer is yes, the follow-up is to find the smallest number of marks/disks for which the answer is no.

If you have one more mark than disks, you will not always be able to cover all of the marks since they could be really far apart.


I assume he meant N disks and N points, and determine the smallest N where the answer is no.

I can definitely prove for N <= 3, but I'm not sure if this can be generalized.  Also all of my notation is lay mathematician.

Consider disks of diameter D.  Any given two points are either distance d < D apart, or d >= D apart.

If all three pairs of points have d >= D, then they can and must be covered by three separate disks. The smallest possible configuration for this is an equilateral triangle of side D. The three covering disks can have their centers on each point, each tangent to the other two disks; they can also be spaced farther apart if desired.  If any one point is more distant than D from the other two, then the third disk can be placed even farther away.

If any pair of points are < D apart, that pair can be covered by just one disk.  Any third point is either covered by this disk, or can be covered by a second disk at worst tangent to the first disk.


Intuitively, this ought to generalize to any N.  But I think I lack the ability to prove that.
Logged
Kirian's Law of f.DS jokes:  Any sufficiently unexplained joke is indistinguishable from serious conversation.

pacovf

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3386
  • Multiediting poster
  • Respect: +3719
    • View Profile
Re: Maths thread.
« Reply #88 on: May 10, 2014, 01:09:59 pm »
0

My attempts to use pennies, pen, and notebook to come up with a counterexample say yes, but I'll keep working on it. Because clearly if the answer is yes, the follow-up is to find the smallest number of marks/disks for which the answer is no.

Maybe the real question (EDIT: as stated by Kirian) is what the smallest number of marks where you cannot always cover them with plates is, and there's some sort of weird argument that lets you find that number in some sort of "orthogonal" reasoning that doesn't actually care much for the premise of the problem.

And he mentions 10 specifically just because some mathematicians like visualizing people getting frustrated over pencils and pennies. Which means that my money is currently on "yes", since otherwise someone might stumble over a counterexample.

@Kirian: it can't be generalized to any N. With N high enough, you can (locally) put the marks in a dense lattice, which means that some marks will fall in between three plates if the lattice is dense (and large) enough. Also if d >= D but d < 2D, you must cover the points with differents plates, but you can't necessarily do that when there are more than three points.
« Last Edit: May 10, 2014, 01:12:13 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.

Polk5440

  • Torturer
  • *****
  • Offline Offline
  • Posts: 1708
  • Respect: +1782
    • View Profile
Re: Maths thread.
« Reply #89 on: May 10, 2014, 01:11:26 pm »
+2

I think that that does not work because The probabilities are not independent.

But Pr(A or B) = Pr(A) + Pr(B) - Pr(A and B) <= Pr(A) + Pr(B), so I'm okay, I think.
Logged

SirPeebles

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3247
  • Respect: +5447
    • View Profile
Re: Maths thread.
« Reply #90 on: May 10, 2014, 01:17:16 pm »
0

I would take some plates.  Place one on the plane, then arrange six tangent plates around this central one in a hexagonal pattern.  This would leave six symmetrically arranged "triangular" gaps.  I would place a mark at the center of each of these seven plates and then one at the center every other (i.e., alternating) gaps.  This would give me ten points, and I doubt that you can cover all ten.  So I haven't worked out a proof, but I suspect that the answer is that you cannot cover this arrangement of ten.
Logged
Well you *do* need a signature...

pacovf

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3386
  • Multiediting poster
  • Respect: +3719
    • View Profile
Re: Maths thread.
« Reply #91 on: May 10, 2014, 01:22:33 pm »
0

yep I am stupid and I do not know how to read.
« Last Edit: May 10, 2014, 01:30:29 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.

Polk5440

  • Torturer
  • *****
  • Offline Offline
  • Posts: 1708
  • Respect: +1782
    • View Profile
Re: Maths thread.
« Reply #92 on: May 10, 2014, 01:24:26 pm »
+1

I would take some plates.  Place one on the plane, then arrange six tangent plates around this central one in a hexagonal pattern.  This would leave six symmetrically arranged "triangular" gaps.  I would place a mark at the center of each of these seven plates and then one at the center every other (i.e., alternating) gaps.  This would give me ten points, and I doubt that you can cover all ten.  So I haven't worked out a proof, but I suspect that the answer is that you cannot cover this arrangement of ten.

Jiggle the plates. You can cover it. Cover each gap point with a plate that also covers one center point. Make sure one of these center points is the center circle. You have 4 points left which you can easily cover with 4 more plates.
Logged

Polk5440

  • Torturer
  • *****
  • Offline Offline
  • Posts: 1708
  • Respect: +1782
    • View Profile
Re: Maths thread.
« Reply #93 on: May 10, 2014, 01:26:07 pm »
0

Discs and tablecloth: Oscar needs more than 10 points to thwart me. The circles can jiggle around too much.

Is that a mathy enough answer for ya'?

No? Ok.

Here's the outline of my proof:

0) Oscar secretly places the points on the table trying to thwart me. I have no idea where they are.
1) I tile the table with infinite number of discs such that they are maximally dense and give the tiling a good spin so that what I've covered is uniformly random.
2) Let Ei be the event that I covered point i (i = 1,2,...,10).
3) I have covered all ten points with probability Pr(E1 & E2 & E3 & ... & E10).
3a) Pr(E1 & E2 & E3 & ... & E10) = 1 - Pr(notE1 or notE2 or notE3 or ... or notE10) >= 1 - Pr(notE1) - Pr(notE2) - ... - Pr(notE10) > 0 (see detail)
4) The probability I have covered the 10 points is positive, so there is some way to cover those 10 points no matter how Oscar places them (pick one and call it the special tiling).
5) What, so we're only allowed to use 10 discs? Remove discs from the special tiling which do not cover a point. We must be left with 10 or fewer discs.

Detail: Pr(notEi) = 1 - pi/(2*sqrt(3)) or approximately .09. To see this, draw equilateral triangles over the circle tiling such that the center of the circles are the vertices of the triangles. Each triangle has area  sqrt(3)*r^2. Each triangle is covered by half a circle, area pi*r^2/2. The ratio is pi/(2*sqrt(3)). The ratio of empty space to covered space in the tiling is thus 1 - pi/(2*sqrt(3)).


I should not have spent my morning on this.....

Pr(E1&E2&E3...) = 1 - Pr(notE1) - Pr(E1| notE2) - Pr(E1&E2| notE3) - ..., so I am afraid that your result is not correct. If you manage to prove it in a way that is independent of N, you should assume that you've made a mistake somewhere.

But I have to say that I really like your argument.

My argument does not work for n > 10. 1 - 10*.9 > 0 but 1 - 11*.9 < 0 and the proof fails.
Logged

qmech

  • Torturer
  • *****
  • Offline Offline
  • Posts: 1918
  • Shuffle iT Username: qmech
  • What year is it?
  • Respect: +2314
    • View Profile
Re: Maths thread.
« Reply #94 on: May 10, 2014, 01:30:03 pm »
+1


My preferred phrasing is that the average number of points uncovered is less than 1, so that there must exist some configuration where 0 points are uncovered.

This is a prototypical application of the probabilistic method.
Logged

heron

  • Saboteur
  • *****
  • Offline Offline
  • Posts: 1023
  • Shuffle iT Username: heron
  • Respect: +1147
    • View Profile
Re: Maths thread.
« Reply #95 on: May 10, 2014, 01:32:17 pm »
0

I think that that does not work because The probabilities are not independent.

But Pr(A or B) = Pr(A) + Pr(B) - Pr(A and B) <= Pr(A) + Pr(B), so I'm okay, I think.

Of course, you are correct. I believe then that this neat trick is called the probabilistic method.

edit: ninja'd
Logged

Polk5440

  • Torturer
  • *****
  • Offline Offline
  • Posts: 1708
  • Respect: +1782
    • View Profile
Re: Maths thread.
« Reply #96 on: May 10, 2014, 01:33:24 pm »
0


My preferred phrasing is that the average number of points uncovered is less than 1, so that there must exist some configuration where 0 points are uncovered.

This is a prototypical application of the probabilistic method.


Oh, okay. I was trying to phrase it like a pigeonhole principle thing.
Logged

heron

  • Saboteur
  • *****
  • Offline Offline
  • Posts: 1023
  • Shuffle iT Username: heron
  • Respect: +1147
    • View Profile
Re: Maths thread.
« Reply #97 on: May 10, 2014, 01:37:25 pm »
+4

I will now post a more straightforward problem, from the 2009 Harvard-MIT Maths Tournament.

Let f(x) = x^4 + ax^3 + bx^2 + cx + d be a polynomial with 4 negative integer roots. If a + b + c + d = 2009, what is the value of d?

None of me or my friends were able to solve it fast enough, but the solution is quite clever.
Logged

qmech

  • Torturer
  • *****
  • Offline Offline
  • Posts: 1918
  • Shuffle iT Username: qmech
  • What year is it?
  • Respect: +2314
    • View Profile
Re: Maths thread.
« Reply #98 on: May 10, 2014, 01:49:28 pm »
0

Very nice!
Logged

SirPeebles

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

I will now post a more straightforward problem, from the 2009 Harvard-MIT Maths Tournament.

Let f(x) = x^4 + ax^3 + bx^2 + cx + d be a polynomial with 4 negative integer roots. If a + b + c + d = 2009, what is the value of d?

None of me or my friends were able to solve it fast enough, but the solution is quite clever.

f(x) = (x+r1)(x+r2)(x+r3)(x+r4) for positive integers r1, ..., r4.
f(1) = 1 + a + b + c  + d = 1 + 2009 = 2010 = 2*3*5*67. [Each is prime, so this is the only way to write it as a product of four integers greater than one.]
f(1) = (1+r1)(1+r2)(1+r3)(1+r4)

So r1 = 1, r2 = 2, r3 = 4, r4 = 66.

And d = f(0) = r1*r2*r3*r4 = 1*2*4*66 = 528
Logged
Well you *do* need a signature...

Pages: 1 2 3 [4] 5 6 ... 42  All
 

Page created in 0.151 seconds with 21 queries.