algorithm
geometry
geometric transformation
rotation
quadratics
function
calculus

Hello.  A few of us at my company have been trying to solve this problem for a few weeks now, without success, and so now I turn to the brilliant minds of the people who frequent this forum for help :-)

We operate a centrifuge that spins between 1.4 G and 9 G.  The command that we send to our motion control algorithm is a G command, so our algorithm takes the G command and computes the required speed of the arm to reach that desired G level.  For steady-state, this is easy and we use the following equation:

$ \omega \equal{} \sqrt{ \frac{ g }{ R } \sqrt{ G_{cmd}^2 \minus{} 1 } }$

which is derived from

$ G_{act}^2 \equal{} \left( \frac{ \omega^2 R }{ g } \right)^2 \plus{} 1$

where $ g$ is the acceleration due to gravity, $ R$ is the arm length, and $ G$ is the commanded or actual G level.

We are often required to follow an arbitrary G profile, however, and the arm's tangential acceleration comes into play.  The new equation that describes the machine's G level is this:

$ G_{act}^2 \equal{} \left( \frac{ \omega^2 R }{ g } \right)^2 \plus{} \left( \frac{ \alpha R }{ g } \right)^2 \plus{} 1$

This is of course quartic in $ \omega$.  When tangential acceleration is neglected, there are two real roots and two imaginary roots.  One of the real roots is negative and the other is positive - this makes identifying the correct choice very easy.  We have tried making the substitution $ \omega \equal{} \omega_0 \plus{} \alpha \triangle t$ and solving for alpha as well as the substitution $ \alpha \equal{} \frac{ \omega \minus{} \omega_0 }{ \triangle t }$, where $ \omega_0$ is the arm speed calculated at the previous frame and $ \triangle t$ is the time elapsed between frames.  In both cases, we can solve the resulting quartic equation, and we again get two real roots and two complex roots.  Ignoring the complex roots leaves us with two choices, both of which are positive.  In case of an increasing G command, we can choose either of the remaining roots, and it gives us a satisfactory solution, where as the G command reaches a plateau, the tangential term is reduced to zero and the solution of this equation matches the solution of the simpler equation above.

The problem is in the case of a decreasing G command.  There are still only two real solutions.  Depending on the shape of the curve we are trying to follow, we must choose one root or the other, and sometimes it is necessary to switch between the two to avoid reaching a point where all four roots are complex.  Unfortunately, while we are capable of doing this, in most cases we can even decide when to switch roots, and the magnitude of the G forces that are generated match the command exactly, the machine motion is unacceptable.  For example, the centrifuge will start deccelerating rapidly, so that the arm actually stops and changes direction and all of the acceleration is a result of the tangential acceleration of the arm.  There would then be a step change the speed or acceleration (or both) to correct the speed and give a more reasonable number.  This, of course, is a solution that we cannot implement.  There is no case in which the arm speed should be less than the speed required to generate 1.4 G.

1.  If a solution exists for the onset, a solution must exist for the offset, right?  I know I can take the desired curve, flip it around in time, find the time history of the rotation rate that generates the correct curve, and flip that around again to get a solution that works.  It will work every time.  Why can't I do this in real-time?

2.  Is there a way that I can impose my additional constraints on the arm speed and acceleration (no step changes in speed, no speed less than the 1.4 G speed, etc.) and solve the problem such that these constraints are met?

Thank you in advance for your help!

-Kerry

Before saying anything, let me ask a couple of questions. What you want basically boils down to solving the differential equation $ \omega^4\plus{}\omega'^2\equal{}H(t)$ (I assumed that $ R\equal{}1$ and $ H\equal{}(G^2\minus{}1)g^2$). Now, what do you mean by saying that this equation is quatric in $ \omega$ :? What you can do is to observe the current $ \omega$ (there cannot be abrupt changes in speed) and decide upon the angular aceleration $ \omega'$ that you can implement applying more power to your engine or pushing the brakes and that is just a bounded function. It is most certainly a quadratic equation and quite a simple one for that having one positive and one negative root. The next question is whether you allow arbitrarily large jerks (jumps in $ \omega'$) or you want to bound $ \omega'$ at the moments of switching from acceleration to deceleration by something. Once you answer that, I'll try to think of what to do here. The problem is that you do not want to turn your centrifuge into a shaker and that there is no way to go down in acceleration fast from the state with large velocity, so you'll have to live with the fact that not all profiles are attainable. So the best you can hope for is a simple algorithm for the requested profile that either returns the control function or tells that the profile is unacceptable. Also, as far as I understood your post, you want a solution that works in real time, i.e., you know the requested acceleration at the given moment, but not the future profile. That imposes some additional restrictions and may result in less smooth operation of the machine than you would like to (unless you want to restrict the possible requests even more). Perhaps I'll ask a few more stupid questions before I'll be able to tell something, so be patient: I want to figure out what exactly the problem is first.

Hello fedja, thanks for the reply.  Let's see if I can answer your questions...

I think we can assume that arbitrarily large jerks are acceptable.  We employ a series of filters and limiters on $ \omega$, $ \omega'$, and $ \omega''$ after we calculate $ \omega$, and if it does turn out to be a problem, even with those limiters in place, then maybe I'll take another look at how I define the problem.

I have come to the realization that not all profiles will be attainable as well.  I've been doing some thinking about what the best way to demonstrate this - I have not yet convinced other people at my company of this.  In any case, it would be good to be able to show (graphically?) that if you are at some G level, the maximum G offset rate that you can achieve is x before the tangential term grows too large.  I think this will be easy to do, I just haven't put much thought into it yet.  The part that makes it hard to convince others that this is true is that if I reverse the profile, I can always find a solution - all onsets are attainable.  I frequently convince myself that all offsets should be possible before I look at the equations again and re-convince myself that this is not the case.  Anyway, in the case of an impossible offset, my plan is to use the simpler algorithm and live with the slightly elevated G level.

Yes, doing this in real-time is a requirement.

I've left the answer to your first question for last because I need to ask another question: With regards to this being a quadratic - how is that so?  I have not yet tried solving this equation as a differential equation - is that what will make this a quadratic?  When I make one of the substitutions I mentioned in my first post (and solve it algebraicly), I get (using the first substitution for example) a $ \omega^4$ term, a $ \omega^2$ term, a $ \omega$ term and a constant term.  I end up with four roots.  Doesn't the $ \omega^4$ term in your differential equation guarantee four roots?

Thanks for the help!

-Kerry

Your post got me thinking about this again - I think the requirement for doing this in real-time without knowing what the future command will look like is what makes some offsets impossible.  The plot for a rapid onset might show that $ \omega$ and $ \omega'$ increase rapidly at first, and at the time that the plateau G level is reached, some of the acceleration is still coming from the tangential term.  It takes a little more time until the machine reaches a constant speed and all of the acceleration comes from the centripetal term.  Without knowing that you have an offset coming up, you don't know to start decelerating the arm (but maintaining a nearly constant G level) until it's too late.

-Kerry

Damn... and now I see why the differential equation is quadratic instead of quartic.   :oops:
So I can't solve it by simply subtracting $ \omega^4$ from both sides because I need to know $ \omega$ and $ \omega'$ at the same instant, right?  I suppose that's what makes it a DE?

Does it matter that I am doing this in discrete time?  Will the solution of a continuous time DE work for me?  It's been several years since I've solved any DEs, so please bear with me.

Thanks,

Kerry

As to the quadratic vs quatric, you, probably, try to solve
$ \omega_{k \plus{} 1} \plus{} \left(\frac {\omega_{k \plus{} 1} \minus{} \omega_k}{\Delta t}\right)^2 \equal{} H(t_{k \plus{} 1})$ for $ \omega_{k \plus{} 1}$.
I claim that there will be nothing wrong with solving
$ \omega_{k} \plus{} \left(\frac {\omega_{k \plus{} 1} \minus{} \omega_k}{\Delta t}\right)^2 \equal{} H(t_{k})$ instead (it will merely mean time delay of $ \Delta t$ plust using the right derivative instead of the left one; both should not matter in the slightest).

If doing it in the real time is a requirement, it is easy to show that you cannot drop your acceleration fast once you reached high velocity. Indeed, assume that you operate in the steady state and your velocity is $ \omega_0$, and that the profile requires you to drop from your current $ H \equal{} \omega_0^4$ to $ H \equal{} \gamma^4\omega_0^4$ within time $ T$ where $ \gamma < 1$. Then the velocity at the time $ T$ must be at most $ \gamma\omega_0$, which requires the tangential acceleration to be at least $ \frac {1 \minus{} \gamma}T\omega_0$ on average on $ [0,T]$. But this tangential acceleration already gives you a huge $ H$ if $ T$ is small and $ \gamma$ is not too close to $ 1$! So, in order to drop your $ H$ by the time $ T$, you have to increase it a lot somewhere between $ 0$ and $ T$. I hope that's a convincing enough argument.

Now, once we agreed that covering all profiles with your restrictions is out of question, let's see what we can do with "reasonable" profiles. The first, maybe rather idiotic, suggestion is just to make one step iteration in the equation $ \omega'^2 \plus{} \omega^4 \equal{} H(t) \equal{} \frac {(G(t)^2 \minus{} 1)g^2}{R^2}$, i.e., to try
\[ \omega(t) \equal{} \left[H(t) \minus{} \frac 1{16}\frac {H'(t)^2}{H(t)^{3/2}}\right]^{1/4}
\]
where, of course, $ H'(t)$ should be approximated as a finite difference (I would even suggest to take this difference with some noticeable step like $ \sqrt {\Delta t}$ to eliminate the noise error but you can experiment with that). If $ |H''|\le 2H^{3/2}$ (which is a theoretical limit for the deceleration from the steady state; if you want, I can demonstrate it), and $ H'$ is not too large compared to $ H$, then this formula gives a fairly nice approximation (though I am not sure if the precision obtained this way is sufficient for your purposes). Play with it and tell me if there are any really important profiles that give you an unreasonably bad approximation. If you have some particular profile for which it is bad, post it and I'll try either to find a better formula or to see why the profile is theoretically impossible with your restrictions. By the way, what is the value of $ R$ for your machine? I'll need it if I have to play with the problem myself: the less $ R$ is, the better my stupid formula works ;)

[quote="fedja"]Now, once we agreed that covering all profiles with your restrictions is out of question, let's see what we can do with "reasonable" profiles. The first, maybe rather idiotic, suggestion is just to make one step iteration in the equation $ \omega'^2 \plus{} \omega^4 \equal{} H(t) \equal{} \frac {(G(t)^2 \minus{} 1)g^2}{R^2}$, i.e., to try
\[ \omega(t) \equal{} \left[H(t) \minus{} \frac 1{16}\frac {H'(t)^2}{H(t)^{3/2}}\right]^{1/4}
\]
where, of course, $ H'(t)$ should be approximated as a finite difference (I would even suggest to take this difference with some noticeable step like $ \sqrt {\Delta t}$ to eliminate the noise error but you can experiment with that). If $ |H''|\le 2H^{3/2}$ (which is a theoretical limit for the deceleration from the steady state; if you want, I can demonstrate it), and $ H'$ is not too large compared to $ H$, then this formula gives a fairly nice approximation (though I am not sure if the precision obtained this way is sufficient for your purposes). Play with it and tell me if there are any really important profiles that give you an unreasonably bad approximation. If you have some particular profile for which it is bad, post it and I'll try either to find a better formula or to see why the profile is theoretically impossible with your restrictions. By the way, what is the value of $ R$ for your machine? I'll need it if I have to play with the problem myself: the less $ R$ is, the better my stupid formula works ;)[/quote]

WOW... I followed the first half of your post OK, but I don't see how you came up with that approximation.  Is that a well-known method?  I don't think it's one that I know...  Anyway, I tried it and it works... most of the time.  I am using $ \triangle t$ for my finite difference because the G commands are supplied to me at the same rate at which I am calculating $ \omega$ and I can't go any smaller than that.  For ~90% of a "typical" profile it works very well and gets very close the commanded signal.  There are a couple of places where it doesn't work, and the G level diverges quite a bit from the command.  Unfortunately all of these places are where the $ H''$ value is above the theoretical limit that you gave in your last post (would you mind sharing how you arrived at that value?).  I assume that this means there is nothing that can be done.  However, some of the places where this occurs are onsets.  I can find a solution for these situations without your approximation.  Does this mean that the $ H''$ limit you calculated applies to onsets as well?

Thanks for your help - you have given me much more insight into this problem.  Our biggest machine has about a 25 foot arm, but we were hopeful that we could find a solution that we could implement in all of our machines, which cover a wide range of arm lengths.

-Kerry

I don't have much time now, so here are a few "dirty quickies" rather than full explanations:
[quote="ETCkerry"]
WOW... I followed the first half of your post OK, but I don't see how you came up with that approximation.  Is that a well-known method?  I don't think it's one that I know...
[/quote]
We decided that we want the machine to run a smoothly as possible. This means that the main part of $ \omega^4\plus{}\omega'^2\equal{}H(t)$ should come from the $ \omega$ part and the $ \omega'$ term shold be small compared to it. Neglecting it entirely, we get $ \omega\equal{}H^{1/4}$. Now this guy has the derivative $ \omega'\equal{}\frac 14 H'H^{\minus{}3/4}$, which may be considered the main term of the true $ \omega'$. Writing the equation $ \omega^4\equal{}H\minus{}\omega'^2$ and substituting the above approximation for $ \omega'$, we get the formula.
[quote]
Anyway, I tried it and it works... most of the time.
[/quote]
Nothing more was really expected :lol:
[quote]
For ~90% of a "typical" profile it works very well and gets very close the commanded signal.
[/quote]
That is even more than I expected! :D
[quote]
There are a couple of places where it doesn't work, and the G level diverges quite a bit from the command.  Unfortunately all of these places are where the $ H''$ value is above the theoretical limit that you gave in your last post (would you mind sharing how you arrived at that value?).
[/quote]
Suppose that you are in the steady state with $ H\equal{}1$. Then your $ \omega\equal{}1$ and $ \omega'\equal{}0$. Now suppose that you start decreasing $ \omega$ as $ 1\minus{}ct^2$ (the order less than quadratic gives even worse picture). Then $ \omega^4\approx 1\minus{}4ct^2$ and $ \omega'^2\equal{}4c^2t^2$, so $ H\approx 1\plus{}4(c^2\minus{}c)t^2$. Now $ c^2\minus{}c\ge \minus{}\frac 14$. Thus, $ H$ cannot go down faster than $ 1\minus{}t^2$, which means $ H''\ge \minus{}2$. The factor $ H^{3/2}$ is just the scaling of the problem.
[quote]
I assume that this means there is nothing that can be done.  However, some of the places where this occurs are onsets.  I can find a solution for these situations without your approximation.  Does this mean that the $ H''$ limit you calculated applies to onsets as well?
[/quote]
You can solve the fast onset, but the solution that you'll get will be with too large tangential component, which will mean that if you suddenly get a request for an offset, you'll still pass the highest point of the profile with positive and not small $ \omega'$ and that means heading for trouble on the descent curve if the latter on is long enough (just try it :)).
My approximation doesn't really know whether the offset or onset will be requested the next moment and is equally ready for both, so the side effect is that it is about as bad on sharp onsets as on sharp offsets.
On the other hand, the restriction $ |H''|\le 2H^{3/2}$ is not so bad: since $ H$ has $ R^2$ in the denominator, all it means is that you need to run profiles with sharper turns on smaller machines. Of course, you can design a profile that won't work on any machine you have but, since some of them (like sharp descents from steady state) are theoretically impossible, I hope you or your boss do not feel too bad about it. If you ever come into a desperate need to get some particular profile that does not satisfy this restriction on any of your machines, let me know and I'll see if I can do anything about that particular one. Until that happens, just consider this inequality as a "law of nature" :)
[quote]
we were hopeful that we could find a solution that we could implement in all of our machines, which cover a wide range of arm lengths.
[/quote]
Good luck, but by now you have seen at least one restriction that cannot be overcome :(.

If any more questions arise, feel free to ask! ;)

I played a bit with an idea to design an optimal control that depends only on $ H$ and $ H'$ and gives you the best outcome in the worst case scenario. Of course, once you incorporate $ H'$, big second derivatives are your enemy, so I restricted them by the condition $ |H''|\le 3H^{3/2}$ (i.e., by 50% over the theoretical limit for the offset). Once you get this restriction for the second derivative and once your profile should stay non-negative ($ H<0$ has no physical meaning and under your conditions even $ H<1$ is impossible), you automatically get a restriction for the first derivative $ |H'|\le 1.6 H^{5/4}$, so I looked at what would be optimal in this box. It took a few hours of computations, guessing, and some experimenting, but finally it seems that the control that is nearly the best is the following:
\[ \omega(t)\equal{}H^{1/4}F\left(\frac{H'^2}{H^{5/2}}\right)\]
where
\[ F(x)\equal{}(1\plus{}S(x)/8)^{\minus{}1/4}\]
and
\[ S(x)\equal{}\begin{cases}x\minus{}\frac {x^2}4,& 0\le x\le 2
\\1,& x>2\end{cases}\]
Here are just a few pictures. The profile is in red, this control is in green, and the trivial one $ \omega\equal{}H^{1/4}$ is in magenta.
1) $ H(t)\equal{}40/(t\plus{}2)^4$ (which is the fastest onset under these restrictions; I drew it as an "offset", but the control is obviously symmetric in time)
[asy]size(300);

real h=0.002, t=2;

real D (real f(real),real x)
{
return (f(x+h)-f(x-h))/2/h;
}

real P(real t, real p)
{
return exp(p*log(t));
}

real H(real t)
{
return 44/(t+2)^4;
}

real f(real x)
{
real a=D(H,x), t=H(x);
return P(t,1/4);
}

real g(real x)
{
return f(x)^4+D(f,x)^2;
}

real r(real t)
{
real s=t-t^2/4;
if (t>2) s=1;
return P(1+s/8,-1/4);
}

real ff(real x)
{
real t=H(x), a=D(H,x);
return P(t,1/4)*r(a^2/P(t,5/2));
}

real gg(real x)
{
return ff(x)^4+D(ff,x)^2;
}

D((0,0)--(t,0), black);

D(graph(H,0,t,1501),red+linewidth(0.75));

D(graph(gg,0,t,1000),green+linewidth(0.75));
D(graph(g,0,t,1000),magenta+linewidth(0.75));[/asy]
2) $ H(t)\equal{}\frac{1}{t^2\plus{}1}$
[asy]size(300);

real h=0.002, t=2;

real D (real f(real),real x)
{
return (f(x+h)-f(x-h))/2/h;
}

real P(real t, real p)
{
return exp(p*log(t));
}

real H(real t)
{
return 1/(t^2+1);
}

real f(real x)
{
real a=D(H,x), t=H(x);
return P(t,1/4);
}

real g(real x)
{
return f(x)^4+D(f,x)^2;
}

real r(real t)
{
real s=t-t^2/4;
if (t>2) s=1;
return P(1+s/8,-1/4);
}

real ff(real x)
{
real t=H(x), a=D(H,x);
return P(t,1/4)*r(a^2/P(t,5/2));
}

real gg(real x)
{
return ff(x)^4+D(ff,x)^2;
}

D((0,0)--(t,0), black);

D(graph(H,0,t,1501),red+linewidth(0.75));

D(graph(gg,0,t,1000),green+linewidth(0.75));
D(graph(g,0,t,1000),magenta+linewidth(0.75));[/asy]
3) $ H(t)\equal{}2\plus{}\cos(1.5 t)$
[asy]size(300);

real h=0.002, t=4;

real D (real f(real),real x)
{
return (f(x+h)-f(x-h))/2/h;
}

real P(real t, real p)
{
return exp(p*log(t));
}

real H(real t)
{
return 2+cos(1.5*t);
}

real f(real x)
{
real a=D(H,x), t=H(x);
return P(t,1/4);
}

real g(real x)
{
return f(x)^4+D(f,x)^2;
}

real r(real t)
{
real s=t-t^2/4;
if (t>2) s=1;
return P(1+s/8,-1/4);
}

real ff(real x)
{
real t=H(x), a=D(H,x);
return P(t,1/4)*r(a^2/P(t,5/2));
}

real gg(real x)
{
return ff(x)^4+D(ff,x)^2;
}

D((0,0)--(t,0), black);

D(graph(H,0,t,1501),red+linewidth(0.75));

D(graph(gg,0,t,1000),green+linewidth(0.75));
D(graph(g,0,t,1000),magenta+linewidth(0.75));[/asy]
4) $ H(t)\equal{}1\plus{}1.5t$
[asy]size(300);

real h=0.002, t=1;

real D (real f(real),real x)
{
return (f(x+h)-f(x-h))/2/h;
}

real P(real t, real p)
{
return exp(p*log(t));
}

real H(real t)
{
return 1+1.5*t;
}

real f(real x)
{
real a=D(H,x), t=H(x);
return P(t,1/4);
}

real g(real x)
{
return f(x)^4+D(f,x)^2;
}

real r(real t)
{
real s=t-t^2/4;
if (t>2) s=1;
return P(1+s/8,-1/4);
}

real ff(real x)
{
real t=H(x), a=D(H,x);
return P(t,1/4)*r(a^2/P(t,5/2));
}

real gg(real x)
{
return ff(x)^4+D(ff,x)^2;
}

D((0,0)--(t,0), black);

D(graph(H,0,t,1501),red+linewidth(0.75));

D(graph(gg,0,t,1000),green+linewidth(0.75));
D(graph(g,0,t,1000),magenta+linewidth(0.75));[/asy]
You should be aware that this control tends to undershoot a bit (the control I proposed first is more "on target" for really smooth profiles but gives you worse "worst case scenario" in the particular box I considered). The precision you are guaranteed with this control under the condition that you never leave the box is 5% for $ H$, which translates into 2.5% for $ G$ (the trivial control can go off by about 16% for $ H$ or 8% for $ G$, the last picture being an example of such behavior). If this is acceptable and if you agree that the restriction is near optimal, I do not see why you shouldn't take it (unless somebody in your company finds a better way). If 2.5% for $ G$ is above the acceptable level, then you have either to impose more severe restrictions on $ H''$, or to try some control that tracks the trajectory rather than uses just local information about $ H$ (which, I'm afraid, will give you a lot of trouble on offsets). Let me know what you have decided :)

Fedja, thank you so much!

I've implemented this controller in a Simulink model of our system, and it appears to work extremely well.  There are a couple of occasional spikes in the signal (it looks like the controller undershoots, then tries to compensate in the next step), but our existing filters are enough to all but eliminate its effects.  I'll have to run it through a bunch more profiles before it gets coded and implemented on the machine, but if these preliminary results are any indication, it looks good.

Thanks for your help!

-Kerry

You are always welcome Kerry! :) Let us know how the extended tests went ;)

If by the spikes you mean something like that
[asy]size(250);

real h=0.0001, t=0.3, p=0.03;

real D (real f(real),real x)
{
return (f(x+h)-f(x-h))/2/h;
}

real I(real f(real),real x)
{
real s=0;
for(int k=-10;k<1;++k)
s+=(k+10)*f(x+k*p/10);
return s/55;
}

real P(real t, real p)
{
return exp(p*log(t));
}

real H(real t)
{
if (t>0) return 1+0.53*(t+t^2);
return 1+0.5*(t-t^2);
}

real f(real x)
{
real a=D(H,x), t=H(x);
return P(t,1/4);
}

real g(real x)
{
return f(x)^4+D(f,x)^2;
}

real r(real t)
{
real s=t-t^2/4;
if (t>2) s=1;
return (P(1+s/8,-1/4)+P(1+t/16,-1/4))/2;
}

real ff(real x)
{
real t=H(x), a=D(H,x);
return P(t,1/4)*r(a^2/P(t,5/2));
}

real fff(real x)
{
return I(ff,x);
}

real gg(real x)
{
return fff(x)^4+D(fff,x)^2;
}

D((-t,0)--(t,0), black);

D(graph(H,-t,t,1501),red);

D(graph(gg,-t,t,2000),green);[/asy]
then it is not a problem at all. Note that the derivative jumped about 6% at $ 0$, so the output of $ \omega^4\plus{}\omega'^2$ has a singularity at $ 0$ because it involves the second derivative of $ H$. If you run $ H$ through some reasonable smoothing filter first, you'll eliminate the spike though some small jump due to the discontinuity of the second derivative will remain present. The filter below is as simple as taking larger step in the approximation of $ H'$ and you see what happens already:
[asy]size(250);

real h=0.001, t=0.3, p=0.03;

real D (real f(real),real x)
{
return (f(x+h)-f(x-h))/2/h;
}

real I(real f(real),real x)
{
real s=0;
for(int k=-10;k<1;++k)
s+=(k+10)*f(x+k*p/10);
return s/55;
}

real P(real t, real p)
{
return exp(p*log(t));
}

real H(real t)
{
if (t>0) return 1+0.53*(t+t^2);
return 1+0.5*(t-t^2);
}

real f(real x)
{
real a=D(H,x), t=H(x);
return P(t,1/4);
}

real g(real x)
{
return f(x)^4+D(f,x)^2;
}

real r(real t)
{
real s=t-t^2/4;
if (t>2) s=1;
return (P(1+s/8,-1/4)+P(1+t/16,-1/4))/2;
}

real ff(real x)
{
real t=H(x), a=D(H,x);
return P(t,1/4)*r(a^2/P(t,5/2));
}

real fff(real x)
{
return I(ff,x);
}

real gg(real x)
{
return fff(x)^4+D(fff,x)^2;
}

D((-t,0)--(t,0), black);

D(graph(H,-t,t,1501),red);

D(graph(gg,-t,t,2000),green);[/asy]

Six months later and we have finally run the tests with the new algorithm - and it works very well.  Taking the tangential acceleration into account allows us to use less acceleration to respond to the same G command... and the pilots noticed the response  :lol:

We had some of our pilots fly both the old algorithm and the new one back to back several times.  Sometimes the pilots were able to note that the delay in G onset was greater when accounting for tangential acceleration, but they were always able to tell that the ride was smoother.  In general, the pilots complained more about the harshness of the ride than the delay, so we decided to keep the new algorithm.  Although the effect is subtle, it brings us a little bit closer to making people believe they are flying a plane instead of a centrifuge.

Fedja - thank you, thank you, thank you!  Your ideas and explanations are much appreciated.

-Kerry

Wonderful!  :lol:  Of course, once we are closer to the real curve, the effect of "seemingly shorter delay" caused by overshooting on the onsets is gone and you'll have to work on how to reduce the real delay now. The smoother ride is due to the same thing: the old control created noticeably more jerk when departing from the "ground state" due to the same overshot and the "down to up" transitions were sharper as well. I wonder if anybody noticed a shorter delay on offsets though :?.

Let us know if you have more problems where mathematics can help :).


inequalities
calculus
function
conics
parabola
inequalities unsolved

Let $a,b,c \geq 0$ such that $a+b+c=4$. Prove that:
$\sqrt{2a+1}+\sqrt{3b+1}+\sqrt{4c+1}\ge 4+\sqrt{7}.$

I'm sorry but this problem is available now to send to TH&TT magazine so, please don't prove it1

Don't mind. I will not send solution to... Can you solve it?

I'm sorry but may be there are others? It is a problem for secondary student so I wonder you are in the first year in High school! I'm in Da Nang too.
And min of this is 5!

It should read:

[quote="ThienA2PctSchool"]Let $a,b,c \geq 0$ such that $a+b+c=4$. Prove that: \[\sqrt{2a+1}+\sqrt{3b+1}+\sqrt{4c+1}\ge 5.\] [/quote]

[quote="dyd"]I will not write up the solution, but any "calculus" students will solve it eagerly using Lagrange (because every variable is stands separately) :D[/quote]
I found a proof but can you show the solution with Lagrange Multipliers?

Yes, my solution using Mixing variables! :D . My friends get 2-th power of each side and subtract 5 in two sides :D

Yeah, this is and monthly mathematical magazine for secondary and high  student in Viet Nam.

TH&TT (Toán học và tuổi trẻ) (Vietnamese) Magazine is Mathematics and Youth Magazine (English)  :D
http://www.nxbgd.com.vn/toanhoctuoitre

Yes, but this site almost in Vietnamese so, you only can read this category( of course, if you aren't Vietnamese)
[url]http://www.nxbgd.com.vn/toanhoctuoitre/?p=7&id=6[/url]

[quote="Lovasz"]
I found a proof but can you show the solution with Lagrange Multipliers?[/quote]

Oops sorry, I was writing without try it first. Using lagrange, it seemed that I've got the maximum. It it about 6.3...

Here's mine.
[quote] Let $a,b,c \ge 0$ such that $a+b+c=4$. Prove that: \[\sqrt{2a+1}+\sqrt{3b+1}+\sqrt{4c+1}\ge 5.\] [/quote]
Let $x=\sqrt{2a+1},b=\sqrt{3b+1}$ and $z=\sqrt{4c+1}$. It implies $a={x^{2}-1 \over 2},b={y^{2}-1 \over 3},c={z^{2}-1 \over 4}$. And we also have $6x^{2}+4y^{2}+3z^{2}=61$ since $a+b+c=4$, where $x \in [1,3],y\in [1,\sqrt{13}],z \in [1,\sqrt{17}]$.
We are now to prove that: \[x+y+z \ge 5 \\ \iff 61(x+y+z)^{2}\ge 25(6x^{2}+4y^{2}+3z^{2}) \\ \iff 122(xy+yz+zx) \ge 89x^{2}+39y^{2}+14z^{2}.\] The last function is a parabola with coefficient $\alpha<0$, so that the maximum value occurs if $x \in \{1,3\},y\in \{1,\sqrt{13}\},z \in \{1,\sqrt{17}\}$. Yieding $LHS \ge 5.$
Proof complete.


For an upcoming international mathematics contest, the participating countries were asked to choose from nine combinatorics problems. Given how hard it usually is to agree, nobody was surprised that the following happened:
[b]i)[/b] Every country voted for exactly three problems.
[b]ii)[/b] Any two countries voted for different sets of problems.
[b]iii)[/b] Given any three countries, there was a problem none of them voted for.
Find the maximal possible number of participating countries.

[hide]
Note that condition (iii) can be restated as follows:

iii) Given any three countries, at least two of them voted for the same problem.

There are $ \binom93 \equal{} 84$ possible voting patterns for the countries. Now, let's call a triple $ \{C_1, C_2, C_3\}$, where no two countries vote for the same problem an [i]offending triple[/i].

The total number of offending triples is $ \frac {84\binom63}{3!} \equal{} 280$.

The number of offending triples that contain a voting configuration $ C$ is $ \frac {\binom63}2 \equal{} 10$.

Therefore, to remove all offending triples, we need to remove at least 28 possible voting configurations out of the total 84, giving a maximum of 56 countries.

This configuration is obviously possible -- say that no country voted for problem #9 (satisfying condition iii). Then there are exactly $ \binom83 \equal{} 56$ different voting patterns.
[/hide]

[quote=ffao]
Therefore, to remove all offending triples, we need to remove at least 28 possible voting configurations out of the total 84, giving a maximum of 56 countries.
[/quote]
Sorry for bump it. But I suppose It's not convincing.
We need to get $28$ offending triples which contain all the $84$ possible voting configurations so that we have to remove at least $28$ possible voting configurations out of the total $84,$ giving a maximum of $56$ countries.


algebra
polynomial
function
calculus
calculus computations

65.  Let $ p(x)$ be the polynomial $ x^3 \plus{} ax^2 \plus{} bx \plus{} c$, where $ a$, $ b$, and $ c$ are real constants.  If $ p(\minus{}3)\equal{}p(2)\equal{}0$ and $ f^\prime(\minus{}3) < 0$, which of the following is a possible value of $ c$?

(A) $ \minus{}27$
(B) $ \minus{}18$
(C) $ \minus{}6$
(D) $ \minus{}3$
(E) -$ \frac{1}{2}$

I know $ c$ must be the product of the roots, but it seems like any of these could be candidates.

Note that the $ x^3$-coefficient is positive. What does this tell you about $ p'$ at the largest and smallest roots? It might help to draw a picture.

And $ \minus{} c$ is the product of the roots, not $ c$.

[hide="Well I managed to discover a number of things which are useless."]
We know the following:
$ 9a\plus{}3b\plus{}c\equal{}27$
$ 4a\plus{}2b\plus{}c\equal{}\minus{}8$

Using a little Gaussian elimination:
$ 6b\plus{}5c\equal{}\minus{}180$
$ 6a\minus{}c\equal{}78$
$ 5a\plus{}b\equal{}35$

And some messing around:
$ b\equal{}(\minus{}180\minus{}5c)/6$
$ a\equal{}(78\plus{}c)/6$

We know by the power rule that:
$ p^\prime(x)\equal{}3x^2\plus{}2ax\plus{}b$
$ p^\prime(\minus{}3)\equal{}27\minus{}6a\plus{}b$
$ 6a\minus{}b>27$

$ 6a>27\plus{}b$
$ 6*(78\plus{}c)/6>27\plus{}b$
$ 78\plus{}c>27\plus{}(\minus{}180\minus{}5c)/6$
$ 468\plus{}6c>162\minus{}180\minus{}5c$
$ 11c>\minus{}486$
$ c>\minus{}44.181818\ldots$

$ 6a\minus{}c>27\plus{}b\minus{}c$
$ 78>27\plus{}b\minus{}c$
$ 51>b\minus{}c$
$ 51>\minus{}(180\plus{}5c)/6$
$ \minus{}306<180\plus{}5c$
$ \minus{}97.2<c$[/hide]

Thanks Bictor.  That makes sense.  I hadn't considered the fact that since the leading coefficient is positive, the polynomial must come from negative infinity.  This means the other root must be less than -3.  Thus, it is either A or B.  But it cannot be B since -3 would have to be a repeated root (which it is not because the function must be increasing or at a critical point when it hits the first zero).

Thanks!


Prove the inequality

[b]a*a/b+b*b/c+c*c/a >=a+b+c+4*(a-b)^2/(a+b+c)[/b]

for all positive numbers a, b ,c .

See here http://www.mathlinks.ro/Forum/viewtopic.php?p=225004#225004  :wink:


Stacey is standing in a field. She walks $ 11$ yards west, $ 30$ yards north, $ 4$ yards west, and finally $ 22$ yards south. How many yards from her starting point is she?

[asy]import olympiad;
import geometry_dev;
pair A=(0,0), B=(-11,0), C=(-11,30), D=(-15,30), E=(-15,8);
draw(A--B--C--D--E, red+linewidth(.75));
dot(A);
dot(E);
label("Start", A, dir(0));
label("End", E, dir(180));
draw(A--E--(-15,0)--cycle, dashed+linewidth(1));
label("$15$", (-7.5,0), dir(270));
label("$8$", (-15,4), dir(180));
markrightangle(A, (-15,0), E, 10);[/asy]
By the Pythagorean Theorem, the distance between where she started and where she ended is
\[ \sqrt {8^2 + 15^2} = \sqrt {64 + 225} = \sqrt {289} = \boxed{17}\]


"A thing worth having is a thing worth cheating for."

                   --W. C. Fields

the answer is 4 hours.  the one with the car drives the other two friends to the party.

This is all i did in a very short time, but i think its worth posting.

-----------

cut the numbers down: 16 mi' to get there, we have 4/3/2 mph devices.

The devices all have to make it there (ie. the car has to be at the end, its
stupid to leave it behind.)  So they all are owned by someone for every
interval.

Suppose the car is owned by A for a hours, B for b hours, C for c hours,
a+b+c = 4.
Suppose the bike is owned by A/B/C for a', b', c' hours, a' + b' + c' = 16/3.
Suppose A/B/C are on foot for a", b", c" hours, a" + b" + c" = 8.  This is because (16 - 4a - 3a')/2 = a", etc.

Now a+a'+a" is the time it takes for A to cover the distance,.. this has to be atleast (4 +  16/3 + 8)/3 = 52/9.

--
We only need an example of that distance.    this can probably be done, but it is hard.  I proved that B does need to share the bike for it to happen, though.


algebra
polynomial
vector
linear algebra
matrix
linear algebra solved

$R$ commutative ring, $A,B \in M_n(R)$
$P(x,y)=det(xA-yB)$ polynomial with variables $x,y$ with $AB=BA$

Prove that $P(B,A)=0_{M_n(R)}$

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

I think this should be in any linear algebra text book/course
which talking about Cayley-Hamilton theorem

Moubi, very good you posted, since I have no idea how to show such things. Can anyone submit a detailed solution and please explain how we should attack such problems. I find them really wierd.  :(

I don't get this :? You wrote $AB=BA$, but $P(B,A)=\det(AB-BA)$. Could you please clarify it? :?

Grobber, you cannot write directly that equality. My teacher told me this is the classical error made when "proving" Hamilton-Cayley!!!

I know what my error was: when I saw Moubinool writing $X,Y$ I thought he was referring to matrices (because of the capital letters). In other words, I thought $P(X,Y)=\det(XA-YB)$, where $X,Y$ are matrices. Had it not been for this misunderstanding, I never would have made the mistake of directly putting the matrices $A,B$ where the variables $x,y$ go :).

I am absolutely convinced that the following is really aberant, but I ask for someone who knows very well such things to explain to me where I am wrong:
  Take the vectors $ e_1=(1,0,...,0), e_2=(0,1,0,...,0),..., e_n=(0,0,...1)$. From the fact that $AB=BA$ we can easily see that we have $ B\cdot ( a_{1i}e_1+...+a_{ni}e_n)=B\cdot (A e_i)=A\cdot (Be_i)=A( b_{1i}e_1+...+b_{ni} e_n)$ , thus
   $ ( a_{1i}B-b_{1i}A)e_1+...+(a_{ni}B-b_{ni}A)e_n=0$ for all $i$. (*)
   Now, let us place ourselves in the ring $M_n(R[A,B])$, where $ R[A,B]$ is the set of all polynomial combinations of powers of $A,B$ and coefficients in $R$. SInce $AB=BA$, $ R[A,B]$ is commutative. We know that in any commutative ring $A$ we have the identity
  $ Com(X)\cdot X=(\sum_{f\in S_n}{eps_f\cdot x_{1f(1)}...x_{nf(n)}})I_n$, for any $X\in M_n(A)$, where $S_n$ is the set of permutations of $1,2,...,n$ and $ eps_f$ is the signature of f and $Com(X)$ is the transpose matrix of the algebraic complements of elements in $X$. This has been usually done in cours for fields, but since it uses only multiplications and additions, it remains true in commutative rings.  Now, consider the vector $Z=^{t}(e_1,e_2,...,e_n)$. From (*) we have that the matrix $ S_{ij}=a_{ji}B-b_{ji}A \in M_n(R[A,B])$ verifies $ SZ=0$ and thus $ Com(S)SZ=0$ and thus $ (\sum_{f\in S_n}{eps_f (a_{f(1) 1}B-b_{f(1)1}A)...(a_{f(n) n}B-b_{f(n) n}A))Z=0}$ from where $\sum_{f\in S_n}{eps_f (a_{f(1) 1}B-b_{f(1) 1}A)...(a_{f(n) n}B-b_{f(n) n}A)=0}$. But this means that $P(A,B)=0$, since we can expand the products in the later sum (because $AB=BA$).
    Thanks to Fedja who indicate mny errors in my initial "solution". Fedja, is it good now?

[quote="harazi"]I am absolutely convinced that the following is really aberant,...[/quote] Actually, it looks almost like a valid proof but it is very hard to read because of several lapses. Here are three:

1) $Ae_i=a_{1i} e_1+a_{2i}e_2+\ldots$, not $a_{i1}e_1+a_{i2}e_2+\dots$
(say, $Ae_1$ is the first column of $A$, not the first row). This seems to force some changes in subsequent formulae.

2) $M_n(R)$ is not a commutative ring, so some extra words should be said to justify the identity for $S\in M_n(M_n(R))$.

3) Is $Y$ the same as $Z$? It has never been defined...

Try to edit it to make it completely readable. Most likely you'll either arrive at a correct proof in the process or will be able to see what is wrong yourself.  :)

Thank you Fedja for your pertinent remarks. I've edited it. Could you please tell me whether is right?  :)

[quote="harazi"]Could you please tell me whether is right?  :)[/quote] Seems fine to me (unless I'm missing something, as usual  :P) except for a minor typo: $P(A,B)$ instead of $P(B,A)$ in the end. Actually it is very close to one of the classical proofs though you work in $M_n(R[A,B])$ while the classical proof stays in $M_n(R)$. Here is how it goes. You start with the identity $Com(xA-yB)\cdot (xA-yB)=P(x,y)I_n$ and note that $Com(xA-yB)=\sum_{i,j}C_{ij}x^iy^j$ where $C_{ij}\in M_n(R)$. The identity can then be interpreted as an identity for polynomials with matrix coefficients (the left hand side is the product of two such polynomials, the second one being $Ax-By$, and the right hand side is a polynomial $\widetilde P(x,y)$ whose coefficients are the coefficients of $P$ times the identity matrix). Now comes the main trick. If you have three polynomials with matrix coefficients $S(x,y), Q(x,y)$ and $\widetilde P(x,y)$ such that $S(x,y)Q(x,y)=\widetilde P(x,y)$ in the sense of the product of polynomials, then $S(B,A)Q(B,A)=\widetilde P(B,A)$, provided that $A$ and $B$ commute with each other and also commute with the coefficients of $Q$. This allows to conclude that $\widetilde P(B,A)=0$, which is the same as $P(B,A)=0$.

but this means that Cayley-Hamilton can be showed very quickly using Fedja's proof ? :huh:

One can deduce Cayley-Hamilton for any ring from CH for fields.  Prove CH in your favourite way for $n \times n$ matrices over the field $Q(x_{11},x_{12},\ldots,x_{nn})$ where the $x_{ij}$ are independent transcendentals.  Then CH holds for the matrix with $x_{ij}$ as entries.  This is an identity in the ring $R = Z[x_{11},x_{12},\ldots,x_{nn}]$ and therefore holds in any quotient of $R$.  But any $n \times n$ matrix can be viewed as an element of a suitable quotient of $R$.

Once you prove it in some field of characteristic zero, the Cayley-Hamilton theorem is simply a collection of polynomial identities with integer coefficients (the variables are the entries of the matrix), which is automatically true over any commutative ring. The $2\times 2$ example to make it clear:
$\det\begin{bmatrix}a-x&b\\c&d-x\end{bmatrix}=x^2-(a+d)x+ad-bc$
$\begin{bmatrix}a&b\\c&d\end{bmatrix}^2-(a+d)\cdot\begin{bmatrix}a&b\\c&d\end{bmatrix}+ (ad-bc)\cdot\begin{bmatrix}1&0\\0&1\end{bmatrix}$
$=\begin{bmatrix}a^2+bc&ab+bd\\ac+cd&d^2+bc\end{bmatrix}- \begin{bmatrix}a^2+ad&ab+bd\\ac+cd&ad+d^2\end{bmatrix}+ \begin{bmatrix}ad-bc&0\\0&ad-bc\end{bmatrix}=\begin{bmatrix}0&0\\0&0\end{bmatrix}$

That is a perfectly good proof of the $2\times2$ case of Cayley-Hamilton, and it obviously works over any commutatitive ring. It does all come down to equating entries of matrices- that's why everything works.


If $a$ is a real root of $x^5 - x^3 + x - 2 = 0$, show that $[a^6] =3$

the equation can be written as $2=\alpha\frac{\alpha^6 + 1} {\alpha^2 + 1}$
and so $\alpha^6 \geq 3$ as $\alpha + \frac{1} {\alpha}\geq 2$
Now to prove that $\alpha^6<4$ it is essential to prove that $2\alpha^2 - 5\alpha + 2 <0$
this is obviously true as the range of $\alpha$ is between 1 and 2.
and we are done.
    Ashwath.

[quote="ashwath.rabindranath"]the equation can be written as $2=\alpha\frac{\alpha^6 + 1} {\alpha^2 + 1}$
and so $\alpha^6 \geq 3$ as $\alpha + \frac{1} {\alpha}\geq 2$
Now to prove that $\alpha^6<4$  [/quote]
$\alpha^5+\alpha=\alpha^3+2.$
Hence, $\frac{\alpha^3+2}{\alpha^3}=\alpha^2+\frac{1}{\alpha^2}>2,$ since $1$ and $-1$ are not roots of equation.
Hence, $\alpha^3<2.$
Id est, $3<\alpha^6<4.$ :)

As in the previous posts, we have that the original condition re-writes as

$\frac{a(a^6+1)}{a^2+1}=2$, from this we have that $a>0$, since $\frac{a^6+1}{a^2+1}>0$...

now, from am-gm we have that $\frac{a^6+1}{2}\geq\frac{a(a^6+1)}{a^2+1}=2 \Rightarrow a^6\geq 3$

now, we want to prove that
$4>a^6 \Leftrightarrow \frac{5a}{a^2+1}>\frac{a(a^6+1)}{a^2+1}=2 \\\Leftrightarrow 0>2a^2-5a+2=(a-2)(2a+1) \Leftrightarrow 0>a-2 \Leftrightarrow \frac{a(a^6+1)}{a^2+1}=2>a \\\Leftrightarrow a^6>a^2\Leftrightarrow a>1 \Leftrightarrow (a-1)(a^3(a+1)+1)>0$
but $(a-1)(a^3(a+1)+1)=1>0$, so we're done  :D

[quote="Maharjun"][hide="click to see solution"]
if $ \alpha$ is a real root of $ {x^5} - {x^3} + x - 2 = 0$

$ \&  \implies {\alpha ^5} - {\alpha ^3} + \alpha  - 2 = 0  \\
  \&  \implies \alpha \left( {{\alpha ^4} - {\alpha ^2} + 1} \right) = 2  \\
  \&  \implies \alpha \frac{{\left( {{\alpha ^6} + 1} \right)}}
{{{\alpha ^2} + 1}} = 2 \implies {\alpha ^6} = \frac{{2\left( {{\alpha ^2} + 1} \right)}}
{\alpha } - 1 $

$ \implies \alpha \ne 0$

$ \because \alpha \in {\bbc R} \implies \alpha^6 >0$

$ \& \therefore \frac{{2\left( {{\alpha ^2} + 1} \right)}}
{\alpha } - 1 > 0 \implies \frac{{2\left( {{\alpha ^2} + 1} \right)}}
{\alpha } > 1 > 0  \\
  \& \because 2\left( {{\alpha ^2} + 1} \right) > 0  \\
  \&  \implies \frac{1}
{\alpha } > 0 \implies \boxed{\alpha  > 0} $

$ \because 2\left( {{\alpha ^2} + 1} \right) \ge 4\alpha \implies \frac{{2\left( {{\alpha ^2} + 1} \right)}}
{\alpha } \ge 4 \implies \frac{{2\left( {{\alpha ^2} + 1} \right)}}
{\alpha } - 1 \ge 3 \implies \boxed{ \alpha^6 \ge 3}$

$ \&  \implies {\alpha ^5} - {\alpha ^3} + \alpha  - 2 = 0  \\
  \&  \implies {\alpha ^5} + \alpha  = {\alpha ^3} + 2  \\
  \&  \implies \alpha \left( {{\alpha ^4} + 1} \right) = {\alpha ^3} + 2  \\ \\
  \& \because \alpha  > 0  \\ \\
  \&  \implies \alpha \left( {{\alpha ^4} + 1} \right) \ge 2{\alpha ^3}.  \\ \\
  \& \because \alpha  \ne  \pm 1 \implies {\alpha ^4} \ne 1{\text{   }}\left[ {{\text{Easy to check by substituting}}} \right]  \\ \\
  \&  \implies \alpha \left( {{\alpha ^4} + 1} \right) = {\alpha ^3} + 2 > 2{\alpha ^3}  \\
  \&  \implies {\alpha ^3} < 2 \implies \boxed{{\alpha ^6} < 4} $

$ \boxed{\left[\alpha^6\right] = 3}$

[b]Q.E.D[/b]
[/hide][/quote]

After proving $\alpha >0$
we can multiply given equation by $\alpha^2 $and add the two equations. So we get$
\alpha(\alpha^6+1) = 2(\alpha^2+1)$
since $\alpha^2+1 \geq 2\alpha $
we get$ \alpha^6+1 \geq 4$.
This implies $\alpha^6 \geq 3$.

note that , if we take $f(x)=x^5-x^3+x-2$ , then $f'(x)=5x^4-3x^2+1=(2x^2-1)^2+x^2+x^4>0$.
so , $f(x)$ is increasing. note that , $f(0)=-2<0$. so , $a>0$.
so , $2=a^5-a^3+a=2=a(a^4-a^2+1)\ge a^3$. it is easy to see that , $a^3=2$ is not possible.
so , $a^6<4$.
now , if possible , assume that ,$a^6<3$.
then $a^6=a^4-a^2+2a<3 \implies a^5-a^3+2a^2<3a \implies a^3-a+2-a^3+2a^2<3a$.
$\implies 1+a^2<2a$, which is a contradiction.
so , $[a^6]=3$ :D

They have modified the 1994 INMO problem
https://artofproblemsolving.com/community/c6h54867p341783

We observe that the primitive $6$th roots of unity are roots and factor the quintic as $(x^2-x+1)(x^3+x^2-x-2)$

There is only one real root, and that is the root of the cubic factor.

We set $y=x^3$ and then $z=y^2$ and get:
\[y+y^{2/3}-y^{1/3}-2=0\implies y^{1/3}=\frac{1\pm\sqrt{9-4y}}{2}\implies y=\frac{7-3y\pm (3-y)\sqrt{9-4y}}{2}\implies(5y-7)^2=(3-y)^2(9-4y)\implies y^3-2y^2+5y-8=0\]

\[z\sqrt{z}-2z+5\sqrt{z}-8=0\implies (z+5)\sqrt{z}=2z+8\implies(z+5)^2z=(2z+8)^2\implies z^3+6z^2-7z-64=0\implies (z+2)^3-19(z+2)-34\]

The latter cubic has only one real root as the turning points are at $3(z+2)^2-19=0\implies z+2=\pm\sqrt{\frac{19}{3}}$ where the cubic is $-34\mp\frac{2}{3}\sqrt{\frac{19}{3}}<-32$.

We now check the cubic at $z=4$ and $z=3$.

$4^3+6\cdot 4^2-7\cdot 4-64=68>0$ and $3^3+6\cdot 3^2-7\cdot 3-64=-4<0$. Hence $3<a^6<4$ and $\lfloor a^6\rfloor=3$.

The given condition is equivalent to
$$\alpha^{6}=\alpha^{4}-\alpha^{2}+2\alpha=\alpha^{4}-(\alpha-1)^{2}+1$$ $$\Leftrightarrow (\alpha^{2}-1)(\alpha^{2}+\alpha+1)(\alpha^{2}-\alpha+1)=(\alpha^{2}+\alpha-1)(\alpha^{2}-\alpha+1)$$
Thus, either $\alpha^{2}-\alpha+1=0$, which yields no real root, or $(\alpha^{2}-1)(\alpha^{2}+\alpha+1)=\alpha^{2}+\alpha-1 \Leftrightarrow \alpha^{3}+\alpha^{2}-\alpha-2=0$, since $\alpha=0$ is not a root.
Now set $f(x)=x^{2}+x^{2}-x-2$. We can easily construct its graph and observe that $f(x)<0$ when $x \le \frac{1}{3}$ and is monotonically increasing after this value. (this can also be easily proved using some basic calculus)
Now, set $\alpha=\sqrt[6]{3}$ and observe that
$$f(\alpha)=\sqrt{3}+\sqrt[3]{3}-\sqrt[6]{3}-2 \approx 1.73 + 1.4 -1.2 -2 <0$$
Now set $\alpha=\sqrt[6]{4}$ and observe that
$$f(\alpha)=\sqrt{4}+\sqrt[3]{4}-\sqrt[6]{4}-2 =\sqrt[3]{4}-\sqrt[6]{4} >0$$
Hence, the only real root of $f(x)$ lies in the interval $(\sqrt[6]{3},\sqrt[6]{4})$ and hence $\lfloor \alpha^{6} \rfloor =3$.
Q.E.D. :D

I guess the easiest way to do this is by showing that a real number greater than 1.25 (or better approximation) cannot be the root of the polynomial. With 1.25 Newton root approximation can be used to get a good approx for the solution. When you see a constant decimal for two to three decimal places you can take it to it’s sixth power and prove that it is less than three.


[quote]Consider $ (a_n)_{n\geq1}$, $ (b_n)_{n\geq1}$, $ (c_n)_{n\geq1}$ defined by:
$ \left\{\begin{array}{{{c}{cccc}a_{n+1}=\frac{1}{2}(b_n+c_n}\
\
b_{n+1}=\frac{1}{2}(c_n+a_n})\
\
c_{n+1}=\frac{1}{2}(a_n+b_n)\end{array}$

Prove that the three rows have the limit $ \frac{1}{3}(a_1+b_1+c_1)$[/quote]

We know what the eigenvectors and eigenvalues of [url=http://en.wikipedia.org/wiki/Circulant_matrix]circulant matrices[/url] look like; see for example the discussion [url=http://www.artofproblemsolving.com/Forum/weblog_entry.php?t=220351#comments]here[/url].

See also [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?t=227753]here[/url], for example.


modular arithmetic
LaTeX
algorithm
logarithms
quadratics
probability
number theory

Hi,

can anyone please tell me if there is a fast way to determine if a given (large) integer is a square?

Also, can anyone tell me what kind of modulus has the least number of quadratic residues? I'm using P1 x P2 x ... x Pn where the P's are successive primes.

Any internet references to suggest?

thanks

Maybe you could just try taking the square root by hand, and see if it comes out to be an integer.

Filletwho - as fast as possible. I have to test a good number of VERY large squares.

Seamusoboyle - No, the modulus, M, is composite. M = p1 x p2 x ... x pn where these p's are the primes 3, 5, 7... i.e. M is the product of consecutive primes.

When the modulus is composite there are generally less quadratic residues. I'd like to find out if there is a better way to reduce these by finding out how to construct a modulus with the least amount. M = 2^t p1p2p3... might be it.

I need a fast algorythm for a computer to see if it is square.

thanks

If you're using a computer, then just use the if statement
if(sqrt(x)==int(sqrt(x)))

[quote="seamusoboyle"]Are quadratic residues are just the squares $(mod$ $p)$???
It can be proven that there are $\displaystyle\frac{p-1}{2}$ sqaures $(mod$ $p)$ with $p$ $prime \geq 3$[/quote]
You can use command [b]\pmod{p}[/b] to produce $\pmod{p}$

Myth, yes, but I'm not using a prime. The Modulus is composite so there will be less residues. This is deliberate because I need to reduce computing time. What I'm looking for is how to define a composite modulus with the VERY LEAST number of quadratic residues.

Yes, if floor(sqrt(n)) == sqrt(n) it is a square of an integer. That's what I'm using but it's too slow for very large squares and there is a great number of them so I thought there might exist a faster way to check, perhaps using modular arithmetic.

thanks

Actually, it was a hint related to $\LaTeX$. It doesn't concern your problem. ;)

mgb, how big are the integers you are checking for squareness?  Also, about how many integers are you checking?

The first thing you would check is the last digit, but if it's not that obvious, try factoring it, it's what I always do and it takes a couple of seconds. Another thing you could do is estimate what the square could be and square that number. If you're lucky, that method would work faster with guess and check.

In my opinion we can quickly compute a square root even for quite large numbers (I mean $\sim 10^3-10^4$ digits).

ok Myth, thanks for the clarification. Yes, checking the last 2 digits would eliminate some of them. The squares are anything from 2^2 to 10000000000000000000000000^2 or more. There's no limit. And I don't know how large it is when the program is running. They are chosen from a start point and from there on the get bigger and there may be a large amount of integers to check.

I recently saw a prog. in c on testing for perfect squareness but I need the mathematics so I can do my own. Can anyone recommend a Number Theory site which might help?

thanks again

Before we talk about square roots, how are you planning to store and do arithmetic on such large-precision integers?  Are you using a particular arbitrary-precision library?

Is this program for a contest or just for fun?

It is a usual task I give to my students to implement large arithmetic. They store data in dynamic arrays of integer type. And when I talk about square roots I mean that we can easily compute the integer part of it.

Ravi B,

if the integers fail to be square they are discarded. No need to store them. The prog. I'm using now is just up to 20 or 30 or so digits but I'll have to figure out how to work with very large squares eventually. It's not a contest, it is a problem I have found a solution to but which is too slow from a computational point of view. I need to find a VERY fast way to test for squareness...

Sorry, when I said store the integers, I didn't mean permanently store them.  I just meant how are you representing the integers?  Most conventional systems let you represent integers up to only 10 digits or so, unless you use a special package.  But I'll assume you have the arithmetic package worked out already.

Regarding square roots, have you tried implementing Newton's method?  For integers with $d$ digits, that will require on the order of $\log_2 d$ iterations to converge.

Is it a floating point or an integer valued algorithm? Tell us, please!

Newton's method is usually stated for floating-point numbers, but you can adapt it for integers by rounding at each step.  Suppose we are trying to find the (integer) square root of n.  Let x be our current guess.  Then at each step we replace x by the nearest integer to $\frac{x + n/x}{2}$.  Stop when you get the same number again (or 1 away from the previous guess).

Unfortunately, division is a quite computationaly intense operation. It requires many steps to perform.

Could you take advantage of squares you already know of from previous computations? :D

I would suggest going forwards instead of backwards.  Just have it store 1^2, 2^2, 3^2, 4^2, rather than going through the integers to find them.  If the multiplication gets slow, then you could do $a_{n+1}=a_n+2n+1$

It's a floating point. I'm using long values in Java for test purposes but a programme for very large numbers will require something else because Java can only deal with 20-digit input.

Yes, Newtons method seems promising. I'll check that one out...

Yes, storing squares is a good answer but how to store gazillions of them?!

I have found some interesting things on the internet. Here's one-

http://documents.wolfram.com/v4/AddOns/StandardPackages/NumberTheory/NumberTheoryFunctions.html

and here's another-

http://www.mathpages.com/home/kmath265.htm

thanks again to all

Hmmm, could you use the fact that

$\displaystyle \sum^n_{i=0} (2i+1)=n^2$???
If your number lies between two different successive values for $n$ its not a square...

Hmmmmm indeed! That is worth thinking about. Thanks...

[quote="JBL"][quote="filletwho"]try factoring it, it's what I always do and it takes a couple of seconds.[/quote]

I think you're missing the point that he's asking about really, really big numbers -- probably numbers with as many digits as the numbers that you factor quickly.  Factoring is a very very slow process for numbers of even a few digits, certainly not an effective way to test squareness when other options are available.[/quote]

I guess, but it's faster than calculating the square root by hand method they teach you in school.

[quote="filletwho"]I guess, but it's faster than calculating the square root by hand method they teach you in school.[/quote]

For very very large cases, it may not be. Think of a 200 digit number that has 2 very large prime factors. You'll be dividing by primes until you go mad.

Does it require a perfect success rate? What if you just check factors of the first, say, 40 primes?  Then again, why don't you just always say it's not a perfect square? :D

I may have a solution. If n is a square it must yield a quadratic residue for each prime p. Including zero there are (p + 1)/2 quadratic residues for each prime, p.

Take about 50 small primes between 1 and 200. Call these P1, P2, P3, ... P50.

Now, suppose n is not square, it may still produce a QR mod p for any of these primes. The chances are about 1/2.

So,

n = q ( mod P1 ) Chances that q is Quadratic Residue = 1/2

n = q2 ( mod P2 ) Chances that q2 is Quadratic Residue = 1/2

1/2 x 1/2 = 1/4

n = q3 ( mod P3 ) Chances that q3 is Quadratic Residue = 1/2

1/2 x 1/2 x 1/2 = 1/8

Continue in this way up to P50

The chances of a nonsquare n stubbornly producing quadratic residues for all 50 primes is 1 / 2^50 which is a very small fraction. If n is square it must produce a quadratic residue for all 50 primes.

This means that only 1 in 2^50 values of n need to be properly checked for squareness because if it fails to produce a quadratic residue for only 1 of the 50 primes it cannot be square.

Can it be this simple or am I missing something?

I'd be interested if anyone has the time and inclination to write a programme to test this and see how long it will take for the largest possible values for n to process in Milliseconds.

If you use Euler's Criterion to test if q is a quad. res. you need to check first if q = 0 because E. Criterion will not operate for zero. If it is zero you can take it that it is a quadratic residue.

Most nonsquare values for n should return false after only a few primes. e.g. only 1 in 64 will get as far as P6.

*************************************

I tried this and it works very well. I used only 10 primes and all of the nonsquares were rejected. It tests a 20 digit number in a few milliseconds so it's very fast.

An interesting point in all of this is if n = q ( mod p ) and q = 0 then p divides n.

If n is square p^2 divides n also because in a square its prime divisors occur to an even exponent. If p^2 does not divide n it cannot be square so it can be rejected on this count alone.

probability 1.01 -

no it dosen't require a perfect success rate - 99% would do very well, but as you can see, this method outlined above is even higher than this.

Whoa, don't post 3 times in a row.  Use the edit button.  I'm going to go back and edit your posts into one.


geometry
inequalities
inequalities solved

Let ABC be a triangle with area 1/4 and sides u,v,w. Prove that for any a,b,c>0 such that ab+bc+ca=1 we have the inequality:
  au^2+bv^2+cw^2>=1.

This one can be generalized as follow
     Let m,n,p are positive numbers. Prove that
           ma^2+nb^2+pc^2>=4* \sqrt (mn+np+pq)*S.
     Here is the proof
           By replacing c^2= a^2+b^2-2abcosC, we have
        (m+p)a^2+(n+p)b^2-2pabcosC>=2 \sqrt [(m+p)(n+p)] ab-2abcosC >=4* \sqrt (mn+np+pq)*S since S=1/2*absinC. :)  :)

Treegoner, can you please explain your inequality

\sqrt (m+n)(n+p) -pcosC \geq  \sqrt (mn+np+pm) senC

Thank you, very much.

You have that |acosx+bsinx|<= \sqrt (a^2+b^2) :D


modular arithmetic
induction
number theory unsolved
number theory

Prove that for every integer power of 2, there exists a multiple of it with all digits (in decimal expression) not zero.

More precisely, it is well-known (and probably already solved here) that fro each positive integer $n$, there exist a integer whose decimal expansion only uses digits $1$ or $2$ and which is divisible by $2^n.$

Pierre.

Ya...we look for a number of the form $1111\cdots12$ with $k+1$ digits.This number is precisely of form $10^k+10^{k-1}+\cdots+10+2=2(5\times \frac{10^k-1}{9}+1)$ so we have to choose a $k$ such that $5(10^k-1)+9 \equiv 0\pmod{2^n}$.But clearly there exists such $k$.(Basically we are solving the system of congruences modulo $2^n$ which is 9=-1 modulo 5.There are infinetely many such triples.Then we solve the congruence $10^k-1 \equiv t\pmod{2^n}$ where $t$ is one such solution).

[quote="sayantanchakraborty"]But clearly there exists such $k$.(Basically we are solving the system of congruences modulo $2^n$ which is 9=-1 modulo 5.There are infinetely many such triples.Then we solve the congruence $10^k-1 \equiv t\pmod{2^n}$ where $t$ is one such solution).[/quote]

BUT This is ABSOLUTELY FALSE!!! :wink:
how about $k$ if $n=4, 5, 6$

pbornszstein gave a correct hint, I will only elaborate it. The hint is well-known too, so don't make a mistake that any of this is mine, the idea is taken from some book(s). Anyways induction works. We need something more. We claim we can find a $n$-digit solution actually. Suppose we have a $n$-digit integer consisting of only $1,2$ that is divisible by $2^n$. Let it be $a_n$. Now suppose $2^{n+1}\mid a_n$. Then we will append a $2$ before $a_n$ and define it to be $a_{n+1}$ , and if that is not the case then we append a $1$, and call it $a_{n+1}$. To understand this :
$a_1=2\mapsto a_2=12\mapsto a_3=112\mapsto a_4=2112\mapsto a_5=22112\mapsto \cdots$
 I hope the idea is clear now. So the induction finishes the proof.


Let x,y,z>0 such that $ xyz\equal{}1$
Prove that: $ \frac{1}{x\plus{}2}\plus{}\frac{1}{y\plus{}2}\plus{}\frac{1}{z\plus{}2}\leq 1$.

After multiplying everything out what is to be proved is:
$ xy\plus{}yz\plus{}zx\geq 3$, which is obviously trrue considering Am-GM:
$ xy\plus{}yz\plus{}zx\geq 3\sqrt[3]{xy*yz*zx}\equal{}3$ :wink:

Do you have a nice solution ? It isn't necessary to multiply everything  :roll:

[quote="rofler"]Jensen's

[hide]
$ \frac {\frac {1}{x \plus{} 2} \plus{} \frac {1}{y \plus{} 2} \plus{} \frac {1}{z \plus{} 2}}{3}\leq\frac {1}{\frac {x \plus{} y \plus{} z}{3} \plus{} 2}\leq\frac {1}{3}$[/hide][/quote]

[hide="I think you are wrong."]$ \frac {\frac {1}{x \plus{} 2} \plus{} \frac {1}{y \plus{} 2} \plus{} \frac {1}{z \plus{} 2}}{3}\leq \frac {1}{\frac {x \plus{} y \plus{} z}{3} \plus{} 2}$
$ \Leftrightarrow (\frac {1}{x \plus{} 2} \plus{} \frac {1}{y \plus{} 2} \plus{} \frac {1}{z \plus{} 2})\frac {x \plus{} y \plus{} z \plus{} 6}{3}\leq 3$
$ \Leftrightarrow (\frac {1}{x \plus{} 2} \plus{} \frac {1}{y \plus{} 2} \plus{} \frac {1}{z \plus{} 2})((x \plus{} 2) \plus{} (y \plus{} 2) \plus{} (z \plus{} 2))\leq 9$ ???[/hide]
And now, who can solve this problem and don't need to multiply everything?

[hide="I hope this is nice enough..."]Note that $ f(x) = \frac {x}{t + x} = 1 - \frac {t}{t + x}$ is strictly increasing for $ t > 0$. Now we have $ \frac {1}{x + 2} = \frac{x^{-\frac{1}{3}}}{x^\frac{2}{3}+2x^{-\frac{1}{3}}}$. Now $ 2x^{-\frac{1}{3}} = 2\frac{(xyz)^\frac{1}{3}}{x^\frac{1}{3}} = 2(yz)^\frac{1}{3}\le y^\frac{2}{3}+z^\frac{2}{3}$. This means that $ \frac{1}{x+2} \le \frac{y^\frac{2}{3}+z^\frac{2}{3}}{2(x^\frac{2}{3}+y^\frac{2}{3}+z^\frac{2}{3}})$. Summing cyclically, we get the desired result.[/hide]

[hide="Jensens does work, but..."] The function we want is $ f(x) \equal{} \frac{1}{e^x \plus{} 2}$, which is concave, not convex.  Use $ a \equal{} \ln x, b \equal{} \ln y, c \equal{} \ln z$.  :) [/hide]

[quote="natural"]Who can help me? I want a nice solution :D[/quote]

I might say something meaningless to the topic, but I think that when the computations are bearable (such as here) and when they make the problem completely trivial is there any rational argument that votes for looking for non-standard ways? :roll:  :wink:

Looking for a nice solution has the advantage that you have to "think out of the box", which in turn makes the solution of non-bashable problems easier. ;)

I don't see what's wrong with rofler's solution. $ \frac{1}{x\plus{}2}$ is convex.

Maybe he wants to restrict the numbers to $ >0$ as required by the problem...

[quote="bertram"] Now $ 2x^{ \minus{} \frac {1}{3}} \equal{} 2\frac {(xyz)^\frac {1}{3}}{x^\frac {1}{3}} \equal{} 2(yz)^\frac {1}{3}\le y^\frac {2}{3} \plus{} z^\frac {2}{3}$..[/hide][/quote]
I don't think it's right! You should check it again and see if it's reverse :wink:
Here's my solution!Hope it's the nicest solution :roll:
Let x=a/b,y=b/c and z=c/a
We have the inequality rewritten as following:
b/(a+2b) +c/(b+2c) +a/(c+2a)=<1
It's equivalent to prove this inequality: a/(a+2b) + b/(b+2c) +c/(c+2a)>=1/2
Using Cauchy-Schwartz's inequality we have: LHS>=(a+b+c)^2/(sigma a^2+2sigma(ab))
Now it's sufficient to prove:(a+b+c)^2/(sigma a^2+2sigma(ab))>=1/2
Clearing denominators and simplifying we have: a^2+b^2+c^2>=ab+bc+ac, which is obviously true!
That leads to the conclusion we need!

[quote="ghjk"][quote="bertram"] Now $ 2x^{ \minus{} \frac {1}{3}} \equal{} 2\frac {(xyz)^\frac {1}{3}}{x^\frac {1}{3}} \equal{} 2(yz)^\frac {1}{3}\le y^\frac {2}{3} \plus{} z^\frac {2}{3}$..[/hide][/quote]
I don't think it's right! You should check it again and see if it's reverse :wink: [/quote]

It's simple AM-GM :O

Rofler's solution uses Jensen the wrong way around; if we plug in $ (x,y,z) \equal{} (100,1,0.01)$ we see that the inequality does not hold.

[quote="bertram"] This means that $ \frac {1}{x + 2} \le \frac {y^\frac {2}{3} + z^\frac {2}{3}}{2(x^\frac {2}{3} + y^\frac {2}{3} + z^\frac {2}{3}})$.[/hide][/quote]
Sorry, I MEANT THIS PART! :blush:

We know from AM-GM that

$ xy+yz+zx \geq 3\sqrt[3]{xy \cdot yz \cdot xz}$.

So,

$ xy+yz+xz \geq 3$, since $ xyz=1$.

Adding terms to both sides gives us

$ xz+yz+xy+4z+4x+4y+12 \leq xyz+2xz+2xy+2yz+4x+4y+4z+8$.

Factoring, we get

$ (x+2)(y+2)+(x+2)(z+2)+(y+2)(z+2) \leq (x+2)(y+2)(z+2)$.

Dividing by $ (x+2)(y+2)(z+2)$ gives us

$ \frac{1}{z+2}+\frac{1}{y+2}+\frac{1}{x+2} \leq 1$,

as desired.

-------

I got this proof from working backwards and reversing the steps

at the end. It requires some multiplication but the Algebra isn't too

bad here.

Lol, I think we all know the bash solution, but he asked us afterwards to give a NON-BASH solution.

Thank you t0rajir0u, I forgot completely about that substitution ( I knew jensen's worked, but $ \frac {f(a) \plus{} f(b) \plus{} f(c)}{3}\le f((abc)^{\frac{1}{3}})$ didn't exactly fit the bill)

[quote="Daan"][quote="worthawholebean"]I don't see what's wrong with rofler's solution. $ \frac {1}{x \plus{} 2}$ is convex.[/quote]

I don't see the problem either. Looks like a nice solution.[/quote]

The problem is that the first inequality is actually reversed. Just make $ x$ really large, then the RHS goes to zero while the LHS is more than 1/2.


algebra polynomial quadratics Vieta function AMC AIME

Let $P(x)$ be a polynomial with integer coefficients that satisfies $P(17)=10$ and $P(24)=17$. Given that $P(n)=n+3$ has two distinct integer solutions $n_1$ and $n_2$, find the product $n_1\cdot n_2$.

[hide="solution"]let $P(x)=(x-17)(x-24)q(x)+r(x)$

$r(x)$ has a degree less than 2 because we divided a 2nd degree polynomial, and that is the remainder, so let $r(x)=ax+b$

using $P(17)=10$ and $P(24)=17$, we get $a=1$ and $b=-7$

so $P(x)=(x-17)(x-24)q(x)+x-7$, to find the roots, we have

$(n-17)(n-24)q(x)+n-7=n+3$ note that since there are 2 distinct integer roots to that, it is a second degree polynomial, and that makes $q(x)$ have a degree of 0, otherwise, there would be a higher degree

since $q(x)$ has a degree of 0, let $q(x)=c$

so we are solving $c(n-17)(n-24)-10=0$ or

$n^2-41n+17*24n-\frac{10}{c}=0$

using the quadratic formula, and simplifying

$x=\frac{41\pm\sqrt{49+\frac{40}{c}}}{2}$

we know that $c$ is an integer because if we multiply out $P(x)$, then $a$ is the lead coefficient, so it must be an integer

also, we know that $c$ divides 40 (otherwise it will not be rational) and the square root has to reduce to an integer, and we see that it occurs when $c=-1$

by vieta's formulas, the constant term is the product of the roots, so $17*24-\frac{10}{-1}=\boxed{418}$[/hide]

[hide="Another solution"]Because $P(x)\in\mathbb{Z}[x]$, we know that $a-b | P(a)-P(b)$, for all $a,b\in\mathbb{Z}$. Therefore, for every $n$ such that $P(n) = n+3$, we have that, $n-17 | P(n)-P(17) = n-7$, so $\exists a\in\mathbb{Z}: n-7 = a(n-17)$. Similary, $\exists b\in\mathbb{Z}: n-14 = b(n-24)$.
So now remark that $10 \equiv 17a-7 \equiv n(a-1) \equiv 0\mod{a-1}$, so $a-1 | 10$ and similary $b-1 | 10$. Therefore, $a,b \in\{-9,-4,-1,0,2,3,6,10\}$.
Now plugging all those values of $a$ into $n-7 = a(n-17)$, we get the values $n\in\{16,15,12,7,27,22,19,18\}$. And for the values of $b$ we get $n\in\{23,22,19,14,34,29,26,25\}$.
The only two solutions that are in both solution sets are 19 and 22, so the answer is $19\cdot 22 = 418$.[/hide]

[quote="usaha"]Wait,  im confused..how did you get the 49 in the quadratic formula :blush:[/quote]

i just used the quadratic formula...(i did not condense the n^1 coefficient)

[hide="Took about a minute to figure out"]
Consider $ g(n)\equal{}f(n)\minus{}n$; then $ g(n_1)\equal{}g(n_2)\equal{}3$ for some integers $ n_1,n_2$, and $ g(17)\equal{}g(24)\equal{}\minus{}7$. For any $ m\in\{n_1,n_2\}$:\[ m\minus{}17|g(m)\minus{}g(17)\equal{}10\qquad m\minus{}24|10\]Thus, for $ k\equal{}m\minus{}24$, both $ k$ and $ k\plus{}7$ divide $ 10$. Clearly $ k\in\{\minus{}5,\minus{}2\}$, thus $ m\in\{19,22\}$ thus $ n_1n_2\equal{}19\cdot22\equal{}\boxed{418}$
The hardest part was definitely the multiplication at the end :P
[/hide]

um i actually think that the other solutions were simpler but what do i know. some one should lock this thread

Wow I overdid this initially...:
Create a new second degree function and call it Q(n)
Q(n)=P(n)-n-3.
Since Q(n) is equal to 0 when n is equal to n1 or n2,
Q(n)=C(n-n1)(n-n2).
Now, plug in n =17 and n=24.
Q(17)=10-18-3=-10
Q(24)=17-24-3=-10
So -10=C(17-n1)(17-n2)
and -10=C(24-n1)(24-n2)

Now, set them equal so (17-n1)(17-n2)=(24-n1)(24-n2).
If you just factor them out and combine like terms, youll notice 7(n1+n2)=24^2-17^2.  So n1+n2=41, WLOG, assume n1<n2 (since n1*n2 is what we need to find)
Since n1 and n2 are integers, they are (20,21), (19,22), (18,23)...

Also, notice that C has to be integer since Q(n) has integer coefficients (since P(n) has integer coefficients), so (17-n1)(17-n2) has to divide -10
So if we just try some of those cases, youll notice that (19,22) when plugged in for n1 and n2 does divides -10, so its 19 and 22, 19*22=418.

We dont need to try many cases if you really want to check (once we get past n2=27, we know itll be bigger than 10 since 17-27 is 10)

^This was an old AIME problem linked to the contest section, you cant lock this, plus AIMEs on Tuesday.

Wait, what's wrong with this solution.

[hide="Solution"]
Since we are given two values of $x$ for which $P(x) = x-7$, we can consider the polynomial $P(x) - (x-7)$. This polynomial has roots 17 and 24, so we can build a quadratic with these very roots: $P(x) - (x-7) = x^2-41x+17\cdot24$. Adding $x-7$ to both sides gives $P(x) = x^2-40x+17\cdot24-7$.

Now, we consider the values of $P$ such that $P(x)=x+3$. This only occurs when $x$ is a root of $P(x)-(x+3)$, or when $x$ is a root of $x^2-41x+17\cdot24-10$. The product of the roots of this polynomial is the answer we are looking for, or $17\cdot24 - 10 = \boxed{398}$.

Now, I'm not sure if we can exactly use the quadratic argument... can someone provide reasoning against that if so? Or are my signs messed up and I should have added 10 instead of subtracting?
[/hide]

The solutions here are not integers.  You must have $a(x^2-41x+17\cdot 24)+(x-7)$ for some integer $a$; you choose $a$ based on the fact that the solutions $n_1$ and $n_2$ are integers.  In fact you must choose $a=-1$, so that your quadratic is instead $-x^2+42x-17\cdot 24-7$.  You can finish the solution from here, correct?

@Lord.of.AMC: When we did this AIME for practice at a camp I went to, about 9 people (myself included) made the same mistake you did... But yeah, tennis is correct in that the solutions are not integers.

Note: This was 2005 AIME II Problem 13.

[hide="Sketchy solution"]
We write $P(x) - x +7 = (x-17)(x-24)Q_1(x) \implies P(x) = (x-17)(x-24)Q_1(x) + x-7$ We set this equal to $P(x) - x - 3$ to get $P(x) = (x-17)(x-24)Q_1(x) + x-7 = (x-n_1)(x-n_2)Q_2(x) + x +3$. Rearranging, we have \[(x-17)(x-24)Q_1(x) = (x-n_1)(x-n_2)Q_2(x) + 10.\] Let $x = 17$ to get $(17-n_1)(17-n_2)Q_2(17) = -10$ and set $x = 24$ to get $(24-n_1)(24-n_2)Q_2(24) = -10$. Now, since $P$ has integer coefficients, each of these terms must be a divisor of $10$, not necessarily positive.

We can say $17-n_1 = a$ and $24-n_1 = b$ so $b-a = 7$. Since $b,a\mid 10$, then one possible solution is $a = -2, b = 5$. This means that $n_1 = 19$. Now, we say $17-n_2 = c$ and $24-n_2 = d$ so $d-c = 7, d,c\mid 10$. Clearly we can't have $c = a$ and $b = d$, so we instead have $c = -5, d = 2$. This implies $n_2 = 22$, so the product is $19 \cdot 22 = \boxed{418}$
We just need to verify that there actually exists such a polynomial $Q_2$ such that $Q_2(17) = -1$ and $Q_2(24) = -1$, which it does since $Q_2(17) + 1 = a(x-17)(x-24)$ is a solution
[/hide]

If the polynomial has an integer coefficient, than this equation is valid. $x-y | P(x)-P(y)$
By given condition, we can know that $n-17 | n-7 $ and $n-24 | n-14$
If we make this clear, we can get $n-17 | 10$ and $n-24 | 10$
The possible value for $n$ that satisfy $n-17 |  10$ is $27, 22, 19, 18, 16, 15, 12, 7$ and only $22,19$ satisfy the both equation.
  So, the product of the $n_1, n_2$ is $19 \cdot 22 = \boxed{418}$

[quote=theax]I know that this is an extremely old topic, but I happened upon this question and I don't really get an aspect of Altheman's solution:

[quote]$ (n \minus{} 17)(n \minus{} 24)q(x) \plus{} n \minus{} 7 \equal{} n \plus{} 3$ note that since there are 2 distinct integer roots to that, it is a second degree polynomial, and that makes q(x) have a degree of 0, otherwise, there would be a higher degree [/quote]

Doesn't it only mean that since there are two distinct solutions to the equation, that the polynomial is at least a quadratic?

  PLEASE HELP!!!![/quote]

Again, sorry for the very old bump, but like the quoted post above, I don't see how $P(x)$ must be exactly quadratic. Can't there be repeated roots or other non integer roots?

p1: Consider a new polynomial, $Q(x) = P(x)-x+7$. Then $Q(x)$ has roots at $17, 24$, so it is in the form $Q(x)=a(x-17)(x-24)$, meaning that $P(x)=a(x-17)(x-24)+x-7$. Setting equal to $x+3$ and factoring gives $a(x-24)(x-17) = 10$. Clearly $\frac{10}{a}$ must be an integer, so testing factors of $10$ shows that $-1$ works, with roots $19,22 \implies \boxed{418}$.

Let $Q(x)=P(x)-(x-7)=a(x-17)(x-24)$. So, $P(x)=a(x-17)(x-24)+(x-7)$. This should be equal to $x+3$ at our two roots. We have that $a(x-17)(x-24)+(x-7)=x+3$, implying that $(x-17)(x-24)=\frac{10}a.$ We see that $a=-1$ works with roots at $19$ and $22$, whose product is $\boxed{418}$.

Alternatively, if you want to do this rigorously without assuming $Q$ is a quadratic (the answer will be the same even if it isn't a quadratic), use the Difference of Polynomials Theorem.

The key is to use the fact that $n_1-k|P(n_1)-P(k)$ and from there it is just number theory. Indeed, we have that $n_1-17|n_1+3-10=n_1-7$ and $n_1-24|n_1+3-17=n_1-14.$ Hence $n_1-17|10,$ $n_1-24|10.$ These two numbers differ by 7-- in particular, only 2,-5 or -2,5 work, yielding $(n_1,n_2)=(19,22)$ in some order for a final answer of $\boxed{418.} \blacksquare$


Simplify, where a, b, c, d, t are real numbers such that the following expression will never be undefined.

$\frac{3ac^2+6tc^2+3acd+6tcd+3ad^2+6td^2}{ac^3+2tc^3-ad^3-2td^3}$


geometry
circumcircle
algebra
polynomial
parallelogram
number theory
relatively prime

[b]Day 1[/b]

Problem 1.

Let $n$ be an integer greater than 1. For a positive integer $m$, let $S_{m}= \{ 1,2,\ldots, mn\}$. Suppose that there exists a $2n$-element set $T$ such that
(a) each element of $T$ is an $m$-element subset of $S_{m}$;
(b) each pair of elements of $T$ shares at most one common element;
and
(c) each element of $S_{m}$ is contained in exactly two elements of $T$.

Determine the maximum possible value of $m$ in terms of $n$.

Problem 2.

Let $A_{1}A_{2}A_{3}$ be an acute triangle, and let $O$ and $H$ be its circumcenter and orthocenter, respectively. For $1\leq i \leq 3$, points $P_{i}$ and $Q_{i}$ lie on lines $OA_{i}$ and $A_{i+1}A_{i+2}$ (where $A_{i+3}=A_{i}$), respectively, such that $OP_{i}HQ_{i}$ is a parallelogram. Prove that
$\frac{OQ_{1}}{OP_{1}}+\frac{OQ_{2}}{OP_{2}}+\frac{OQ_{3}}{OP_{3}}\geq 3$.

Problem 3.

For a positive integer $n$, let $S$ denote the set of polynomials $P(x)$ of degree $n$ with positive integer coefficients not exceeding $n!$. A polynomial $P(x)$ in set $S$ is called [i]fine[/i] if for any positive integer $k$, the sequence $P(1),P(2),P(3), \ldots$ contains infinitely many integers relatively prime to $k$. Prove that at least 71% of the polynomials in the set $S$ are fine.

[b]Day 2[/b]

Problem 4.

Consider the polynomials
$f(x) =\sum_{k=1}^{n}a_{k}x^{k}$  and  $g(x) =\sum_{k=1}^{n}\frac{a_{k}}{2^{k}-1}x^{k}$,
where $a_{1},a_{2},\ldots,a_{n}$ are real numbers and $n$ is a positive integer. Show that if 1 and $2^{n+1}$ are zeros of $g$ then $f$ has a positive zero less than $2^{n}$.

Problem 5.

Find all finite sets $S$ of points in the plane with the following property: for any three distinct points $A,B,$ and $C$ in $S,$ there is a fourth point $D$ in $S$ such that  $A,B,C,$ and $D$ are the vertices of a parallelogram (in some order).

Problem 6.

Let $ABC$ be an acute scalene triangle with $O$ as its circumcenter. Point $P$ lies inside triangle $ABC$ with $\angle PAB = \angle PBC$ and $\angle PAC = \angle PCB$. Point $Q$ lies on line $BC$ with $QA = QP$. Prove that $\angle AQP = 2\angle OQB$.

#1 : http://www.mathlinks.ro/Forum/viewtopic.php?p=841269#841269
#2 : http://www.mathlinks.ro/Forum/viewtopic.php?p=841272#841272
#3 : http://www.mathlinks.ro/Forum/viewtopic.php?p=281962#281962
#4 : http://www.mathlinks.ro/Forum/viewtopic.php?p=661463#661463
#5 : http://www.mathlinks.ro/Forum/viewtopic.php?p=841274#841274
#6 : http://www.mathlinks.ro/Forum/viewtopic.php?p=734440#734440


limit
integration
real analysis
real analysis unsolved

I like this one:

Suppose $f \in C^2$ ($R->R$). Does the existence of $\lim_{x->+\infty}f(x)+2f'(x)+f''(x)$ imply the existence
of $lim_{x->+\infty}f(x)$ ?

Let us start with the following problem.
Given diff. equation
$y'+y=g(x),x{\in}{\mathbb{R}}$.
We know that $\lim_{x{\rightarrow}\infty}{g(x)}=a$.Show that every solution of that diff. equation has limit at $\infty$.
Indeed put $y=ze^{-x}$,then we get $z'e^{-x}=g(x)$,so $z(x)=c+\int_{0}^{x}{g(t)e^{t}dt}$,hence
$y(x)=e^{-x}(c+\int_{0}^{x}{g(t)e^{t}dt})$.Using l'Hospitale rule
$\lim_{x{\rightarrow}\infty}{y(x)}=\lim_{x{\rightarrow}\infty}{\frac{c+\int_{0}^{x}{g(t)e^{t}dt}}{e^{x}}} =\lim_{x{\rightarrow}\infty}{\frac{g(x)e^{x}}{e^{x}}}=a$.
To the original problem we have
$\lim_{x{\rightarrow}\infty}{((f+f')+(f+f')')}=a$,so
$\lim_{x{\rightarrow}\infty}{(f+f')}=a$,so
$\lim_{x{\rightarrow}\infty}{f}=a$.


Find the requested value of cot x, if csc x = 12/5

x stands for theta; sorry I'm learning how to use latex

[hide="hint"]
Find what $\text{sin}x$ is then use your pythagorean identity to find $\text{cos}x$. [/hide]


AMC
AIME
geometry
3D geometry
prism
rectangle

I would like to start an AIME leveled marathon.
Solve the problem, and then post a new one.

New Problem: There exists prism with dimensions 3 by 4 by 5. Find volume of the region that contains all the points inside or 1 unit away from the prism.

[hide="Solution"]If I'm not mistaken, it's just $ (3 \minus{} 2)(4 \minus{} 2)(5 \minus{} 2) \equal{} 1 \cdot 2 \cdot 3 \equal{} \boxed {6}$[/hide]
[hide="NP"]In a given circle, the length of diameter $ AB$ is a 2-digit integer. Reversing the digits of $ AB$ gives the length of a perpendicular chord, $ CD$. The distance from their intersection point $ H$ to the center of the circle is a positive rational number. Determine the length of $ AB$.[/hide]

EDIT:this is totally wrong, I think the correct answer is $ \boxed{154\plus{}14\dfrac{2}{3} \pi}$. I got this by adding the volume of the rectangular prisms and the cylinders and the spheres.

There's already one at: http://www.artofproblemsolving.com/Forum/viewtopic.php?t=299143.

This one is not just EASY AIME, the topic is AIME

[hide="Solution"]$ AB\equal{}10x\plus{}y; CD\equal{}10y\plus{}x; HO\equal{}t$
$ [(10x\plus{}y)/2]^2\equal{}[(10y\plus{}x)/2]^2\plus{}t^2$
$ 9\cdot11(x\plus{}y)(x\minus{}y)/4\equal{}t^2\in\mathbb{Q}$
$ x\plus{}y\equal{}11\implies (x,y)\equal{}(6,5)\implies AB\equal{}65$[/hide]
New Problem:
How many ways are there to cover a 3 x 8 rectangle with 12 identical dominoes?
[hide="hint"]There is a recursive solution![/hide]


analytic geometry
geometry
linear algebra
matrix
Pythagorean Theorem
AMC

Triangle $ ABC$ has vertices $ A\equal{}(3,0)$, $ B\equal{}(0,3)$, and $ C$, where $ C$ is on the line $ x\plus{}y\equal{}7$. What is the area of $ \triangle ABC$?

$ \textbf{(A)}\ 6\qquad
\textbf{(B)}\ 8\qquad
\textbf{(C)}\ 10\qquad
\textbf{(D)}\ 12\qquad
\textbf{(E)}\ 14$

[hide]
By the pythagorean theorem, $ AB\equal{}3\sqrt{2}$. We can use 45-45-90 triangles to find that the hieght of ABC, or the distance between AB and x+y=7, is $ 2\sqrt{2}$. Hence, the area is $ \frac{3\sqrt{2} *2\sqrt{2}} {2}\equal{}6\Rightarrow \boxed{A}$
[/hide]

[quote="Illos"]I forgot to divide by 2 on this problem. :wallbash_red:[/quote]

right there with you buddy  :(

[quote="aznlord1337"]Let C be $ (7,0)$ so base is 4 and height is 3 so area is 6.[/quote]Exactly what I did.

[hide="My solution"]
Is rather similar to axnlord's solution, except I first graphed it out, and then set $C=(7,0)$, and now we have $2$ triangles. The smaller triangle's area is $\frac{3\times3}{2}=\frac{9}{2}$, the larger triangle's area is $\frac{7\times3}{2}=\frac{21}{2}$, so we subtract the two areas: ${\frac{21}{2}-\frac{9}{2}=\frac{12}{2}=\boxed{6}=\text{A}}$[/hide]

[quote="tc1729"][hide="trololol"]
Choosing a random point that satisfies $x+y=7$ say $(2, 5)$. The area of the triangle is $\frac{1}{2}|\Delta |$

Where $\Delta$ is the determinant of the $3\times 3$ matrix

\[
\begin{bmatrix}
       1 & 3 & 0           \\[0.3em]
       1 & 0           & 3 \\[0.3em]
       1           & 2 & 5
     \end{bmatrix}
\]

\[ = 1\begin{bmatrix} 0 & 3 \\[0.3em]
2 & 5 \end{bmatrix}-3\begin{bmatrix} 1 & 3 \\[0.3em]
1 & 5\end{bmatrix}\]

$ = 0-3\times 2 - 3(5-3) = -12$
$\implies\text{Area} = \frac{1}{2}|-12| = \boxed{6}$[/hide][/quote]

If I took that long on an AMC #9 (especially this problem), I'd be sad.

@ above it doesn't take all that long to compute the determinant though

Here's what I did:

$x+y=7$ is the same as $y=-x+7$

So there are three points: $(3,0), (0,3)$ and $(x,-x+7)$

I just used "down products - up products"

So, $\text{Area}=\frac{1}{2} |(9+0+0)-(-3x+21+3x+0)| = \frac{1}{2} |-12|=\boxed{6}$

@Above
That is the [url=http://www.artofproblemsolving.com/Wiki/index.php/Shoelace_Theorem]shoelace theorem.[/url] (Of course, it goes by many names)

@2 posts above
Yes, it doesn't take much time to take the determinant of this problem, but compare the first solution (letting C be 7,0) vs the determinant one. I'd still say the first one is faster.
Either way, both posts chose a specific point for C.

yeah a good thing about these problems is that you can just assume the simplest case and it should work if the conditions are met

[hide=solution]The problem statement strongly implies that $C$ can be anywhere on the line, so simply assume $C=(7, 0)$. Then \[[\triangle ABC]=\displaystyle\frac{1}{2}BC\,\text{dist}(A, BC)=\displaystyle\frac{1}{2}(7-3)\text{dist}\left[(3, 0), x\text{-axis}\right]=2\cdot 3=\boxed{\textbf{(A)} ~6}\][/hide]


Can I get score if I wrote a right solution but wrong number from the problem?(problem 3, I looked at number 100 and I think that it's 1 :( )

Assuming that was your only mistake, you should get at least 4 or maybe even 5, since it's such a minuscule error (and has almost nothing to do with actually solving the problem). USAMTS grading is based much more on the ideas behind your answer rather than the answer itself.

By the way, don't worry when you make a mistake - it's quite a common experience. On #2 I had a full solution but completely forgot to mention the case where $ x \equal{} n \minus{} 1$. I'll probably lose a point for that, but I still enjoyed participating in this round.


The number  $1999$  is multiplied by a  $1742$-digit number that has all its digit equal to  $1$. What is the sum of all the digits of the number obtained?

[hide="Not sure"]
Let's call the 1742-digit number $n$.

$2000n$ is simply 22222[1742 2s]...000.
$n$ is simply 11111...[1742 1s],
Now we need to find $2000n-n$.

(1) Look at the last numbers in $2000n-n$ It's:
...2222000-...1111111.

which comes to:
...1110889

(2) Now let's look at the first few digits.  Since there are $3$ more digits in $2000n$ than in $n$,
2222222...-0001111...
which comes to:
2221111...

It's clear that there are $1745$ digits in $1999n$.  From (1), the last 4 digits are $0889$, and from 2, the first 3 digits are $222$.  The rest of the digits (1738) are $1$s.

$2+2+2+0+8+8+9+1738\cdot1$
$=1769$
[/hide]
Yeah...not a great solution...

[hide="another way?"]Just do long multiplication: 111....111 on top, and 1999 on bottom. It's quite a logic game when deciding how many ones there are in the product, but consider how many digits are in the product. [/hide]


trigonometry
function
calculus
derivative
calculus computations

Show that $ 1 \cdot \sin\frac{\pi}{2n}\plus{}3\cdot \sin\frac{3\pi}{2n}\plus{}5 \cdot \sin\frac{5\pi}{2n}\plus{}\cdots\plus{}(2n\minus{}1)\cdot \sin\frac{(2n\minus{}1)\pi}{2n}\equal{}n \csc \frac{\pi}{2n}$.

let $ r\equal{}e^{\frac{i\pi}{2n}}$, so $ r^{2n}\equal{}\minus{}1$

then we want to show $ Im(\sum_{k\equal{}1}^n (2k\minus{}1)r^{2k\minus{}1})\equal{}\frac{n}{Im(r)}$

$ \sum_{k\equal{}1}^n (2k\minus{}1)r^{2k\minus{}1}\equal{}r\sum_{k\equal{}1}^n (2k\minus{}1)r^{2k\minus{}2}\equal{}r\frac{d}{dr}( \sum_{k\equal{}1}^n r^{2k\minus{}1})$

$ \sum_{k\equal{}1}^n r^{2k\minus{}1}\equal{}r\sum_{k\equal{}0}^{n\minus{}1} (r^2)^k\equal{}r\frac{1\minus{}r^{2n}}{1\minus{}r^2}\equal{}\frac{2r}{1\minus{}r^2}$

$ \frac{d}{dr}(\frac{2r}{1\minus{}r^2})\equal{}\frac{2}{1\minus{}r^2}\plus{}\frac{4r^2}{(1\minus{}r^2)^2}\equal{} 2\frac{1\plus{}r^2}{(1\minus{}r^2)^2}$

so if you can show.. $ Im\left(\frac{2r(1\plus{}r^2)}{(1\minus{}r^2)^2}\right)\equal{}\frac{n}{Im(r)}$ you'd be done

Alternatively, let $ \theta \equal{} \pi/(2n)$, and consider the function

$ f(z) \equal{} \minus{} \sum_{k\equal{}1}^n \cos (2k\minus{}1)z$.

Then

$ f'(z) \equal{} \sum_{k\equal{}1}^n (2k\minus{}1) \sin (2k\minus{}1)z$,

where upon evaluating the derivative at $ z \equal{} \theta$ gives the desired sum.  We endeavor to compute $ f(z)$.  To this end, let $ \zeta \equal{} e^{iz}$.  Then

$ f(z) \equal{} \minus{}\frac{1}{2} \sum_{k\equal{}1}^n (\zeta^{2k\minus{}1} \plus{} \zeta^{\minus{}(2k\minus{}1)}) \equal{} \minus{}\frac{1}{2} \sum_{k\equal{}\minus{}n\plus{}1}^n \zeta^{2k\minus{}1}$

$ \equal{} \minus{}\frac{\zeta^{2n} \minus{} \zeta^{\minus{}2n}}{2(\zeta\minus{}\zeta^{\minus{}1})} \equal{} \minus{}\frac{\sin(2nz)}{2 \sin z}$.

Hence

$ f'(\theta) \equal{} \left[\frac{\frac{1}{2} \cos z \sin 2nz \minus{} n \cos 2nz \sin z}{\sin^2 z}\right]_{z \equal{} \theta} \equal{} n \csc \frac{\pi}{2n}$,

as claimed.

multiplying by $ 2\sin\frac{2\pi}{n}$ and applying prod-to-sum formulas, we get to prove that
$ \sum_{k\equal{}0}^n(2k\minus{}1)\left(\cos\frac{(k\minus{}1)\pi}{n}\minus{}\cos\frac{k\pi}{n}\right)\equal{}2n$...

this turns to be equivalent to prove that $ \sum_{k\equal{}0}^n\cos\frac{k\pi}{n}\equal{}0$, which is clear, and we're done... :D


Let $ T$ be a linear operator on a finite-dimensional vector space $ V$, and let $ W_1,W_2,\ldots ,W_k$ be $ T$-invariant subspaces of $ V$ such that $ V\equal{}W_1\oplus W_2\oplus\cdots\oplus W_k$. Prove that $ \det(T)\equal{}\det(T_{W_1})\det(T_{W_2})\cdots\det(T_{W_k})$.

Choose bases for each of those subspaces, and combine them for a basis of the whole space. The matrix of $ T$ is now block diagonal, and it's obvious.


A lattice point is a point whose coordinates are both integers.  How many lattice points are on the boundary or inside the region bounded by the $ x$-axis, the line $ x\equal{}4$ and the curve $ y\equal{}2\sqrt{x}$?

We must have $ 0\leq x\leq 4$ and $ y\leq 2\sqrt{x}$.

For $ x\equal{}4$, we get $ y\leq 4$, so there are $ 5$ values of $ y$ here.

For $ x\equal{}3$, we get $ y\leq 3.4$, so $ 4$.

For $ x\equal{}2$, we get $ y\leq 2.8$, which gives us $ 3$.

For $ x\equal{}1$, we get $ y\leq 2$ which is also $ 3$.

$ x\equal{}0$ gives us $ y\leq 0$, there's only 1 pair.

$ 5\plus{}4\plus{}3\plus{}3\plus{}1\equal{}\boxed{16}$


Show that the equation X^4+4Y^4=Z² has no solutions in integer numbers


Because I was bored, here's a problem :D .

Without calculating values, find the largest number that MUST divide $ \frac {3}{2}(2n \minus{} 3)(n \plus{} 2)(n \plus{} 1)$.

EDIT: I realized that the title was off... Sorry!

hello, here you must distinguish three cases:
$ n\equiv 0 \mod 3$
$ n\equiv 1 \mod 3$
$ n\equiv 2 \mod 3$
Sonnhard.

2n-3 isn't nessescarily divisible by 3. :huh: What do you mean?

The title hints at "factoring" :D

Clearly either $ n\plus{}1$ or $ n\plus{}2$ is even, so we need to show that one of the three factors is divisible by 3.  If both $ n\plus{}1$ and $ n\plus{}2$ aren't divisible by 3, then $ n$ is divisible by 3 and $ 2n\minus{}3$ is as well.


Segments $AC$ and $BD$ meet at $P$, and $|PA| = |PD|$, $|PB| = |PC|$. $O$ is the circumcenter of the triangle $PAB$. Show that $OP$ and $CD$ are perpendicular.

Any way , it should be preolympiad but never mind!

 Triangles PAB and PCD are equal , so $\angle DCP = \angle ABP = a$. This gives $\angle AOP = 2a$, so $\angle OPA = 90 - a$. Since $\angle OPA + \angle C = 90$, the result follwes.

 Babis

we know this fact that if we invert a cicle round a point on it, the circle turn into a line,which is prependicular to

a line which is diameter of the circle and also contains the center of inversion.

then circle$APB$ turned into line $CD$, because $AP.PC=BP.PD$.

and as i said, we can conclude that $OP$ is prependicular to $CD$. ;)


i have two questions i can't figure out.. help would be appreciated.

1)

The function [i]f[/i] satisfies the functional equation:
[i]f([/i]x) + [i]f[/i](y) = [i]f[/i](x+y) - xy - 1

for every pair x,y of real numbers. If [i]f[/i](1) = 1, the number of integers n =! 1 for which [i]f[/i](n) = n is:

2)

If  :theta: is a constant such that 0 <  :theta:  <  :pi: and z + 1/z = 2cos  :theta: , then for each positive integer n, z^n + 1/(z^n) equals:
a) 2 cos  :theta:
b) 2^n cos  :theta:
c) 2 cos^n  :theta:
d) 2 cos n :theta:
e) 2^n cos^n  :theta:

thanks

Hmm, number 1 looks remarkably like the Mandelbrot team round 3 ... go figure.

Hints:[hide] I suggest you calculate a few small values and then try and figure out some kind of general trend.

 For number 2, you might try just solving for z.[/hide]

Did you get these from the AOPS problems at the end of the chapter?  I remember doing 2, and i think 1 looks familiar.  For 2 i did what joel suggested.

actually, these are questions from the anniversary AHSME compilation. looking through aops, i can't find these questions in them. thanks for the hints.. i still have to try working them out.

There's a very normal method for doing problems like #2. Specifically, you might wonder where 2 cos :theta: comes from. This motivates the hint in spoiler:

[hide]cos :theta: =(ei:theta:+e-i:theta:)/2.[/hide]

For #1:  [hide]Instead of trying to figure out the function it might be easier to find a relationship between f(x) and f(x+1).[/hide]


1.) Find the sum of all positive proper fractions whose denominators are less than or equal to 35.  Do not disregard equivalent fractions, and state the answer as a mixed number. [hide]ANSWER: 297 1/2[/hide]

2.) An integer is called "decreasing" if each digit is less than the one to its left.  For example, 5320 is decreasing.  How many decreasing integers are there between 2000 and 7000? [hide]ANSWER: 35[/hide]

3.) How many three-digit numbers have a digital root of 1? [hide]ANSWER: 100[/hide]

sorry I was unclear with the question format.

#1 Hint
   For this one it is handy to know the triangle number formula: $ {n^{2}\plus{}n\over 2}$ or $ {n*(n\plus{}1)\over2}$. Some people incorrectly refer to this as the simga function which is more broad than 1+2+3...+n.

[hide=" My try at problem 1"]
   Lets first try a few sample denominators. When we have a denomanator of two there is only one proper fraction $ {1\over 2}$. Lets move on to a denomanator of three.

Here we have two possible proper fractions $ {1\over3}and{2\over3}$ If we add those two fractions we get one. Mark that down.

With a denomanator of four we have $ {1\over4},{2\over4}and{3\over4}$ If we add those together we get $ {6\over4}$ or just 1.5

If we use the triangle formula to sum all the numberators that are proper we can go much faster. So $ {4*5\over2}\equal{}10$ we get $ {10\over5}\equal{}2$. See a patern?

We find that the sum of all the proper numberators for any given denomanator = $ {denominator\over2}\minus{}.5$ but more importantly that the result goes up by .5 for each time the denominator increases by one. We can then see that if we mulitply our sequence of answers ($ .5\plus{}1\plus{}1.5\plus{}2$) by two we get 1+2+3+4 and we can divide by two at the end to achive the same answer.

Phew

So $ {1\plus{}2\plus{}3\plus{}4...34\over2}$ is the answer. We use our handy dandy triangle formula to get our numberator $ {34*35\over2}\equal{}595$ and so the answer after a long (and probably hard to understand) explanation is $ {595\over2}or 279\plus{}{1\over2}$
[/hide]

Wow. I hope you can understand that.

#2 Hint

  For this one, you need to really grasp the basics of the decreasing number. For example, what is the smallest four digit decreasing number. You should be able to figure this out but, [hide="here it is"]3210[/hide]

Both the previous problem and the current one require pattern recognition if you haven't seen the type of problems before (or just forget how to do them like me :P.)

Figure out how many decreasing numbers there are inbetween 3000 and 5000 and try to find a pattern.

[hide="my full solution"]

there is only one number that works in the three thousands and that is 3210.

For four thousand there are four. From least to greatest: 4210, 4310, 4320 and 4321.

At five thousand it gets trickier. From least to greatest: 5210, 5310, 5320, 5321, 5410, 5420, 5421, 5430, 5431 and 5432 but we notice that the first four are the same as the four thousands.

At six thousand we can use the pattern that we saw in the fives and skip listing the first ten numbers: 6510, 6520, 6521, 6530, 6531, 6532, 6540, 6541, 6542 and 6543.

So we just counted 35 of them.

Sorry that that was so blunt with just the counting of the numbers. Maybe someone else could help to fand a faster solution. [/hide]

Problem three hint:

For problem three I don't really know what a digital root is. However after looking it up I found it was the sum of each of the digits in a number. e.g. the digital root of 6,578 is 6+5+7+8=26 and 2+6=8 so the digital root of 6578
=8 Sorry if that was a little chunky

[hide="My solution for #3"]

The question to ask is, how can you get a digital root of one, and there are three solutions. Your digits can either add up to one, ten or a two digit number with digits that add up to ten, e.g. 19.

Lets start by counting all the three digit numbers whose digits add up to one…………… ok so there's only 100 but that one counts too.

Now how can we find all the ways a three digit number's digits can add up to 10? First we see that if we switch around the places of digits it doesn't matter, so 280 and 820 both count. well 1 and 9 add up to ten so lets use them as an example for two of the digits of the three digit number. we get 019, 091, 109, 190, 901, 910. There are only four (excluding the two digit numbers) If we use other pairs of numbers that add up to ten (e.g. 2 and 8) we can just multiply by four to get their totals.

there are four pairs of unique numbers that add up to ten, but then there is 5+5. That is special because 55 isn't different than 55 (unlike 28 and 82) so there are half as many possible answers giving us 4*4+2=18. We have eighteen plus one so far but we still have more to go.

There are sets of three numbers that add up to 10 as well. Lets find them all now and put them into different catigories. 1+1+8, 2+2+6, 3+3+4, and 4+4+2 are all special because they contain two of one digit so they are each worth four. 4*4+18=34 so far. 1+2+7, 1+3+6, and 1+4+5 are all the sets that contain 1. Each has six resulting three digit numbers so 4*6=24 +34=58
Then 2+3+5 is the only one we haven't covered yet. 6+58=64. There aren't any more like this so we move on to our third way of getting digital roots equal to 1.

Oy this is long.

So all together so far we have 64. now how many three digit numbers can add up to 19 (because 27 is to high)? If you're lost, review the third way to get digital roots of one (above). we get 1+9+9, 2+8+9, 3+7+9, 3+8+8, 4+6+9, 4+7+8, 5+5+9, 5+6+8, 5+7+7. there are four repeat numbers so 16+64=80 and there are five others so 30+80=110? I would check that answer or find a flaw in my reasoning. [/hide]

Hope this helps.

If you had read his, you would have seen it's just it's the sum of all the digits in a number

dracs taxi -

If I understood your solution correctly, you found the sum of the fractions that had a denominator of up to 34.  However, the question was asking for denominators less than or equal to 35, which includes 35.  Interestingly enough, you got the right answer...

Haha,
Rexamine my reasoning. when the denominator was 2 the result was .5 which I then multiplied by two to get 1. With the example of 35 as the denominator we get $ {({34*35\big)\over 2 }\over35}\equal{}{17*35\over35}\equal{} 17$ (I used the triangle formula in there) Sorry about the parentheses. When we multiply by two we get 34, the last number in the sequence I added.
So you see that was an easy mistake to make and I didn't explain why I selected 34 as the final number.
Hope you're not to confused.

ɖɺɐɕ

P.S. thanks for backing up the forum guidelines XPmath