Gauss
analytic geometry
Euler
function
calculus
integration
LaTeX

Hi, I have some difficulty with problem 2.20, 2.21, and 2.30, from the book Introduction to Mechanics by Kleppner and Kolenkow.  I have posted up the two pages of problems of interest, and some of my initial work on them, although I don't think I can handle this by myself.  I need your help on this, especially if you can show me quicker, more straightforward ways to handle this, or if I'm misusing a concept in my solution

Thanks!

Dont post the whole page, just crop the relevant problem and post it. :wink:

Well, my thought is that I might be able to solve more problems from that page, and post it to check that my way of solving it is correct.  If so, I wouldn't need to make new threads, which would take too much space.

I have an approach for 2.20, though I know something is wrong.

[hide]Call the horizonal acceleration of masses $ m_1$ and $ m_2$ with respect to some fixed frame $ a_1$ and $ a_2$ respectively. Let the vertical acceleration of mass $ m_3$ be $ a_3$ (downward direction positive), and let the tension in the rope connecting $ m_2$ and $ m_3$ be $ T$.

By conservation of linear momentum $ m_1v_1 \plus{} m_2v_2 \equal{} 0$, so differentiating with respect to t, $ m_1a_1 \plus{} m_2a_2 \equal{} 0$ and $ m_1a_1 \equal{} \minus{}m_2a_2$.

The acceleration of the mass $ m_2$ with respect to mass $ m_1$ should be equal in magnitude to the downward acceleration of mass $ m_3$ because the length of the string connecting them is fixed. So the net acceleration of mass $ m_2$ in the fixed frame should be $ a_2 \equal{} a_3 \plus{} a_1$.

The forces acting on $ m_3$ yield $ m_3g \minus{} T \equal{} m_3a_3$, and the force acting on $ m_2$ yields $ T \equal{} m_2a_3$ (the acceleration within the moving frame) [note: this is the part that I think is wrong].

All together this yields the following 4 equations with 4 unknown quantities:

1.) $ m_1a_1 \equal{} \minus{}m_2a_2$
2.) $ a_2 \equal{} a_3 \plus{} a_1$
3.) $ m_3g \minus{} T \equal{} m_3a_3$
4.) $ T \equal{} m_2a_3$

Solving by substitution we get $ m_3g \minus{} m_2a_3 \equal{} m_3a_3 \implies a_3 \equal{} \frac{m_3g}{m_2 \plus{} m_3}$ and
$ m_1a_1 \equal{} \minus{}m_2(a_3 \plus{} a_1) \equal{} \minus{}\frac{m_2m_3g}{m_2 \plus{} m_3} \minus{} m_2a_1$

which gives $ a_1(m_1 \plus{} m_2) \equal{} \minus{}\frac{m_2m_3g}{m_2 \plus{} m_3}$
So $ a_1 \equal{} \minus{}\frac{m_2m_3g}{(m_1\plus{}m_2)(m_2 \plus{} m_3)}$[/hide]

If you chose an inertial frame for conservation of momentum, I think you have to account for the fact that m3 itself also has a leftward acceleration component, equal to a1.

Also, I meant problem 2.20 and 2.30 only, were my problems.  I think gauss pretty nailed problem 2.20, so now let's move to 2.30, which gives me headaches  :oops:

Thus m2a2= - (m1+m3)a1

That's true, but it still doesn't lead to the correct answer.

Second correction, in addition to the first one:

When we solved the equations  (3) and (4), we forgot to use non-inertial frames?

[hide="Set up for #2.30"]Since the desired result is $ \ddot{r}_A$ this suggests that you should use Lagrangian mechanics for this problem because the notation is consistent with the notation typically used in Lagrangian mechanics, where $ \ddot{r}_A$ represents the acceleration of the $ r_A$ coordinate.

The Lagrangian for an arbitrary system in generalized coordinates $ q$ and $ \dot{q}$ is given by:

\[ \mathcal{L} = T(\dot{q},q) - V(\dot{q},q)\]

where $ T$ is the total kinetic energy, and $ V$ is the total potential energy. (If you don't like the variable names, don't bust my chops. They're traditional. I didn't pick 'em.)

The first thing you should notice about this problem is that $ V = 0$, there is no potential function. You are told to neglect gravity and there are no springs, no magnetic fields, or other common sources of potential. So then,

\[ \mathcal{L} = T\]

This simplifies things quite a bit.

Since the problem concerns a rotating disc, it is preferable to define $ T$ in polar coordinates:

\[ T =\frac12 m_A\dot{r}_{A}^2 +\frac12 m_Ar_{A}^2\dot{\phi}^2 +\frac12 m_B\dot{r}_{B}^2 +\frac12 m_Br_{B}^2\dot{\phi}^2\]

We also have the auxiliary equations

\begin{eqnarray*} r_A + r_B &=&\ell \\ \dot{\phi} &=&\omega\end{eqnarray*}

The reason I used $ \dot{\phi}$ instead of plugging in $ \omega$ directly is because this way if needs be I could write an equation of motion in the $ \phi$ direction as well as in the $ r_A$ direction.

Since we are only concerned with motion in the $ r_A$ direction I shall make the following substitutions before doing anything else.

\begin{eqnarray*} r_B &=& \ell - r_A \\ \dot{r}_B &=& \dot{\ell} - \dot{r}_A \\ \dot{\phi} &=&\omega\end{eqnarray*}

\[ T =\frac12 m_A\dot{r}_{A}^2 +\frac12 m_Ar_{A}^2\omega^2 +\frac12 m_B(\dot{\ell} -\dot{r}_A)^2 +\frac12 m_B(\ell - r_A)^2\omega^2\]

Now, in general to find the equation of motion in the $ q$ direction one writes the Euler-Lagrange differential equation: $ \frac{d}{d t}\left(\frac{\partial \mathcal{L}}{\partial \dot{q}}\right) -\frac{\partial \mathcal{L}}{\partial q} = 0$.

As applied to this problem this becomes

\[ \frac{d}{d t}\left(\frac{\partial T}{\partial \dot{r}_A}\right) -\frac{\partial T}{\partial r_A} = 0\]

After you write this down, solve it for $ \ddot{r}_A$, and you're done.

** [b]Caveat:[/b] If the string is inextensible (it doesn't stretch) then $ \dot{\ell} = 0$. It seems as though this might be the case since $ \dot{\ell}$ is not one of the variables that your final answer is supposed to include.[/hide]

That Lagrange Euler equation seems really useful.  So basically, you are just defining the behavior system using its lagrangian, the difference between kinetic and potential energies...  That's pretty damn vicious.

About the string.  If the string was extensible, wouldn't that add a potential energy function though? This is purely hypothetical... (suppose the string stiffness was k?)

[quote="integration"]That Lagrange Euler equation seems really useful.  So basically, you are just defining the behavior system using its lagrangian, the difference between kinetic and potential energies...  That's pretty - vicious.[/quote]

Yes, you got it.  :) The Euler-Lagrange differential equation is quite useful, yes. It comes from the calculus of variations, and in this context incorporates all of Newton's laws in a single equation.

[quote="integration"]About the string.  If the string was extensible, wouldn't that add a potential energy function though? This is purely hypothetical... (suppose the string stiffness was k?)[/quote]

Yes, it would, which is another reason to think that the authors intended that the string be inextensible. Else one would incorporate the potential of the string into the Lagrangian, which implies an equation of motion in $ \ell$ that is coupled with the equation of motion in $ r_A$, in short, an unholy mess!

Oh, and another clarification...

For now, I pretty much accept without question that choose L=T-V, allows the principle of least action to be applied to classical mechanics (correct me if I'm wrong).  So basically, when solving mechanics problems (motion of particles), you are finding the path were the line integral of L dt is minimized.

But I feel more queasy about the liberal use of coordinates.  You see, with Newton Mechanics, motion into 3 dimensions, and treating each cartesian dimension separately is OK, for me.

1. So basically, Dr. No, if we were to use Euler Lagrange to solve motion in 3-D over time, we would have 1 euler lagrange equation for each coordinate?
Can we treat each equation separately, thus finding x(t)=?, y(t)=?, z(t)=?, and making a combo of them to find v(t), a(t)?

2. This is the part that makes me troubled.  How can that Euler Lagrange equation work separately for [i]polar[/i] coordinates, which seems what you have done, since you basically ignored motion in the tangential direction, and set up motion in the radial direction for your equation?

3.  And if Euler-lagrange is as powerful as you used it (being able to separate motion in polar coordinates and solve separately), are there kinds of coordinates where we have to beware before setting an Euler-lagrange equation for each coordinate?

Are there limiting cases?

Thanks so much!

PS: Could you also look at problem 2.20?  I posted my solution, but apparently, I got something wrong, and don't know what...

[quote="integration"]Oh, and another clarification...

For now, I pretty much accept without question that choose L=T-V, allows the principle of least action to be applied to classical mechanics (correct me if I'm wrong).  So basically, when solving mechanics problems (motion of particles), you are finding the path were the line integral of L dt is minimized.[/quote]

Yep, that's the idea.

[quote="integration"]But I feel more queasy about the liberal use of coordinates.  You see, with Newton Mechanics, motion into 3 dimensions, and treating each cartesian dimension separately is OK, for me.[/quote]

That's the beauty of the Lagrangian approach, the coordinates $ q$ and $ \dot{q}$ are generalized coordinates -- meaning that you are free to choose whatever coordinates are most convenient for you to solve the problem.

When I first learned to do this in grad school (I'm an engineer who became a physicist later because I wanted to teach. Most physicist's see this stuff as advanced undergrads.) my professor insisted on first writing the Lagrangian in Cartesian coordinates then transforming it to a more suitable set of coordinates. {It was instructive, but a pain in the posterior to do every time you want to solve a problem as far as I'm concerned.} The point is, whatever coordinates you choose, your Lagrangian should agree, under transformation, with the Lagrangian (of the same system) in any other coordinates you might have picked.

[quote="integration"]1. So basically, Dr. No, if we were to use Euler Lagrange to solve motion in 3-D over time, we would have 1 euler lagrange equation for each coordinate?
Can we treat each equation separately, thus finding x(t)=?, y(t)=?, z(t)=?, and making a combo of them to find v(t), a(t)?[/quote]

That's correct. I should have been more explicit when I wrote the general formula.

\[ \mathcal{L}(q_1,q_2,q_3,\ldots q_n;\dot{q}_1,\dot{q}_2,\dot{q}_3,\ldots \dot{q}_n, t)\\ = T(q_1,q_2,q_3,\ldots q_n;\dot{q}_1,\dot{q}_2,\dot{q}_3,\ldots \dot{q}_n, t) - V(q_1,q_2,q_3,\ldots q_n;\dot{q}_1,\dot{q}_2,\dot{q}_3,\ldots \dot{q}_n, t)\]

I was just being lazy -- all the subscripts and what not are a lot of $ \text{\LaTeX}$ code to write.

Nevertheless, the Euler-Lagrange Diff EQ applied to an individual coordinate pair $ (q_i,\dot{q}_i)$ gives the equation of motion in the $ q_i$ direction. For example, the Euler-Lagrange Diff EQ for this particular coordinate pair is $ \frac{d}{d t}\left(\frac{\partial \mathcal{L}}{\partial \dot{q}_i}\right) -\frac{\partial \mathcal{L}}{\partial q_i} = 0$

So the answer is yes, you do get a separate equation for each direction.

For instance let us consider a particle of mass $ m$ under the influence of gravity,

\begin{align*} V(z) &= mgz \\ T(\dot{x},\dot{y},\dot{z}) &=\frac12m\dot{x}^2 +\frac12 m\dot{y}^2 + \frac12 m\dot{z} \\ \mathcal{L} &= T - V =\frac12m\dot{x}^2 +\frac12 m\dot{y}^2 + \frac12 m\dot{z} - mgz\end{align*}

Then
\begin{align*}\frac{d}{d t}(\frac{\partial \mathcal{L}}{\partial \dot{x}}) -\frac{\partial \mathcal{L}}{\partial x} &= 0 \implies m\ddot{x} = 0 \\ \frac{d}{d t}(\frac{\partial \mathcal{L}}{\partial \dot{y}}) -\frac{\partial \mathcal{L}}{\partial y} &= 0 \implies m\ddot{y} = 0 \\ \frac{d}{d t}(\frac{\partial \mathcal{L}}{\partial \dot{z}}) -\frac{\partial \mathcal{L}}{\partial z} &= 0 \implies m\ddot{z} = -mg\end{align*}

This make sense because there are no forces in the x or y directions -- momentum is conserved in these directions, such coordinates are called [i]cyclic coordinates.[/i]

[quote="integration"]2. This is the part that makes me troubled.  How can that Euler Lagrange equation work separately for [i]polar[/i] coordinates, which seems what you have done, since you basically ignored motion in the tangential direction, and set up motion in the radial direction for your equation?[/quote]

I could have found the tangential motion had I needed to, but it wasn't required for the problem.

[quote="integration"]3.  And if Euler-lagrange is as powerful as you used it (being able to separate motion in polar coordinates and solve separately), are there kinds of coordinates where we have to beware before setting an Euler-lagrange equation for each coordinate?

Are there limiting cases?[/quote]

No, typically not. As I said the $ q$ coordinates are general coordinates. It is up to you to choose what coordinates are most convenient for your system.

The Euler-Lagrange equation as I have given it, i.e. with the right hand side equal to zero, is really only applicable to free particles. Where there are constraints present, or non-conservative forces, these appear on the right hand side of the equals sign, as in:

\[ \frac{d}{d t}\left(\frac{\partial \mathcal{L}}{\partial \dot{q}_i}\right) -\frac{\partial \mathcal{L}}{\partial q_i} = F_{q_i}\].

There was a constraint in your problem here, $ r_B + r_A =\ell$, but I eliminated it [i]a priori[/i] by solving the constraint equation for $ r_B$ and substituting this back into the Lagrangian. If I hadn't done this I would have had to use Lagrange multipliers to simultaneously solve more than one equation of motion.

[quote="integration"]PS: Could you also look at problem 2.20?  I posted my solution, but apparently, I got something wrong, and don't know what...[/quote]
I'll give it a look, but I thought you had it handled so I initially ignored it. Though I'm not going to make you any promises that I'll be able to find where you went wrong. Okay?

[hide="Cant we do this:"]
$ \ddot r_a \equal{} a \\
 \\
\; \text{Draw the FBD of both masses,} \\
 \\
m_B\omega^2(l \minus{} r_a) \minus{} T \equal{} m_Ba \ldots\ldots\ldots\ldots(1) \\
 \\
m_A\omega^2r_a \minus{} T \equal{} m_Aa \ldots\ldots\ldots\ldots (2) \\
 \\
\; \therefore a \equal{} \frac {\omega^2[m_Bl \minus{} r_A(m_B \plus{} m_A)]}{m_B \minus{} m_A} \ldots\ldots\ldots (1) \minus{} (2)$

Thus, $ a$ is positive ($ r_A$ increases) if $ m_B > m_A$ or negative ($ r_A$ decreases) if $ m_A > m_B$.
[/hide]

[quote="Rajiv"]Cant we do this:
$ \ddot r_a \equal{} a \\
 \ldots \\
\; \therefore a \equal{} \frac {\omega^2[m_Bl \minus{} r_A(m_B \plus{} m_A)]}{m_B \minus{} m_A} \ldots\ldots\ldots (1) \minus{} (2)$

Thus, $ a$ is positive ($ r_A$ increases) if $ m_B > m_A$ or negative ($ r_A$ decreases) if $ m_A > m_B$.
[/quote]

Rajiv,

By my calculation $ \ddot{r}_A \equal{} \omega^2 r_A \minus{}\frac{m_B}{m_A \plus{} m_B}\omega^2 \ell$.

I'll let you figure out which of us is correct.

[quote="integration"]Sure!  You know, that lagrangian mechanics is the kind of thing that absolutely makes my day  :D[/quote]

I didn't get the same answer to P2.20 as the authors of your text, but I did get something of the same form.

I'll show it to you any how and maybe you can figure out where I (or they) went wrong.

To begin with,

\[ T =\frac12(m_1\dot{x}_1^2 +m_2\dot{x}_2^2 + m_3\dot{x}_3^2 + m_3\dot{y}^2)\]

It is rather obvious that $ \dot{x}_3 =\dot{x}_1$.

Thus $ T$ becomes $ T =\frac12(\{m_1 + m_3\}\dot{x}_1^2 +m_2\dot{x}_2^2 + m_3\dot{y}^2)$.

The potential we'll call $ V^{\prime}(y) = m_3gy$.

There are two equations of constraint that can be written.

You should be able to see that $ x_2 = \ell - y \implies x_2 + y -\ell = 0$, where $ \ell$ is the length of the cable between $ m_2$ and $ m_3$.

This is our first equation of constraint: $ \phi(x_2, y) = x_2 + y -\ell = 0$.

As Gauss202 pointed out, $ m_1\dot{x}_1 + m_2\dot{x}_2 = 0$ by the conservation of momentum.

Integrating both sides of this equation with respect to time: $ m_1x_1 + m_2x_2 = C$

This gives our second constraint equation: $ \phi_2(x_1,x_2) = m_1x_1 + m_2x_2 - C = 0$.

Since these equations are equal to zero we may add them to the potential without affecting it in any way.

\[ V(x_1,x_2,y) = V^{\prime} +\lambda_1\phi_1(x_2, y) +\lambda_2\phi_2(x_1, x_2)\]

The scalar constants $ \lambda_1$ and $ \lambda_2$ are undetermined (Lagrange) multipliers.

With that in mind the Lagrangian is given by,

\[ \mathcal{L} = T(\dot{x}_1,\dot{x}_2,\dot{y}) -V(x_1,x_2,y) \\ = T(\dot{x}_1,\dot{x}_2,\dot{y}) -\{V^{\prime} +\lambda_1\phi_1(x_2, y) +\lambda_2\phi_2(x_1, x_2)\} \\ =\frac12(\{m_1 + m_3\}\dot{x}_1^2 +m_2\dot{x}_2^2 + m_3\dot{y}^2) -m_3g y -\lambda_1(x_2 + y -\ell) -\lambda_2(m_1x_1 + m_2x_2 - C)\]

\[ \frac{d}{dt}\left(\frac{\partial \mathcal{L}}{\partial \dot{x}_1}\right) -\frac{\partial \mathcal{L}}{\partial x_1} = 0 \\ \\ \implies (m_1 + m_3)\ddot{x}_1 +\lambda_2m_1 = 0\]

\[ \frac{d}{dt}\left(\frac{\partial \mathcal{L}}{\partial \dot{x}_2}\right) -\frac{\partial \mathcal{L}}{\partial x_2} = 0 \\ \\ \implies m_2\ddot{x}_2 +\lambda_1 +\lambda_2m_2 = 0\]

\[ \frac{d}{dt}\left(\frac{\partial \mathcal{L}}{\partial \dot{y}}\right) -\frac{\partial \mathcal{L}}{\partial y} = 0 \\ \\ \implies m_3\ddot{y} + m_3g +\lambda_1 = 0\]

We then have the following equations of motion.

\begin{eqnarray}(m_1 + m_3)\ddot{x}_1 +\lambda_2m_1 &=& 0 \\ m_2\ddot{x}_2 +\lambda_1 +\lambda_2m_2 &=& 0 \\ m_3\ddot{y} + m_3g +\lambda_1 &=& 0\end{eqnarray}

Combining these EOM's to eliminate the Lagrange multipliers we obtain,

\[ m_2(m_1 + m_3)\ddot{x}_1 -m_1m_2\ddot{x}_2 + m_1m_3(\ddot{y} + g) = 0\]

The conservation of momentum equation $ \implies m_1\ddot{x}_1 = -m_2\ddot{x}_2$.

Substituting this into the equation above we obtain,

\[ \{m_2(m_1 + m_3) + m_1^2\}\ddot{x}_1 + m_1m_3(\ddot{y} + g) = 0\]

Finally, according to the problem statement $ \ddot{y} = 0$ ; it follows,

\[ \boxed{\therefore \ddot{x}_1 = \frac{- m_1m_3 g}{m_1^2 + m_1m_2 + m_2m_3}}\]

[quote="Rajiv"][quote="Dr. No"]
Rajiv,

By my calculation $ \ddot{r}_A \equal{} \omega^2 r_A \minus{} \frac {m_B}{m_A \plus{} m_B}\omega^2 \ell$.
[/quote]

That leads us to:
$ \ddot r_A \equal{} \omega^2\left(\frac {r_A(m_B \plus{} m_A) \minus{} m_Bl}{m_A \plus{} m_B}\right)$

While my expression is the mostly the same except my denominator is $ m_A \minus{} m_B$.

Where did I go wrong? (Why does this happen to me all the time! :wallbash_red: )[/quote]

From what I can tell in your $ \text{Eq. (1)}$. (Hint: $ m_B$ [b]does not[/b] accelerate with acceleration $ a$.)

I solved it!  All that was missing from the previous solution was the number -M2 ^2, which has to be added if we solved for the Free-body diagrams in a non-inertial frame.

Here is my updated solution.  When i'll have more time, I'll try to solve it using lagrangian mechanics /energy principles.

[quote="Dr. No"]Hint: $ m_B$ [b]does not[/b] accelerate with acceleration $ a$.[/quote]

Does $ m_B$ accelerates with $ \minus{}a$. That was what I was planning to do initially but if both accelerate in same direction, why should the signs be different?

If mB is moving closer to the origin, (center of rotation), mA is moving away from the center of rotation,  Thus R'' a=-R''b.

We're in polar coordinates, and since we solve for radial accelerations, we have to use radial coordinates.

PS: don't ask me, I myself feel really queasy applying newton's laws in polar coordinates  :blush:

[quote="Rajiv"][quote="Dr. No"]Hint: $ m_B$ [b]does not[/b] accelerate with acceleration $ a$.[/quote]

Does $ m_B$ accelerates with $ \minus{} a$. That was what I was planning to do initially but if both accelerate in same direction, why should the signs be different?[/quote]

Recall
$ r_B \equal{} \ell \minus{} r_A \\ \ddot{r}_B \equal{} \minus{}\ddot{r}_A$

[quote="Dr. No"]
$ r_B \equal{} \ell \minus{} r_A \\
\ddot{r}_B \equal{} \minus{} \ddot{r}_A$

[/quote]

Oops! I didn't think about that. Thanks. So, with $ \ddot r_B \equal{} \minus{}a$, my answer is correct.
 :D

[quote="Rajiv"]Oops! I didn't think about that. Thanks. So, with $ \ddot r_B \equal{} \minus{} a$, my answer is correct.
 :D[/quote]

You asked where you had gone wrong. I believe that is where, yes. When I worked it out I used the fact that $ r_B \equal{} \ell \minus{}r_A$ to eliminate $ r_B$ from my system of equations before I even wrote down the equations of motion, so my analysis was slightly different from yours. Nevertheless, you can check to see if this was why our results are different by making the substitution $ \ddot{r}_B \equal{} \minus{}a$ in your analysis, re-solving for $ a$, and then see whether our results agree. If so, it would be verification for both of us that FBD analysis and Lagrangian analysis are consistent with one another. Else if not then one of us did something wrong, and I'm not above admitting that in such a case it might've been me.

Just reviving this... I'm soon gonna post more solutions!

Problem 2.29

Solution

[hide]

Formula from K&K

$ \vec a \equal{} (\ddot r \minus{} r \dot \theta ^2) \hat {r} \plus{} (r \ddot \theta \plus{} 2 \dot r \dot \theta) \hat {\theta}$
$ \vec a \equal{} \minus{} v_o t \omega ^2 \hat {r} \plus{} 2 v_o \omega \hat {\theta}$

Slides when condition

$ gu \equal{} a$

$ gu \equal{} | \minus{} v_o t \omega ^2 \hat {r} \plus{} 2 v_o \omega \hat {\theta}|$
$ gu \equal{} [(v_o t \omega ^2)^2 \plus{} 4 v_o^2 \omega^2]^{\frac 12}$
$ t \equal{} \sqrt {\frac {(gu)^2 \minus{} 4 \omega ^2 v_0 ^2}{\omega ^4 v_o ^2}}$

Friction has a total magnitude of gu, and an angular  component 2 omega v_o.

So
$ \alpha \equal{} arcsin (\frac {2 \omega v_o}{gu})$
[/hide]

I'll solve this another way next time, b/c it's not really a good solution (plug and chug)

How do you solve problem 2.32?  I have no idea how to approach it.

Can you write problem 2.32?

You only posted up to 2.30. :D.

2.32:  Oops! I was reading along the book, haha...

A wheel of radius R rolls along the ground with velocity V.  A pebble is carefully released on top of the wheel so that it is instantaneously at rest (WTH??) on the wheel.

a.  Show that the pebble will immediately fly off the wheel if V greater than sqrt {Rg}.
b. Show tha in the case where V smalller (Rg) ^(1/2), and the cofficient of friction is 1, the pebble satarts to slide when it has rotated through an angle given by theta = arcos (1/sqrt (2) )(V^2/(Rg))- pi/4.

I'm going to post the rest of the problems soon.

PS: Since I'm working on this book this summer, I'll post all new problems in this thread, and work at a constant pace with you guys (I'll probably need your help to solve many of the problems in here).

OK, Is part a correct?

Solution a:

[hide]

$ a_{max} \equal{} g$
$ a_{point on wheel edge relative to center} \equal{} \frac {v^2}{R}$
$ v_{max} \equal{} sqrt {Rg}$

[/hide]

Not sure how to solve b.

Part b: $ \frac{1}{\sqrt{2}}(\cos\theta \minus{} \sin\theta) \equal{} \cos(\theta \plus{} \pi/4)$ should help.

Umm.. Ok I think the problem is I don't get what the problem is asking for 2.32.

Can sb help for problem 2. 24 (Posted at the beginning of the thread)

Here's my attempt:

[hide]

Let's consider an infinitesimal part of the the thread, which is in equilibrium.
Let $ T$ be the thread tension, $ d\theta$ the infinitesimal angle subtended by the infinitsimal thread length.

using a force-body diagram, we obtain:

$ T sin (\delta \theta) \equal{} T \delta \theta \equal{}$ normal force exerted by the wood on the thread.

In the horizontal direction

\[ uN \equal{} dT cos (\frac {\delta \theta}{2})\]
We obtain a differential equation, with

\[ dT \equal{} \frac { uT d \theta}{cos (\frac {\delta \theta}{2})}\]

I solved it, but didn't get the supposed result.

[/hide]

Can sb help?[/hide]

2.32: The forces on the pebble are the gravitational force, the normal force, the centrifugal force (from its frame of reference), and the frictional force.  Use the radial component of the gravitational force and the centripetal force to determine the normal force.  Then determine the frictional force from that.  Then determine the angle at which the frictional force fails to counteract the tangential component of the gravitational force.  Lastly, use that trig identity I mentioned.

2.24: To be precise, $ dF_\perp \equal{} 2T\sin(d\theta/2) \equal{} T d\theta$.  Hence the infinitesimal frictional force is $ dF_\mathrm{fric} \equal{} \mu T d\theta$.  But this is just the infinitesimal change in the tension, or $ \minus{} dT$.  This gives you the separable equation
\[ \frac {dT}{d\theta} \equal{} \minus{} \mu T.
\]
Solving gives $ T(\theta) \equal{} T_0 e^{ \minus{} \mu\theta}$.  This is almost exactly the same as what you did, but you have to realize that as $ d\theta \rightarrow 0$, the $ \cos(d\theta/2)$ term becomes 1.

THANX  lot for solve this problem,beacuse i can't solve this.... and i can fly :pilot:

[quote="genericme"]2.32: The forces on the pebble are the gravitational force, the normal force, the centrifugal force (from its frame of reference), and the frictional force.  Use the radial component of the gravitational force and the centripetal force to determine the normal force.  Then determine the frictional force from that.  Then determine the angle at which the frictional force fails to counteract the tangential component of the gravitational force.  Lastly, use that trig identity I mentioned.

2.24: To be precise, $ dF_\perp \equal{} 2T\sin(d\theta/2) \equal{} T d\theta$.  Hence the infinitesimal frictional force is $ dF_\mathrm{fric} \equal{} \mu T d\theta$.  But this is just the infinitesimal change in the tension, or $ \minus{} dT$.  This gives you the separable equation
\[ \frac {dT}{d\theta} \equal{} \minus{} \mu T.\]
Solving gives $ T(\theta) \equal{} T_0 e^{ \minus{} \mu\theta}$.  This is almost exactly the same as what you did, but you have to realize that as $ d\theta \rightarrow 0$, the $ \cos(d\theta/2)$ term becomes 1.[/quote]

hey..yes.....f_s-mgsin(theta)=0 and f_s= N.mu (mu=1)==>F_N=N=mgsin(theta) (I)
F_N-mgcos(theta)=-mv^2/R (II)
I AND II===>mgsin(theta)-mgcos(theta)=-mv^2/R
cos(theta)-sin(theta)=v^2/Rg
$ \frac {1}{\sqrt {2}}(\cos\theta \minus{} \sin\theta) \equal{} \cos(\theta \plus{} \pi/4)$
===>theta=[1/(2^1/2) (v^2/Rg)]-pi/4
huraaaaaaaaaaaa   :clap:


function
real analysis
real analysis unsolved

[quote="Mitzah"]Let $a>\frac{1}{4}$. How many continuous functions $f: R \to R$ with the property that $(f \circ f) (x) = x^2+a$, for all $x \in R$ do there exist?[/quote]
There are infinitely many. Here is how to construct such functions:

Choose $0 < c < a$ and set $a_0 = 0, \, a_1 = c, \, a_{k+1} = a_{k-1}^2+a$ for $k \ge 1$. Since $x^2 + a > x$ for all $x$, the $a_k$ go to $\infty$. Then set $I_k = [a_k,a_{k+1}]$ for $k = 0, 1, ...$.

Now pick an arbitrary continuous strictly increasing function $f$ on $[0,c]$ such that $f(0) = c, \, f(c) = a$. That is, $f: I_0 \to I_1$ is a homeomorphism. Let $g=f^{-1}: I_1 \to I_0$ be its inverse, and define $f(x) = g(x)^2+a$ for $x \in I_1$. One checks that $f$ is defined unambiguously at $x=a_1=c$ and that $f$ is continuous and strictly increasing. Also, $f(I_1) = I_2$. Denote the inverse of $f$ again by $g$. Note that $f(f(0)) = 0^2 + a$.

Suppose now $f$ has been defined on $\cup_{i \le k}I_i$ and is continuous and strictly increasing there, with inverse $g$, such that $f(I_{j}) = I_{j+1}$ for $j = 0, \dots, k-1$ and $f(f(x)) = x^2 + a$ for $x \le a_{k-1}$. Define $f(x) = g(x)^2+a$ for $x \in I_{k+1}$. One checks that $f$ is increasing and continuous (in particular at $x = a_{k+1}$) and that for $a_{k-1} \le x \le a_k$
$f(f(x)) = g(f(x))^2 + a = x^2 + a$
by construction.
Thus $f$ has been constructed inductively on $[0,\infty)$. Set $f(x) = f(-x)$ for $x < 0$ to obtain a function that is defined for all $x$.

One can show that the property $\forall_x f(f(x)) = x^2 + a$ together with $a > 1/4$ implies that $x < f(x) < x^2+a$, $f$ is even, and $f$ is 1-1 on $[0,\infty)$, so all solutions of the problem may be found in this manner.


Let $n$ be a positive integer. Denote by $S_n$ the set of points $(x, y)$ with integer coordinates such that \[ \left\lvert x\right\rvert + \left\lvert y + \frac{1}{2} \right\rvert < n. \] A path is a sequence of distinct points $(x_1 , y_1), (x_2, y_2), \ldots, (x_\ell, y_\ell)$ in $S_n$ such that, for $i = 2, \ldots, \ell$, the distance between $(x_i , y_i)$ and $(x_{i-1} , y_{i-1} )$ is $1$ (in other words, the points $(x_i, y_i)$ and $(x_{i-1} , y_{i-1} )$ are neighbors in the lattice of points with integer coordinates). Prove that the points in $S_n$ cannot be partitioned into fewer than $n$ paths (a partition of $S_n$ into $m$ paths is a set $\mathcal{P}$ of $m$ nonempty paths such that each point in $S_n$ appears in exactly one of the $m$ paths in $\mathcal{P}$).

Suppose you have a partition of less than $ n$ paths. Then start from $ (0,n \minus{} 1)$ and work your way down to $ (0, \minus{} n)$ along the right edge of $ S_n$ performing the following algorithm when going from each point.

(example of described path for $ S_4$)
[code]...V...
..o>V..
.ooo>V.
ooooo>V
oooooV<
.oooV<.
..oV<..
...X...[/code]

If a path already has the point you're coming from and the point you're going to as adjacent in the path, do nothing.

If not the first case, and the point you're coming from and the point you're going to are both endpoints of paths, join them (one less path).

If not the first case, and there is exactly one endpoint among the point you're coming from and the point you're going to, remove a segment from the one in the middle of a path (paths +1) and now you have two endpoints; join them (paths -1). If the point in the middle of the path is the one you're coming from, remove the segment that doesn't come from the point that came before it. The number of paths remains the same.

If not the first case, and both points are in the middle of a path... well this is impossible. Since the two points are in the middle of the path, they are adjacent to two other points. But they are also adjacent to each other, so both are adjacent to at least three points. And now you can prove, looking at the path we're going to, that no two points adjacent to at least three others are travelled consecutively.

So given any configuration we can create the path shown above without increasing the number of paths. The remaining points form $ S_{n\minus{}1}$. Now suppose for some positive integer $ n$, we have a partition into less than $ n$ paths. Apply the algorithm to make the path shown above. Then the remaining points are partitioned into less than $ n\minus{}1$ paths. Apply the algorithm again. Repeat until we show that $ S_1$ is partitioned into less than $ 1$ path. This is absurd, and we're done.

[hide="Vague, very unrigorous and unelegant proof overview"]Um, my proof was lke 10% rigorous.  I just proved that the generalized formula for the number of lattice points was $ 2n^2$, and then I proved that the maximum number of segments for one path was 2n-1, meaning the maximum number of points was 2n.  Dividing, I got that there could be at least $ \frac {2n^2} {2n}\equal{}n$ paths.  I know I'm making seriously wrong assumptions, but oh well.  Can't remember my actual proof though.[/hide]

Can anyone give me an estimation of how many points out of 7 that would be? :D

Maybe 1 or 2?

[quote="MellowMelon in other topic"]You may as well face it that score estimates from people on this forum will almost certainly suck. Just don't worry about it.[/quote]

I won't estimate your score, but I can tell you your lemma that one path has at most $ 2n$ points is false. For $ S_3$, take the following path:

$ (0,2) (0,1) (1,1) (1,0) (2,0) (2, \minus{} 1) (1, \minus{} 1) (0, \minus{} 1)$
$ (0,0) ( \minus{} 1,0) ( \minus{} 2,0) ( \minus{} 2, \minus{} 1) ( \minus{} 1, \minus{} 1) ( \minus{} 1, \minus{} 2) (0, \minus{} 2) (0, \minus{} 3)$

This path contains $ 16$ points, which is greater than $ 2 \cdot 3 \equal{} 6$.

Oh...  Wow, that's disappointing...  Well...  I stand corrected...

So, suppose we have a valid pathing of S_i-1 with at least i-1 paths, as Mellow says. Then, how do we know the paths can't just be extended into the points in S_i but not S_i-1, and/or two paths in S_i-1 can be joined with no more than one new path? I don't quite follow your proof.

Mellow, I didnt read most of your proof, but I think i had the same general idea as you did.

[hide="Solution Outline"]I proved this the same way as in the official solution.  Basically, color all the points in $ S_{n}$ white or black such that each row of points starts and ends with a white point.  This is essentially a checkerboard pattern, except that the middle two rows are identical.  We have $ 2n$ more white points than black points, and we can only "recover" white points by having paths whose endpoints are both white (this can only happen $ n \minus{} 1$ times, once for each path) or by using the adjacent white squares in the middle two rows (there are only $ n$ such pairs).  Therefore we can't make up for those $ 2n$ extra white points, so there's no partition into fewer than $ n$ paths.[/hide]

Don't worry, my actual proof was a lot more rigorous.  :)

This solution is different from the official so please critique it.
[hide="My proof"]We induct on $ n$ to prove that an $ n\minus{}1$-path partition is impossible. This can be restated as saying that we cannot fit $ 2n^2\minus{}n\plus{}1$ edges into the graph with each vertex having degree at most 2. The base case is trivial (2 edges when there only is 1). Suppose it was possible for $ n\plus{}1$, and we'll prove it's possible for $ n$.

Call the 'complete' network (graph) of points $ G_{n\plus{}1}$ and the $ n$-path partition for $ n\plus{}1$ is a subgraph of $ G_{n\plus{}1}$, $ H_{n\plus{}1}$. There are a total of $ 2(n\plus{}1)^2\minus{}n\equal{}2n^2\plus{}3n\plus{}2$ edges in $ H_{n\plus{}1}$ out of $ 4n^2\plus{}4n\plus{}1$ in $ G_{n\plus{}1}$ (not hard to prove), and each vertex has maximum order 2. Now consider the complement of $ H_{n\plus{}1}$ in $ G_{n\plus{}1}$, that is, take all the edges in $ G_{n\plus{}1}$ that are not in $ H_{n\plus{}1}$ and of course all the vertices. Call this $ F_{n\plus{}1}$ We will trim $ F_{n\plus{}1}$ down a bit to get $ H_n$.

First, call the points in $ S_{n\plus{}1}$ but not $ S_n$ exterior points, and the points in $ S_n$ interior points. $ F_{n\plus{}1}$ has $ 2n^2\plus{}n\minus{}1$ edges. Since the interior points have degree 4 in $ G_{n\plus{}1}$, they have degree at least 2 in $ F_{n\plus{}1}$, for a total degree of $ 4n^2\plus{}m$ where $ 0\le m\le 2n\minus{}2$ since the total overall degree is $ 2(2n^2\plus{}n\minus{}1)\equal{}4n^2\plus{}2n\minus{}2$. This makes the total degree of the exterior points $ 2n\minus{}2\minus{}m$. Since the exterior points are not connected in $ G_{n\plus{}1}$, these $ 2n\minus{}2\minus{}m$ edges must connect on exterior point to an interior point.

I then take away $ 2n\minus{}2$ edges and the exterior points, yielding $ 2n^2\minus{}n\plus{}1$ edges and the interior points, which is $ H_n$, as follows: First take away those $ 2n\minus{}2\minus{}m$ interior-exterior edges and shave off all the exterior points. Then the total degree (now just of the interior points) must be $ 4n^2\minus{}2n\plus{}2\plus{}2m$.

Let the number of 0-degree vertices be $ a$, 1-degree vertices be $ b$, 2-degree vertices be $ c$, 3-degree vertices be $ d$, and 4-degree vertices be $ e$. Since all the vertices began as 2-degree or higher, $ 2a\plus{}b\le2n\minus{}2\minus{}m$. Moreover, the total degree is $ b\plus{}2c\plus{}3d\plus{}4e\equal{}2(2n^2)\plus{}(d\plus{}2e)\minus{}(b\plus{}2a)\equal{}4n^2\minus{}2n\plus{}2\plus{}2m$. So $ d\plus{}2e\equal{}b\plus{}2a\minus{}(2n\minus{}2\plus{}2m)\le (2n\minus{}2\minus{}m)\minus{}(2n\minus{}2\minus{}2m)\equal{}m$ So we can use our last $ m$ edges to remove any excess degree on vertices with degree 3 or 4, yielding $ H_n$.[/hide]
I know that solution is much longer than the official one, but does it work?

Very good solution, I didn't see the "hole" :?:

[quote="nealth"]This is my scanned solution. I purposefully cut off the top so that people won't know my student number.  :lol:
I know it has a hole, but I hope it's worth 2 or 3 points[/quote]

 :D I've finally found a proof that is close to mine except that in the end I especially mentioned when N=2or 3, it takes at least 2,3 paths relatively...(and that my answer wasn't that full-proofed for I only had 15 minutes to write up the thing :( )

This is pretty much MellowMelon's proof, except a lot less concise and much less clear (as I didn't include diagrams and felt the need to explain everything).

It is evident that the set of lattice points satisfying this is composed of two isosceles triangular grids: one with a base with midpoint $ (0,0)$, base length $ 2(n\minus{}1)$, height $ n\minus{}1$, with its vertex at $ (0,n\minus{}1)$, and another which is the first one reflected over $ y\equal{}\minus{}\frac{1}{2}$ - that is, base midpoint at $ (0,\minus{}1)$, base length $ 2(n\minus{}1)$, height $ n\minus{}1$, and vertex at $ (0,\minus{}n)$.

Now we define a [b]side path[/b] to be a path between two side points of our figure (i.e. $ (x,y)$ is a side point of our figure if there are only two points which are in the figure out of $ (x\plus{}1,y),(x\minus{}1,y),(x,y\plus{}1),(x,y\minus{}1)$) with certain restrictions. Letting the two points be $ (a,b),(c,d)$ and letting the line through them be $ y\equal{}f(x)$ we need that every side point $ (x,y)$ satisfying $ y \le f(x)$ be in the path [b]or[/b] every side point satisfying $ y\ge f(x)$ be in the path if the points are noncollinear. If they're collinear, then the side points in the path are either the ones on the line through them and between the two points, or the complement of that set. In addition, regardless of collinearity, the only other points in our path can be the points bordering at least two side points within the path.

This (absolutely ridiculous, I'm sorry) definition is not as complicated as it sounds; it just means that every side point on the side of the figure "between" the two points is in the path, and the side path moves in a staircase fashion betwene them. Noting that by definition, each pair of side points has two possible side paths between them, we prove the following lemma:

[b]Lemma:[/b] Both side paths of a pair of side points $ (a,b),(c,d)$ are actually possible iff the two points are the vertices of the isosceles triangles. Otherwise, one path is achievable iff the two points are on the same side of the $ y$-axis.

[b]Proof:[/b] We prove the result that no side path can travel through points on both sides of the $ y$-axis, which quickly gives the desired result, because the second part is immediately equivalent and for the first part, two side points on the same side of the $ y$ axis have a line through them which self-evidently does not intersect the $ y$-axis within the boundaries of our figure; hence the path on the side of that line which doesn't contain the $ y$-axis is attainable while the other is not. The side path between the two vertices of the triangles is also easily shown to be attainable; move in a staircase fashion from top one (down one, right one, etc.) until one reaches $ (n\minus{}1,\minus{}1)$, then repeat the same process except as a reflection across $ y\equal{}\minus{}\frac{1}{2}$.

On to the proof of our intermediate result: Suppose a side path went through side points on both sides of the $ y$-axis. Then it would have to pass through one of the vertices of the two isoceles triangles as they are the only side points linking the two side of our figure. WLOG, let the one it passes through be $ (0,\minus{}n)$. It must then also pass through $ (\minus{}1,\minus{}n\plus{}1)$ and $ (1,\minus{}n\plus{}1)$. But the only point adjacent to our triangle vertex is $ (0,\minus{}n\plus{}1)$ and from here only one of these two points can be reached, WLOG choose $ (1,\minus{}n\plus{}1)$ (since by definition going up again to $ (0,\minus{}n\plus{}2)$ would result in a non-side path). However, after the side path passes through $ (1,\minus{}n\plus{}1)$, by definition it can only travel along the side and bordering-side points, and so for the side path to reach $ (\minus{}1,\minus{}n\plus{}1)$ it must cross the $ y$-axis at the other end; through $ (0,n\minus{}1)$. But to get there, it must pass through $ (0,n\minus{}2)$, and then once it reaches that point, there are no other points bordering $ (0,n\minus{}1)$, so we're "stuck". Contradiction (and none too soon!).

Now we prove another lemma:

[b]Lemma:[/b] Consider one of the side paths connecting the two isosceles triangles' vertices (WLOG the on the positive side of the $ y$-axis) and the side path connecting $ (\minus{}1,n\minus{}2)$ and $ (\minus{}1,\minus{}n\plus{}1)$. The minimal number of paths which our figure can be partitioned into can be attained with these in place.

[b]Proof:[/b] Consider a partition which attains the minimum, and specifically the path containing $ (\minus{}0,\minus{}n)$. It of course must connect to the point directly above it, or the partition wouldn't be optimal. Now, we show by a "smoothing" process that it is possible to change the partition to one with a side path from $ (\minus{}0,\minus{}n)$ to $ (0,n\minus{}1)$. without increasing the number of paths.

Consider each successive point so that the paths in the given partition differ from a partition with such a side path; in particular consider the path that contains the point which would otherwise be in the side path.

[b]Case 1:[/b] The point which would otherwise be in the side path is a side point.

In this case, this point must simply be connected to the next point in the side path (since each side point borders only two points), s we can simply connect the preceding point in the path to it. If the preceding point is already connected to another non-side path point, disconnect it - we can do this, as we merged two paths without disconnecting anything earlier.

[b]Case 2:[/b] The point is a point which borders the side points.

If this point is connected to the side point following it on the would-be path, then we can simply use our above logic. If it's not connected to it but is also connected to only at most one of the non-side points it borders, we can disconnect it and connect it to the path without increasing the number of side paths.

Finally, if it's connected to both of the non-side points it borders, we can't disconnect it without splitting a path in two, but we can compensate by linking it to both the existing side path and the next point in the side path, hence connecting two existing paths. We can do this without forming a loop because each side point only borders two other points.

We can apply the same logic to the other path (by symmetry), and so our lemma follows.

Finally, we prove our claim by induction. We have two base cases; note that when $ n\equal{}1$ or $ 2$, by inspection (if I could draw a diagram I would be more rigorous, I swear) we can't partition the figure $ S_n$ into fewer than $ n$ paths.

Now, suppose that we can't partition $ S_n$ into fewer than $ n$ paths for $ n\equal{}k\minus{}2$. By our lemma, if it were possible to partition $ S_k$ into fewer than $ k$ paths, we could do it with the side paths (call them $ a,b$) mentioned in our lemma in place. However, $ S_k\setminus (a\cup b)$ is just $ S_{k\minus{}2}$, which means that $ S_{k\minus{}2}$ could be partitioned into fewer than $ k\minus{}2$ paths - contradiction.

The result follows.

Does this proof work? It's pretty similar to MellowMelon's.

Assume that it is possible to partition the region into fewer than $n-1$ paths.

Consider the staircase-shaped path, $P$, formed along the right edge of the region. If any unit segment of $P$ is not joined in the partition, then draw it in. Then, if necessary, erase the segment that now sticks out from a point in $P$ to an adjacent point to the left. Clearly the number of paths does not increase. Then, we are left with $S_{n-1}$ which is partitioned with fewer than $n-2$ paths. Then keep going, until you have one point left, but no paths, a contradiction.

[quote="luie1168e"]which USAMO is this?[/quote]

It's from 2008. Sorry for reviving it. I keep thinking my solution is too simple, so I was hoping someone could tell me if I'm missing something obvious.

Here's the major problem I see with your solution: "Clearly the number of paths does not increase."

It's true (as the me of almost 3 years ago showed in the first reply), but to say it's "clearly" true is handwaving.

[hide]Let $G_n$ be the graph whose vertices are lattice points in $S_n$ and where edges are drawn between neigboring lattice points. Denote the left-most and right-most edges $l$ and $r$, their neighbors to the top $a$ and $b$, and their neighbors to the bottom $c$ and $d$, respectively. Now, each partition $P$ of $S_n$ into $m$ paths is equivalent to a partition $Q$ of $G_n$ into $m$ Hamiltonian paths. Since there are $2n^2$ vertices in total, the number of edges in $Q(G_n)$ is $2n^2-m$.

Claim: number of edges in $Q(G_n)$ is at most $2n^2-n$, with maximality only if (i) $l$ and $r$ are connected (ii) $a$ or $b$ is connected (iii) $c$ or $d$ is connected.
Proof: We proceed by induction. For $n=1$ this may be manually checked. Assume the claim true for $n-1$. Let $X, Y$ be the $G_{n-1}$ inside $G_n$ sharing the same top vertex and the same bottom vertex, respectively, and $Q(X), Q(Y)$ to be the respective graphs under $Q$. Note $Q(X), Q(Y)$ only consists of Hamiltonian paths, so they may be seen as some partition of $G_{n-1}$. We calculate to find there are $8(n-1)$ edges and $2n-3$ degree-4 vertices in $G_n/X$, of which no two share an edge. Therefore at least $2(2n-3)$ edges have been removed in $Q(G_n)/Q(X)$, which means the number of edges in $Q(G_n)/Q(X)$ is at most $4n-2$, with equality only if all edges not connected to a degree-4 vertex remains; in particular, $l, r, a, b$ must all remain.
If $Q(X)$ does not have maximal number of edges, then the number of edges in $Q(G_n)$ is at most $2(n-1)^2-(n-1)-1+4n-2 = 2n^2-n$. If $Q(X)$ has the maximal number of edges, then either $a$ or $b$ will have its top-right and right neighbors both connected, so it cannot be connected, which means the number of edges in $Q(G_n)/Q(X)$ is at most $4n-3$, and so the number of edges in $Q(G_n)$ is also at most $2(n-1)^2-(n-1)+4n-3 = 2n^2-n$, completing our proof for the upper bound. Note in both cases maximality are achieved only if $l, r$ and either of $a$ or $b$ are connected. By the same reasoning on $Q(Y)$, maximality is achieved only if $c$ or $d$ are connected, completing our proof for maximality condition.[/hide]

A bit easy for a #3, seeing that I got this during while trying to sleep on a train ride to visit my grandmother (and I normally suck at combo). This is more or less equivalent to MellowMelon's solution, but here's how I phrased it in my head.

We proceed by induction on $n$. The base case $n=1$ is clear, so suppose $n > 1$. Let $A$ denote the set of points
\[ A = \left\{ (x,y) : x + \left\lvert y+\frac12 \right\rvert \ge n - 2  \right\}. \]
An example when $n=4$ is displayed below.
[asy]
	int n = 4;
	for (int a=-4; a<=4; ++a) {
		for (int b=-4; b<=4; ++b) {
			if (abs(a) + abs(b+0.5) < n) {
				if (a + abs(b+0.5) > n-2) dot( (a,b), red+4 );
				else dot( (a,b), black+3 );
			}
		}
	}
	draw((0,3)--(0,2)--(1,2)--(1,1)--(2,1)--(2,0)--(3,0)--(3,-1)--(2,-1)--(2,-2)--(1,-2)--(1,-3)--(0,-3)--(0,-4), red);
[/asy]
For any minimal partition $\mathcal P$ of $S_n$, let $P$ denote the path passing through $(n-1,0)$. Pick $\mathcal P$ such that $\left\lvert P \cap A \right\rvert$ is maximal.  We claim that in this case $P = A$.

Assume not. Starting from $(n-1,0)$, walk along $P$ in any direction until we encounter a vertex $v$ such that $v$ is not adjacent to any vertex in $A$ we have not already seen.  We consider three cases.
[list]
[*] If $v = (0,n-1)$ or $v = (0,-n)$, then this is clearly an endpoint of $P$. In that case $P$ spans all of $A$, as desired.
[*] If $v$ is an endpoint other than that, then let $a$ be the "next" vertex in $A$. By minimality of $\mathcal P$, $a$ must not be an endpoint. Now delete any vertex adjacent to $a$, and add the edge $av$. This increases $\left\lvert P \cap A \right\rvert$ without affecting the number of paths, contradiction.
[*] If $v$ is not an endpoint, again let $a$ be the "next" vertex in $A$. Delete the edge joining $v$ to the vertex not in $A$, and add the edge $va$. We again arrive at a contradiction.[/list]
This forces $A \subseteq P$.  Clearly this implies $P=A$. The remainder of $S_n$ is just $S_{n-1}$, and hence this requires at least $n-1$ paths to cover by the inductive hypothesis.  So $S_n$ requires at least $n$ paths.

Moral of the story: look at maximal things.

There's a very short proof by coloring the points. :)
Let's color the points that $ y \geq 0 $ by coloring the most outside points black and coloring the inside points
to have no white points next to a white point and no black point next to a black point alternatively. :)
And color the points that $ y < 0 $ by doing the same thing above.
Now let's say the number of paths are $ m $ and $ k $ be the number of $ x $ that there exist a path that
goes through the segment $ (x,0),(x,-1) $.
Now let's delete the segments $ (x,0),(x,-1) $. Then, we get total $ m+k $ paths and no path goes through the line
$ y=0 $ and $ y=-1 $. So, the maximum number of black points - white points on each path is at most 1, so the paths on
$ y \geq 0 $ and $ y<0 $ must be at least $ n $. Which means that $ m+k \geq 2n $.
But,we know that $ k \leq n $. So, we get $ m \geq n $. :P

Let $A$ be the point $(0,n-1)$ and take some partition of $S_n$. We will give a series of steps that does not increase the number of paths while shifting the path through $A$ to the rightmost one; i.e. the series of steps $(0,n-1), (0,n-2), (1,n-2), (1,n-3),..., (n-1,0)$.

Let $P$ be the path containing $(0,n-1)$ and suppose that $P$ goes through $(x,n-1-x)$ but not $(x,n-2-x)$ for some $x$. Then deleting the edges out of $(x,n-2-x)$ will add at most one path to the partition. However, now connect $(x+1,n-2-x), (x, n-2-x), (x,n-1-x)$. This connects two paths in the partition, decreasing the size of the partition by one, and thus after this algorithm the size of the partition does not increase.

Now suppose that $P$ goes through $(x, n-2-x)$ but not $(x+1,n-2-x)$ for some $x$. Deleting the edges out of $(x,n-2-x)$; this adds at most one path to the partition. But then by connecting $(x,n-2-x)$ to $(x+1,n-2-x)$ will connect two paths, reducing the size of the partition by one yet again.

By repeating this process, we eventually get a path from $(0,n-1)$ to $(n-1,0)$. Similarly, we can get a path from $(0,-n)$ to $(n-1,-1)$. If $(n-1,-1)$ and $(n-1,0)$ are not connected, then we can simply connect them to decrease the number of paths by one (as those two vertices cannot be connected to any other vertex).

But now we have a path $P$ such that when taken out, the graph $S_{n-1}$ remains. It's easy to check that $S_1$ has needs at least $1$ path in its partition, so by induction it follows that $S_n$ cannot be partitioned into fewer than $n$ parts.

Color the points of (rotated) $S_n$ as follows.
[asy]
int n = 5;
for (int i = -n; i < n; ++i)
for (int j = -n; j < n; ++j) {
if (abs(j) + abs(i+1/2) < n) {
dot((i, j), (abs(2*j) + abs(2*i+1) - 2*n - 1) % 4 == 0 ? red : black);
}}
for (int i = -(n-1); i <= (n-1); i += 2) {
draw((0, i)--(-1, i), dotted);
}
[/asy]
Then there are $2n$ more black points than red ones, and $n$ black-black dotted segments. This is the only information about $S_n$ we will use.

For each path $P$, let $f(P)$ denote $\#(\text{black points on } P) - \#(\text{red points on } P)$ and $g(P)$ denote the number of dotted segments used by $P$.

The main idea is to use the following (obvious) inequality: for any path $P$,
\[g(P) \ge f(P) - 1.\]
Considering $S_n = P_1 \sqcup \dots \sqcup P_k$, summing the above inequality
\[\big(g(P_1) + \dots + g(P_k)\big) \ge \big(f(P_1) + \dots + f(P_k)\big) - k\]
or $g(P_1) + \dots + g(P_k) \ge 2n - k$. But the sum of the $g$'s is at most $n$ (number of dotted segments), so $k \ge n$ as desired.

Induct on $n$, base case $n=1$ trivial. Assume we need at least $n-1$ paths for $S_{n-1}$. Suppose we have a configuration of less than $n$ paths for $S_n$.

[color=#00f][b]Claim:[/color][/b]  There exists a configuration with the same number of paths, one of whose paths is the rightmost [i]double-staircase[/i]: the path that starts at $(0,n-1)$ and ends at $(0,-n)$ sticking to the right edge of $S_n$.

[color=#00f][i]Proof:[/i][/color]  The main idea is to construct the rightmost staircase by rearranging paths to get what we need.

Suppose we have the staircase from $(0,n-1)$ till $A$. Say we need to add horizontal edge $AB$, assuming it doesn't already exist. Rearrange by deleting the next edge coming out of $A$ and instead connecting $AB$; this creates one new path and joins two paths, keeping the total number of paths invariant.
[asy] size(10cm); dot((0,1)); dot((0,2)); dot((1,1)); dot((1,0)); dot((-1,2)); dot((-1,3)); dot((-1,1)); dot((0,0)); dot((-1,0)); dot((2,0)); dot((2,-1)); dot((1,-1)); draw((-1,3)--(-1,2)--(0,2)--(0,1)--(-1,1)--(-1,0),blue); draw((1,1)--(1,0)--(1,-1)--(2,-1),red); label("$\cdots$",(2,-1),E); label("$\vdots$",(-1,0),S); label("$\ddots$",(-1.2,3),NW); label("$A$",(0,1),NE); label("$B$",(1,1),NE);

label("$\longrightarrow$", (4.5,1));

dot((8,1)); dot((8,2)); dot((9,1)); dot((9,0)); dot((7,2)); dot((7,3)); dot((7,1)); dot((8,0)); dot((10,0)); dot((7,0)); dot((10,-1)); dot((9,-1)); draw((7,3)--(7,2)--(8,2)--(8,1)--(9,1),blue); draw((7,1)--(7,0),blue); draw((9,1)--(9,0)--(9,-1)--(10,-1),red); label("$\cdots$",(10,-1),E); label("$\vdots$",(7,0),S); label("$\ddots$",(6.8,3),NW); label("$A$",(8,1),NE); label("$B$",(9,1),NE); [/asy]
The edge containing $B$ in its path must have been vertically below, since we assumed $AB$ is empty initially. So this process also adds the necessary vertical edge after $B$ to continue the staircase. (Alternatively, a similar rearrangement works for getting necessary vertical edges.)

We end this process with the staircase from $(0,n-1)$ to $(n-1,0)$. Similarly, make the staircase from $(0,-n)$ to $(n-1,-1)$. Finally connect the two staircases if they aren't already; this will not increase the number of paths. $\blacksquare$

Now remove the double-staircase and we are left with $S_{n-1}$, which by induction needs at least $n-1$ paths. Adding the one path implies we need at least $n$ paths, contradiction.

[hide=Motivation]The ``rearranging paths'' idea basically pushes the paths along the right edge of $S_n$ by clever rearranging. The main point is that rearranging works well since deleting the double-staircase leaves $S_{n-1}$, and if we can somehow push the remaining paths into $S_{n-1}$ by rearranging, then by induction there must be at most $n-1$. The problem is basically general enough that it [i]gives[/i] us this information, and allows to just focus on pushing/rearranging to create the double-staircase. Related to [b]circular optimization[/b]?
[/hide]
[hide=Remark]I found this similar to USAMO 2017/4, where this [b]local[/b] messing around solution works, but there is also a much nicer global solution (like the one above) which shows really what's going on in the problem.[/hide]

My approach is similar to Cantonmathguy's except expressed less elegantly.

What a magical problem.

Define $T_n$ to be the set of points $(x,y)$ satisfying $n-1<|x|+|y+1/2|<n$, so $S_n=T_n\cup T_{n-1}\cup\cdots \cup T_1$. Observe that any two points in $S_n$ with distance $1$ from each other must be in some $T_i$ and $T_{i-1}$ unless they are the pair $(i,0),(i,-1)$ or $(-i,0),(-i,-1)$. Draw an edge between any two adjacent elements of a path. Then, the total number of edges, $E$, is upper-bounded by
\[2|T_{n-1}|+2|T_{n-3}|+\cdots + \varepsilon\]
where $\varepsilon$ is the sum of the number of pairs of points with distance $1$ away from each other in each of $T_n,T_{n-2},\dots$ because every edge is either counted by $\sum_i 2|T_{n-2i-1}|$ or by $\varepsilon$ and any edge between adjacent elements of some $T_{n-2i-1}$ is counted twice by this sum. Observe that if $n=2k$ then $\varepsilon=2k$ and if $n=2k+1$ then $\varepsilon=2k+1$, so $\varepsilon=n$. Remark that the number of paths is $2n^2-|E|$ because there are $2n^2$ points in $S_n$ so the result follows by viewing $S_n$ as a forest with edges $E$. Hence it suffices to demonstrate
\[n^2-n\ge |T_{n-1}|+|T_{n-3}|+\cdots .\]
Remark that each $T_i$ contains $4i-2$ elements: $2i-1$ with $y\ge 0$ and $2i-1$ with $y<0$. If $n$ is even and equal to $2k$, this sum is
\[\sum_{i=1}^k (4(2i-1)-2)=\sum_{i=1}^k (8i-6)=4(k^2+k)-6k=4k^2-2k=n^2-n.\]
If $n$ is odd and equal to $2k+1$, this sum is
\[\sum_{i=1}^k (4\cdot 2k-2)=4(k^2+k)-2k=4k^2+2k=(2k+1)^2-2k-1=n^2-n.\]
Either way, we are done.

[hide=hint] Use a colouring argument, focusing on the lower and upper halves of the collection of lattice points. [/hide]
[hide=solution]Note that $S_n$ is invariant under reflection in the line $y = - \frac{1}{2}$, as $|y + \frac{1}{2}| = |-y-1 + \frac{1}{2}|$, and the part with $y \geq 0$ has $2n-1-2y$ lattice points at each value where on each successive $y$ value the two outer points are removed.
Now, colour the lattice points with red and blue, where lattice points with an odd/even sum are coloured red and the rest are coloured blue.
Then in the upper half of the figure there are $n$ more (WLOG) red points than blue points, and in the lower half there are $n$ more blue points than red points. Let a [b]lower-path[/b]
be a subsection of a path in one of the partitions which is only in the lower half of the $S_n$, and for which there is no subsection of a path in the same partition such that the subsection is only in the lower half and contains it; let an [b]upper-path[/b] be the equivalent version for the upper half of $S_n$.
Then note that there must be at least $n$ lower paths starting and ending on a blue lattice point, and $n$ upper paths starting and ending on a red lattice point, as a lower/upper path will always contain at most one more of one colour than the other, with equality iff it starts and ends on that colour, as if a path is on one colour, either it moves to a lattice point of the other colour or stops, so since we need that the upper paths in total pass through $n$ more red points than blue points, there must be at least $n$ upper-paths and at least $n$ lower-paths. However, since we want that it is possible to partition $S$ into $n-1$ paths or less, the total number of times a path crosses from the lower section to the upper section across a boundary containing a red lattice point in the upper section and a blue lattice point in the lower section must be at least $n+1$, as if we cross such a boundary $k$ times, then there are at most $n-1+k$ possible upper/lower paths starting and ending on the desired colour, as if a path crosses from the upper section to the lower section then the upper path ends on the point where it crosses, and the lower path starts on that crossing point, so since if we cross any boundary between the upper path and the lower path $k$ times then there are at most $n-1+k$ upper/lower paths, and since only paths starting at the crossing point of the correct colour are counted, the result follows. However, on the boundary between the lower half and the upper half there are only $n$ red lattice points in the upper half, so we are done.[/hide]

Note that $S_n$ can be thought of as the manhattan metric semicircle with radius $n - 1$, reflected across $y = -\frac{1}{2}$.
Note that if we create a path along the sides of the diagonal with length two edges by zigzagging up then down, this allows us to induct to the case of $n - 1$.
It remains to show that any optimal partition into paths contains this edge path.
Note that we can WLOG assume that the length two edges are in the same path by connecting if needed.

[b][color=pink]Claim:[/color][/b] Consider the two points on the border a zig-zag apart. Take an optimal config. It is possile to connect the two points into the same path while not disconnecting any two other border points while remaining optimal, under the assumption that neither point is on the edge.
[i]Proof.[/i] Suppose a partition is optimal and does not have the two points in the same path.
Consider the common neighbor of both of them. We can disconnect this common neighbor from neighbor paths and connect them to the two points. If this point connects either to one of the two points or only once, it can be seen that the number of paths is preserved.
Else, this breaks a path through the common neighbor point with its other two neighbors. However, this can just be repeated by connecting those two neighbors with their other common neighbor point until this is finished. $\blacksquare$
In the case of one of the point being a corner, this could break the corner point connecting to another point.
Then, we can repeat this to connect all the zig-zags on the edge. This then must be the edge path, so we induct downward and finish.

Even though this problem doesn't look that interesting, someone dropped me a [hide=word]"coloring"[/hide], and this immediately became one of my favorite problems.

Color the points in the region black and white such that the points around the outer rim are black, and except for $n$ vertical segments in the middle two rows, every black point only borders white points.

The argument here becomes clear: consider taking paths away from the region, and look at $\Delta$, the difference between the number of black and white points. Originally, $\Delta = 2n$.

For some path $P$, denote by $f(P)$ the number of vertical black segments in $P$. For $g(P)$ the change in $\Delta$ after removing $P$, we have $g(P) \leq f(P) + 1$. Suppose we have a partition into $k$ paths; then, $$2n = \sum_{i=1}^k g(P_i) \leq \sum_{i=1}^k f(P_i) + k = n+k.$$ Therefore $k \geq n$.

Does this work? I feel like i phrased it differently

    The idea is to induct down, base case n=1 trivial. Now look locally: In the diagram, we can change the paths slightly to not make more paths, but have the path stay along the right staircase.  and um oops i understnad that the graph is not correct, jstu ingnore the rightmost and leftmost two corners. so basically since this does not change \# of paths, you can keep perturbing that it stays in shape of staircase. so now indicuct down to at least n-1.

Welp I'm not very good at combo (this took a while)

Label the topmost point $A_1$ and the bottommost point $A_{4n-2}$. Traveling along the [i]left edge[/i] of $S_n$, label the $i$th point from the top $A_i$.

The idea is to [b]split and merge[/b] paths while not increasing the number of paths to obtain a path $A_1\to A_2\to \dots\to A_{4n-2}$. This will complete the question by induction (the base case of $n=1$ is easy).

Turns out it's not very difficult to do so. Assume that we currently have a path $A_1\to A_2\to \dots \to A_k \to B_1\to B_2\to \dots \to B_{\ell}$ where $B_1\neq A_{k+1}$. The goal is to show we can modify the paths to have $B_1=A_{k+1}$. In particular, it's possible to have $A_{k+1}\in \{B_2,B_3,\dots,B_{\ell}\}$.
[list]
[*] When $k$ is odd, then $\ell=0$. This is trivial as the only location for $B_1$ otherwise is the point $A_{k+1}$. Now split a path so that $A_{k+1}$ is an endpoint. This increases the path count by at most $1$. Evidently $A_{k+1}$ is not a part of our current path ($\ell=0$) hence we can merge $A_k\to A_{k+1}$ and decrease the path count by $1$. This is fine.
[*] When $k$ is even, then $A_{k+1}$ is an endpoint of its path. Now if $B_{\ell}=A_{k+1}$, it turns out that removing $A_k\to B_1$ and replacing with $A_k\to B_{\ell}=A_{k+1}$ suffices.

Otherwise $A_{k+1}$ is not part of our current path, hence remove the edge $A_k\to B_1$. The path count has increased by at most $1$, and now $A_k$ and $A_{k+1}$ are endpoints of their own (distinct) paths. So merge these, decreasing the path count by $1$.
[/list]
All cases are exhausted, done!

Actually, we need to handle the case where $A_k$ is at the middle of $S_n$. Luckily, the same concepts work.

Color the points on or above the $x$-axis black and white in a checkerboard pattern, and separately color the points below the $x$-axis black and white in a checkerboard pattern, such that both of the leftmost points in $S$ are white. Cut each path at any point where it has two consecutive white points. There are only $n$ pairs of consecutive white points, so the number of paths increases by at most $n$. The final number of paths is at least $2n$, because there are $2n$ more white than black points, and each path has at most one more white than black point on it. This finishes the proof.


calculus
topology
probability
geometry
derivative
linear algebra

No, not even close. I never did that, even when I was a "rookie."

All right, I can only speak for myself. There are a few other professors around here - any of them who have different takes on this are welcome to reply.

The exercises are designed for people who don't already know calculus, or linear algebra - they're there as a guide to understanding, and as a means to practice certain skills. I already know calculus, and I already know linear algebra; I don't need the reinforcement. I will usually read through the text and see what arguments are made (although I don't always do that with calculus books - I just assume that certain things are there, and that sometimes gets me in trouble.)

I see my role in class as providing organization, structure, insight. It's not going over every detail, every method, every problem type, because there's no structure in that. I'm not going to repeat exactly what was in the book; rather I'll try for a variation of the idea that might reach people who didn't follow the book's version. But there are others who might find that the book speaks to them more clearly than I do. I've taught courses directly from notes I wrote myself, with no other textbook - and even there, I find that I can't do an in-class presentation exactly the way it was in the notes, even though I wrote the notes myself.

It was a little different when I taught for the first time a subject in which I had less background: numerical analysis, for instance. In that case, I paid rather more attention to the textbook, and probably did do a few sample problems as I prepared (but that's a few problems, a small minority.) Even there, understand that I wasn't reading the textbook as a first-time student would but as a mathematician - looking for the big themes and the major structures. (By the way, numerical analysis is a logical subject with lots of nice mathematics - mostly calculus - in it; it just makes sense, and that helps someone like me.)

One of the raging debates in teacher preparation is just how far beyond the particular subject being taught a teacher should be. In order to teach high school Algebra I, does one really need to know about homomorphisms of groups and how to construct $\epsilon$-$\delta$ analysis proofs? Does it really take a Ph.D. in mathematics to teach Linear Algebra or Differential Equations? I'm not really going to argue those things one way or another here, but some of what I've been saying above suggests what all of that excess training might really be good for.

Lets say a professor specializes in algebraic topology, for example, and needs to teach an advanced probabiliy course/quantitative finance. Is it ever the case that the professor has to learn topics that he didnt study at an advanced level (such as probability theory) in a short amount of time? Or take the case of an applied mathematician teaching knot theory and topology. Would is then be more reasonable for the professor to do all of the difficult problems? Also, do you think it would be more efficient to have students read and understand all of the math concepts first, and then do the exercises later (i.e. the top down approach of actively reading a linear algebra book from beginning to end, and then doing selected problems afterwards)?

Or even consider a case when a math professor has to teach an introductory mechanics course (if this was to ever happen). Would he find it easy?

I'm not sure at all, but I think the top universities have big enough faculties that the above described scenarios should never happen. ie, a professor teaching something he doesn't really want to/is really uncomfortable with

I think at lots of universities there are professors who teach lower-level courses in areas that are not their specialties, but whether or not that means the lower-level courses are not well presented is a different issue.

[quote="ragingbullrocky"]If a professor teaches a course (say Calculus or Linear Algebra) does he do all the problems in the book to prepare? Is this generally the case with young professors?[/quote]

Absolutely not.  I have not ever even heard of such a thing, or even the suggestion that such a thing is a good idea.  Most profs do not even work out the *assigned* book problems before assigning them.

For a course such as calculus or linear algebra, the prof typically knows how to do nearly every problem soon after he reads it, assuming that he or she has prepared for the lectures.  There's little value in actually working out the problems.  Most of the valuable prep time goes into preparing the lectures.

Your question about higher level courses is very different.  Typically, departments try to assign profs to classes that are related to their fields of specialization, but this is not always possible.  There's still little harm, though.  Any competent math PhD should be *able* (though possibly unwilling) to teach a wide variety of courses in the undergraduate curriculum.  When the prof is not expert in the material, this usually just means that you'll get a more standard textbook treatment of the subject, without an advanced perspective.  (This is consistent with Merryfield's post.)  Your example of the topologist teaching finance is a bit far-fetched, but less extreme scenarios do play out, and even your scenario could happen if the topologist actually wanted to teach the finance class.  Also, I can't imagine a scenario in which a prof might say, "I really do not feel comfortable teaching this class," and still be forced to teach it.

To take a personal example, the first class I had to teach was a differential equations course for engineers.  I had to teach Laplace transforms, despite literally never having computed a Laplace transform in my life.  It made no difference to me, and I taught it just as I taught more familiar subjects.  I'm sure my students had no idea that it was new to me.

wow, goes to show you that basically after one obtain a PhD say in math, that the overall experience has prepared him to learn just about any subject on the fly. How did you ever manage to teach laplace transforms, when you yourself did not know it? Did you take the book, and like absorb all the material in say a week?

[b] Would you be able to teach introductory mechanics, or quantum mechanics, just as you taught laplace transforms (i.e. learn enough of the material to teach it)? [/b]

[quote="ragingbullrocky"]Lets say a professor specializes in algebraic topology, for example, and needs to teach an advanced probabiliy course/quantitative finance. Is it ever the case that the professor has to learn topics that he didnt study at an advanced level (such as probability theory) in a short amount of time?...[/quote]
Sometimes, especially when I teach a graduate course, I, indeed, need to learn new things myself before I go and teach them. Then I work through a book (or books) like any student would do with solving exercises, etc. But it never happens "in a short amount of time" because, under normal circumstances, the teaching assignments are known at least half a year in advance and half a year is a sufficient time to prepare for virtually any course. After all, the students are assumed to absorb the material within the same half a year time frame so if you cannot get it yourself in this time, what can you expect of them? The general rule is that you can expect an average student to spend one hour on a material/problem that takes you ten minutes (some people will argue that "ten" here should be replaced by "five" or "fifteen", but that's not the point). The only other time I attempt to solve problems from the textbook is when I assign extra credit exercises. Then I want to be sure that the level of difficulty is exactly right, so often I even look for several possible solutions and make guesses about how many students would choose this or that way to approach the question. As to the regular problems I assign, I just look at them and try to get a general feeling of what they might be about. If the answers are available, I also occasionally check that they are not too ugly, but that is it.

[quote]It is important that one does not over prepare for a lecture. Generally, one should arrive at class a few minutes early, open the book, and glance at the topics to be covered that day.   Lectures prepared in this manner have a certain freshness and spontaneity that is often missing in carefully prepared lectures.   In addition, students will gain a greater appreciation for a correct proof if they see how much time can be spent on a wrong approach.[/quote]
From [url=http://www.pen.k12.va.us/Div/Winchester/jhhs/math/humor/guide.html]A Guide For Teaching Mathematics[/url]

Funnily enough, when I did exactly this teaching a business calculus class, my students were far happier than when I spent half an hour preparing my lectures for the same course. The reason was that when I prepared for the lectures, I tended to go quite a bit beyond the scope of the book and do things the way I thought appropriate, after which the poor students could not understand why $(fg)'=f'g+fg'$ is just a partial case of $\left(\frac{fg}h\right)'=\frac{fg}h\left[\frac{f'}f+\frac{g'}g-\frac{h'}h\right]$. Another example of such overpreparedness was my attempt to teach the students what it means to understand a concept of, say, range of a function. The question I asked them was: "If you know nothing but the range of $f$, what can you say about $f$". The answer I expected was "we can tell whether $f$ attains its maximum" or something in the same spirit. Needless to say, I got a dead silence instead. An attempt to throw in a few proofs and ask my students common sense questions like "All boogles are woogles and some woogles are coogles; can we conclude that some coogles are boogles?" finished the story. On the other hand, when I came to the class, opened the book, and cheerfully said with genuine amazement: "Ah, we have the product rule today!" and went on doing 10 virtually identical examples and repeating three times that "the derivative of the product is not the product of the derivatives", everybody was happy. So, at least sometimes, it is, indeed, VERY important not to overprepare for a lecture :P.

My teaching style is such that I work very closely with the text I select, and so I tend to work a lot of problems from these texts myself.  However, what it means for me to work a problem varies substantially from text to text and even from problem to problem---90% of the time or more, I look at problems in calc/linalg/absalg and do them in my head within seconds.  Some upper-level classes I teach focus on discussion of problems and the text, and for those I tend to leave myself notes about how to do the harder problems.  This semester I'm teaching a seminar out of a very concise text, and I spend a couple of hours on some of the problems because I just find them interesting.


The $ 24^\text{th}$ day of a particular month is a Saturday. On what day of the week was the first day of that month?

If the $ 24^\text{th}$ day is Saturday, than the $ 22^\text{nd}$ day is Thursday, and since $ 22$ is a multiple of $ 7$, plus $ 1$, the $ 22^\text{nd}$ day of any month falls on the same day of the week as the $ 1^\text{st}$ day of the same month, and thus, the first day of that month was a $ \fbox{\text{Thursday}}$.


For $ x,y,z \in \mathbb{R^\plus{}}$ and $ x\plus{}y\plus{}z\equal{}1$ .
Prove that  $ 7(xy \plus{} yz \plus{} xz) \leq 2 \plus{} 9xyz$

[hide="Solution"]First we homogeniolize it,

$ 7(x \plus{} y \plus{} z)(xy \plus{} yz \plus{} xz) \leq 2(x \plus{} y \plus{} z)^3 \plus{} 9xyz$

$ 7( \sum_{sym} x^2y \plus{} 3xyz) \leq 2( \sum_{cyc} x^3 \plus{} 3 \sum_{sym} x^2y \plus{} 6xyz) \plus{} 9xyz$

$ 7 \sum_{sym} x^2y \plus{} 21xyz \leq \sum_{sym} x^3 \plus{} 6 \sum_{sym} x^2y \plus{} 21xyz$

$ \sum_{sym} x^2y \leq \sum_{sym} x^3$

Which is true by Muirhead ((2,1,0) vs (3,0,0)) so we are done.[/hide]

[quote="rajelaz"]For $ x,y,z \in \mathbb{R^ \plus{} }$ and $ x \plus{} y \plus{} z \equal{} 1$ .
Prove that  $ 7(xy \plus{} yz \plus{} xz) \leq 2 \plus{} 9xyz$[/quote]
\[ 7(xy \plus{} yz \plus{} xz) \leq 2 \plus{} 9xyz\]
\[ \Longleftrightarrow 7(xy \plus{} yz \plus{} xz)(x\plus{}y\plus{}z) \leq 2(x\plus{}y\plus{}z)^3 \plus{} 9xyz\]
\[ \Longleftrightarrow 2(x^3\plus{}y^3\plus{}z^3) \ge xy(x\plus{}y)\plus{}yz(y\plus{}z)\plus{}zx(z\plus{}x)\]
\[ \Longleftrightarrow \sum{(x\plus{}y)(x\minus{}y)^2} \ge 0.\]

[quote="kuing"].........
\[ \Longleftrightarrow 2(x^3 \plus{} y^3 \plus{} z^3) \ge xy(x \plus{} y) \plus{} yz(y \plus{} z) \plus{} zx(z \plus{} x)\]

\[ \Longleftrightarrow \sum{(x \plus{} y)(x \minus{} y)^2} \ge 0.\]
[/quote]
\[ 2(x^3 \plus{} y^3 \plus{} z^3) \ge xy(x \plus{} y) \plus{} yz(y \plus{} z) \plus{} zx(z \plus{} x)\]
also follows from Schur's ineq of 3rd degree, because from Schur:
$ \sum x^3 \plus{} 3xyz\geq \sum xy(x \plus{} y)$
And $ 3xyz\leq x^3 \plus{} y^3 \plus{} z^3$ from AM-GM.  :)


Besides discrete and graph theory, can anyone name some mathematic branches that is useful for a graduate student in computer science ?

Graph theory is really a part of discrete math but anyway, in my opinion, almost all the math has some use in computer science. Other math branches that we learn at university (CS major) are analysis and algebra - I'm sorry if that's not what they're called in English - and people running our university probably know what they're doing (I hope :) ) so you're most likely going to need those.

In fact I think all topics of mathematics help computer scientist.
But most useful math is,,

algebra including

modula algebra (crypt)
linear algebra (data structure)

and etc,

I think.

~~;

Now a days lattice theory and its companion FCA (Formal Concept Analysis) playing a vital role in Computers filed especially in Data Mining, Knowledge acquitization etc..,


ratio
geometry
rectangle
analytic geometry
graphing lines
slope
function

The given set of data , $ (x_{1},y_{1}),(x_{2},y_{2}),(x_{3},y_{3})...$ , I can get the Least-Squares line by using $ y \equal{} a\plus{}bx$ .

Now ,  the set of data is $ (1,1,7), (2,1,8), (3,2,3), (4,3,2)$ , Should I use  $ y \equal{} a \plus{} bx \plus{} cz \  \   or   \  \ z \equal{} a \plus{} bx \plus{} cy$  to get the Least-Squares line ?

when $ y \equal{} a \plus{} bx \plus{} cz$ , I get $ y \equal{} \frac{5}{3}\plus{}\frac{11}{30}x\minus{}\frac{1}{6}z$
when $ z \equal{} a \plus{} bx \plus{} cy$ , I get $ z\equal{}10\plus{}\frac{1}{3}x\minus{}\frac{10}{3}y$

Why different ? And is this correct ?

Least-squares regression analysis applied to fitting a plane to a set of 3-d points is so very counter-intuitively more complicated than the 2-d version fitting a line to a set of 2-d points.  I wrote a psych term paper on it (math major)... if you have Maple, you can play with the attached .mws or .mw files (same content, different maple worksheet versions). Otherwise, see the attached PDF, a print-to-PDF version of the Maple worksheet (can't play with it, but it's something).

Getting back to the original question:

Very importantly: those are not lines. Those are the equations of planes. (As benorin said.)

Next: in regression, you say that one variable (call it the dependent variable) depends, imperfectly, on certain other variables. If you change the identity of what you consider a dependent variable and what you consider an independent variable, you get a different line/plane/whatever. Always. Or at least, always unless there's perfect correlation, and in the real world, when is there ever perfect correlation?

Let's go back to a two dimensional example: we have a collection of points $ (x_i,y_i).$ They don't even have to be points - they can be any joint distribution. We calculate the following quantities:

$ \overline{x} \equal{} \frac1n\sum x_i.$

$ \overline{y} \equal{} \frac1n\sum y_i.$

$ \sigma_x \equal{} \sqrt {\overline{x^2} \minus{} \overline{x}^2},$ where $ \overline{x^2} \equal{} \frac1n\sum x_i^2.$

$ \sigma_y \equal{} \sqrt {\overline{y^2} \minus{} \overline{y}^2}.$

$ \text{Cov}(x,y) \equal{} \frac1n\sum x_iy_i \minus{} \overline{x}\,\overline{y}.$

$ \rho \equal{} \frac {\text{Cov}(x,y)}{\sigma_x\sigma_y}.$ This is the [b]correlation coefficient.[/b]

For the sake of the argument, suppose $ (\overline{x},\overline{y}) \equal{} (5,3),$ $ \sigma_x \equal{} 2,$ $ \sigma_y \equal{} 1,$ and $ \rho \equal{} .7.$

The point $ (5,3)$ is the center of mass of the entire two-dimensional distribution. All of the lines we care about will go through the center of mass.

Note that there's no reason to assume that $ x$ and $ y$ have the same units of measurement; they're probably just completely different things, like time and distance. Hence, on an $ x,y$ plane, angle-geometric notions like "a $ 45^{\circ}$ line" don't even make sense - at least not without some standard measuring stick. That's what $ \sigma_x$ and $ \sigma_y$ are - standard measuring sticks for the two variables. If I were to make new graph paper for this, I'd draw the lines $ x \equal{} 5$ and $ y \equal{} 3$ that go through the center of mass and then I would mark off from there vertical lines every two units (because $ \sigma_x \equal{} 2$) and horizontal lines every one unit (because $ \sigma_y \equal{} 1.$) The nicest way then to draw the graph would be to choose the aspect ratio in such a way that the rectangles of the grid I just drew appear as squares. In that aspect ratio, if there are many, well-distributed points, the points will appear as an elliptical cloud. The crossing $ 45^{\circ}$ lines in this aspect ratio would then be the major and minor axes of that elliptical cloud.

So I'm singling out the line $ \frac {y \minus{} 3}1 \equal{} \frac {x \minus{} 5}2,$ or perhaps $ \frac {y \minus{} 3}1 \equal{} \minus{} \frac {x \minus{} 5}2.$ In the original coordinates, these are lines of slope $ \pm .5.$ But these are not regression lines. They're "standard lines in the standard measurement grid."

If we now say that we want to find the least squares regression line for $ y$ considered as a function of $ x,$ then we get something that is shallower than the line I just mentioned, shallower by the proportion of the correlation coefficient. That is, the regression line for $ y$ in terms of $ x$ is $ \frac {y \minus{} 3}1 \equal{} .7\left(\frac {x \minus{} 5}{2}\right),$ a line of slope $ .35.$

On the other hand, if we reverse that and ask for the least squares line for $ x$ in terms of $ y,$ we get a steeper line. We get $ \frac {x \minus{} 5}2 \equal{} .7\left(\frac {y \minus{} 3}1\right)$, which is a line of slope $ \frac {.5}{.7}\approxeq .714.$

The two regression lines are not equal. The line for $ y$ considered as a function of $ x$ is always flatter than the standard line, and the line for $ x$ considered as a function of $ y$ is always steeper then the standard line. Always, unless we have perfect correlation. Perfect correlation means $ \rho \equal{} 1$ or $ \rho \equal{} \minus{} 1,$ in which case all the points lie perfectly on a line.

The opposite extreme would be zero correlation - in my square aspect ratio graph, the elliptical cloud of points iwould become a circle. In this case, with $ \rho \equal{} 0,$ the least squares line for $ y$ in terms of $ x$ is horizontal, and the least squares line for $ x$ in terms of $ y$ is vertical.

Actually, my question is from the exercise of one book .There is one answer in this book ,see below, but there is no explanation about how to get it.

$ y\equal{}\frac{3}{2}x\minus{}\frac{3}{2}$

Could someone point how to get the answer out ? Is this a correct answer ?

That doesn't make a lot of sense - why are the data ordered triples when the question asks for just $ x$ and $ y?$ If you treat the third coordinate as irrelevant and just take the data as the points $ (1,1),(2,1),(3,2),(4,3)$ then I get the regression line $ y\equal{}.7x\plus{}0,$ or if you reversed the regression, $ x\equal{}\frac{14}{11}y\plus{}\frac{3}{11},$ neither of which match what you just said. Other possible interpretations look even further away.

I think you haven't told us everything.

I have to make a contrite apology for my huge mistake. :blush:
The given set of data from the book should  be $ (1,1.7),(2,1.8),(3,2.3),(4,3.2)$ , not $ (1,1,7),(2,1,8),(3,2,3),(4,3,2)$ and now I can get the Least-Squares line by using $ y\equal{}a\plus{}bx .$
My answer to the question is  $ y\equal{}1\plus{}\frac{1}{2}x$ . I hope this is a correct answer and I think I need to check my eyesight.   :D

Yes, regression line $ y\equal{}.5x\plus{}1,$ with $ \rho\equal{}.9416.$

Reverse regression $ x\equal{}1.773y\minus{}1.489,$ approximately.


[quote="orangefronted"]Find all ordered nonnegative intger triples (x,y, z) such that x >= y >= z and x^2 + y^2-2z^2 = 8.[/quote]
- - - Incomplete - - -

A couple of solutions:
[hide]
Note:  The work for the cases is not shown, but it needs
to be to support/justify them.

Three variables or two variables equal to zero:

No solutions for this

-------------------------------------------------------

$ z \equal{} 0$:

$ (2,2,0)$

--------------------------------------------------------

$ x \equal{} y$ and $ z$ is different from them:

No solutions for this

---------------------------------------------------------

$ y \equal{} z$ and $ x$ is different from them:

$ (3,1,1)$

----------------------------------------------------------

Only $ x \equal{} 0$:

No solutions for $ y$ and $ z$, because of the size restrictions

------------------------------------------------------------

Only $ y \equal{} 0$:

No solutions for $ z$ because of the size restrictions, so there
are no solutions here.

------------------------------------------------------------

$ x > y > z$:

*** This case has not been worked out/analyzed by me yet.

[/hide]

[hide="hopefully complete set:"]We must have $ x^2\plus{}y^2\equal{}2z^2\plus{}8$.  Now to make the right side even, $ x$ and $ y$ must be of the same parity, so we can write $ x\equal{}m\plus{}n$ and $ y\equal{}m\minus{}n$ for some nonnegative integers $ m\geq n$.  This transforms the equation into $ m^2\plus{}n^2\equal{}z^2\plus{}2^2$.

We recall the identity $ (ac\plus{}bd)^2\plus{}(bc\minus{}ad)^2\equal{}(ac\minus{}bd)^2\plus{}(bc\plus{}ad)^2$.  There are three mappings we can do to preserve the equality but flip the signs of either $ a, b, c, d$ or the numbers inside the squares.  We can take the absolute value of $ a, b, c, d$.  We can switch $ a$ and $ c$, and switch $ b$ and $ d$ at the same time.  Finally, we can switch $ c$ and $ d$.  The first switch makes sure all $ a, b, c, d$ are nonnegative.  The second makes sure that either $ (bc\minus{}ad)$ and $ (ac\minus{}bd)$ are both negative or both nonnegative.  The final switch makes sure $ (bc\minus{}ad)$ and $ (ac\minus{}bd)$ are nonnegative.  So assume that $ a, b, c, d, bc\minus{}ad, ac\minus{}bd\geq 0$.

Let $ 2\equal{}bc\plus{}ad$.  Then either $ b$ or $ c$ is 0 and $ ad\equal{}2$, or $ b\equal{}c\equal{}a\equal{}d\equal{}1$.  The first case gives $ 2^2\plus{}k^2\equal{}k^2\plus{}2^2$, so $ (x, y, z)\equal{}(k\plus{}2, |k\minus{}2|, k)$ or $ (x, y, z)\equal{}(3, 1, 1), (2, 2, 0)$.  Other $ k$ don't work because $ z>y$.  The second case gives $ 2^2\plus{}0^2\equal{}2^2\plus{}0^2$, giving $ (x, y, z)\equal{}(2, 2, 0)$.

Let $ 2\equal{}ac\minus{}bd$.  Then we need to find when $ y\geq z\Rightarrow (ac\plus{}bd)\minus{}(bc\minus{}ad)\geq bc\plus{}ad$ or $ ac\plus{}bd\equal{}2\plus{}2bd\geq 2bc$, meaning that $ 1\plus{}bd\geq bc$, or $ (d\minus{}c)b\geq \minus{}1$.  Then either $ d\minus{}c\geq 0 (1)$ or $ c\minus{}d\equal{}b\equal{}1$.  If $ c\minus{}d\equal{}b\equal{}1$, then $ 2\equal{}a(d\plus{}1)\minus{}d\equal{}ad\plus{}a\minus{}d$ so $ 1\equal{}(a\minus{}1)(d\plus{}1)$, so $ (a, b, c, d)\equal{}(2, 1, 1, 0)$ and $ (x, y, z)\equal{}(3, 1, 1)$.

Now back to $ (1)$.  We have $ d\geq c$.  Then $ (a\minus{}b)d\equal{}bd\minus{}ad\geq ac\minus{}bd\equal{}2$ so $ a\geq b$.  But then $ ad\geq ac\geq bc$ so $ bc\minus{}ad\leq 0$.  Thus equality must hold, and $ a\equal{}b$ and $ c\equal{}d$ so $ ac\minus{}bd\equal{}ac\minus{}ac\equal{}0$, impossible.  Hence the only solutions are $ (x, y, z)\equal{}(3, 1, 1), (2, 2, 0)$.[/hide]

[quote="Arrange your tan"]
$ x > y > z$:[/quote]

A quick finish is to take $ 8 \equal{} x^2 \plus{} y^2 \minus{} 2z^2 \ge (z \plus{} 2)^2 \plus{} (z \plus{} 1)^2 \minus{} 2z^2 \equal{} 6z \plus{} 5 > 8$ for $ z > 0$. Sorry, tenniskidperson3  :wink:

edit; a complete solution would be, as $ x > z$, $ 8 \equal{} x^2 \plus{} y^2 \minus{} 2z^2 \ge (z\plus{}1)^2 \plus{} z^2 \minus{} 2z^2 \equal{} 2z\plus{}1 \Longrightarrow z \le 3,$ and $ x^2 \plus{} y^2 \equal{} 8\plus{}2z^2 \in \{8,10,16,26\}$; a couple cases then finishes.


Does there exist a non-constant function $ f: \mathbb{N}^2\rightarrow \mathbb{N}$ such that

$ f(x,y)\plus{}f(y,x)\equal{}f(x^2,y^2)\plus{}1$,

for all $ x,y\in \mathbb N$?

Yes. For example $ f(x,y)\equal{}1$ if $ x$ or $ y$ is not power of 2. We can define $ f(2^k,2^m)\equal{}g(k,m), k\ge 0,m\ge 0$, suth that $ g(2k,2m)\equal{}2g(k,m)\minus{}1\equal{}2g(m,k)\minus{}1$.


abstract algebra
group theory
superior algebra
superior algebra unsolved

let $ (G,.)$ be a  not cyclic group and $ |G| \equal{} 12$ and we suppose that there exist $ a \in G$ such that $ o(a) \equal{} 6$ and let $ H \equal{} < a >$ and $ b \in G \minus{} H .$
1)prove that $ G \equal{}${$ e,a,a^2,a^3,a^4,a^5,b,ab,a^2b,a^3b,a^4b,a^5b$}.
2)prove that $ bab^{ \minus{} 1}  \in H$ and prove  that there exixt $ j \in${$ 1,2,3,4,5$} such as $ bab^{ \minus{} 1} \equal{}a^j$ and $ b^2 \in${$ e,a^2,a^4$}.
3)prove that $ j \equal{} 1$ or $ 5$.
4) and  if $ j \equal{} 1$ then $ G$ is an abelian group and there exist $ x \in G \minus{} H$ such that $ o(x) \equal{} 2$.

[quote="pleurestique"]in 2), what is $ j$ supposed to do?[/quote]
sorry, I correct it :)


i know it might seem kinda stupid, but i really don't get this one. i set up proportions, (kinda)... but i got it wrong. i was almost sure i got it right...

EDIT:sry, i forgot to post the problem... cam one someone delete this thread, please? :blush:

I'll try and post the problem as best as I can remember.

Workers in a factory produce Whoosits and Widgets. Each worker produces each toy at the same rate, and all workers are identical, but the time necessary to make each product is not necessarily the same.

In one hour, 100 workers can produce 300 widgets and 200 whoosits. In two hours, 60 workers can produce 240 widgets and 300 whoosits. In three hours, 50 workers can produce 150 widgets and m whoosits. Find M.

[hide="Solution"]
Put everything into worker-hours.
Let widgets = A, whoosits = B.
$100 \text{wh}= 300A+200B$
$120 \text{wh}= 240A+300B$
---------------------------
$150 \text{wh}= 150A+xB$

Solve for constants A and B in the first two equations.
Eventually, you get A = 1/7, B = 2/7.
Plug in these constants to the lower equation:
$150 \text{wh}= 150 \cdot \frac{1}{7}+\frac{2x}{7}$
From here, multiply both sides by seven, solve for X:
$1050 \text{wh}= 150+2x$
$900 \text{wh}= 2x$
$x = \boxed{450}\text{whoosits}$
[/hide]

I took the tope eqn and multiplied by 3/2 and the bottom one by 5/4 and just found the relationship of widgets to whoosits. Not bad at all.


Let a,b,c,d,x,y,z,w be a positive real numbers
prove that $ ((a\plus{}b)(c\plus{}d)\plus{}(x\plus{}y)(z\plus{}w))^\frac{1}{2}
  \ge (ac\plus{}xz)^\frac{1}{2}
\plus{}(bd\plus{}yw)^\frac{1}{2}$

[quote="csbonny"]Let a,b,c,d,x,y,z,w be a positive real numbers
prove that $ ((a \plus{} b)(c \plus{} d) \plus{} (x \plus{} y)(z \plus{} w))^\frac {1}{2} \ge (ac \plus{} xz)^\frac {1}{2} \plus{} (bd \plus{} yw)^\frac {1}{2}$[/quote]
It's wrong. Let $ (a,b,c,d)\equal{}(x,y,z,w)\equal{}(1,2,3,4)$.


For $0 \leq d \leq 9$, we define the numbers \[S_{d}=1+d+d^{2}+\cdots+d^{2006}\]Find the last digit of the number \[S_{0}+S_{1}+\cdots+S_{9}.\]

[quote="skimnc"]There is probably a way better way to do this but I felt like trying it.

[hide]$S_{d}=\sum_{n=0}^{2006}d^{n}= \frac{1 \cdot (1-d^{2006})}{1-d}=\frac{d^{2006}-1}{d-1}$

$S_{0}=1 \Rightarrow$ Last digit is $1$
$S_{1}=1+2006 \cdot 1=2007 \Rightarrow$ Last digit is $7$
$S_{2}=2^{2006}-1 \Rightarrow$ Last digit is $3$

[hide]Note that:
$2^{1}-1=1$; Last digit is $1$.
$2^{2}-1=3$; Last digit is $3$.
$2^{3}-1=7$; Last digit is $7$.
$2^{4}-1=15$; Last digit is $5$.
$2^{5}-1=31$; Last digit is $1$.
$2^{6}-1=63$; Last digit is $3$.
$2^{7}-1=127$; Last digit is $7$.
$2^{8}-1=255$; Last digit is $5$.
$2^{9}-1=511$; Last digit is $1$.
$\ldots$
$2^{2004}-1 \Rightarrow$; Last digit is $5$.
$2^{2005}-1 \Rightarrow$; Last digit is $1$.
$2^{2006}-1 \Rightarrow$; Last digit is $3$.

So the $2^{2006}-1$ will have a last term of $3$.[/hide]

$S_{3}=\frac{3^{2006}-1}{3-1}=\frac{3^{2006}-1}{2}\Rightarrow$ Last digit is $4$.

[hide]Note that:
$\frac{3^{1}-1}{2}=1$; Last digit is $1$.
$\frac{3^{2}-1}{2}=4$; Last digit is $4$.
$\frac{3^{3}-1}{2}=13$; Last digit is $3$.
$\frac{3^{4}-1}{2}=40$; Last digit is $0$.
$\frac{3^{5}-1}{2}=121$; Last digit is $1$.
$\frac{3^{6}-1}{2}=364$; Last digit is $4$.
$\frac{3^{7}-1}{2}=1093$; Last digit is $3$.
$\frac{3^{8}-1}{2}=3280$; Last digit is $0$.
$\frac{3^{9}-1}{2}=9841$; Last digit is $1$.
$\ldots$
$\frac{3^{2004}-1}{2}\Rightarrow$; Last digit is $0$.
$\frac{3^{2005}-1}{2}\Rightarrow$; Last digit is $1$.
$\frac{3^{2006}-1}{2}\Rightarrow$; Last digit is $4$.[/hide]

We can continue to note that the last digit of $S_{d}$ will always be the same last digit of $\frac{d^{2}-1}{d-1}$ aka it will be $d+1$ with the exception of $d=1,6$ in which case it is $\frac{d^{1}-1}{d-1}=1$

$S_{0}\Rightarrow 1$
$S_{1}\Rightarrow 7$
$S_{2}\Rightarrow 3$
$S_{3}\Rightarrow 4$
$S_{4}\Rightarrow 5$
$S_{5}\Rightarrow 6$
$S_{6}\Rightarrow 1$
$S_{7}\Rightarrow 8$
$S_{8}\Rightarrow 9$
$S_{9}\Rightarrow 0$

$1+7+3+4+5+6+1+8+9+0=44 \Rightarrow$ Last digit is $\boxed{4}$.[/hide][/quote]
my solution is the same as you but i dont think it's the best way :D
could anybody have another idea ?  :)

I see why $1$ doesn't work out to be $d+1$ but why doesn't $6$?  I noticed the pattern was it repeated every $5$ numbers but I have no clue as to why $6$ randomly decides to not work.

I originally only carried the sum formula out to $r^{n}$ when it should of been $r^{n+1}$..  I edited it.

[quote="Farenhajt"]Or we can sum the thing by the columns instead of rows:

Ten ones give $10$, ten first powers give $45$, ten squares give $0+1+4+9+6+5+6+9+4+1=45$, ten cubes give $45$, ten fourth powers give $0+1+6+1+6+5+6+1+6+1=33$. From fifth power on, the cycle repeats. Hence we have $10+501\cdot(45+45+45+33)+45+45\equiv 8\pmod{10}$[/quote]
I am agree with you. Also doing the same and i think it is the easiest way to calculate. Thanks


modular arithmetic
linear algebra
matrix

Let $ a_{1}, a_{2}, \ldots, a_{n}$ be $ n$ natural numbers satisfying $ a_{i}\leq i$ for each $ i \in \overline{1,n}$. Prove that if $ \sum_{i=1}^{n}a_{i}$ is even, then one of the expressions of the form $ \pm a_{1}\pm a_{2}\pm \ldots \pm a_{n}$ is equal to $ 0$.

It's a classic, but I don't think it can be called [b]very easy[/b].

I would have expected a little more enthusiasm!

Consider the matrices from the set $S\subset\mathcal{M}_{n}(\mathbb{R})$ with diagonal entries a permutation of the set $\{(-1)^{k_{1}}a_{1},\hdots(-1)^{k_{n}}a_{n}\},\ k_{i}\in\mathbb{N},\ i\in [1,n]\cap \mathbb{Z}.$  Clearly, $\sum a_{i}\equiv 0\pmod 2$ must be true in order to have $\sum (-1)^{k_{i}}a_{i}=0$. We are to prove that $\exists_{k_{i}\in\mathbb{N},i\in [1,n]\cap \mathbb{Z}}$ such that there exists a matrix $\textbf{M}\in S$  with $\text{Trace}(\textbf{M})=0$.  There exists a theorem that says that a matrix $\textbf{M}$ satisfies $\text{Trace}(\textbf{M})=0$ if and only is there exist matrices $\textbf{A,B}$ such that $\textbf{M}=\textbf{AB}-\textbf{BA}$.  Find a matrix $\textbf{M}\in S$ such that it is in the form $\textbf{AB}-\textbf{BA},\ \textbf{A,B}\in\mathcal{M}_{n}(\mathbb{R})$ with the given conditions.  I believe that this is a possible approach.


note that $ x\equal{}y$ if not the $ LHS$ is irrational.
now the rest is done by inequalities.

[quote="mrmohamed"][quote="zaya_yc"]$ x,y \in N$
solve: $ (\sqrt {5} \plus{} 1)^{2x} \plus{} (\sqrt {5} \minus{} 1)^{2y} \equal{} 2^{x}(y^{2} \plus{} 2)$[/quote]
(x,y)=(o,o)
mrmohamed[/quote]

$ x,y$ natural number . sorry I mistake.

$ (\sqrt {5} \plus{} 1)^{2x} \plus{} (\sqrt {5} \minus{} 1)^{2x} \equal{} 2^{x}(y^{2} \plus{} 2)$

The only solutions are $ (x$,$ y)\equal{}(0$,$ 0)$ and $ (x$,$ y) \equal{} (1$,$ 2)$.


When simplified $ \sqrt{1\plus{} \left (\frac{x^4\minus{}1}{2x^2} \right )^2}$ equals:

$ \textbf{(A)}\ \frac{x^4\plus{}2x^2\minus{}1}{2x^2} \qquad
\textbf{(B)}\ \frac{x^4\minus{}1}{2x^2} \qquad
\textbf{(C)}\ \frac{\sqrt{x^2\plus{}1}}{2} \\
\textbf{(D)}\ \frac{x^2}{\sqrt{2}} \qquad
\textbf{(E)}\  \frac{x^2}{2}\plus{}\frac{1}{2x^2}$


Students taking the USAMO (particularly for the first time) might be interested in reading a set of articles we wrote last year called [url=http://www.artofproblemsolving.com/Resources/AoPS_R_A_HowWrite.php]How to Write a Solution[/url].

Agreed that the article mentioned in the first post is a great resource for USAMO participants, especially first-timers.

Nice. I read through it and it really helps a lot. THX


Let $ a,b,c$ be the non-negative number which are not greater than 1.Prove that $ a^4\plus{}b^4\plus{}c^4\plus{}d^4\plus{}(ab)^2\plus{}(bc)^2\plus{}(cd)^2\plus{}(da)^2\plus{}8(1\minus{}a)(1\minus{}b)(1\minus{}c)(1\minus{}d)$≥$ 1$

Is there anyone interested in this ineq?The solution is very simple!


Specify the steps of an algorithm that locates an element in a list of increasing integers by successively splitting the list into four sublists of equal (or as close to equal as possible) size, and restricting the search to the appropriate piece. (Hint: see binary search algorithm.)

can any one help me solve this thanku

This is more of a Computer Science and Informatics thing.  I have no idea of your CS background, but I would suggest taking the hint and reading about the binary search algorithm. http://en.wikipedia.org/wiki/Binary_search