# Dominion Strategy Forum

• June 22, 2017, 11:31:00 pm
• Welcome, Guest

### News:

DominionStrategy Wiki

Pages: 1 2 3 ... 35 [All]

0 Members and 1 Guest are viewing this topic.

#### Ozle

• Cartographer
• Offline
• Posts: 3625
• Sorry, this text is personal.
• Respect: +3329
« on: May 08, 2014, 04:04:21 pm »
+3

Yeah so let's talk about maths....
Logged
Try the Ozle Google Map Challenge!
http://forum.dominionstrategy.com/index.php?topic=7466.0

Sullying players Enjoyment of Innovation since 2013 Apparently!

#### Awaclus

• Offline
• Posts: 9098
• (´｡• ω •｡)
• Respect: +8883
« Reply #1 on: May 08, 2014, 04:05:47 pm »
+2

Shouldn't this be on the Innovation forum?

#### sudgy

• Cartographer
• Online
• Posts: 3120
• It's pronounced "SOO-jee"
• Respect: +2285
« Reply #2 on: May 08, 2014, 04:27:06 pm »
+2

Actually, this might be a good idea.  It takes over the random stuff thread a lot.

Can anyone show me why the solution to y'' = -y is A*sin(x) + B*cos(x)?  It might be too complicated for me, but I'm still curious.  I can see that it needs to be sinusoidal, and that that equation is a solution, but how do you derive 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

#### DStu

• Margrave
• Offline
• Posts: 2627
• Respect: +1476
« Reply #3 on: May 08, 2014, 04:31:06 pm »
0

Actually, this might be a good idea.  It takes over the random stuff thread a lot.

Can anyone show me why the solution to y'' = -y is A*sin(x) + B*cos(x)?  It might be too complicated for me, but I'm still curious.  I can see that it needs to be sinusoidal, and that that equation is a solution, but how do you derive it?
In my analysis course, we proved that the solution is unique (given starting point and derivative), and defined sin/cos as the solution...
Logged

#### Axxle

• Torturer
• Offline
• Posts: 1664
• Most Valuable Serial Killer
• Respect: +1921
« Reply #4 on: May 08, 2014, 04:33:43 pm »
+4

Is maths anything like math?
Logged
We might be from all over the world, but "we all talk this one language  : +1 card + 1 action +1 buy , gain , discard, trash... " - RTT

#### Ozle

• Cartographer
• Offline
• Posts: 3625
• Sorry, this text is personal.
• Respect: +3329
« Reply #5 on: May 08, 2014, 04:44:56 pm »
+2

Is maths anything like math?

yes it's the proper short form of mathematics
Logged
Try the Ozle Google Map Challenge!
http://forum.dominionstrategy.com/index.php?topic=7466.0

Sullying players Enjoyment of Innovation since 2013 Apparently!

#### qmech

• Torturer
• Offline
• Posts: 1915
• Works with high probability
• Respect: +2288
« Reply #6 on: May 08, 2014, 04:53:44 pm »
+3

Actually, this might be a good idea.  It takes over the random stuff thread a lot.

Can anyone show me why the solution to y'' = -y is A*sin(x) + B*cos(x)?  It might be too complicated for me, but I'm still curious.  I can see that it needs to be sinusoidal, and that that equation is a solution, but how do you derive it?

The best way to see it is if you already know a little bit about exponentials.  The derivative of exp(kx) is k.exp(kx), for any k.  So the second derivative of exp(kx) is k^2.exp(kx).  So you get a solution if k^2 = 1, i.e. if k = +-i.  So for any constant A and B, A.exp(ix) + B.exp(-ix) is a solution.  This happens to be equivalent to your expression with sines and cosines (with a different A and B).

The reason why these are all the solutions is that the solution space is two-dimensional.  This is perhaps believable because you get one arbitrary constant from each of the implicit integrations, but showing it formally might be a bit beyond you right now.  (I can't remember how to do it offhand.)

[Aside that might be better ignored: you've almost certainly only be told that it means for a function from R to R to be differentiable, so my example that brings in complex numbers is a bit of a cheat.  It does go to the heart of the matter though: it's not so much of an exaggeration to say that making that kind of argument work is the main reason physicists and engineers care about complex numbers.]
« Last Edit: May 08, 2014, 05:02:18 pm by qmech »
Logged

#### SirPeebles

• Cartographer
• Offline
• Posts: 3247
• Respect: +5403
« Reply #7 on: May 08, 2014, 04:54:30 pm »
+2

Actually, this might be a good idea.  It takes over the random stuff thread a lot.

Can anyone show me why the solution to y'' = -y is A*sin(x) + B*cos(x)?  It might be too complicated for me, but I'm still curious.  I can see that it needs to be sinusoidal, and that that equation is a solution, but how do you derive it?

One way to derive it is to use Euler's formula!

Suppose we already know how to solve y' = k y to get y = e^(kt).  Then e^(kt) is also a solution to the equation y'' = k^2 y.  But of course so is e^(-kt).  It turns out that if y1 and y2 are both solutions to y'' = k^2 y, then so is A*y1 + B*y2 for any constants A and B (a differential equation with this property is called a homogeneous linear equation).  So A*e^(kt) + B*e^(-kt) is a solution to y'' = k^2 y.  To get your equation, just choose k = i.  So the solutions are A*e^(it) + B*e^(-it).  If A=B=1/2, you get cos(t).  If A= 1/(2i) and B = -1/(2i), you get sin(t).

edit:  ninja'd by qmech.  one way to get some intution for why that gives all solutions is that having these two parameters A and B provides precisely enough space to have a unique solution matching any pair of initial conditions of y(0) and y'(0).  Physically, y'' = - y models the motion of a ball hanging on a spring, and for any initial position and initial velocity there is "obviously" a unique motion which unfolds.
« Last Edit: May 08, 2014, 04:58:35 pm by SirPeebles »
Logged
Well you *do* need a signature...

#### heron

• Jester
• Offline
• Posts: 970
• Respect: +1089
« Reply #8 on: May 08, 2014, 04:59:48 pm »
+5

Maths competitions is pretty much my biggest hobby, although currently I'm a little burned out after the USA Junior Maths Olympiad.

My favorite subject is combinatorics, and least favorite is geometry. The only way that I can solve geometry problems is plotting the figure into the complex plane.

Here is a fun maths problem: Let n be a natural number. 2n distinct points are plotted in the plane. Half of them are colored red, and the other half are colored orange. The points are then divided into n pairs, each with 1 red and 1 orange point. Then, a line segment is drawn between the 2 points in each pair. Prove that there is a way to pair the points such that after the line segments are drawn, none of the line segments intersect each other.
Logged
PPR is for wimps.

#### sudgy

• Cartographer
• Online
• Posts: 3120
• It's pronounced "SOO-jee"
• Respect: +2285
« Reply #9 on: May 08, 2014, 05:13:34 pm »
+1

One way to derive it is to use Euler's formula!

The reason I was asking was because the derivation of Euler's formula that I saw used it at a part...
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

#### LastFootnote

• Online
• Posts: 6419
• Respect: +8258
« Reply #10 on: May 08, 2014, 05:14:38 pm »
+2

Is maths anything like math?

yes it's the proper short form of mathematics

I disagree!

*drives off*
Logged

#### SirPeebles

• Cartographer
• Offline
• Posts: 3247
• Respect: +5403
« Reply #11 on: May 08, 2014, 05:27:41 pm »
+1

One way to derive it is to use Euler's formula!

The reason I was asking was because the derivation of Euler's formula that I saw used it at a part...

Yeah.  This is how I proved Euler's Formula in my differential equations class a few months ago.

In general, there is no such thing as "the definition" of a mathematical object like sine.  Rather, there is a web of equivalent statements, any one of which can be used as "the definition".  So to prove it in an entirely satisfactory way, I would need to know the definition you are starting with.

Another way to solve the equation y'' = -y is to search for a power series solution.  Suppose we want the solution which matches y(0) = 0, y'(0) = 1.  Then
y = 0 + x + a2 x^2 + a3 x^3 + ...
y'' = 2 a2 + 2*3 a3 x + 3*4 a4 x^2 + ...

Since we want y'' = -y, we match up coefficients and solve.  You'll arrive at the Taylor series for sin(x).
Logged
Well you *do* need a signature...

#### qmech

• Torturer
• Offline
• Posts: 1915
• Works with high probability
• Respect: +2288
« Reply #12 on: May 08, 2014, 05:34:14 pm »
+1

Here is a fun maths problem:

I assume the points should be in general position?

Here's another: is it always possible to cover 10 marks on a white table cloth with 10 plates that cannot overlap?
Logged

#### sudgy

• Cartographer
• Online
• Posts: 3120
• It's pronounced "SOO-jee"
• Respect: +2285
« Reply #13 on: May 08, 2014, 05:36:57 pm »
+1

One way to derive it is to use Euler's formula!

The reason I was asking was because the derivation of Euler's formula that I saw used it at a part...

Yeah.  This is how I proved Euler's Formula in my differential equations class a few months ago.

In general, there is no such thing as "the definition" of a mathematical object like sine.  Rather, there is a web of equivalent statements, any one of which can be used as "the definition".  So to prove it in an entirely satisfactory way, I would need to know the definition you are starting with.

Another way to solve the equation y'' = -y is to search for a power series solution.  Suppose we want the solution which matches y(0) = 0, y'(0) = 1.  Then
y = 0 + x + a2 x^2 + a3 x^3 + ...
y'' = 2 a2 + 2*3 a3 x + 3*4 a4 x^2 + ...

Since we want y'' = -y, we match up coefficients and solve.  You'll arrive at the Taylor series for sin(x).

Aaaaaaaaand I don't understand it.  I guess I'll wait until I know more to think about 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

#### scott_pilgrim

• Jester
• Offline
• Posts: 958
• Respect: +1857
« Reply #14 on: May 08, 2014, 05:58:39 pm »
+3

Here is a fun maths problem: Let n be a natural number. 2n distinct points are plotted in the plane. Half of them are colored red, and the other half are colored orange. The points are then divided into n pairs, each with 1 red and 1 orange point. Then, a line segment is drawn between the 2 points in each pair. Prove that there is a way to pair the points such that after the line segments are drawn, none of the line segments intersect each other.

Can we please color them red and blue?  Red and orange will look so similar...
Logged

#### SirPeebles

• Cartographer
• Offline
• Posts: 3247
• Respect: +5403
« Reply #15 on: May 08, 2014, 06:06:05 pm »
+2

One way to derive it is to use Euler's formula!

The reason I was asking was because the derivation of Euler's formula that I saw used it at a part...

Yeah.  This is how I proved Euler's Formula in my differential equations class a few months ago.

In general, there is no such thing as "the definition" of a mathematical object like sine.  Rather, there is a web of equivalent statements, any one of which can be used as "the definition".  So to prove it in an entirely satisfactory way, I would need to know the definition you are starting with.

Another way to solve the equation y'' = -y is to search for a power series solution.  Suppose we want the solution which matches y(0) = 0, y'(0) = 1.  Then
y = 0 + x + a2 x^2 + a3 x^3 + ...
y'' = 2 a2 + 2*3 a3 x + 3*4 a4 x^2 + ...

Since we want y'' = -y, we match up coefficients and solve.  You'll arrive at the Taylor series for sin(x).

Aaaaaaaaand I don't understand it.  I guess I'll wait until I know more to think about it.

Let me try one more.  I think the definition of sine you have in mind is geometric.  Here's a derivation that is based on the unit circle.

It is easier for me to think of if the independent variable is t for time.  In fact, let's rephrase the problem as looking for the function x(t) for which x'' = - x.

A common technique is to remove the second derivative by introducing a new function, y(t) = x'(t).  Then our differential equation just says y'(t) = -x(t).  In other words, we now have two equations with two unknown functions (but no second derivatives!)

x' = y
y' = -x

At each time t, let P(t) be the point in the plane with x coordinate x(t) and y coordinate y(t).  So P(t) = ( x(t), y(t) ).  As time proceeds, in which direction will this point move?  For that we need to see what the rate of change of P is.  That's the derivative dP/dt, which in this case is P'(t) = ( x'(t), y'(t) ) = (y,-x) from our pair of differential equations.

Now, the direction from the origin to (x,y) is perpendicular with to the direction from the origin to (-y,x),   So P(t) moves around the origin in a circle with a constant speed.

Now suppose our initial conditions are x(0) = 1, x'(0) = 0.  Well, y(0) = x'(0) = 0, so the point starts at (1,0).  The speed is given by v^2 = (x')^2 + (y')^2 = (y)^2 + (-x)^2 = y^2 + x^2.  At t=0 this gives v(0)=1, and since the speed is constant we have v(t) = 1.  Thus the distance traveled in time t is just v*t = 1*t = t, and so t is equal to the angle swept out as measured in radians.  The x-coordinate is therefore x(t) = cos(t).

Logged
Well you *do* need a signature...

#### Polk5440

• Torturer
• Offline
• Posts: 1590
• Respect: +1534
« Reply #16 on: May 08, 2014, 06:08:44 pm »
+1

One way to derive it is to use Euler's formula!

The reason I was asking was because the derivation of Euler's formula that I saw used it at a part...

Yeah.  This is how I proved Euler's Formula in my differential equations class a few months ago.

In general, there is no such thing as "the definition" of a mathematical object like sine.  Rather, there is a web of equivalent statements, any one of which can be used as "the definition".  So to prove it in an entirely satisfactory way, I would need to know the definition you are starting with.

Another way to solve the equation y'' = -y is to search for a power series solution.  Suppose we want the solution which matches y(0) = 0, y'(0) = 1.  Then
y = 0 + x + a2 x^2 + a3 x^3 + ...
y'' = 2 a2 + 2*3 a3 x + 3*4 a4 x^2 + ...

Since we want y'' = -y, we match up coefficients and solve.  You'll arrive at the Taylor series for sin(x).

Aaaaaaaaand I don't understand it.  I guess I'll wait until I know more to think about it.

(Edit: I said something kind of stupid here. )

It's short, simple, and spawned a whole subfield in economics (matching theory). And it insults the general population at the very end (see page 15). What entertainment!
« Last Edit: May 08, 2014, 06:29:35 pm by Polk5440 »
Logged

#### heron

• Jester
• Offline
• Posts: 970
• Respect: +1089
« Reply #17 on: May 08, 2014, 06:23:57 pm »
+2

Here is a fun maths problem: Let n be a natural number. 2n distinct points are plotted in the plane. Half of them are colored red, and the other half are colored orange. The points are then divided into n pairs, each with 1 red and 1 orange point. Then, a line segment is drawn between the 2 points in each pair. Prove that there is a way to pair the points such that after the line segments are drawn, none of the line segments intersect each other.

Can we please color them red and blue?  Red and orange will look so similar...

Actually, I think we might be best with black and white to minimize the effects of color blindness.
Logged
PPR is for wimps.

#### Watno

• Margrave
• Offline
• Posts: 2577
• Respect: +2680
« Reply #18 on: May 08, 2014, 06:25:06 pm »
+3

But I guess the background is white, so you won't be able to see the white points.
Logged

#### sudgy

• Cartographer
• Online
• Posts: 3120
• It's pronounced "SOO-jee"
• Respect: +2285
« Reply #19 on: May 08, 2014, 06:37:36 pm »
+1

(Edit: I said something kind of stupid here. )

I was about to respond to the thing you said was stupid, but it was gone!  :O :O :O

I'll respond to it anyway.  I've actually not taken a single bit of calculus officially.  I've just studied it in my free time, because I know that will help me in the future (I want to do physics in college, and from what I've seen, it requires a lot of calculus).  It's all for fun anyway, and I was just curious about something, so I thought I would ask here (I'd already looked at a few other places and couldn't find anything).
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

#### navical

• Bishop
• Offline
• Posts: 122
• Respect: +136
« Reply #20 on: May 08, 2014, 08:00:07 pm »
+5

Here is a fun maths problem: Let n be a natural number. 2n distinct points are plotted in the plane. Half of them are colored red, and the other half are colored orange. The points are then divided into n pairs, each with 1 red and 1 orange point. Then, a line segment is drawn between the 2 points in each pair. Prove that there is a way to pair the points such that after the line segments are drawn, none of the line segments intersect each other.

Assume that no three points lie on the same straight line, since otherwise it fails for e.g. four points on a straight line coloured RROO in that order.

Call the set of points A. We will do this by induction on n. Clearly, when n=1 it's possible.

So for n>1, consider the convex hull of A, which is a convex polygon with vertices at points of A such that no point of A is outside the polygon. There are two cases: all the vertices of the convex hull are the same colour, or some are different. If some are different, then two adjacent vertices F and G will be different, and we can safely draw a line between them; no line between two points will ever leave the convex hull, and F and G are both outside the convex hull of the remaining points. Then the number of remaining points is less than n, so by induction we're done.

If all the points on the convex hull have the same colour - red, without loss of generality - then pick two, call them X and Y, and consider a straight line L perpendicular to the line between X and Y. If the line L is very close to X, then there are more red points than orange points on the side of L closer to X. If the line L is very close to Y, then there are more orange points than red points on the side of L closer to X. The aim is to move L from close to X to close to Y, and at some point, there will be equal numbers of orange points and red points on the side of L closer to X.

The only way this can fail to happen is if there are two orange points P and Q which lie on the same line K which is perpendicular to the line between X and Y, and there is one more red point than orange point on the side of K closer to X. (So if L is just closer to X than K, there is one more red than orange on X's side, and if L is just closer to Y than K, there is one more orange than red on X's side). In this situation, however, putting L in the same place as K and then twisting it very slightly around the midpoint of the line segment PQ will give us a line L with equal numbers of orange points and red points on the side of L closer to X, as wanted.

Then we can apply induction to the points on the side of L closer to X, and separately to the points on the side of L closer to Y, to get a set of lines that works for all the points.

Remark: I think this proof only actually requires no four points to lie on the same line, but it was easier to write up with three.
« Last Edit: May 08, 2014, 08:02:33 pm by navical »
Logged

#### AndrewisFTTW

• Saboteur
• Offline
• Posts: 1110
• Respect: +1060
« Reply #21 on: May 08, 2014, 08:23:52 pm »
+1

Logged
Wins: M39, M41, M48, M96, M97
Losses: M40, M43, M45, BM17 (?), RMM13, RMM17, RMM20, NM7, ZM18
MVPs: M97
Mod/Co-Mod: M46, M49, M52, NM10

#### heron

• Jester
• Offline
• Posts: 970
• Respect: +1089
« Reply #22 on: May 08, 2014, 08:26:53 pm »
+7

I think that proof works. Nice. Also, yes, I probably should have specified that no three points are collinear.

Here is mine:

Consider 4 points which are the endpoints of two intersecting line segments. Those points form a convex quadrilateral, and the segments are the diagonals of that quadrilateral. We can re-pair those 4 points so that those two segments are two opposite sides of the quadrilateral and do not intersect. From the triangle inequalities, we know that the sum of the lengths of two opposite sides of a convex quadrilateral is strictly less than the sum of the lengths of the diagonals.

Now, consider the pairing of points which leads to the least total length of the line segments. We know that such a pairing exists since there is a finite number of points. Assume that two of the segments in this pairing intersect. Then, we can re-pair them as described above, and the total length of the line segments will decrease. But that is a contradiction, since we started with the pairing with the least total length.

Therefore the pairing with the least total length of line segments will not have any intersecting segments.
Logged
PPR is for wimps.

#### SirPeebles

• Cartographer
• Offline
• Posts: 3247
• Respect: +5403
« Reply #23 on: May 08, 2014, 08:36:04 pm »
+3

I didn't want to post a problem while heron's was still on the table, but now I'll share it.  This is my favorite math problem.  It is from a fairly well-known math contest, so don't spoil it if you've seen it.

Each point on the xy-plane is colored white.  You have a paintbrush tool with the peculiar property that when you click on a point, each point an irrational distance from where you clicked will be colored black.  For instance, if you click on the origin (0,0), then (1,1) will turn black since sqrt(2) is irrational, but (0,1) will not turn black.

Is it possible to color the entire plane black with a finite number of clicks?  And if so, what is the fewest number of clicks required?
Logged
Well you *do* need a signature...

#### sudgy

• Cartographer
• Online
• Posts: 3120
• It's pronounced "SOO-jee"
• Respect: +2285
« Reply #24 on: May 08, 2014, 09:11:30 pm »
+1

I didn't want to post a problem while heron's was still on the table, but now I'll share it.  This is my favorite math problem.  It is from a fairly well-known math contest, so don't spoil it if you've seen it.

Each point on the xy-plane is colored white.  You have a paintbrush tool with the peculiar property that when you click on a point, each point an irrational distance from where you clicked will be colored black.  For instance, if you click on the origin (0,0), then (1,1) will turn black since sqrt(2) is irrational, but (0,1) will not turn black.

Is it possible to color the entire plane black with a finite number of clicks?  And if so, what is the fewest number of clicks required?

Ooh!  The lower bound is 2! (not 2!, but two with an actual exclamation mark (although 2! = 2...))
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
• Posts: 3247
• Respect: +5403
« Reply #25 on: May 08, 2014, 09:28:49 pm »
+1

why?
Logged
Well you *do* need a signature...

#### sudgy

• Cartographer
• Online
• Posts: 3120
• It's pronounced "SOO-jee"
• Respect: +2285
« Reply #26 on: May 08, 2014, 09:31:18 pm »
+1

why?

Well, all points have other points that are a rational distance away.  So it can't be one, since one click will not turn the points a rational distance away black.
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

#### heron

• Jester
• Offline
• Posts: 970
• Respect: +1089
« Reply #27 on: May 08, 2014, 09:33:25 pm »
+2

Well, you cannot color the plane black with just two clicks.
WLOG you click (0,0) and (k,0).
If all of the points are colored black, then there does not exist a point (a,b) such that sqrt(a^2 + b^2) is rational and sqrt((a - k)^2 + b^2) is rational. However, if a = k/2, and b = sqrt(q^2 - a^2), where q is some rational number, then sqrt(a^2 + b^2) is rational and sqrt((a - k)^2 + b^2) = sqrt(a^2 + b^2). So it is impossible to color the entire plane black with just two clicks.

I believe you can color the plane with three clicks.
Consider the clicks (0,0); (1,0); and (sqrt(2),0). Assume that there exists a point (a,b) that is colored white. Then sqrt(a^2 + b^2); sqrt((a - 1)^2 + b^2); and sqrt((a - sqrt(2))^2 + b^2) are all rational.
Note that since the product of two rational numbers is always rational, the square root of an irrational number is never rational. Since we have sqrt((a - 1)^2 + b^2) = sqrt(a^2 + b^2 - 2a + 1) is a rational number, and we know that a^2 + b^2 is rational, we see that a must be rational. (This is because the sum of 2 rational numbers is always rational, and the sum of a rational number and an irrational number is always irrational).

We also have that sqrt((a - sqrt(2))^2 + b^2) = sqrt(a^2 + b^2 - 2a*sqrt(2) + 2) is a rational number. We know that a^2 + b^2 +2 is rational, so 2a*sqrt(2) must be rational as well. However, the product of a rational number and an irrational number is always irrational, so a must be irrational, which is a contradiction.

Therefore the plane can be colored black in a minimum of 3 clicks.

Note: All of my statements about sums and products of rational and irrational numbers are easily proven using the definition of a rational number, or all already given by the closure properties.

Hopefully that is all correct, that was a nice problem.
« Last Edit: May 08, 2014, 09:36:30 pm by heron »
Logged
PPR is for wimps.

#### sudgy

• Cartographer
• Online
• Posts: 3120
• It's pronounced "SOO-jee"
• Respect: +2285
« Reply #28 on: May 08, 2014, 09:36:50 pm »
+1

why?

Well, all points have other points that are a rational distance away.  So it can't be one, since one click will not turn the points a rational distance away black.

Oh, I see what you are saying.  I meant, "I know the answer is at least 2."  Not, "The answer is 2."  Oops.
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
• Posts: 3247
• Respect: +5403
« Reply #29 on: May 08, 2014, 10:08:38 pm »
+5

heron's argument looks good.

Here's my favorite solution.  Click any point, but consider the portion of the plane which is not turned black.  It will be a collection of concentric circles, one for each rational number.  Call these the red circles.  Now click any other point, and call the rational circles about that point the blue circles.  After these two clicks, the only points which are still white are where a blue and a red circle intersect.  There is a countable number of red circles and a countable number of blue circles, and each pair intersects at most twice, so after two clicks only a countable number of white points remain.  Let's call these points the stubborn points.

Now where should we make the third click?  Let's call a point "good" if clicking there will finish the job, and call it "bad" if it leaves a white point leftover.  Then the "bad" points are precisely the rational-radius circles centered on the stubborn points.  Thus the bad points lie on a countable number of circles.  But the plane is not a countable union of circles*, so there must exist a "good" point.

*Why can't the plane be a countable union of circles?  There are two quick arguments.

1) [Measure theory] A circle has measure zero (Roughly this means that a circle has zero area.  Here I am referring to the circle, not the solid disk.).  A countable union of measure zero sets still has measure zero, and therefore cannot be the full plane.  Indeed, we see that almost all points are "good".

2) [Baire category]  A circle in the plane is nowhere dense.  The "bad" points therefore form a meager set.  But the plane is not meager.

Note:  The only property of the irrational numbers we use is that their complement is countable.  So for instance, a paintbrush which colors only at transcendental distances will also color the entire plane in three clicks.  And you can choose "almost any" three distinct points to click, in the technical measure theory sense.

edit:  Here's a third way to see that the plane is not a countable union of circles, without using scary words.  (It is secretly just argument 1)

3) [No scary words]  A circle can always be "thickened" into narrow round band whose area is as small as you'd like.  List your countable collection of circles C1, C2, C3, ... .  Thicken C1 to a narrow band of area at most 1/2, thicken C2 to a band of area at most 1/2^2, thicken C3 to at most 1/2^3, and so forth.  Then the union of these thickened circles has area at most 1/2 + 1/2^2 + 1/2^3 + ... = 1.  Thus the union does not cover the entire plane.
« Last Edit: May 08, 2014, 10:35:17 pm by SirPeebles »
Logged
Well you *do* need a signature...

#### pacovf

• Margrave
• Offline
• Posts: 2949
• Multiediting poster
• Respect: +3243
« Reply #30 on: May 08, 2014, 10:32:24 pm »
+1

So uh tensorial notation from my string theory course (technically physics, but oh well), something bothers me with the Polyakov action. At some point we want to know the variation of sqrt(-det(g) ) when g varies, g being a 2d metric.

I am told that d(sqrt( -det(g) )) = +1/2 * sqrt( -det(g) ) * gab * dgab = -1/2 * sqrt( -det(g) ) * gab * dgab

So gab * dgab = - gab * dgab, and that sign change is bugging the hell out of me. So, can someone explain that to me, or is it an error?
« Last Edit: May 08, 2014, 10:38:58 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.

#### AndrewisFTTW

• Saboteur
• Offline
• Posts: 1110
• Respect: +1060
« Reply #31 on: May 08, 2014, 10:49:06 pm »
0

I got a D in geometry. Then I failed algebra 2. Then when I got to college I had to take basic algebra again for no credit. I think I took another math course and I probably got a C or something.
Logged
Wins: M39, M41, M48, M96, M97
Losses: M40, M43, M45, BM17 (?), RMM13, RMM17, RMM20, NM7, ZM18
MVPs: M97
Mod/Co-Mod: M46, M49, M52, NM10

#### AndrewisFTTW

• Saboteur
• Offline
• Posts: 1110
• Respect: +1060
« Reply #32 on: May 08, 2014, 10:49:57 pm »
+2

Ozle was my teacher.
Logged
Wins: M39, M41, M48, M96, M97
Losses: M40, M43, M45, BM17 (?), RMM13, RMM17, RMM20, NM7, ZM18
MVPs: M97
Mod/Co-Mod: M46, M49, M52, NM10

#### SirPeebles

• Cartographer
• Offline
• Posts: 3247
• Respect: +5403
« Reply #33 on: May 08, 2014, 10:53:02 pm »
+1

So uh tensorial notation from my string theory course (technically physics, but oh well), something bothers me with the Polyakov action. At some point we want to know the variation of sqrt(-det(g) ) when g varies, g being a 2d metric.

I am told that d(sqrt( -det(g) )) = +1/2 * sqrt( -det(g) ) * gab * dgab = -1/2 * sqrt( -det(g) ) * gab * dgab

So gab * dgab = - gab * dgab, and that sign change is bugging the hell out of me. So, can someone explain that to me, or is it an error?

I'm a bit rusty on this stuff.  If I recall correctly, gab * gab = gbb = tr g.  Is there any reason in your context to assume that the trace of your metric is constant?  Because then your identity just follows from the product rule.  That is, differentiating the trace would give gab * dgab + gab * dgab = 0.

edit:  oh, gbb isn't the trace of g, is it?  It's the trace of the Kronecker delta, or whatever is appropriate for your signature.  So yeah, it should be a constant, so what you're looking for comes right out of the product rule.

edit 2:  The signature doesn't come into play for the scalar gbb.  That is just the trace of the Kronecker symbol, which is the number of dimensions.  In this case, 2.
« Last Edit: May 08, 2014, 11:24:03 pm by SirPeebles »
Logged
Well you *do* need a signature...

#### qmech

• Torturer
• Offline
• Posts: 1915
• Works with high probability
• Respect: +2288
« Reply #34 on: May 09, 2014, 03:28:33 am »
+1

Two very nice solutions.  I managed to get the splitting out with the ham sandwich theorem, and was hoping there would be an elementary way to do it.
Logged

#### WalrusMcFishSr

• Minion
• Offline
• Posts: 642
• An enormous walrus the size of Antarctica
• Respect: +1779
« Reply #35 on: May 09, 2014, 04:04:21 am »
+3

Can you extend that irrational paintbrush problem to n dimensions?
Logged
My Dominion videos: http://www.youtube.com/user/WalrusMcFishSr   <---Bet you can't click on that!

#### qmech

• Torturer
• Offline
• Posts: 1915
• Works with high probability
• Respect: +2288
« Reply #36 on: May 09, 2014, 04:10:46 am »
+2

Can you extend that irrational paintbrush problem to n dimensions?

Yes, it works straightforwardly.

(Post 1000 is in the maths thread!  I mean, whatever.)
Logged

#### Joseph2302

• Jester
• Offline
• Posts: 817
• "Better to be lucky than good"
• Respect: +535
« Reply #37 on: May 09, 2014, 05:06:17 am »
+5

Logged
Mafia Stats:
Town: 11 games, 5 wins
Scum: 3 games, 1 win

#### pacovf

• Margrave
• Offline
• Posts: 2949
• Multiediting poster
• Respect: +3243
« Reply #38 on: May 09, 2014, 06:13:38 am »
+1

So uh tensorial notation from my string theory course (technically physics, but oh well), something bothers me with the Polyakov action. At some point we want to know the variation of sqrt(-det(g) ) when g varies, g being a 2d metric.

I am told that d(sqrt( -det(g) )) = +1/2 * sqrt( -det(g) ) * gab * dgab = -1/2 * sqrt( -det(g) ) * gab * dgab

So gab * dgab = - gab * dgab, and that sign change is bugging the hell out of me. So, can someone explain that to me, or is it an error?

I'm a bit rusty on this stuff.  If I recall correctly, gab * gab = gbb = tr g.  Is there any reason in your context to assume that the trace of your metric is constant?  Because then your identity just follows from the product rule.  That is, differentiating the trace would give gab * dgab + gab * dgab = 0.

edit:  oh, gbb isn't the trace of g, is it?  It's the trace of the Kronecker delta, or whatever is appropriate for your signature.  So yeah, it should be a constant, so what you're looking for comes right out of the product rule.

edit 2:  The signature doesn't come into play for the scalar gbb.  That is just the trace of the Kronecker symbol, which is the number of dimensions.  In this case, 2.

Ugh, you are obviously right.

[ By definition in the tensor notation, gab= (gab)-1, where the -1 means the inverse of the metric, not the inverse of gab, tensor notation can be very unclear. So yeah, gab * gab = gab * gba = Iaa = n (where n dimension), and derivation indeed gives the result. ]

What bothered me in the equation is that, "usually", Aa*Ba = Aa*Ba because of the symmetry of the metric (sometimes you don't use a metric to lower and raise indices though). Somehow I can't make sense of why this is different when using dg. Note that in this case, g is a variable that happens to be a metric, so there's no reason why you should use g to raise and lower indices, in fact we had defined another metric beforehand. If we call hab the object that we use to lower indices (probably the predefined metric, but when reading the notes again, I noticed it wasn't specified), we get:

hac*hbd*gab*dgcd = - hca*hdb*gab*dgcd

And somehow that doesn't feel right, 95% of the time h is symmetric, and in the cases where it isn't, I've only encountered antisymmetric h. I guess there must be a reason that prevents me from raising and lowering indices for dg, but I don't see why.
« Last Edit: May 09, 2014, 06:42:34 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.

#### SirPeebles

• Cartographer
• Offline
• Posts: 3247
• Respect: +5403
« Reply #39 on: May 09, 2014, 10:30:30 am »
+2

Ugh, you are obviously right.

[ By definition in the tensor notation, gab= (gab)-1, where the -1 means the inverse of the metric, not the inverse of gab, tensor notation can be very unclear. So yeah, gab * gab = gab * gba = Iaa = n (where n dimension), and derivation indeed gives the result. ]

What bothered me in the equation is that, "usually", Aa*Ba = Aa*Ba because of the symmetry of the metric (sometimes you don't use a metric to lower and raise indices though). Somehow I can't make sense of why this is different when using dg. Note that in this case, g is a variable that happens to be a metric, so there's no reason why you should use g to raise and lower indices, in fact we had defined another metric beforehand. If we call hab the object that we use to lower indices (probably the predefined metric, but when reading the notes again, I noticed it wasn't specified), we get:

hac*hbd*gab*dgcd = - hca*hdb*gab*dgcd

And somehow that doesn't feel right, 95% of the time h is symmetric, and in the cases where it isn't, I've only encountered antisymmetric h. I guess there must be a reason that prevents me from raising and lowering indices for dg, but I don't see why.

Suppose you have a matrix A, and you change it by a small amount dA.  How much does the inverse of A change by?  Well, A-1A = I, after the change we will have (A-1 + d[A-1])(A + dA) = I to first order, so A-1 dA + d[A-1] A = 0. That is essentially what we just proved if you put in A = g and contract indices.

The reason that the indices don't behave the way you are expecting is because d[A-1] is NOT just the matrix inverse of dA.  If you raise the indices on dgab then you get the equivalent of (dg)-1, which is not the same thing as d(g-1).
Logged
Well you *do* need a signature...

#### Kirian

• Offline
• Posts: 6799
• An Unbalanced Equation
• Respect: +8736
« Reply #40 on: May 09, 2014, 10:33:10 am »
+1

I took two years of college physics and two years of calculus... and I have exactly no idea what y'all are talking about.
Logged
Kirian's Law of f.DS jokes:  Any sufficiently unexplained joke is indistinguishable from serious conversation.

#### SirPeebles

• Cartographer
• Offline
• Posts: 3247
• Respect: +5403
« Reply #41 on: May 09, 2014, 10:39:54 am »
+2

I took two years of college physics and two years of calculus... and I have exactly no idea what y'all are talking about.

Newton's laws of motion only apply to inertial frames.  For example, if you consider motion from the noninertial frame where the Earth is at rest, then F = ma gets cluttered up with extra terms which are often interpreted as fictitious forces, namely centrifugal force and Coriolis force.  The tensor notation was developed by Albert Einstein during his work on general relativity as a way of writing down laws of physics which hold in any frame, inertial or not.  Nowadays it is used throughout physics, not only in general relativity.
Logged
Well you *do* need a signature...

#### pacovf

• Margrave
• Offline
• Posts: 2949
• Multiediting poster
• Respect: +3243
« Reply #42 on: May 09, 2014, 10:48:50 am »
+2

The reason that the indices don't behave the way you are expecting is because d[A-1] is NOT just the matrix inverse of dA.  If you raise the indices on dgab then you get the equivalent of (dg)-1, which is not the same thing as d(g-1).

Oh, ok, so basically dgab and dgab as "defined" in that result are not the same tensor modulo index raising. Man, that could definitely use a footnote. Thanks for the explanation, though! Much appreciated.

I took two years of college physics and two years of calculus... and I have exactly no idea what y'all are talking about.

Me neither.
Logged
pacovf has a neopets account.  It has 999 hours logged.  All his neopets are named "Jessica".  I guess that must be his ex.

#### SirPeebles

• Cartographer
• Offline
• Posts: 3247
• Respect: +5403
« Reply #43 on: May 09, 2014, 10:51:00 am »
+1

I don't think they are usually even tensors.

Edit:  I take that back.  If g and g+dg are both tensors, then so is dg.
« Last Edit: May 09, 2014, 10:54:27 am by SirPeebles »
Logged
Well you *do* need a signature...

#### DStu

• Margrave
• Offline
• Posts: 2627
• Respect: +1476
« Reply #44 on: May 09, 2014, 10:56:08 am »
+3

Quote
I took two years of college physics and two years of calculus... and I have exactly no idea what y'all are talking about.

Me neither.

I'm about to defend my math phd thesis, and I quitted this subthread at "tensor"...
Logged

#### Kirian

• Offline
• Posts: 6799
• An Unbalanced Equation
• Respect: +8736
« Reply #45 on: May 09, 2014, 11:04:41 am »
+5

I'm trying to mostly ignore it, it'll just make me tensor.
Logged
Kirian's Law of f.DS jokes:  Any sufficiently unexplained joke is indistinguishable from serious conversation.

#### pacovf

• Margrave
• Offline
• Posts: 2949
• Multiediting poster
• Respect: +3243
« Reply #46 on: May 09, 2014, 11:26:07 am »
+1

Quote
I took two years of college physics and two years of calculus... and I have exactly no idea what y'all are talking about.

Me neither.

I'm about to defend my math phd thesis, and I quitted this subthread at "tensor"...

I nearly quitted this thread at "trascendental". Somehow I feel that if tensors want to make you quit, you know how to use that. Or you've had to work with non-commutative algebras.

Is there any other big pure maths sector? Differential Geometry, Number Theory, Algebra and its numerous spin-offs... Topology, Set Theory...
« Last Edit: May 09, 2014, 11:35:22 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.

#### DStu

• Margrave
• Offline
• Posts: 2627
• Respect: +1476
« Reply #47 on: May 09, 2014, 11:29:22 am »
+1

Quote
I took two years of college physics and two years of calculus... and I have exactly no idea what y'all are talking about.

Me neither.

I'm about to defend my math phd thesis, and I quitted this subthread at "tensor"...

I nearly quitted this thread at "trascendental". Somehow I feel that if tensors want to make you quit, you know how to use that. Or you've had to work with non-commutative algebras.

Is there any other big pure maths sector?
Actually, applied math.  But actually from all of these, I probably can handle tensors if I must, but the point is that here I don't need to, so...
Logged

#### pacovf

• Margrave
• Offline
• Posts: 2949
• Multiediting poster
• Respect: +3243
« Reply #48 on: May 09, 2014, 11:31:23 am »
+1

Want kind of applied?

I'm doing mostly theoretical physics (but I did some engineering before, so I've forgotten some advanced probability and statistics), so that's differential geometry, group theory and gauge theory (not sure if that last one is actually a math discipline).
Logged
pacovf has a neopets account.  It has 999 hours logged.  All his neopets are named "Jessica".  I guess that must be his ex.

#### DStu

• Margrave
• Offline
• Posts: 2627
• Respect: +1476
« Reply #49 on: May 09, 2014, 11:33:41 am »
+2

Want kind of applied?

I'm doing mostly theoretical physics (but I did some engineering before, so I've forgotten some advanced probability and statistics), so that's differential geometry, group theory and gauge theory (not sure if that last one is actually a math discipline).

Probablitly theory / stochastic analysis, concerend with speed of convergence of Markov chains, mostly on function spaces...
Logged

#### Watno

• Margrave
• Offline
• Posts: 2577
• Respect: +2680
« Reply #50 on: May 09, 2014, 12:17:59 pm »
0

There's also Discrete Mathematics.

Why is Set Theory associated with Algebra by the way? My university does this as well, but I don't really see it (though I haven't done an set theory lectures yet).
Logged

#### SirPeebles

• Cartographer
• Offline
• Posts: 3247
• Respect: +5403
« Reply #51 on: May 09, 2014, 12:26:48 pm »
+1

I don't usually see algebra lumped with set theory.
Logged
Well you *do* need a signature...

#### sudgy

• Cartographer
• Online
• Posts: 3120
• It's pronounced "SOO-jee"
• Respect: +2285
« Reply #52 on: May 09, 2014, 12:43:29 pm »
0

Hehe, I just read about power series and such last night, and now understand SirPeebles first thing about it.  I'm trying to find a good smiley for this but I can't think of 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

#### soulnet

• Mountebank
• Offline
• Posts: 2142
• Respect: +1733
« Reply #53 on: May 09, 2014, 03:12:10 pm »
0

There's also Discrete Mathematics.

Why is Set Theory associated with Algebra by the way? My university does this as well, but I don't really see it (though I haven't done an set theory lectures yet).

You can see any logic as an algebra.

(I am assuming by "Set Theory" you mean something like "ZFC theory" or its vicinity)
Logged

#### pacovf

• Margrave
• Offline
• Posts: 2949
• Multiediting poster
• Respect: +3243
« Reply #54 on: May 09, 2014, 03:13:51 pm »
0

You can see anything as a category, if you think about it long enough.

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

#### soulnet

• Mountebank
• Offline
• Posts: 2142
• Respect: +1733
« Reply #55 on: May 09, 2014, 03:20:41 pm »
0

You can see anything as a category, if you think about it long enough.

ugh, categories. That is just the extreme result of the fallacy "more general is better". Using too general tools usually hides the meaning of what you prove.
Logged

#### SirPeebles

• Cartographer
• Offline
• Posts: 3247
• Respect: +5403
« Reply #56 on: May 09, 2014, 03:43:50 pm »
+3

You can see anything as a category, if you think about it long enough.

ugh, categories. That is just the extreme result of the fallacy "more general is better". Using too general tools usually hides the meaning of what you prove.

I've got to disagree here.  Category theory opens up some incredibly beautiful unifications and dualities.
Logged
Well you *do* need a signature...

#### soulnet

• Mountebank
• Offline
• Posts: 2142
• Respect: +1733
« Reply #57 on: May 09, 2014, 04:13:24 pm »
0

You can see anything as a category, if you think about it long enough.

ugh, categories. That is just the extreme result of the fallacy "more general is better". Using too general tools usually hides the meaning of what you prove.

I've got to disagree here.  Category theory opens up some incredibly beautiful unifications and dualities.

That's not really disagreeing. My point is not "category theory is useless" but "trying to get category theory to be an all-encompassing theory" is a counterproductive goal, regardless on whether it is possible or not, and a significant amount of category theorist seem to advocate that goal (this is hugely biased by the ones that I know or have heard off, and not being in the field myself, could easily be a narrow view).
Logged

#### navical

• Bishop
• Offline
• Posts: 122
• Respect: +136
« Reply #58 on: May 09, 2014, 05:51:39 pm »
0

I think that proof works. Nice. Also, yes, I probably should have specified that no three points are collinear.

Here is mine:

Consider 4 points which are the endpoints of two intersecting line segments. Those points form a convex quadrilateral, and the segments are the diagonals of that quadrilateral. We can re-pair those 4 points so that those two segments are two opposite sides of the quadrilateral and do not intersect. From the triangle inequalities, we know that the sum of the lengths of two opposite sides of a convex quadrilateral is strictly less than the sum of the lengths of the diagonals.

Now, consider the pairing of points which leads to the least total length of the line segments. We know that such a pairing exists since there is a finite number of points. Assume that two of the segments in this pairing intersect. Then, we can re-pair them as described above, and the total length of the line segments will decrease. But that is a contradiction, since we started with the pairing with the least total length.

Therefore the pairing with the least total length of line segments will not have any intersecting segments.

Oh, very nice.
Logged

#### qmech

• Torturer
• Offline
• Posts: 1915
• Works with high probability
• Respect: +2288
« Reply #59 on: May 10, 2014, 04:33:32 am »
+1

Here's another: is it always possible to cover 10 marks on a white table cloth with 10 plates that cannot overlap?

Reposting this.  The solution is a very neat trick which is tremendously useful when doing real maths.
Logged

#### SirPeebles

• Cartographer
• Offline
• Posts: 3247
• Respect: +5403
« Reply #60 on: May 10, 2014, 05:50:22 am »
0

Here's another: is it always possible to cover 10 marks on a white table cloth with 10 plates that cannot overlap?

Reposting this.  The solution is a very neat trick which is tremendously useful when doing real maths.

Surely it depends on the sizes and shapes of the plates and of the cloth.
Logged
Well you *do* need a signature...

#### qmech

• Torturer
• Offline
• Posts: 1915
• Works with high probability
• Respect: +2288
« Reply #61 on: May 10, 2014, 08:20:30 am »
0

Here's another: is it always possible to cover 10 marks on a white table cloth with 10 plates that cannot overlap?

Reposting this.  The solution is a very neat trick which is tremendously useful when doing real maths.

Surely it depends on the sizes and shapes of the plates and of the cloth.

Marks are points and plates are disks of equal size.  Assume the tablecloth is R^2.  The question is whether it's possible to cover all of the points with any number of disks (although you obviously don't need more than 10).

Note that it's important what number 10 is: if I can put points sufficiently densely everywhere then it's impossible because the disks can't overlap, and it's obviously possible for, say, 2 points.
Logged

#### pacovf

• Margrave
• Offline
• Posts: 2949
• Multiediting poster
• Respect: +3243
« Reply #62 on: May 10, 2014, 08:25:59 am »
0

I assume you can choose the size of the plates?

But then if you can choose the size of the plates, the answer is obviously yes, you just have to get small enough plates.

And if you can't choose the size of the plates, you are not even sure that you can fit all 10 plates on the cloth, so the answer is no, you can't always fit them in such a way as to cover all 10 points.

I am with SirPeebles in this one, I think we are missing a premise.
« Last Edit: May 10, 2014, 08:41:23 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.

#### qmech

• Torturer
• Offline
• Posts: 1915
• Works with high probability
• Respect: +2288
« Reply #63 on: May 10, 2014, 08:41:22 am »
0

I assume you can choose the size of the plates?

No.  Or yes, but the points are placed afterwards.
Logged

#### pacovf

• Margrave
• Offline
• Posts: 2949
• Multiediting poster
• Respect: +3243
« Reply #64 on: May 10, 2014, 08:46:31 am »
0

I assume you can choose the size of the plates?

No.  Or yes, but the points are placed afterwards.

Huh? If the points are placed after placing the plates, you can always place them outside the plates, since the plates are disks...?
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
• Posts: 1915
• Works with high probability
• Respect: +2288
« Reply #65 on: May 10, 2014, 08:52:13 am »
0

The disks are placed after the points.
Logged

#### Watno

• Margrave
• Offline
• Posts: 2577
• Respect: +2680
« Reply #66 on: May 10, 2014, 08:53:10 am »
+1

I think the suggested sequence was
1)Choose a size for the plates
2)Place points
3)Place plates

Also he said that the cloth is R^2
Logged

#### liopoil

• Margrave
• Offline
• Posts: 2551
• Respect: +2437
« Reply #67 on: May 10, 2014, 08:57:10 am »
0

must the center of each plate be over the tablecloth? Or can you hang them over the table, with just a little bit on the table.
Logged

#### Watno

• Margrave
• Offline
• Posts: 2577
• Respect: +2680
« Reply #68 on: May 10, 2014, 08:58:06 am »
0

Also he said that the cloth is R^2
Logged

#### qmech

• Torturer
• Offline
• Posts: 1915
• Works with high probability
• Respect: +2288
« Reply #69 on: May 10, 2014, 08:59:10 am »
0

must the center of each plate be over the tablecloth? Or can you hang them over the table, with just a little bit on the table.

That would be allowed: you can assume the tablecloth is infinite.
Logged

#### liopoil

• Margrave
• Offline
• Posts: 2551
• Respect: +2437
« Reply #70 on: May 10, 2014, 09:00:13 am »
0

must the center of each plate be over the tablecloth? Or can you hang them over the table, with just a little bit on the table.

That would be allowed: you can assume the tablecloth is infinite.
...then how is the tablecloth R^2?
Logged

#### liopoil

• Margrave
• Offline
• Posts: 2551
• Respect: +2437
« Reply #71 on: May 10, 2014, 09:00:44 am »
0

Am I missing what R^2 means?
Logged

#### Watno

• Margrave
• Offline
• Posts: 2577
• Respect: +2680
« Reply #72 on: May 10, 2014, 09:02:13 am »
0

R^2 is supposed to be the plane of real numbers
Logged

#### qmech

• Torturer
• Offline
• Posts: 1915
• Works with high probability
• Respect: +2288
« Reply #73 on: May 10, 2014, 09:12:21 am »
0

Sorry, R^2 is what I call an infinite (two-dimensional) plane, because you can specify any point in it with two real numbers.  Just think of it as an infinitely large tablecloth.
Logged

#### liopoil

• Margrave
• Offline
• Posts: 2551
• Respect: +2437
« Reply #74 on: May 10, 2014, 09:47:18 am »
0

oh, duh, yeah, I've seen a capital R used for the set of real numbers before, although normally it's supposed to be all fancy and stuff, right? But that's inconvenient to type of course. Anyway, yeah, I don't know how to go about proving that. I feel like there should be a fairly simple iterative process to find a configuration. Although maybe it's possible to show that there is a configuration without finding it. Well, I'll read someone's solution whenever they figure it out .
Logged

#### Watno

• Margrave
• Offline
• Posts: 2577
• Respect: +2680
« Reply #75 on: May 10, 2014, 09:49:09 am »
+9

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

#### qmech

• Torturer
• Offline
• Posts: 1915
• Works with high probability
• Respect: +2288
« Reply #76 on: May 10, 2014, 09:57:29 am »
0

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

#### pacovf

• Margrave
• Offline
• Posts: 2949
• Multiediting poster
• Respect: +3243
« 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
• Posts: 1915
• Works with high probability
• Respect: +2288
« Reply #78 on: May 10, 2014, 11:19:20 am »
+1

Is the solution constructive?

Good question.
Logged

#### sitnaltax

• Conspirator
• Offline
• Posts: 230
• Respect: +377
« 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

• Jester
• Offline
• Posts: 970
• Respect: +1089
« 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
PPR is for wimps.

#### DStu

• Margrave
• Offline
• Posts: 2627
• Respect: +1476
« 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
• Posts: 2681
• Respect: +1456
« 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

• Conspirator
• Offline
• Posts: 230
• Respect: +377
« 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
• Posts: 2551
• Respect: +2437
« Reply #84 on: May 10, 2014, 12:58:53 pm »
0

Logged

#### Polk5440

• Torturer
• Offline
• Posts: 1590
• Respect: +1534
« 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

• Jester
• Offline
• Posts: 970
• Respect: +1089
« 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
PPR is for wimps.

#### Kirian

• Offline
• Posts: 6799
• An Unbalanced Equation
• Respect: +8736
« 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

• Margrave
• Offline
• Posts: 2949
• Multiediting poster
• Respect: +3243
« 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
• Posts: 1590
• Respect: +1534
« 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
• Posts: 3247
• Respect: +5403
« 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

• Margrave
• Offline
• Posts: 2949
• Multiediting poster
• Respect: +3243
« 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
• Posts: 1590
• Respect: +1534
« 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
• Posts: 1590
• Respect: +1534
« 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
• Posts: 1915
• Works with high probability
• Respect: +2288
« 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

• Jester
• Offline
• Posts: 970
• Respect: +1089
« 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
PPR is for wimps.

#### Polk5440

• Torturer
• Offline
• Posts: 1590
• Respect: +1534
« 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

• Jester
• Offline
• Posts: 970
• Respect: +1089
« 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
PPR is for wimps.

#### qmech

• Torturer
• Offline
• Posts: 1915
• Works with high probability
• Respect: +2288
« Reply #98 on: May 10, 2014, 01:49:28 pm »
0

Very nice!
Logged

#### SirPeebles

• Cartographer
• Offline
• Posts: 3247
• Respect: +5403
« 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...

#### SirPeebles

• Cartographer
• Offline
• Posts: 3247
• Respect: +5403
« Reply #100 on: May 10, 2014, 02:09:25 pm »
0

Here's a question.  When is the next year in which the corresponding variant of heron's problem would have a unique answer?
Logged
Well you *do* need a signature...

#### pacovf

• Margrave
• Offline
• Posts: 2949
• Multiediting poster
• Respect: +3243
« Reply #101 on: May 10, 2014, 02:15:39 pm »
0

Here's a question.  When is the next year in which the corresponding variant of heron's problem would have a unique answer?

Somehow I doubt that there is a smart way to answer this.
Logged
pacovf has a neopets account.  It has 999 hours logged.  All his neopets are named "Jessica".  I guess that must be his ex.

#### heron

• Jester
• Offline
• Posts: 970
• Respect: +1089
« Reply #102 on: May 10, 2014, 02:27:27 pm »
+2

Fortunately it does not take very many years; 2020 = 2*2*5*101 so the answer is 2019.
Logged
PPR is for wimps.

#### SirPeebles

• Cartographer
• Offline
• Posts: 3247
• Respect: +5403
« Reply #103 on: May 10, 2014, 02:28:20 pm »
0

Fortunately it does not take very many years; 2020 = 2*2*5*101 so the answer is 2019.

What if the roots are distinct negative integers?

edit:  It's not that much more interesting, so I'll just post it.  2030 = 2*5*7*29, so it would be in 2029.
« Last Edit: May 10, 2014, 02:29:33 pm by SirPeebles »
Logged
Well you *do* need a signature...

#### dnkywin

• Scout
• Offline
• Posts: 42
• Respect: +56
« Reply #104 on: May 12, 2014, 12:09:47 am »
0

Heh, as someone who's working behind the scenes, it's nice to see HMMT problems being discussed here.

Here's one of my favorite math competition problems of all time (bonus points if you can find the source):

We have a sequence of real numbers a(0), a(1), a(2), ... that satisfies a(n) = r * a(n-1) + s * a(n-2) for some real numbers r,s. Is it possible that a(n) is never 0, but for any positive real number x we can find integers i and j such that |a(i)|< x < |a(j)| ?
« Last Edit: May 12, 2014, 12:12:10 am by dnkywin »
Logged

#### DStu

• Margrave
• Offline
• Posts: 2627
• Respect: +1476
« Reply #105 on: May 12, 2014, 02:22:48 am »
+2

Heh, as someone who's working behind the scenes, it's nice to see HMMT problems being discussed here.

Here's one of my favorite math competition problems of all time (bonus points if you can find the source):

We have a sequence of real numbers a(0), a(1), a(2), ... that satisfies a(n) = r * a(n-1) + s * a(n-2) for some real numbers r,s. Is it possible that a(n) is never 0, but for any positive real number x we can find integers i and j such that |a(i)|< x < |a(j)| ?
my guess is    no
as

For this to be true, you need a subsequence which converges to 0, and a subsequence that convergece to +inf or -inf.  But the recursion formula should lead to an exponential behaviour like with the Fibonacci sequence (write it in 2d linear recursion, find the eigenvalues/vectors) which leads to exponential behaviour (as long as the absolute value of all eigenvalues does not equal 1. In which case you might have oscillating behaivour depending of the second eigenvalue, but the absolute value stays constant).
In any case you can write a(n) as sum of two complex exponetials, and I don't see how this sum can have both subsequences converging to 0 and to +-inf.

Maybe I'm missing something without writing it down, but in this case this method is exactly what you need to find how it is possible.
Logged

#### Ozle

• Cartographer
• Offline
• Posts: 3625
• Sorry, this text is personal.
• Respect: +3329
« Reply #106 on: May 12, 2014, 02:40:45 am »
+4

Heh, as someone who's working behind the scenes, it's nice to see HMMT problems being discussed here.

Here's one of my favorite math competition problems of all time (bonus points if you can find the source):

We have a sequence of real numbers a(0), a(1), a(2), ... that satisfies a(n) = r * a(n-1) + s * a(n-2) for some real numbers r,s. Is it possible that a(n) is never 0, but for any positive real number x we can find integers i and j such that |a(i)|< x < |a(j)| ?

Moat?
Logged
Try the Ozle Google Map Challenge!
http://forum.dominionstrategy.com/index.php?topic=7466.0

Sullying players Enjoyment of Innovation since 2013 Apparently!

#### pacovf

• Margrave
• Offline
• Posts: 2949
• Multiediting poster
• Respect: +3243
« Reply #107 on: May 12, 2014, 05:53:44 am »
+1

Heh, as someone who's working behind the scenes, it's nice to see HMMT problems being discussed here.

Here's one of my favorite math competition problems of all time (bonus points if you can find the source):

We have a sequence of real numbers a(0), a(1), a(2), ... that satisfies a(n) = r * a(n-1) + s * a(n-2) for some real numbers r,s. Is it possible that a(n) is never 0, but for any positive real number x we can find integers i and j such that |a(i)|< x < |a(j)| ?
my guess is    no
as

For this to be true, you need a subsequence which converges to 0, and a subsequence that convergece to +inf or -inf.  But the recursion formula should lead to an exponential behaviour like with the Fibonacci sequence (write it in 2d linear recursion, find the eigenvalues/vectors) which leads to exponential behaviour (as long as the absolute value of all eigenvalues does not equal 1. In which case you might have oscillating behaivour depending of the second eigenvalue, but the absolute value stays constant).
In any case you can write a(n) as sum of two complex exponetials, and I don't see how this sum can have both subsequences converging to 0 and to +-inf.

Maybe I'm missing something without writing it down, but in this case this method is exactly what you need to find how it is possible.

Had arrived to the same conclusion as DStu, but hadn't thought about complex solutions, for some reason. If both "eigenvalues" (e1, e2) have same absolute value larger than one, but their arguments cannot be transformed from one to the other by multiplication by a rational number, it should work.

The idea is that sometimes e1^n and e2^n will have a very similar argument, and hence a(n) will have a very high absolute value, and sometimes their argument will differ by more or less Pi, and hence they will mostly cancel each other, and can get arbitrarily close to zero in absolute value.

EDIT: or maybe not. The absolute value of ei^n might grow fast enough that it can't be cancelled by the nearly opposing arguments. Don't know how to prove it either way.

Scratch that, a(n) has to be real. I agree with DStu, then.
« Last Edit: May 12, 2014, 06:21:48 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.

#### SirPeebles

• Cartographer
• Offline
• Posts: 3247
• Respect: +5403
« Reply #108 on: May 12, 2014, 06:18:56 am »
+1

I agree with pacovf that it may be possible.  You can get a(n) to look something like (2^n)*cos(n).  But I'm not sure whether such a sequence will have a subsequence converging to zero or not.  I seem to recall this question coming up in my thesis, and I think I abandoned it for a different approach.
Logged
Well you *do* need a signature...

#### pacovf

• Margrave
• Offline
• Posts: 2949
• Multiediting poster
• Respect: +3243
« Reply #109 on: May 12, 2014, 10:19:11 am »
+1

Been thinking about it for a while. My gut instinct tells me that minn<N [cos(n)] ~ 1/N, but I can't manage to prove it. I've been working around the fact that cos(x+e) ~ e when cos(x) = 0, so the question is how "quickly" n approaches N*Pi, but I've only managed to compare it to things that go slower, not faster...
« Last Edit: May 12, 2014, 10:24:34 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.

#### SirPeebles

• Cartographer
• Offline
• Posts: 3247
• Respect: +5403
« Reply #110 on: May 12, 2014, 10:23:09 am »
0

Been thinking about it for a while. My gut instinct tells me that minn<N [cos(n)] ~ 1/N, but I can't manage to prove it

Yeah, that's what I've been thinking too.
Logged
Well you *do* need a signature...

#### SirPeebles

• Cartographer
• Offline
• Posts: 3247
• Respect: +5403
« Reply #111 on: May 12, 2014, 10:38:33 am »
+1

Been thinking about it for a while. My gut instinct tells me that minn<N [cos(n)] ~ 1/N, but I can't manage to prove it. I've been working around the fact that cos(x+e) ~ e when cos(x) = 0, so the question is how "quickly" n approaches N*Pi, but I've only managed to compare it to things that go slower, not faster...

So here's my line of reasoning.  Let's say the cosine has a frequency f.  Instead of looking at cos(2*pi*f*n), let's look at the points traced out on the unit circle and see how close they get to the y-axis.  Well, if f is rational then there are only finitely many points, so assume f is irrational.  Then they form a dense subset of the unit circle.  In fact, I suspect that for large N, the first N points should be close to uniformly distributed around the unit circle.  If so, then we would expect that for large N, the point closest to the y-axis is off by an angle of about 2pi/N, which would give a value for cosine of about 2pi/N.
Logged
Well you *do* need a signature...

#### pacovf

• Margrave
• Offline
• Posts: 2949
• Multiediting poster
• Respect: +3243
« Reply #112 on: May 12, 2014, 11:14:24 am »
0

Been thinking about it for a while. My gut instinct tells me that minn<N [cos(n)] ~ 1/N, but I can't manage to prove it. I've been working around the fact that cos(x+e) ~ e when cos(x) = 0, so the question is how "quickly" n approaches N*Pi, but I've only managed to compare it to things that go slower, not faster...

So here's my line of reasoning.  Let's say the cosine has a frequency f.  Instead of looking at cos(2*pi*f*n), let's look at the points traced out on the unit circle and see how close they get to the y-axis.  Well, if f is rational then there are only finitely many points, so assume f is irrational.  Then they form a dense subset of the unit circle.  In fact, I suspect that for large N, the first N points should be close to uniformly distributed around the unit circle.  If so, then we would expect that for large N, the point closest to the y-axis is off by an angle of about 2pi/N, which would give a value for cosine of about 2pi/N.

Ah, this should be true, and constitute a proof if using the proper formalism.

The points should be distributed uniformly on the circle for N large enough, I think three years ago one of my teachers did a 10 minute aside to kinda prove it, but I don't remember how he did it... I think it's a bit tricky to demonstrate rigourously.
« Last Edit: May 12, 2014, 11:16:58 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.

#### Cuzz

• Explorer
• Offline
• Posts: 324
• Respect: +439
« Reply #113 on: May 12, 2014, 03:08:34 pm »
0

Been thinking about it for a while. My gut instinct tells me that minn<N [cos(n)] ~ 1/N, but I can't manage to prove it. I've been working around the fact that cos(x+e) ~ e when cos(x) = 0, so the question is how "quickly" n approaches N*Pi, but I've only managed to compare it to things that go slower, not faster...

So here's my line of reasoning.  Let's say the cosine has a frequency f.  Instead of looking at cos(2*pi*f*n), let's look at the points traced out on the unit circle and see how close they get to the y-axis.  Well, if f is rational then there are only finitely many points, so assume f is irrational.  Then they form a dense subset of the unit circle.  In fact, I suspect that for large N, the first N points should be close to uniformly distributed around the unit circle.  If so, then we would expect that for large N, the point closest to the y-axis is off by an angle of about 2pi/N, which would give a value for cosine of about 2pi/N.

I don't think any irrational value gives a dense orbit, but a full measure set should. In fact I think a full-measure set of f will give you uniform distribution by the Birkhoff ergodic theorem.
Logged

#### soulnet

• Mountebank
• Offline
• Posts: 2142
• Respect: +1733
« Reply #114 on: May 12, 2014, 03:35:03 pm »
+1

This is one of the best pure-math (i.e., no computability or algorithmic considerations) problems I have encountered:

Are there polynomials in two variables p,q such that given f(x,y) = (p(x,y),q(x,y)) f's range is R^2 - {(0,0)}?
Logged

#### SirPeebles

• Cartographer
• Offline
• Posts: 3247
• Respect: +5403
« Reply #115 on: May 12, 2014, 03:38:18 pm »
0

Been thinking about it for a while. My gut instinct tells me that minn<N [cos(n)] ~ 1/N, but I can't manage to prove it. I've been working around the fact that cos(x+e) ~ e when cos(x) = 0, so the question is how "quickly" n approaches N*Pi, but I've only managed to compare it to things that go slower, not faster...

So here's my line of reasoning.  Let's say the cosine has a frequency f.  Instead of looking at cos(2*pi*f*n), let's look at the points traced out on the unit circle and see how close they get to the y-axis.  Well, if f is rational then there are only finitely many points, so assume f is irrational.  Then they form a dense subset of the unit circle.  In fact, I suspect that for large N, the first N points should be close to uniformly distributed around the unit circle.  If so, then we would expect that for large N, the point closest to the y-axis is off by an angle of about 2pi/N, which would give a value for cosine of about 2pi/N.

I don't think any irrational value gives a dense orbit, but a full measure set should. In fact I think a full-measure set of f will give you uniform distribution by the Birkhoff ergodic theorem.

The unit circle is compact.  If the frequency is irrational, then the orbit never repeats, and there will be an infinite subset of the unit circle, and therefore it will have an accumulation point.  This means that for any positive epsilion, one can find two points in the orbit whose angles differ by less than epsilon.  But one of these points comes sooner than the other, so this means that there is some N(epsilon) such that if you take a point in the orbit and move forward N(epsilion) steps, then you will have moved forward by this same angle less than epsilon.  It follows that the orbit is dense.
Logged
Well you *do* need a signature...

#### Cuzz

• Explorer
• Offline
• Posts: 324
• Respect: +439
« Reply #116 on: May 12, 2014, 03:51:27 pm »
0

Been thinking about it for a while. My gut instinct tells me that minn<N [cos(n)] ~ 1/N, but I can't manage to prove it. I've been working around the fact that cos(x+e) ~ e when cos(x) = 0, so the question is how "quickly" n approaches N*Pi, but I've only managed to compare it to things that go slower, not faster...

So here's my line of reasoning.  Let's say the cosine has a frequency f.  Instead of looking at cos(2*pi*f*n), let's look at the points traced out on the unit circle and see how close they get to the y-axis.  Well, if f is rational then there are only finitely many points, so assume f is irrational.  Then they form a dense subset of the unit circle.  In fact, I suspect that for large N, the first N points should be close to uniformly distributed around the unit circle.  If so, then we would expect that for large N, the point closest to the y-axis is off by an angle of about 2pi/N, which would give a value for cosine of about 2pi/N.

I don't think any irrational value gives a dense orbit, but a full measure set should. In fact I think a full-measure set of f will give you uniform distribution by the Birkhoff ergodic theorem.

The unit circle is compact.  If the frequency is irrational, then the orbit never repeats, and there will be an infinite subset of the unit circle, and therefore it will have an accumulation point.  This means that for any positive epsilion, one can find two points in the orbit whose angles differ by less than epsilon.  But one of these points comes sooner than the other, so this means that there is some N(epsilon) such that if you take a point in the orbit and move forward N(epsilion) steps, then you will have moved forward by this same angle less than epsilon.  It follows that the orbit is dense.

Ahh, of course, nevermind. You're talking about circle rotation (theta -> theta + alpha), and I was thinking of angle k-tupling instead for some reason (theta -> k*theta).
Logged

#### SirPeebles

• Cartographer
• Offline
• Posts: 3247
• Respect: +5403
« Reply #117 on: May 12, 2014, 03:57:42 pm »
0

Yeah, I'm thinking of the powers of e^(i*alpha).
Logged
Well you *do* need a signature...

#### SirPeebles

• Cartographer
• Offline
• Posts: 3247
• Respect: +5403
« Reply #118 on: May 12, 2014, 05:02:37 pm »
0

This is one of the best pure-math (i.e., no computability or algorithmic considerations) problems I have encountered:

Are there polynomials in two variables p,q such that given f(x,y) = (p(x,y),q(x,y)) f's range is R^2 - {(0,0)}?

That is a nice one.  I like topological proofs.
Logged
Well you *do* need a signature...

#### soulnet

• Mountebank
• Offline
• Posts: 2142
• Respect: +1733
« Reply #119 on: May 12, 2014, 05:38:22 pm »
0

That is a nice one.  I like topological proofs.

The only proof I know is not topological.
Logged

#### SirPeebles

• Cartographer
• Offline
• Posts: 3247
• Respect: +5403
« Reply #120 on: May 12, 2014, 06:25:57 pm »
0

That is a nice one.  I like topological proofs.

The only proof I know is not topological.

Oh, I see that I made a mistake.
Logged
Well you *do* need a signature...

#### pacovf

• Margrave
• Offline
• Posts: 2949
• Multiediting poster
• Respect: +3243
« Reply #121 on: May 12, 2014, 08:10:41 pm »
0

This is one of the best pure-math (i.e., no computability or algorithmic considerations) problems I have encountered:

Are there polynomials in two variables p,q such that given f(x,y) = (p(x,y),q(x,y)) f's range is R^2 - {(0,0)}?

Does this work? I tend to skip stuff with multivariate problems...

By reductio at absurdo

Let's define F(x,y) = p(x,y)^2+q(x,y)^2

There exists R such that for x^2+y^2 > R^2, F(x,y) > 1. We study the restriction of F to (x,y) such that x^2+y^2 =< R^2

F (restricted) is continuous over a closed space, and admits values arbitrarily close to 0. Hence it reaches 0 at some point, contradiction.

Hence there aren't any such polynomials.

Will we ever get a problem where we actually get to find a counter-example?
« Last Edit: May 12, 2014, 08:37:20 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.

#### florrat

• Minion
• Offline
• Posts: 541
• Respect: +746
« Reply #122 on: May 12, 2014, 08:41:00 pm »
+1

There exists R such that for x^2+y^2 > R^2, F(x,y) > 1.
Why?
Logged

#### soulnet

• Mountebank
• Offline
• Posts: 2142
• Respect: +1733
« Reply #123 on: May 12, 2014, 09:07:30 pm »
0

Will we ever get a problem where we actually get to find a counter-example?

I won't answer that, but I will just say, your proof is wrong.
Logged

#### pacovf

• Margrave
• Offline
• Posts: 2949
• Multiediting poster
• Respect: +3243
« Reply #124 on: May 12, 2014, 09:13:40 pm »
0

There exists R such that for x^2+y^2 > R^2, F(x,y) > 1.
Why?

Now that you mention it, that is indeed harder to prove than I thought at first (my idea was that even polynomials tend towards infinity, but that doesn't trivially imply what I wrote). Hmmm...

Will we ever get a problem where we actually get to find a counter-example?

I won't answer that, but I will just say, your proof is wrong.

Hmmm... indeed. So, the answer is yes, such a polynomial exists, right?
I guess that my mistake was the one pointed by florrat?
« Last Edit: May 12, 2014, 09:16:27 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.

#### dnkywin

• Scout
• Offline
• Posts: 42
• Respect: +56
« Reply #125 on: May 13, 2014, 01:02:07 am »
0

Will we ever get a problem where we actually get to find a counter-example?

I won't answer that, but I will just say, your proof is wrong.
Try my problem maybe?  I'll post a solution after a while if nobody gets it.
Logged

#### Kirian

• Offline
• Posts: 6799
• An Unbalanced Equation
• Respect: +8736
« Reply #126 on: May 13, 2014, 10:50:38 am »
+2

I'm thinking of a number between 1 and 100.  What is it?  Show your work.

I think I'm turning into Ozle.
Logged
Kirian's Law of f.DS jokes:  Any sufficiently unexplained joke is indistinguishable from serious conversation.

#### SirPeebles

• Cartographer
• Offline
• Posts: 3247
• Respect: +5403
« Reply #127 on: May 13, 2014, 10:56:18 am »
0

12.7
Logged
Well you *do* need a signature...

#### Awaclus

• Offline
• Posts: 9098
• (´｡• ω •｡)
• Respect: +8883
« Reply #128 on: May 13, 2014, 11:48:27 am »
0

I'm thinking of a number between 1 and 100.  What is it?  Show your work.

I think I'm turning into Ozle.
You are Ozle. Or rather, we all are Wandering Winder.

#### pacovf

• Margrave
• Offline
• Posts: 2949
• Multiediting poster
• Respect: +3243
« Reply #129 on: May 13, 2014, 12:14:20 pm »
+6

I am Spartacus.

EDIT: I think we should start a new thread where we could just post any little random tidbit that doesn't deserve its own topic
« Last Edit: May 13, 2014, 12:17:10 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.

#### navical

• Bishop
• Offline
• Posts: 122
• Respect: +136
« Reply #130 on: May 13, 2014, 05:41:44 pm »
0

Love this solution, but I think there is a minor bug:
Ah, good point.

I agree your fix does work.

I think the easiest way to define "opposite points" is to draw a line through one point that's otherwise outside the convex hull, then drawing a perpendicular to that, calling that the y-axis and using a point with the highest y-coordinate. But your way is neater.

I did wonder about the complexity of the algorithm, but it's not something I know much about, so thankyou for working it out Although the thing I like most about this solution is that it's constructable with straight edge and compass - interesting the different attitudes.
Logged

#### liopoil

• Margrave
• Offline
• Posts: 2551
• Respect: +2437
« Reply #131 on: May 13, 2014, 05:57:18 pm »
+2

I'm thinking of a number between 1 and 100.  What is it?  Show your work.
((x^2)-1)/2 where x is the base you are using. Work:

let x represent the base you are using. I interpret that for a number n to be between two numbers a and b means that abs(n-a)=abs(n-b). 1 = 1 base 10 for any base because x^0 always equals 1. 100 is equal to x^2 in any base. In representing numbers in my experience one always uses an integer base (how would a non-integer base work?), and this is clearly a base greater than 1 because you used both 1s and 0s. For any integer greater than 1, x^2>1. That means that for a number n between 1 and x^2, n-1=x^2-n. From there we can get that n = ((x^2)-1)/2.

Ask a silly question and ask for work to be shown, get a silly answer with some sloppy reasoning.
Logged

#### soulnet

• Mountebank
• Offline
• Posts: 2142
• Respect: +1733
« Reply #132 on: May 14, 2014, 11:02:56 am »
+2

Polynomial's problem actual proof:

p(x,y) = xy - 1
q(x,y) = (xy-1) x^2 - y

Verification is left as exercise for the reader (it is not hard at all).

This is an additional line to make it seem like it might be a proof instead of just the counterexample.

« Last Edit: May 14, 2014, 11:04:30 am by soulnet »
Logged

#### SirPeebles

• Cartographer
• Offline
• Posts: 3247
• Respect: +5403
« Reply #133 on: May 14, 2014, 11:19:40 am »
0

Well what do you know.  I didn't think it would be possible, but that works.
Logged
Well you *do* need a signature...

#### soulnet

• Mountebank
• Offline
• Posts: 2142
• Respect: +1733
« Reply #134 on: May 14, 2014, 11:51:50 am »
0

Well what do you know.  I didn't think it would be possible, but that works.

For your peace of mind, nobody actually solved it during the contest.
Logged

#### pacovf

• Margrave
• Offline
• Posts: 2949
• Multiediting poster
• Respect: +3243
« Reply #135 on: May 14, 2014, 12:10:45 pm »
0

Well what do you know.  I didn't think it would be possible, but that works.

For your peace of mind, nobody actually solved it during the contest.

I guess you don't know what the logic to construct the counter example is? I'm kinda... unsatisfied, right now.
Logged
pacovf has a neopets account.  It has 999 hours logged.  All his neopets are named "Jessica".  I guess that must be his ex.

#### soulnet

• Mountebank
• Offline
• Posts: 2142
• Respect: +1733
« Reply #136 on: May 14, 2014, 12:44:20 pm »
0

I guess you don't know what the logic to construct the counter example is? I'm kinda... unsatisfied, right now.

I don't. And as you can imagine, the dimension and cardinality of the space of counterexamples is the same as the dimension and cardinality of all polynomials, so it is hard to say there is something "special".
Logged

#### SirPeebles

• Cartographer
• Offline
• Posts: 3247
• Respect: +5403
« Reply #137 on: May 14, 2014, 02:07:29 pm »
+1

Well what do you know.  I didn't think it would be possible, but that works.

For your peace of mind, nobody actually solved it during the contest.

I guess you don't know what the logic to construct the counter example is? I'm kinda... unsatisfied, right now.

A cubic polynomial always has a real root.  So consider px^3 + qx + r = 0. This always has a solution unless both p and q are zero while r is nonzero, so let's just choose r = p+1 to avoid all three being zero.  Solve for q and you find -q = px^2 + r/x.  We want q to be a polynomial, so let's add a new variable y = r/x.  Voila.  Now p = r - 1 = xy - 1, and -q = p x^2 + r/x = (xy - 1) x^2 + y.
Logged
Well you *do* need a signature...

#### dominator 123

• Young Witch
• Offline
• Posts: 146
• Notice the space
• Respect: +290
« Reply #138 on: May 15, 2014, 10:25:36 am »
0

Well what do you know.  I didn't think it would be possible, but that works.

For your peace of mind, nobody actually solved it during the contest.

I guess you don't know what the logic to construct the counter example is? I'm kinda... unsatisfied, right now.

A cubic polynomial always has a real root.  So consider px^3 + qx + r = 0. This always has a solution unless both p and q are zero while r is nonzero, so let's just choose r = p+1 to avoid all three being zero.  Solve for q and you find -q = px^2 + r/x.  We want q to be a polynomial, so let's add a new variable y = r/x.  Voila.  Now p = r - 1 = xy - 1, and -q = p x^2 + r/x = (xy - 1) x^2 + y.
Or simply the cubic graph ranges from -infinity to infinity so it must cross the line x=0 somewhere.
Logged
dominator 123 plays a Scout
... dominator 123 reveals a Tournament, a Baron, a Province and an Estate

#### heron

• Jester
• Offline
• Posts: 970
• Respect: +1089
« Reply #139 on: May 15, 2014, 07:21:31 pm »
0

I think I will post a well-known combinatorics question now:

17 students take a 9-question test. For each question on the test, at least 11 students answered the question correctly. Prove there there exist 2 students such that between them they have answered each question correctly.
Logged
PPR is for wimps.

#### SirPeebles

• Cartographer
• Offline
• Posts: 3247
• Respect: +5403
« Reply #140 on: May 16, 2014, 09:09:15 am »
0

I just read a headline asking whether a certain national health policy would lead to fewer deaths.  I wish news reporters were better at mathing

(I'm not giving further details because I don't want a political/policy discussion)
Logged
Well you *do* need a signature...

#### Jack Rudd

• Jester
• Offline
• Posts: 932
• Shuffle iT Username: Jack Rudd
• Respect: +806
« Reply #141 on: May 16, 2014, 12:53:50 pm »
+1

I think I will post a well-known combinatorics question now:

17 students take a 9-question test. For each question on the test, at least 11 students answered the question correctly. Prove there there exist 2 students such that between them they have answered each question correctly.
With at least 99 correct answers and only 17 students, at least one student must have at least six answers right. Let us concentrate on that student and the three questions he got wrong (if he got 7 or more right, the same types of arguments work but are significantly more trivial to see). Then each of those three questions can only have been got wrong by five of the other students. Even if no two of those students got the same question wrong, that accounts for only fifteen students. The other student therefore got them all right.
Logged
Centuries later, archaeologists discover the remains of your ancient civilization.

Evidence of thriving towns, Pottery, roads, and a centralized government amaze the startled scientists.

Finally, they come upon a stone tablet, which contains but one mysterious phrase!

'ISOTROPIC WILL RETURN!'

#### sudgy

• Cartographer
• Online
• Posts: 3120
• It's pronounced "SOO-jee"
• Respect: +2285
« Reply #142 on: June 16, 2014, 12:12:30 am »
0

(This is probably actually not the best way to go about things, and is half in jest.  You'll see my point at the end.)

Alright, so I decided to try to extend the divisor function σ(n) to the Gaussian Integers.  I realized that the best way to do this is to make it so that only certain numbers can be divisors, because making them all divisors makes the divisor function equal to 0.  After much trial and error, I figured out what would make the best sections.  The two sections are:

Section 1: All numbers in the first and second quadrants of the Cartesian Plane, including the negative reals and not including the positive reals.

Section 2: All numbers in the third and fourth quadrants, including the positive reals and not including the negative reals.

All of the divisors of a Gaussian Integer Z are defined as the Gaussian Integers x in the same section as Z, that, when multiplied by another Gaussian Integer y in the same section, equal Z.

Using this definition, we can find the value of the divisor function for a few different complex numbers:

σ(i) = 0
σ(1 + i) = 0 (I think)
σ(-2i) = (-2i) + (1) + (1 - i) + (2) + (-i) = 4 - 4i
σ(3i) = 0

Wait, let's look at the abundancy at a couple of those.  i and 3i both have an abundancy of 0.  That means they are friendly.  You might not notice, but this has huge ramifications.

...I just proved the existence of imaginary friends.

(Yes, this was inspired by this xkcd)
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

#### heron

• Jester
• Offline
• Posts: 970
• Respect: +1089
« Reply #143 on: June 17, 2014, 11:54:15 pm »
0

I am stumped by the following combinatorics question:

In a mathematical competition some competitors are friends. Friendship is always mutual. Call a group of competitors a clique if each two of them are friends. (In particular, any group of fewer than two competitors is a clique.) The number of members of a clique is called its size.

Given that, in this competition, the largest size of a clique is even, prove that the competitors can be arranged into two rooms such that the largest size of a clique contained in one room is the same as the largest size of a clique contained in the other room.

(ISL 2007, Vasily Astakhov)

I have so far tried induction of various forms, none of which proved successful. I also thought that maybe proving the contrapositive would be easier, but it wasn't. My current tactic is to try to create an algorithm to produce the two rooms with equally sized cliques. This path shows some progress, but there are many cases.

Maybe one of you guys will have better luck.
Logged
PPR is for wimps.

#### DStu

• Margrave
• Offline
• Posts: 2627
• Respect: +1476
« Reply #144 on: June 18, 2014, 01:33:57 am »
0

"size of a clique contained in one room" is now only the size on the subset of competitors that are in this room, ignoring the other room? Or do you have to place cliques in one room? Obviously not, because in this case the result would be false...
Logged

#### florrat

• Minion
• Offline
• Posts: 541
• Respect: +746
« Reply #145 on: June 18, 2014, 02:47:16 am »
+1

This problem is very very hard. I recognize it for being problem IMO 2007-3 which should give an indication of the difficulty. (what does ISL mean? IMO shortlist?)

I have never solved this problem, but I've read the solution when I participated in that IMO a couple years back. You indeed construct an algorithm to make the clique sizes equal.
IIRC, you start with everyone in room A, and then send persons to room B one by one. The nice thing about this is that when you send a person from room A to room B, the max clique size in room A goes down by at most one and the max clique size in room B goes up by one. So the only way this can go wrong is when at some point the difference in max clique size is one, and when you send a person to room B which changes the clique size in both rooms. Unfortunately, you cannot avoid this case in general, so you have to do some more work by sending the right people in room B back to room A.
I forgot the details. If you want to know the solution, you can find it here [pdf].

"size of a clique contained in one room" is now only the size on the subset of competitors that are in this room, ignoring the other room?
Yes
« Last Edit: June 18, 2014, 02:49:20 am by florrat »
Logged

#### heron

• Jester
• Offline
• Posts: 970
• Respect: +1089
« Reply #146 on: June 18, 2014, 07:49:43 pm »
0

This problem is very very hard. I recognize it for being problem IMO 2007-3 which should give an indication of the difficulty. (what does ISL mean? IMO shortlist?)

I have never solved this problem, but I've read the solution when I participated in that IMO a couple years back. You indeed construct an algorithm to make the clique sizes equal.
IIRC, you start with everyone in room A, and then send persons to room B one by one. The nice thing about this is that when you send a person from room A to room B, the max clique size in room A goes down by at most one and the max clique size in room B goes up by one. So the only way this can go wrong is when at some point the difference in max clique size is one, and when you send a person to room B which changes the clique size in both rooms. Unfortunately, you cannot avoid this case in general, so you have to do some more work by sending the right people in room B back to room A.
I forgot the details. If you want to know the solution, you can find it here [pdf].

"size of a clique contained in one room" is now only the size on the subset of competitors that are in this room, ignoring the other room?
Yes

Thanks for the link. Yes, ISL stands for IMO Shortlist. Nested acronyms ftw.

I see that if I had continued down that path I might have finished. Oh well. Maybe if I had used the same style of diagram they used in the solution I would have been able to envision the cases better.

It's cool that you went to IMO though! I hope to be able to go in two years, but I will need to make a lot of improvement.
Logged
PPR is for wimps.

#### scott_pilgrim

• Jester
• Offline
• Posts: 958
• Respect: +1857
« Reply #147 on: June 18, 2014, 08:15:15 pm »
+4

Logged

#### ConMan

• Saboteur
• Online
• Posts: 1154
• Respect: +1260
« Reply #148 on: June 18, 2014, 11:29:12 pm »
0

Nested acronyms ftw.

NAF!
I prefer recursive acronyms. For example, TIARA is a recursive acronym.
Logged

#### Tables

• Margrave
• Offline
• Posts: 2651
• Build more Bridges in the King's Court!
• Respect: +3125
« Reply #149 on: June 27, 2014, 08:17:12 am »
0

Consider the complete graph on 7 vertices (that is, 7 points, all of which have an edge connecting them to every other point). It has 21 edges. It's possible to pick 7 triangles of 3 edges such that the edges form a triangle, and each edge is part of only one triangle (an example is shown below).

How many different sets of triangles can be picked like this?

My answer: I made the answer 30, which I think is correct, but I think it's an interesting enough question to have a go at.
Logged
...spin-offs are still better for all of the previously cited reasons.
But not strictly better, because the spinoff can have a different cost than the expansion.
I hereby declare myself the best dominion player in the world. Obviously.

#### Kirian

• Offline
• Posts: 6799
• An Unbalanced Equation
• Respect: +8736
« Reply #150 on: June 27, 2014, 08:40:38 am »
+1

OK, strange question: in UK and non-US post-colonies, you shorten "mathematics" to "maths."  Do you also shorten "economics" to "econs"?
Logged
Kirian's Law of f.DS jokes:  Any sufficiently unexplained joke is indistinguishable from serious conversation.

#### Kirian

• Offline
• Posts: 6799
• An Unbalanced Equation
• Respect: +8736
« Reply #151 on: June 27, 2014, 08:44:48 am »
0

Consider the complete graph on 7 vertices (that is, 7 points, all of which have an edge connecting them to every other point). It has 21 edges. It's possible to pick 7 triangles of 3 edges such that the edges form a triangle, and each edge is part of only one triangle (an example is shown below).

How many different sets of triangles can be picked like this?

My answer: I made the answer 30, which I think is correct, but I think it's an interesting enough question to have a go at.

Do rotations and reflections count as unique sets?  I'm assuming not, but maybe you counted them.
Logged
Kirian's Law of f.DS jokes:  Any sufficiently unexplained joke is indistinguishable from serious conversation.

#### navical

• Bishop
• Offline
• Posts: 122
• Respect: +136
« Reply #152 on: June 27, 2014, 08:46:34 am »
0

OK, strange question: in UK and non-US post-colonies, you shorten "mathematics" to "maths."  Do you also shorten "economics" to "econs"?
If it gets shortened at all, it would be "econ", but I've not really heard that from people other than economics students (or at least, students who study some economics)
Logged

#### Tables

• Margrave
• Offline
• Posts: 2651
• Build more Bridges in the King's Court!
• Respect: +3125
« Reply #153 on: June 27, 2014, 09:03:33 am »
0

Consider the complete graph on 7 vertices (that is, 7 points, all of which have an edge connecting them to every other point). It has 21 edges. It's possible to pick 7 triangles of 3 edges such that the edges form a triangle, and each edge is part of only one triangle (an example is shown below).

How many different sets of triangles can be picked like this?

My answer: I made the answer 30, which I think is correct, but I think it's an interesting enough question to have a go at.

Do rotations and reflections count as unique sets?  I'm assuming not, but maybe you counted them.

Yes, provided it's actually unique and not just a recolouring (e.g. if you'd be rotating/reflecting in a way that made the 7 same triangles I did but with different colours, that doesn't count).

OK, strange question: in UK and non-US post-colonies, you shorten "mathematics" to "maths."  Do you also shorten "economics" to "econs"?

I don't think I've ever heard economics shortened, but econ would seem the natural way to shorten it if it were.
Logged
...spin-offs are still better for all of the previously cited reasons.
But not strictly better, because the spinoff can have a different cost than the expansion.
I hereby declare myself the best dominion player in the world. Obviously.

#### Kirian

• Offline
• Posts: 6799
• An Unbalanced Equation
• Respect: +8736
« Reply #154 on: June 27, 2014, 10:56:02 am »
0

Consider the complete graph on 7 vertices (that is, 7 points, all of which have an edge connecting them to every other point). It has 21 edges. It's possible to pick 7 triangles of 3 edges such that the edges form a triangle, and each edge is part of only one triangle (an example is shown below).

How many different sets of triangles can be picked like this?

My answer: I made the answer 30, which I think is correct, but I think it's an interesting enough question to have a go at.

Do rotations and reflections count as unique sets?  I'm assuming not, but maybe you counted them.

Yes, provided it's actually unique and not just a recolouring (e.g. if you'd be rotating/reflecting in a way that made the 7 same triangles I did but with different colours, that doesn't count).

Let me rephrase: Your solution contains triangles 123, 145, 167, 246, 257, 347, and 357.  A tau/7 rotation clockwise is the set of triangles 234, 256, 127, 357, 136, 145, and 146.

If these are unique solutions, then you've provided seven solutions with your diagram, because it doesn't have sevenfold symmetry.  Is it correct that your diagram is really seven unique solutions?

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

#### sudgy

• Cartographer
• Online
• Posts: 3120
• It's pronounced "SOO-jee"
• Respect: +2285
« Reply #155 on: June 27, 2014, 03:13:40 pm »
0

Consider the complete graph on 7 vertices (that is, 7 points, all of which have an edge connecting them to every other point). It has 21 edges. It's possible to pick 7 triangles of 3 edges such that the edges form a triangle, and each edge is part of only one triangle (an example is shown below).

How many different sets of triangles can be picked like this?

My answer: I made the answer 30, which I think is correct, but I think it's an interesting enough question to have a go at.

I remember my mathbook last year had a formula for this, but I can't remember 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

#### heron

• Jester
• Offline
• Posts: 970
• Respect: +1089
« Reply #156 on: June 27, 2014, 03:17:59 pm »
0

Logged
PPR is for wimps.

#### soulnet

• Mountebank
• Offline
• Posts: 2142
• Respect: +1733
« Reply #157 on: June 28, 2014, 02:44:49 am »
+1

I agree with Kirian's request for clarification. Are the nodes labeled or indistinguishable? Rotations and symmetry in graphs are strange, because it is not just rotating and symmetry, since the topology is not geometric.
Logged

#### florrat

• Minion
• Offline
• Posts: 541
• Respect: +746
« Reply #158 on: June 28, 2014, 08:42:47 am »
0

Assuming the two colorings Kirian gives count as different solutions, I get -135- colorings (I can write an explanation later)
Logged

#### silverspawn

• Cartographer
• Offline
• Posts: 3784
• ♦ Twilight ♦
• Respect: +1648
« Reply #159 on: June 28, 2014, 10:19:12 am »
0

i have this task I'm struggling with. I'm sure I can selfishly abuse this thread to get some help... right?

so the growth rate of a plant is proportional to its height and anti proportional to the third power (do you say it like that?) of the time passed. the height is y and y(1) = 5.

so I made the equation y'(t) = y * 1/t³ * K

and I have this formula that says
Quote
y' = g(t)*h(y) => INTEGRAL(1/h(y)) = INTEGRAL(g(t))

so i define g(t) := K/t³ and h(y) := y, and use the formula and then I get

INTEGRAL(1/y) = INTEGRAL(1/t³*K)
and so
ln(y) = K * (-1/2 (t^-2)) | e^
y = e^(-1/2 K*(t^-2))

so y(1) = e^(-1/2K) = 5 | ln
-1/2 K = ln(5) | *(-2)
K = -2ln(5)

and so

y(t) = e^[-1/2(-2ln(5)) * t^-2)]
y(t) = [e^(ln(5))]^(t^-2)
y(t) = 5^(t^-2)
y(t) = 5^(1/t²)

so the plant has infinite height right after it spawns and then shrinks really fast? that doesn't sound right
Logged

#### Kirian

• Offline
• Posts: 6799
• An Unbalanced Equation
• Respect: +8736
« Reply #160 on: June 28, 2014, 10:34:13 am »
0

Assuming the two colorings Kirian gives count as different solutions, I get -135- colorings (I can write an explanation later)

If all seven rotations are unique, the final answer has to be divisible by 7, doesn't it?
Logged
Kirian's Law of f.DS jokes:  Any sufficiently unexplained joke is indistinguishable from serious conversation.

#### pacovf

• Margrave
• Offline
• Posts: 2949
• Multiediting poster
• Respect: +3243
« Reply #161 on: June 28, 2014, 11:32:30 am »
0

i have this task I'm struggling with. I'm sure I can selfishly abuse this thread to get some help... right?

so the growth rate of a plant is proportional to its height and anti proportional to the third power (do you say it like that?) of the time passed. the height is y and y(1) = 5.

so I made the equation y'(t) = y * 1/t³ * K

and I have this formula that says
Quote
y' = g(t)*h(y) => INTEGRAL(1/h(y)) = INTEGRAL(g(t))

so i define g(t) := K/t³ and h(y) := y, and use the formula and then I get

INTEGRAL(1/y) = INTEGRAL(1/t³*K)
and so
ln(y) = K * (-1/2 (t^-2)) | e^
y = e^(-1/2 K*(t^-2))

so y(1) = e^(-1/2K) = 5 | ln
-1/2 K = ln(5) | *(-2)
K = -2ln(5)

and so

y(t) = e^[-1/2(-2ln(5)) * t^-2)]
y(t) = [e^(ln(5))]^(t^-2)
y(t) = 5^(t^-2)
y(t) = 5^(1/t²)

so the plant has infinite height right after it spawns and then shrinks really fast? that doesn't sound right

Setting t = 0 doesn't make any sense because of your differential equation. It spawns at t = 1 (or t0 =/= 0, whatever) in the model you are using, so it has a limited height when it "spawns". And for t very large, the plant is actually decreasing in size very slowly...

On the other hand, if you choose y(t0) <  1, K becomes positive. Your plant then increases in size, but never getting larger than 1. I would guess that makes more intuitive sense (since we are working in arbitrary units, you can choose 1 to be anything you like with the relevant rescaling).
« Last Edit: June 28, 2014, 11:41:32 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.

#### Kirian

• Offline
• Posts: 6799
• An Unbalanced Equation
• Respect: +8736
« Reply #162 on: June 28, 2014, 11:34:09 am »
0

Silverspawn, the problem as given needs a second initial condition; you've forgotten to introduce a constant of integration, but once you have that there's no second initial condition.

Are we supposes to assume that y(0)=0?
Logged
Kirian's Law of f.DS jokes:  Any sufficiently unexplained joke is indistinguishable from serious conversation.

#### pacovf

• Margrave
• Offline
• Posts: 2949
• Multiediting poster
• Respect: +3243
« Reply #163 on: June 28, 2014, 11:38:12 am »
0

Silverspawn, the problem as given needs a second initial condition; you've forgotten to introduce a constant of integration, but once you have that there's no second initial condition.

Are we supposes to assume that y(0)=0?

AFAIK, he's not missing any condition. It's a first order differential equation, one condition is enough. His integration is somewhat dirty (lacks integration constant indeed), but the result is correct.
inb4 I am showed the error in my ways.

y(0) = 0 is not a very interesting case though
« Last Edit: June 28, 2014, 11:45:49 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.

#### Kirian

• Offline
• Posts: 6799
• An Unbalanced Equation
• Respect: +8736
« Reply #164 on: June 28, 2014, 11:45:29 am »
0

Silverspawn, the problem as given needs a second initial condition; you've forgotten to introduce a constant of integration, but once you have that there's no second initial condition.

Are we supposes to assume that y(0)=0?

AFAIK, he's not missing any condition. It's a first order differential equation, one condition is enough.
inb4 I am showing the error in my ways.

y(0) = 0 is not a very interesting case though

Then it's not a completely defined equation... because we don't know the initial rate.  We have y' = ky/t^3 and not y' = y/t^3
Logged
Kirian's Law of f.DS jokes:  Any sufficiently unexplained joke is indistinguishable from serious conversation.

#### WalrusMcFishSr

• Minion
• Offline
• Posts: 642
• An enormous walrus the size of Antarctica
• Respect: +1779
« Reply #165 on: June 28, 2014, 11:46:06 am »
+1

i have this task I'm struggling with. I'm sure I can selfishly abuse this thread to get some help... right?

so the growth rate of a plant is proportional to its height and anti proportional to the third power (do you say it like that?) of the time passed. the height is y and y(1) = 5.

so I made the equation y'(t) = y * 1/t³ * K

and I have this formula that says
Quote
y' = g(t)*h(y) => INTEGRAL(1/h(y)) = INTEGRAL(g(t))

so i define g(t) := K/t³ and h(y) := y, and use the formula and then I get

INTEGRAL(1/y) = INTEGRAL(1/t³*K)
and so
ln(y) = K * (-1/2 (t^-2)) | e^
y = e^(-1/2 K*(t^-2))

so y(1) = e^(-1/2K) = 5 | ln
-1/2 K = ln(5) | *(-2)
K = -2ln(5)

and so

y(t) = e^[-1/2(-2ln(5)) * t^-2)]
y(t) = [e^(ln(5))]^(t^-2)
y(t) = 5^(t^-2)
y(t) = 5^(1/t²)

so the plant has infinite height right after it spawns and then shrinks really fast? that doesn't sound right

It's been a while, but I'll try...

I think part of the problem is after

INTEGRAL(1/y) = INTEGRAL(1/t³*K)

we need an integration constant C. So

ln(y) = K * (-1/2 (t^-2)) + C

or going to the more usual way

y = C * e^(-1/2 K*(t^-2))

The problem is I'm not sure you can solve C and K at the same time without some extra information. Even with y(1)=5 you get different answers for different values of K.

Solving in terms of K you end up with a solution like

y = 5e ^ ((K * (t^2 - 1)) / 2t^2)

which for positive K gives a behavior more like what you'd expect for a plant. You might want to wait for one of the real mathematicians to chime in though.

PPE: I agree with Kirian
Logged
My Dominion videos: http://www.youtube.com/user/WalrusMcFishSr   <---Bet you can't click on that!

#### Tables

• Margrave
• Offline
• Posts: 2651
• Build more Bridges in the King's Court!
• Respect: +3125
« Reply #166 on: June 28, 2014, 11:48:43 am »
+1

I agree with Kirian's request for clarification. Are the nodes labeled or indistinguishable? Rotations and symmetry in graphs are strange, because it is not just rotating and symmetry, since the topology is not geometric.

Yeah, sorry, I knew it wasn't entirely clear, I hoped numbering the vertices made it clearer but apparently not. The two examples Kirian gave would be distinct.

Assuming the two colorings Kirian gives count as different solutions, I get -135- colorings (I can write an explanation later)

If all seven rotations are unique, the final answer has to be divisible by 7, doesn't it?

No, not necessarily. Some rotations could give solutions that had already been counted, I believe.

(Also I'm just going to throw this here, how I came up with the question. I'm currently playing a game called Xenoblade Chronicles, for about the 10th time, and it has 7 playable characters. You always have 3 active characters at a time, which are the ones who participate in battles and stuff. I noticed you could form 7 parties of characters such that everyone was in a party with everyone else, exactly once. I then started wondering how many possible ways you could arrange the people into 7 battle parties, as above. And so the question was born. Hopefully if you get what I'm saying here you'll also get what things I'm looking for that count and what doesn't).
Logged
...spin-offs are still better for all of the previously cited reasons.
But not strictly better, because the spinoff can have a different cost than the expansion.
I hereby declare myself the best dominion player in the world. Obviously.

#### sudgy

• Cartographer
• Online
• Posts: 3120
• It's pronounced "SOO-jee"
• Respect: +2285
« Reply #167 on: June 28, 2014, 11:49:19 am »
+4

Here's an integral symbol for you all to be able to copy and paste: ∫

(I'm getting tired of seeing INTEGRAL everywhere)
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

#### Tables

• Margrave
• Offline
• Posts: 2651
• Build more Bridges in the King's Court!
• Respect: +3125
« Reply #168 on: June 28, 2014, 11:54:22 am »
+6

Here's an integral symbol for you all to be able to copy and paste: ∫

(I'm getting tired of seeing INTEGRAL everywhere)

Logged
...spin-offs are still better for all of the previously cited reasons.
But not strictly better, because the spinoff can have a different cost than the expansion.
I hereby declare myself the best dominion player in the world. Obviously.

#### SirPeebles

• Cartographer
• Offline
• Posts: 3247
• Respect: +5403
« Reply #169 on: June 28, 2014, 11:55:29 am »
+4

Here's an integral symbol for you all to be able to copy and paste: ∫

(I'm getting tired of seeing INTEGRAL everywhere)

I knew sum one would make that joke.
Logged
Well you *do* need a signature...

#### pacovf

• Margrave
• Offline
• Posts: 2949
• Multiediting poster
• Respect: +3243
« Reply #170 on: June 28, 2014, 11:55:48 am »
0

y' = dy/dt = K*y/t3

=> dy/y = K * dt/t3  (yes yes physicists are eeevil)

=> ∫y(1)y(t) dy/y = ∫1t K*dt/t3

=> ln(y(t)/y(1)) = K/2 * (1-1/t2)

Somehow when I did this in my mind knowing y(1) actually helped me find K. So once again I bow to the wisdom of Kirian.
I stand by my previous result that you need K positive to get a sensible progression for the plant, though.

EDIT: groan...
« Last Edit: June 28, 2014, 12:05:59 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.

#### SirPeebles

• Cartographer
• Offline
• Posts: 3247
• Respect: +5403
« Reply #171 on: June 28, 2014, 11:58:05 am »
0

I think we've given plenty of hints towards how to do his homework problem already, we don't need to present a detailed write up.
Logged
Well you *do* need a signature...

#### silverspawn

• Cartographer
• Offline
• Posts: 3784
• ♦ Twilight ♦
• Respect: +1648
« Reply #172 on: June 28, 2014, 01:10:14 pm »
0

I think we've given plenty of hints towards how to do his homework problem already, we don't need to present a detailed write up.
it's not a homework. i've had maths 2 semesters ago, but the lecture was at 8am, and i wasn't capable of standing up at 6am regularly, so I stopped visiting it at some point, and then I didn't want to visit it again because I had already skipped too many lectures (and the lecture was kind of bad too); now I want to write the exam at the end of this semester. unfortunately, I now have just a script to learn from.

which means I don't have get something done or anything, I just need to be able to do it properly.

I think what you're supposed to do is not calculate K but do it relative to K instead, like so

Quote
Solving in terms of K you end up with a solution like

y = 5e ^ ((K * (t^2 - 1)) / 2t^2)

which for positive K gives a behavior more like what you'd expect for a plant. You might want to wait for one of the real mathematicians to chime in though.

based on how it's formulated

thanks *)
Logged

#### florrat

• Minion
• Offline
• Posts: 541
• Respect: +746
« Reply #173 on: June 28, 2014, 06:06:22 pm »
0

[note: spoilers for triangle puzzle below]

@silverspawn: Not sure if the integral problem was already sorted out completely, but Kirian is right, you need an constant of integration. So the equation you get is (ln is for barbarians, I use log with base e):

log(y) = K * (-1/2 (t^-2)) + C

(note that you only need a constant on one side of the equation, since if you have constants on both sides, you could just define a new constant as the difference between the two constants you had, and use that instead)

Now you want to use the information y(1) = 5 to eliminate the constant C, and then you'll be able to get a formula

y(t) = *something which depends on t and K*

If all seven rotations are unique, the final answer has to be divisible by 7, doesn't it?
As Tables said, some solutions will be rotated to themselves. However, this is only possible if every rotation of that solution will be identical to it.

[sidenote]You can see this as follows. Suppose that if by rotating 3 times (3/7tau) you get to the same solution, then if you rotate 3*5 times, you'll get to the same solution as well (because you did 3 rotations 5 times, which doesn't change anything), but rotating 15 times is the same as rotating once. And if rotating once doesn't change anything, any rotation doesn't change anything. On a more technical note: the reason is that since 7 is prime, (Z/7Z,+) is a group.[/sidenote]

Indeed, there are two solutions which are rotated to themselves, namely:
124 and its rotations (124,235,346,457,561,672,713)
134 and its rotations (134,245,356,467,571,612,723)
And the remaining number of solutions - 133 - is indeed divisible by 7.

---

Back to the original puzzle, to see that the answer is 135, consider the following. First note that the problem is equivalent to finding the number of ways to pick 7 triangles such that no two triangles have 2 nodes in common (since a triangle has an edge in common if and only if it has 2 nodes in common).

For convenience we don't have names for the 7 nodes yet. Pick two arbitrary nodes, and call them node 1 and node 2. First let's see how many ways there are to put node 1 in three triangles with the other six nodes. There has to be a triangle with both nodes 1 and 2, and there are 5 possibilities for that. Call the third node of this triangle node 3, and call the other four nodes 4-7 in any order. For the triangle with both nodes 1 and nodes 4, there are 3 possibilities (by picking any of nodes 5-7), and for the remaining triangle with 1 as node there's just 1 possibility (picking the remaning two nodes).

Now every node other than node 1 still needs two more triangles. Let's focus on node 2, which still needs triangles with nodes 4,5,6,7. There are 3 ways to split these four nodes in two groups of two nodes, which is the number of ways to pick the remaining two triangles containing node 2. Also node 3 needs two more triangles with nodes 4,5,6,7, so there are also 3 possibilities for that.

In total there are 5*3*3*3=135 possible colorings.
Logged

#### heron

• Jester
• Offline
• Posts: 970
• Respect: +1089
« Reply #174 on: June 28, 2014, 10:12:04 pm »
+2

Now every node other than node 1 still needs two more triangles. Let's focus on node 2, which still needs triangles with nodes 4,5,6,7. There are 3 ways to split these four nodes in two groups of two nodes, which is the number of ways to pick the remaining two triangles containing node 2.

Except, one of the ways you split those four nodes will result in a triangle with two nodes that were used in one of the triangles with node one.
(e.g. if 145 is a triangle, then then the other triangles with node 2 must be 246 and 257 or 247 and 256, but not 245 and 267.)
So, in fact there are just two ways to pick the remaining two triangles for node 2.

Similarly, there is just 1 way to pick all of the remaining triangles, so I stand by my answer of thirty.
Logged
PPR is for wimps.

#### florrat

• Minion
• Offline
• Posts: 541
• Respect: +746
« Reply #175 on: June 29, 2014, 02:39:56 pm »
0

That's a good point, I stand corrected.
Logged

#### heron

• Jester
• Offline
• Posts: 970
• Respect: +1089
« Reply #176 on: July 08, 2014, 11:58:51 pm »
0

Well, the problems for day 1 of the international mathematical olympiad are released today. http://www.artofproblemsolving.com/Forum/resources.php?c=1&cid=16&year=2014&sid=e94cbd1547c0c955ad8ef37cf50e71a0

I solved #1 and #2 (with some help from friends) in just under 2 hours, and am reasonably sure that I could solve #3 with complex numbers in the remaining 150 minutes if I were actually participating in the IMO, but it did not sound very fun to do for practice. I guess I will try to see if I can bash out that solution tomorrow.

I think that the problems are relatively easy for the IMO though, especially #2. What do you guys think?
Logged
PPR is for wimps.

#### SirPeebles

• Cartographer
• Offline
• Posts: 3247
• Respect: +5403
« Reply #177 on: July 29, 2014, 03:02:29 pm »
+13

Logged
Well you *do* need a signature...

#### Kirian

• Offline
• Posts: 6799
• An Unbalanced Equation
• Respect: +8736
« Reply #178 on: July 29, 2014, 03:30:51 pm »
+3

...because they're uncountable?
Logged
Kirian's Law of f.DS jokes:  Any sufficiently unexplained joke is indistinguishable from serious conversation.

#### Joseph2302

• Jester
• Offline
• Posts: 817
• "Better to be lucky than good"
• Respect: +535
« Reply #179 on: September 26, 2014, 12:37:15 pm »
0

I reckon P=NP, would be so cool if it did.
Logged
Mafia Stats:
Town: 11 games, 5 wins
Scum: 3 games, 1 win

#### florrat

• Minion
• Offline
• Posts: 541
• Respect: +746
« Reply #180 on: November 28, 2014, 06:34:07 pm »
+1

(continued from discussion in random stuff thread)
Mathematicians rarely prove things in a logic where proof-checking is decidable. They prove things in some form of intuitionisitic logic, usually with higher-order functions. SOME (possibly most, but I don't know) of those proofs COULD be translated into a proof in a logical system with computable proof-checking available, but (almost) nobody does it. And few people care enough to even have a sentence that says "this proof can *clearly* be made using this amount of logical power, so, we are cool".
Can you elaborate what you mean with the first sentence? Can you give a specific undecidable logic where you think mathematicians work in?
I think most mathematician have faith that both their theorems and their proofs can be encoded in - for example - ZFC in classical first order logic, which is AFAIK the most accepted foundation of mathematics under mathematicians. Checking a formal proof in this logic is super decidable (I think linear in the length of the proof). Higher-order logics (intuitionistic or not) can also be decidable, such as the intentional Martin-Löf type theory. True, extensional type theory is undecidable, but I'm claiming that mathematicians rarely work specifically in extensional type theory (if only because they don't specify in which logic they work, and hence their informal proof can be formalized in many logics, some of which are decidable).

Or are you talking about another problem: translating mathematical proofs on paper accepted by other mathematicians to rigorous formal proofs in some (decidable) logic? I agree that such a translation is infeasibly hard, but I think this problem is too vague to say that it is undecidable. I think that if a proof contains enough details, it should be possible to translate it into a formal proof. This is what happens with proof assistants all the time.
There is some value in the generalization, of course, which is mostly connecting things that were seemingly disconnected. My point is that there is also a loss in value because the proof done directly on the subject at hand is much more illustrating on the phenomena the person reading the theorem is interested in. So, my point is not that category theory is useless (although I think category theory is a drug at this point, kind of like string theory for mathematicians), but that it is over-praised as the ultimate tool and even the only thing that is worthy (or legit...).

So, to come back to my original post, more general is not always better. I agree with you that it is sometimes better and I would add that it is usually incomparable.

Caveat + example: My very first paper on my PhD topic is a simple combinatorial proof of a fact that was already known, but required to combine more general results from three different papers. Doing that lead to the ability to produce results for similar scenarios which an author of one of those papers was unable to get despite working in the question for some time.
I agree that a simple elementary proofs has a lot of merits. However, I do prefer a simple general proofs over complicated elementary proofs. And it is pretty common that a proof becomes simpler in a general setting. For example in category theory, there's often just one thing you can do in a proof, which makes proofs not that hard to find. More specifically about category theory: I'm neither saying that it is "the ultimate tool" or that it's the only worthy thing. However, I do think it's a very useful and very important tool. You might be interested in this (short) answer on stackexchange which gives examples where category theory has been useful for other fields of mathematics.

And yes, in the end, a general theory is not strictly better, so a more general and a less general theory are incomparable, but I think the more general theory is better in 9 out of 10 aspects.
Logged

#### soulnet

• Mountebank
• Offline
• Posts: 2142
• Respect: +1733
« Reply #181 on: November 29, 2014, 12:41:01 pm »
+1

Can you elaborate what you mean with the first sentence? Can you give a specific undecidable logic where you think mathematicians work in?
http://en.wikipedia.org/wiki/Higher-order_logic

I think most mathematician have faith that both their theorems and their proofs can be encoded in - for example - ZFC in classical first order logic, which is AFAIK the most accepted foundation of mathematics under mathematicians.
My point is precisely that most mathematicians (barring those working in logic) do not. They usually do things like "let f be a function" or "consider the smallest subset such that", and those are second-order logic statements. And in category theory it is probably worse, as you are constantly using functions as the domain of functions, which takes you to third-order already, and then you are done with full-decidability.

First order is extremely weak, you cannot even define the natural numbers or the real numbers with it.

One possible thing is that all the proofs that use higher-order logic can be translated into weaker logics. That seems completely plausible to me. However, it would be extremely difficult to do, and quite likely, a waste of time. I don't care that math works by consensus, I actually like that it behaves like this, I like math being a science.

Checking a formal proof in this logic is super decidable (I think linear in the length of the proof). Higher-order logics (intuitionistic or not) can also be decidable, such as the intentional Martin-Löf type theory. True, extensional type theory is undecidable, but I'm claiming that mathematicians rarely work specifically in extensional type theory (if only because they don't specify in which logic they work, and hence their informal proof can be formalized in many logics, some of which are decidable).

Any FOL with finitely many symbols is decidable. I never thought about linearity, but I guess you are probably right (if you count as "length of the proof" the sum of the lengths of each step). However, the size of a formal proof in an extension of a formal system like SP is probably enormous compared with the actual proof people write in a paper using a mixture of higher-order symbols (like functions) and natural language. Any quantification I can make here is no better than a wild guess, but if someone proofs that actual theorems can be proof with manageable-size proofs in a formal decidable system I would be amazed.

Or are you talking about another problem: translating mathematical proofs on paper accepted by other mathematicians to rigorous formal proofs in some (decidable) logic? I agree that such a translation is infeasibly hard, but I think this problem is too vague to say that it is undecidable. I think that if a proof contains enough details, it should be possible to translate it into a formal proof. This is what happens with proof assistants all the time.

I guess this is kind-of answered above. I think the problem is unfeasible hard even for computer/human teams.

You might be interested in this (short) answer on stackexchange which gives examples where category theory has been useful for other fields of mathematics.

I may get to read that eventually. I have some grasp on category theory: my best friend and two other friends did their masters' thesis on it, and two of them are currently finishing their PhDs on it as well. I was never too impressed I am afraid. That being said, with the current immense subdivision of fields of math, is hard to be really impressed by anything in which you are not an expert, so that's not really a meaningful statement. I am not claiming that category theory is worthless, I just think that people are too eager for an all-encompassing theory of things that they will praise anything that sounds like it may be it. I believe such a thing does not exist, and moreover, we are getting far away from it. And I don't think there is a problem with that. Gödel, man. Same thing will likely happen at every level.

And yes, in the end, a general theory is not strictly better, so a more general and a less general theory are incomparable, but I think the more general theory is better in 9 out of 10 aspects.

I probably disagree with you in which constitutes an "aspect".
Logged

#### florrat

• Minion
• Offline
• Posts: 541
• Respect: +746
« Reply #182 on: November 30, 2014, 01:06:30 am »
+3

http://en.wikipedia.org/wiki/Higher-order_logic
But is proof checking undecidable in higher order logic? I tried to google it, but didn't find anything meaningful. The only thing the wikipedia article states about undecidability is about higher order unification, which is not needed to check a fully annotated proof.

My point is precisely that most mathematicians (barring those working in logic) do not. They usually do things like "let f be a function" or "consider the smallest subset such that", and those are second-order logic statements.
First order is extremely weak, you cannot even define the natural numbers or the real numbers with it.
In set theory (in particular first order ZFC) all these statements can be expressed in first order logic. "f is a function from A to B" can be defined as "f is a subset of the cartesian product A * B and for all a in A there is a unique b in B such that the ordered pair (a,b) is in f." All these notions themselves can be also defined until you only have elementhood as primitive notion (and of course the logical notions (connectives and quantifiers)). After this, you can use this to quantify over functions, and similarly for subsets. And (of course) you can define the real numbers and natural numbers in set theory.

I guess this is kind-of answered above. I think the problem is unfeasible hard even for computer/human teams.
Well, if you allow humans, this already happens today. Proofs are provided by a human to a computer program called a proof assistant, which can then fill in the remaining gaps, and produce a formal proof. This is called interactive theorem proving, and I'm currently doing a PhD related to this :-) It currently is much more work to write down a proof which will be accepted by the proof assistant than it is to write a proof on paper (hopefully this will change in the future).
However, many impressive results have already been formally proved this way. Perhaps most notably the Kepler conjecture, which asks what is the densest way to place spheres in space. This problem has been open for almost 400 years, until Thomas Hales claimed he found a proof in 1998. However, this proof was so complicated (and involved a lot of calculations performed by a computer) that it could not be verified by other mathematicians. Since then Hales has worked on a formalization in a proof assistant, which he completed this summer.

These proof assistants can output a formal proof. Usually those logical systems are more complicated than just first (or higher) order logic (allowing things like definitions or inductively defined structures), but it is definitely a logical system you can write down in a couple of pages, and which has decidable proof checking.

I just think that people are too eager for an all-encompassing theory of things that they will praise anything that sounds like it may be it. I believe such a thing does not exist, and moreover, we are getting far away from it. And I don't think there is a problem with that. Gödel, man. Same thing will likely happen at every level.
Yeah, people tend to advocate too much for they like or belief in, including mathematical foundations. I also don't think there is a unique "best" foundation.
Logged

#### qmech

• Torturer
• Offline
• Posts: 1915
• Works with high probability
• Respect: +2288
« Reply #183 on: November 30, 2014, 05:04:28 am »
+3

Well, if you allow humans, this already happens today. Proofs are provided by a human to a (computer program called a) proof assistant, which can then fill in the remaining gaps, and produce a formal proof. This is called a PhD student.

is how I expected this to go.

Logged

#### blueblimp

• Margrave
• Offline
• Posts: 2681
• Respect: +1456
« Reply #184 on: November 30, 2014, 10:11:47 am »
0

However, many impressive results have already been formally proved this way. Perhaps most notably the Kepler conjecture, which asks what is the densest way to place spheres in space. This problem has been open for almost 400 years, until Thomas Hales claimed he found a proof in 1998. However, this proof was so complicated (and involved a lot of calculations performed by a computer) that it could not be verified by other mathematicians. Since then Hales has worked on a formalization in a proof assistant, which he completed this summer.
Cool. I knew of formal proof methods being applied to the Four Colour Theorem, which states that any planar graph may have its faces coloured with four colors such that no two adjacent faces have the same colour. That is a similar situation in that the theorem was reduced to a bunch of computational case checking.

Here's a crazy idea I had related to proof assistants. There are many online programming contests, such as Topcoder, where you're asked to write program solving some algorithmic problem. An analogous competition wouldn't be feasible for math proofs, because the solutions require human judging, which would be impractical at that scale. An automated proof checker could fix that problem by allowing automated checking of the proofs, at the cost of requiring competitors to write formal proofs.

My question is whether there's a formal proof system that would be appropriate for that application. The main requirement would be that formalizing the proof, once you're familiar with the proof system, needs to be significantly easier than thinking of the informal proof in the first place. For example, ideally an hour or so would be enough for a skilled competitor to solve and formalize a problem of difficulty comparable to an easy Putnam problem. Is there any system capable of that today?
Logged

#### florrat

• Minion
• Offline
• Posts: 541
• Respect: +746
« Reply #185 on: November 30, 2014, 05:41:20 pm »
+1

Yes, the Four Colour Theorem is also an impressive result that has been formally proven in a proof assistant.

I'm afraid that currently, you'll have no chance to give a proof in a proof assistant in similar time to giving it on paper. The problem is just that you have to give much more detail in the proof assistant. You can call some automated procedures for some basic steps, but it doesn't come near the steps mathematicians leave out in written proofs. To give you a rough idea about which level of detail is required, see for example this proof that the square root of 2 is not rational.

Still, it would be a pretty cool idea. It would be already feasible to do now, but currently you'll be mostly checking how well someone can formalize proofs in a proof assistant, rather than how well someone can come up with the proofs in the first place.
Logged

#### Trogdor the Burninator

• Bishop
• Offline
• Posts: 112
• Respect: +37
« Reply #186 on: November 30, 2014, 08:50:47 pm »
+1

How did the constipated mathematician solve his problem?
He worked it out with a pencil...

Logged

#### AndrewisFTTW

• Saboteur
• Offline
• Posts: 1110
• Respect: +1060
« Reply #187 on: December 01, 2014, 02:39:26 pm »
+2

How did the constipated mathematician solve his problem?
He worked it out with a pencil...

Where's the "unsubscribe" button?
Logged
Wins: M39, M41, M48, M96, M97
Losses: M40, M43, M45, BM17 (?), RMM13, RMM17, RMM20, NM7, ZM18
MVPs: M97
Mod/Co-Mod: M46, M49, M52, NM10

#### Trogdor the Burninator

• Bishop
• Offline
• Posts: 112
• Respect: +37
« Reply #188 on: December 03, 2014, 11:39:35 am »
+1

How did the constipated mathematician solve his problem?
He worked it out with a pencil...

Where's the "unsubscribe" button?

Mwa ha ha! Trogdor strikes again!!
Logged

#### sudgy

• Cartographer
• Online
• Posts: 3120
• It's pronounced "SOO-jee"
• Respect: +2285
« Reply #189 on: December 03, 2014, 05:12:33 pm »
0

I always feel amazing when I figure out some new (for me) math thing on my own...  I just realized that the derivative of the volume of a sphere is the surface area of the sphere...  I have no idea of the implications, but it's still really cool.
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

#### liopoil

• Margrave
• Offline
• Posts: 2551
• Respect: +2437
« Reply #190 on: December 03, 2014, 05:17:49 pm »
0

I always feel amazing when I figure out some new (for me) math thing on my own...  I just realized that the derivative of the volume of a sphere is the surface area of the sphere...  I have no idea of the implications, but it's still really cool.
That's true?

Let's see.... 4/3 pi r^3.... 4 pi r^2.

Is 4 pi r^2 the surface area of a sphere? I honestly don't know. If so, that is pretty cool.

Now that I think about it, the same is true for a circle; the derivative of pi r^2 is 2 pi r.

Is it true for an n-sphere? I don't know why you would ever take the derivative of a volume anyway though.
Logged

#### WalrusMcFishSr

• Minion
• Offline
• Posts: 642
• An enormous walrus the size of Antarctica
• Respect: +1779
« Reply #191 on: December 03, 2014, 05:19:55 pm »
+6

Yep...it makes perfect sense if you think about "growing" a sphere by stacking lots of thin shell "surface areas" on each other.
Logged
My Dominion videos: http://www.youtube.com/user/WalrusMcFishSr   <---Bet you can't click on that!

#### Kirian

• Offline
• Posts: 6799
• An Unbalanced Equation
• Respect: +8736
« Reply #192 on: December 03, 2014, 05:25:14 pm »
+4

I always feel amazing when I figure out some new (for me) math thing on my own...  I just realized that the derivative of the volume of a sphere is the surface area of the sphere...  I have no idea of the implications, but it's still really cool.
That's true?

Let's see.... 4/3 pi r^3.... 4 pi r^2.

Is 4 pi r^2 the surface area of a sphere? I honestly don't know. If so, that is pretty cool.

Now that I think about it, the same is true for a circle; the derivative of pi r^2 is 2 pi r.

Is it true for an n-sphere? I don't know why you would ever take the derivative of a volume anyway though.

The volume of an n-sphere is the integral from 0 to r of the surface area (concentric spherical shells).

So the answers are yes, and, you wouldn't, but you'd integrate the surface area.
Logged
Kirian's Law of f.DS jokes:  Any sufficiently unexplained joke is indistinguishable from serious conversation.

#### Kirian

• Offline
• Posts: 6799
• An Unbalanced Equation
• Respect: +8736
« Reply #193 on: December 03, 2014, 05:25:50 pm »
0

And, ninja'd.
Logged
Kirian's Law of f.DS jokes:  Any sufficiently unexplained joke is indistinguishable from serious conversation.

#### soulnet

• Mountebank
• Offline
• Posts: 2142
• Respect: +1733
« Reply #194 on: December 03, 2014, 06:33:04 pm »
0

But is proof checking undecidable in higher order logic? I tried to google it, but didn't find anything meaningful. The only thing the wikipedia article states about undecidability is about higher order unification, which is not needed to check a fully annotated proof.
I guess I always thought unification < proof checking because, you know, who fully annotates proofs? I guess fully annotated proof checking is always computable in a "reasonable" proof system, because that is a pretty good definition for the intuitive idea of a "reasonable" proof system.

In set theory (in particular first order ZFC) all these statements can be expressed in first order logic. "f is a function from A to B" can be defined as "f is a subset of the cartesian product A * B and for all a in A there is a unique b in B such that the ordered pair (a,b) is in f." All these notions themselves can be also defined until you only have elementhood as primitive notion (and of course the logical notions (connectives and quantifiers)). After this, you can use this to quantify over functions, and similarly for subsets. And (of course) you can define the real numbers and natural numbers in set theory.
Maybe we have different ideas of what a "definition" entails. For me, if your definition accept non-standard models (i.e., models other than isomorphisms of the idea you have in your head), then, it is not a good definition. And I think any first order theory that includes the natural numbers always accepts non-standard models (and similarly for the reals).

These proof assistants can output a formal proof. Usually those logical systems are more complicated than just first (or higher) order logic (allowing things like definitions or inductively defined structures), but it is definitely a logical system you can write down in a couple of pages, and which has decidable proof checking.

I did not know it was a common practice to "re-prove" things with proof assistants. I knew about the four color theorem case and I have heard recently of the Kepler conjecture in the "news", but not that it was widely done. I am still willing to bet it is only a negligible percentage of the theorems done (and with good reason).

I also don't think there is a unique "best" foundation.

Logged

#### qmech

• Torturer
• Offline
• Posts: 1915
• Works with high probability
• Respect: +2288
« Reply #195 on: December 04, 2014, 04:06:58 am »
0

Maybe we have different ideas of what a "definition" entails. For me, if your definition accept non-standard models (i.e., models other than isomorphisms of the idea you have in your head), then, it is not a good definition. And I think any first order theory that includes the natural numbers always accepts non-standard models (and similarly for the reals).

Yes, that's Löwenheim–Skolem.  And I'm not sure how disturbing I find it.  At least everything you can prove about the natural numbers is true there.

I always feel amazing when I figure out some new (for me) math thing on my own...  I just realized that the derivative of the volume of a sphere is the surface area of the sphere...  I have no idea of the implications, but it's still really cool.

This hints at why the similarity of the notation ∂A for the boundary of a set A to a derivative is not entirely coincidental.
Logged

#### heron

• Jester
• Offline
• Posts: 970
• Respect: +1089
« Reply #196 on: January 02, 2015, 08:28:27 pm »
0

Here's a classic problem:

What is the least prime factor of 63^128 + 1?

Edit: Um, made an error here. More difficult version found a few posts below.

« Last Edit: January 02, 2015, 09:57:03 pm by heron »
Logged
PPR is for wimps.

#### silverspawn

• Cartographer
• Offline
• Posts: 3784
• ♦ Twilight ♦
• Respect: +1648
« Reply #197 on: January 02, 2015, 09:14:43 pm »
+1

Here's a classic problem:

What is the least prime factor of 63^128 + 1?

Moat?
Logged

#### liopoil

• Margrave
• Offline
• Posts: 2551
• Respect: +2437
« Reply #198 on: January 02, 2015, 09:26:09 pm »
+3

Here's a classic problem:

What is the least prime factor of 63^128 + 1?
Does this work?

63 = 7*3^2, so 63^128 + 1 = 7^128*3^256 + 1

The last digits of powers of 3 are 3, 9, 7, 1, repeat. 256 is divisible by 4 so the power of 3 term ends in 1.

The last digits of powers of 7 end in 7, 9, 3, 1, repeat. 128 is divisible by 4 so the power of 7 term ends in 1. Their product must also end in 1 then. Add one and the expression ends in 2. Therefore the number is divisible by 2, which is the smallest prime that there is. So the answer is 2.
Logged

#### heron

• Jester
• Offline
• Posts: 970
• Respect: +1089
« Reply #199 on: January 02, 2015, 09:56:31 pm »
0

Oh whoops, made an error with the problem. Um, we'll call that easy mode. But yea, liopoil has it right.
Okay, hard mode:

What is the least prime factor of 252^128 + 1?
Logged
PPR is for wimps.

#### liopoil

• Margrave
• Offline
• Posts: 2551
• Respect: +2437
« Reply #200 on: January 02, 2015, 10:30:31 pm »
0

Oh whoops, made an error with the problem. Um, we'll call that easy mode. But yea, liopoil has it right.
Okay, hard mode:

What is the least prime factor of 252^128 + 1?
So, uhh, the last digit is 7... and so the least prime factor is at the lowest 11...

252 is 10 mod 11. 10^128 + 1 is 127 0s with 1s at either end, so odd number of digits and the 1s are both in 'odd' digits, so the expression is not divisible by 11.

252 is 5 mod 13. Cycle of powers of 5 mod 13 is 5, 12, 8, 1, repeat. 128 is divisible by 4, so the expression is 2 mod 13, not divisible by 13.

252 is 12 mod 17... and I'm starting to get the feeling I need a better approach to solve this.
Logged

#### heron

• Jester
• Offline
• Posts: 970
• Respect: +1089
« Reply #201 on: January 02, 2015, 10:58:12 pm »
0

Oh whoops, made an error with the problem. Um, we'll call that easy mode. But yea, liopoil has it right.
Okay, hard mode:

What is the least prime factor of 252^128 + 1?
So, uhh, the last digit is 7... and so the least prime factor is at the lowest 11...

252 is 10 mod 11. 10^128 + 1 is 127 0s with 1s at either end, so odd number of digits and the 1s are both in 'odd' digits, so the expression is not divisible by 11.

252 is 5 mod 13. Cycle of powers of 5 mod 13 is 5, 12, 8, 1, repeat. 128 is divisible by 4, so the expression is 2 mod 13, not divisible by 13.

252 is 12 mod 17... and I'm starting to get the feeling I need a better approach to solve this.

Yea, I wanted to make the answer big enough that you wouldn't want to just check all of the primes in order, but small enough that you can check that the number is actually prime pretty quickly.
Logged
PPR is for wimps.

#### liopoil

• Margrave
• Offline
• Posts: 2551
• Respect: +2437
« Reply #202 on: January 02, 2015, 11:49:42 pm »
+1

Call the value of the expression x and its least prime factor n. x is 0 mod n, so 252^128 is n - 1 mod n. Assume n < 128. Since n is prime I think (not sure) that means those cycles must have a length which is a factor of n - 1. Then (252 mod n)^ (128 mod n - 1) is n - 1 mod n. This rules out 17. Plugging in 19 we get 5 squared which is not 18 mod 19. For 23 we get 22 ^ 18, but since 22 is the first term in the cycle and 18 isn't anywhere near a factor of 22 we see it doesn't work without computation. 29 yields 20 ^ 16. Yikes. 31 yields 4 ^ 4 = 256, which is congruent to 10 (mod 31) which is not 30. Okay back to thinking more generally...

Okay maybe n > 128. I think all my statements are still true, just less useful.  I don't know what I'm doing, and am increasingly feeling like I'm entirely on the wrong track. I don't know anything about these cycles!
Logged

#### heron

• Jester
• Offline
• Posts: 970
• Respect: +1089
« Reply #203 on: January 02, 2015, 11:58:04 pm »
0

You are more on the right track than you think.

Some things you might want to consider/hints:

I'll call the least prime factor p.
Yes, 252^128 = -1 (mod p). And yes, 252^n is periodic modulo p, where the period is a factor of p-1. Make sure you know why it is a factor of p-1.
In other words, p-1 is a multiple of the period. Now, if only you knew what the period was...
Logged
PPR is for wimps.

#### GeoLib

• Jester
• Offline
• Posts: 965
• Respect: +1254
« Reply #204 on: January 03, 2015, 01:47:53 am »
+3

Here's a classic problem:

What is the least prime factor of 63^128 + 1?
Does this work?

63 = 7*3^2, so 63^128 + 1 = 7^128*3^256 + 1

The last digits of powers of 3 are 3, 9, 7, 1, repeat. 256 is divisible by 4 so the power of 3 term ends in 1.

The last digits of powers of 7 end in 7, 9, 3, 1, repeat. 128 is divisible by 4 so the power of 7 term ends in 1. Their product must also end in 1 then. Add one and the expression ends in 2. Therefore the number is divisible by 2, which is the smallest prime that there is. So the answer is 2.

So for the easy version, Can't we just say 3^256*7^128 is odd, so add one and it must be even, so 2?
Logged
—Count Grishnakh

#### Titandrake

• Torturer
• Offline
• Posts: 1920
• Respect: +1897
« Reply #205 on: January 03, 2015, 03:35:19 am »
+1

Ooh, I do so love a number theory puzzle. I think it's the correct answer but there are gaps in my proof that I'm working on fixing.

We want the smallest prime p such that 252^128 = -1 mod p.

Since we're always going to work mod some prime p, by Fermat's Little Theorem a^{p-1} = 1 mod p. In particular, this gives that for any k such that a^k = 1 mod p, k must be a factor of p-1. I'm sure there's a way to prove this without too much machinery, but I'll just cite Lagrange's Theorem and move on.

We know a^n is periodic in mod p. First, we need to show a^n = -1 for some n mod p.  Here's the hole: not sure how you do this.

Let k be the period, meaning the smallest positive exponent where a^k = 1. Let k' be the power such that a^k' = -1, where k' < k. Then since a^{2k'} = (-1)^2 = 1, we must have k' = k / 2. Quick proof: if k' < k/2, then 2k' < k and k cannot be the period since a^{2k'} = a^0 = 1, a contradiction. If k' > k/2, then a^{2k' - k} = 1 as well, and 2k' - k < k, also a contradiction. Therefore, we must have k' = k / 2.

So, in particular, this gives that the powers such that a^n = -1 mod p are k/2, 3k/2, 5k/2, 7k/2, ... or equivalently some odd multiple of k'. But 128 is a power of 2. Therefore, we must have k' = 128 => k = 256. So, 256 is a factor of p-1. Luckily, it turns out 257 is prime, so the answer is 257.

Edit: Have verified with computer my answer is correct. Working on the hole-filling now.

Edit 2: Some general cleaning up.
« Last Edit: January 03, 2015, 05:36:13 am by Titandrake »
Logged
I have a blog! It's called Sorta Insightful. Check it out?

#### heron

• Jester
• Offline
• Posts: 970
• Respect: +1089
« Reply #206 on: January 03, 2015, 11:08:06 am »
0

You have the correct answer there, here is a comment and a method to prove that your answer is indeed a factor:

Yea, it is much more annoying to work with -1 mod p than with 1 mod p. It gets a lot less messy if you multiply by 252^128-1 to get 252^256 - 1. Then you know a^n = 1 mod p where n is a factor of 256, and you can quickly ascertain that n is not a factor of 128, because then p|252^128 - 1.
So 256|p-1, and as you noted, 257 is prime.

Probably the fastest way to check that 257|252^128 + 1 is via Euler's criterion for quadratic residues and quadratic reciprocity. Euler's criterion tells us that a^((p-1)/2) = 1 (mod p) if a is a quadratic residue mod p and -1 if it is a nonresidue. 252 = 7*6^2, and so (6^((257-1)/2))^2 = 1 (mod 257). So we want that 7^128 = -1 (mod 257). From the quadratic reciprocity law, 7^128 (mod 257) and 257^3 (mod 7) are either both +1 or both -1, since 7 and 257 are not both 3 (mod 4). So, 257^3 = 5^3 = -1 (mod 7), so 7^128 = -1 (mod 257). So that's it, 252^128 + 1 = 0 (mod 257).
Logged
PPR is for wimps.

#### liopoil

• Margrave
• Offline
• Posts: 2551
• Respect: +2437
« Reply #207 on: January 03, 2015, 11:39:23 am »
0

Here's a classic problem:

What is the least prime factor of 63^128 + 1?
Does this work?

63 = 7*3^2, so 63^128 + 1 = 7^128*3^256 + 1

The last digits of powers of 3 are 3, 9, 7, 1, repeat. 256 is divisible by 4 so the power of 3 term ends in 1.

The last digits of powers of 7 end in 7, 9, 3, 1, repeat. 128 is divisible by 4 so the power of 7 term ends in 1. Their product must also end in 1 then. Add one and the expression ends in 2. Therefore the number is divisible by 2, which is the smallest prime that there is. So the answer is 2.

So for the easy version, Can't we just say 3^256*7^128 is odd, so add one and it must be even, so 2?
Or just Odd number to natural power is odd, so add one and it must be even, so 2. I didn't expect it to be so easy, so I wrote more.

Still working on the real problem, haven't read Titandrake's solution or heron's comment on it.
Logged

#### Kirian

• Offline
• Posts: 6799
• An Unbalanced Equation
• Respect: +8736
« Reply #208 on: January 04, 2015, 09:33:31 am »
+2

Here's a classic problem:

What is the least prime factor of 63^128 + 1?

Moat?

For some reason, this joke never gets old.
Logged
Kirian's Law of f.DS jokes:  Any sufficiently unexplained joke is indistinguishable from serious conversation.

#### Awaclus

• Offline
• Posts: 9098
• (´｡• ω •｡)
• Respect: +8883
« Reply #209 on: January 04, 2015, 09:47:31 am »
+4

#### liopoil

• Margrave
• Offline
• Posts: 2551
• Respect: +2437
« Reply #210 on: January 04, 2015, 10:38:39 am »
0

I think we need to get more creative. Whenever I see ~5 characters of spoiler-ed text I immediately know what it says. Add some spaces at one end or something! That would make it funnier.
Logged

#### SwitchedFromStarcraft

• Saboteur
• Offline
• Posts: 1088
• Respect: +840
« Reply #211 on: January 04, 2015, 10:53:34 am »
0

I think we need to get more creative. Whenever I see ~5 characters of spoiler-ed text I immediately know what it says. Add some spaces at one end or something! That would make it funnier.

Like I did in the first spoiler here:

Logged
Quote from: Donald X.
Posting begets posting.

Quote from: Asper
Donald X made me a design snob.

There is a sucker born every minute.

#### Awaclus

• Offline
• Posts: 9098
• (´｡• ω •｡)
• Respect: +8883
« Reply #212 on: January 04, 2015, 11:14:21 am »
+2

I think we need to get more creative. Whenever I see ~5 characters of spoiler-ed text I immediately know what it says. Add some spaces at one end or something! That would make it funnier.

But you still have to check every time.

#### sudgy

• Cartographer
• Online
• Posts: 3120
• It's pronounced "SOO-jee"
• Respect: +2285
« Reply #213 on: January 04, 2015, 11:44:14 am »
+3

I think we need to get more creative. Whenever I see ~5 characters of spoiler-ed text I immediately know what it says. Add some spaces at one end or something! That would make it funnier.

But you still have to check every time.

You see the spoiler, and the first thing you think when you see it, is "Is it Haha!"
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

#### SwitchedFromStarcraft

• Saboteur
• Offline
• Posts: 1088
• Respect: +840
« Reply #214 on: January 04, 2015, 11:47:36 am »
+5

I always check, on the theory that one day it will read "Is it Ozle?"
Logged
Quote from: Donald X.
Posting begets posting.

Quote from: Asper
Donald X made me a design snob.

There is a sucker born every minute.

#### sudgy

• Cartographer
• Online
• Posts: 3120
• It's pronounced "SOO-jee"
• Respect: +2285
« Reply #215 on: January 15, 2015, 03:28:02 pm »
0

So, there's something I've been wondering.  As far as I understand, here's how you solve the differential equation y' = y:

y' = y
dy/dx = y
dy/y = dx
∫dy/y = ∫dx
ln |y| = x + C
|y| = e^(x + C)
|y| = (e^x)*(e^C)
Since e^C is any positive number:
|y| = Ce^x (C > 0)
Getting rid of the absolute value allows the right side to be negative:
y = Ce^x (C ≠ 0)

The problem is, C = 0 is a solution, but I don't see how to make it a part of the process of getting the solution.
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

• Offline
• Posts: 6214
• Respect: +7412
« Reply #216 on: January 15, 2015, 03:32:57 pm »
+1

Logged

#### heron

• Jester
• Offline
• Posts: 970
• Respect: +1089
« Reply #217 on: January 15, 2015, 03:33:44 pm »
+4

I think the problem is that when you go from dy/dx = y to dy/y = dx, you assume that y ≠ 0.
Logged
PPR is for wimps.

#### Witherweaver

• Offline
• Posts: 6214
• Respect: +7412
« Reply #218 on: January 15, 2015, 03:34:39 pm »
0

So, there's something I've been wondering.  As far as I understand, here's how you solve the differential equation y' = y:

y' = y
dy/dx = y
dy/y = dx
∫dy/y = ∫dx
ln |y| = x + C
|y| = e^(x + C)
|y| = (e^x)*(e^C)
Since e^C is any positive number:
|y| = Ce^x (C > 0)
Getting rid of the absolute value allows the right side to be negative:
y = Ce^x (C ≠ 0)

The problem is, C = 0 is a solution, but I don't see how to make it a part of the process of getting the solution.

C=0 => y=0 => y'/y does not make many senses.

Edit: Ninja'd
Logged

#### sudgy

• Cartographer
• Online
• Posts: 3120
• It's pronounced "SOO-jee"
• Respect: +2285
« Reply #219 on: January 15, 2015, 03:37:50 pm »
0

So, even though d/dx 0 = 0 it doesn't satisfy the equation y' = y?
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

• Offline
• Posts: 6214
• Respect: +7412
« Reply #220 on: January 15, 2015, 03:42:26 pm »
0

So, even though d/dx 0 = 0 it doesn't satisfy the equation y' = y?

It satisfies the equation, but if you're going to tell me that 1 = kx (for some finite real k) and therefore 1/x = k, you're also implicitly telling me that x is not zero.
Logged

#### scott_pilgrim

• Jester
• Offline
• Posts: 958
• Respect: +1857
« Reply #221 on: January 15, 2015, 03:43:34 pm »
0

So, even though d/dx 0 = 0 it doesn't satisfy the equation y' = y?

Yes it does, it's an alternate solution.  Whenever you divide by a variable (this applies to basic algebra as well), you have to check whether that variable could be 0; in this case, it can.  For example, 0 is a solution of x=x^3, even though you only get 1 or -1 when you divide both sides by x.
Logged

#### Polk5440

• Torturer
• Offline
• Posts: 1590
• Respect: +1534
« Reply #222 on: January 15, 2015, 03:43:55 pm »
0

So, there's something I've been wondering.  As far as I understand, here's how you solve the differential equation y' = y:

y' = y
dy/dx = y
dy/y = dx

You rule out y = 0 as a solution here because you divide by y and then integrate. You can't do this if y is identically equal to zero. So the solution method misses the trivial solution (y = 0 implies y' = 0 so that works as a solution). But normally people don't care about the trivial solutions, so it's not a big deal in this case.

[analytic details about integration go here]

Ninja'd...

Edit: scott says it better...
Logged

#### Witherweaver

• Offline
• Posts: 6214
• Respect: +7412
« Reply #223 on: January 15, 2015, 03:45:06 pm »
0

In other words, your solution technique only finds nonzero y that solves y' = y.

Then you can simply observe that y=0 solves the equation as well, so that

y(x) = Ce^x

describes a family of solutions for all real C.
Logged

#### sudgy

• Cartographer
• Online
• Posts: 3120
• It's pronounced "SOO-jee"
• Respect: +2285
« Reply #224 on: January 15, 2015, 03:45:53 pm »
0

Ah, I get it now.  Thanks!
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

#### pacovf

• Margrave
• Offline
• Posts: 2949
• Multiediting poster
• Respect: +3243
« Reply #225 on: January 15, 2015, 03:46:40 pm »
0

You could also prove that all the solutions to y' = y are proportional to each other, and then prove that exp is a solution. Then you find that 0 is also a solution. You don't even need to define ln to prove this.

PPE ~317: geez people you're like a pack of hungry wolves.
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
• Online
• Posts: 3120
• It's pronounced "SOO-jee"
• Respect: +2285
« Reply #226 on: January 15, 2015, 03:56:19 pm »
0

You could also prove that all the solutions to y' = y are proportional to each other, and then prove that exp is a solution. Then you find that 0 is also a solution. You don't even need to define ln to prove this.

PPE ~317: geez people you're like a pack of hungry wolves.

Well, there are like 317 different ways to solve differential equations...
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
• Online
• Posts: 3120
• It's pronounced "SOO-jee"
• Respect: +2285
« Reply #227 on: February 11, 2015, 03:36:21 pm »
0

Is there any website like wolframalpha that will give me a step-by-step solution to whatever I put in without making me pay money?
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

#### scott_pilgrim

• Jester
• Offline
• Posts: 958
• Respect: +1857
« Reply #228 on: February 11, 2015, 03:40:37 pm »
+3

But wolfram has the best step-by-step solutions!

Logged

#### Ozle

• Cartographer
• Offline
• Posts: 3625
• Sorry, this text is personal.
• Respect: +3329
« Reply #229 on: February 11, 2015, 03:48:33 pm »
+3

Post it here, i'll do it for you!
Logged
Try the Ozle Google Map Challenge!
http://forum.dominionstrategy.com/index.php?topic=7466.0

Sullying players Enjoyment of Innovation since 2013 Apparently!

#### sudgy

• Cartographer
• Online
• Posts: 3120
• It's pronounced "SOO-jee"
• Respect: +2285
« Reply #230 on: February 11, 2015, 03:53:26 pm »
0

But wolfram has the best step-by-step solutions!

But you have to pay money...
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

#### pacovf

• Margrave
• Offline
• Posts: 2949
• Multiediting poster
• Respect: +3243
« Reply #231 on: February 11, 2015, 03:59:03 pm »
+1

Pretty sure scotty was being sarcastic there, or at the very least facetious.
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

• Offline
• Posts: 6214
• Respect: +7412
« Reply #232 on: February 11, 2015, 04:00:16 pm »
0

Pretty sure scotty was being sarcastic there, or at the very least facetious.

Maybe even sarcetious.  Or facastic.
Logged

#### sudgy

• Cartographer
• Online
• Posts: 3120
• It's pronounced "SOO-jee"
• Respect: +2285
« Reply #233 on: February 11, 2015, 04:13:20 pm »
0

Also, that example is really easy...
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

• Offline
• Posts: 6214
• Respect: +7412
« Reply #234 on: February 11, 2015, 04:25:35 pm »
+1

Is there any website like wolframalpha that will give me a step-by-step solution to whatever I put in without making me pay money?

Step 1: Integrate by parts
Step 2: Profit
Logged

#### pacovf

• Margrave
• Offline
• Posts: 2949
• Multiediting poster
• Respect: +3243
« Reply #235 on: February 11, 2015, 04:29:36 pm »
+2

Personally, I prefer the Feynman method:

1. You write down the problem.
2. You think very hard.
3. You write down the answer.
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
• Online
• Posts: 3120
• It's pronounced "SOO-jee"
• Respect: +2285
« Reply #236 on: February 11, 2015, 04:33:38 pm »
0

Is there any website like wolframalpha that will give me a step-by-step solution to whatever I put in without making me pay money?

Step 1: Integrate by parts
Step 2: Profit

Personally, I prefer the Feynman method:

1. You write down the problem.
2. You think very hard.
3. You write down the answer.

Already tried both of these for the past hour or two.
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

#### pacovf

• Margrave
• Offline
• Posts: 2949
• Multiediting poster
• Respect: +3243
« Reply #237 on: February 11, 2015, 04:40:11 pm »
0

I don't know of any free automatic solver, sorry...

In the meantime, you could try posting the problem that is bothering you. Ozle has already offered to write the proof down!
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
• Online
• Posts: 3120
• It's pronounced "SOO-jee"
• Respect: +2285
« Reply #238 on: February 11, 2015, 06:38:06 pm »
0

∫sqrt(1-x2) dx

I've tried a bajillion methods.  I know the answer from wolframalpha, but still can't figure it out.
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

• Offline
• Posts: 6214
• Respect: +7412
« Reply #239 on: February 11, 2015, 06:45:01 pm »
+2

∫sqrt(1-x2) dx

I've tried a bajillion methods.  I know the answer from wolframalpha, but still can't figure it out.

Well, sqrt{1-x^2} is naturally the length of a leg of a right triangle if the other leg is x and the hypotenuse is 1.  So draw that triangle.  Call one of the angles theta.  Make a natural substitution (i.e., x = trigfunction(theta)).  Take differentials and plug it into the integral.  Then you have an integral of trig functions, and you can do that.

Edit: The integrand itself, \sqrt{1-x^2}, is also a convenient trig function of theta.  (Also, fixed a typo above.)
« Last Edit: February 11, 2015, 06:46:13 pm by Witherweaver »
Logged

#### liopoil

• Margrave
• Offline
• Posts: 2551
• Respect: +2437
« Reply #240 on: February 11, 2015, 06:50:14 pm »
0

Disclaimer: I am currently taking Calc. A, so fair chance I have no clue what I'm talking about

-1/3x(1 - x2)3/2 + c

Thinking about what gives sqrt(1 - x2) when you take it's derivative... this is what I get. First I increased the exponent on the outside by one, then multiplied by the reciprocal of the inside function (1 - x2). Then I multiplied by the reciprocal of the new outer exponent, and added the constant of integration.

PPE: It seems witherweaver knows what he's talking about and I don't. That is an integral sign, right? Mind explaining where I err? Something tells me it shouldn't be this simple.
« Last Edit: February 11, 2015, 06:51:51 pm by liopoil »
Logged

#### sudgy

• Cartographer
• Online
• Posts: 3120
• It's pronounced "SOO-jee"
• Respect: +2285
« Reply #241 on: February 11, 2015, 06:56:45 pm »
0

-1/3x(1 - x2)3/2 + c

Differentiating this involves a product rule, making its derivative 1/3 sqrt(1-x2) (4 x2-1), not sqrt(1-x2)
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

#### liopoil

• Margrave
• Offline
• Posts: 2551
• Respect: +2437
« Reply #242 on: February 11, 2015, 06:58:39 pm »
0

-1/3x(1 - x2)3/2 + c

Differentiating this involves a product rule, making its derivative 1/3 sqrt(1-x2) (4 x2-1), not sqrt(1-x2)
ah yes, thank you... not so simple when the power on the inside is greater than 1. And wolfram disagrees with me too, so looks like I have no clue.
Logged

#### heron

• Jester
• Offline
• Posts: 970
• Respect: +1089
« Reply #243 on: February 11, 2015, 07:01:52 pm »
+1

Okay hint: sqrt(1 - x^2) is hard to integrate, darn. Good thing we have techniques for getting around that, namely substitution. What sort of substitution could you make so that sqrt(1 - x^2) turns into something nicer?

Alternative strategy: Apply geometry.
Logged
PPR is for wimps.

#### sudgy

• Cartographer
• Online
• Posts: 3120
• It's pronounced "SOO-jee"
• Respect: +2285
« Reply #244 on: February 11, 2015, 07:10:48 pm »
0

Okay hint: sqrt(1 - x^2) is hard to integrate, darn. Good thing we have techniques for getting around that, namely substitution. What sort of substitution could you make so that sqrt(1 - x^2) turns into something nicer?

I tried all sorts of things like this, to no avail.  I tried u = 1 - x2, but that makes du = -2x dx, making it even more confusing.  I tried crazy forms of integration by parts but that didn't work either.

Quote
Alternative strategy: Apply geometry.

I just did what Witherweaver said and it worked.  Yay!
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

• Offline
• Posts: 6214
• Respect: +7412
« Reply #245 on: February 11, 2015, 07:48:40 pm »
0

"Geometry" mean "trigonometry" here
Logged

#### silverspawn

• Cartographer
• Offline
• Posts: 3784
• ♦ Twilight ♦
• Respect: +1648
« Reply #246 on: February 11, 2015, 08:20:54 pm »
0

I actually have a math exam coming up in a few days. So, I'll also try this (without using geometry)

So, there is this formula which I think works

which you have to read from the right side. So you have
$f(x) = \sqrt{1-x^2}$

you define $g(x) = sin(x)$ and

$f(g(x)) * g'(x) = \sqrt{1-sin^2(x)} * cos(x) = \sqrt{cos^2(x))} * cos(x) = cos^2(x)$

which according to my list of common integrals I made to use in the exam is the derivation of

$\frac{x+\frac{sin(2x)}{2}}{2}$

and so

$\int_{b}^{a} \sqrt{1-x^2} = \int_{\arcsin b}^{\arcsin a} \frac{x + \frac{sin(2x)}{2}}{2}$

edit: ehhm that's of course not an integral anymore on the right side

so... is that correct?

« Last Edit: February 11, 2015, 08:28:37 pm by silverspawn »
Logged

#### heron

• Jester
• Offline
• Posts: 970
• Respect: +1089
« Reply #247 on: February 11, 2015, 09:11:39 pm »
+1

Okay hint: sqrt(1 - x^2) is hard to integrate, darn. Good thing we have techniques for getting around that, namely substitution. What sort of substitution could you make so that sqrt(1 - x^2) turns into something nicer?

I tried all sorts of things like this, to no avail.  I tried u = 1 - x2, but that makes du = -2x dx, making it even more confusing.  I tried crazy forms of integration by parts but that didn't work either.

Quote
Alternative strategy: Apply geometry.

I just did what Witherweaver said and it worked.  Yay!

You never tried sinu = x though did you
In calc AB class, the teacher never told us that you could do u-substitutions like that, but when you think about it, it is a natural extension of the technique.

As for geometry, I just meant use the area under a curve definition of the integral. It's not too difficult to find the area of those bits of circle.
Logged
PPR is for wimps.

#### heron

• Jester
• Offline
• Posts: 970
• Respect: +1089
« Reply #248 on: February 11, 2015, 09:18:06 pm »
0

For additional integration practice, here is a problem:

Given two randomly selected points in a unit square, what is the probability that the distance between them is greater than 1/2?
(2015 AMC A, modified)

The original problem specified that the points lie on the perimeter of the square, which makes the problem significantly easier, and allows you to use geometry rather than calculus.

Edit: Also, sqrt(1 - x^2) would be one of the integrals you would need to evaluate in the original problem.
« Last Edit: February 11, 2015, 09:50:38 pm by heron »
Logged
PPR is for wimps.

#### sudgy

• Cartographer
• Online
• Posts: 3120
• It's pronounced "SOO-jee"
• Respect: +2285
« Reply #249 on: February 11, 2015, 10:19:54 pm »
0

As for geometry, I just meant use the area under a curve definition of the integral. It's not too difficult to find the area of those bits of circle.

Well, I knew that, I was trying to find a better reason though.
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