[quote="Virgil Nicula"]$x,y,z>0\Longrightarrow\sum\frac{xy^{2}}{y+z}\ge \frac{xy+yz+zx}{2}\ .$[/quote]
We have
$\sum\frac{xy^{2}}{y+z}= \sum\frac{{(xy)}^{2}}{xy+zx}$

$\therefore$ By Cauchy in Engel form, we have
$\sum\frac{{(xy)}^{2}}{xy+zx}\ge \frac{{(\sum xy)}^{2}}{\sum xy+yz}= \frac{xy+yz+zx}{2}.$

Find the least value $k>0$ such that the following inequality
  $\sum_{cyc}\frac{xy^{2}}{y+z}\leq\frac{k(x^{2}+y^{2}+z^{2})-(k-1)(xy+xz+yz)}{2}$
holds for all positive $x,y$ and $z.$

$\sum \frac{xy^{2}-xz^{2}}{y+z}= \sum xy-xz = 0 \Rightarrow \sum \frac{xy^{2}}{y+z}=$ $\frac{1}{2}\sum \frac{xy^{2}+xz^{2}}{y+z}$ $\ge$ $\frac{1}{4}\sum \frac{x(y+z)^{2}}{y+z}$ $=$ $\frac{1}{4}\sum x(y+z) = \frac{\sum xy}{2}$

[quote="arqady"]Find the least value $k>0$ such that the following inequality
  $\sum_{cyc}\frac{xy^{2}}{y+z}\leq \frac{k(x^{2}+y^{2}+z^{2})-(k-1)(xy+xz+yz)}{2}$
holds for all positive $x,y$ and $z.$[/quote]

$(x, y, z) \to (1, 1, 0) \Rightarrow 1 \le \frac{k+1}{2}\Leftrightarrow k \ge 1$. If $k = 1$, $\sum x^{2}-\sum \frac{xy^{2}+xz^{2}}{y+z}= \sum \frac{xy(x-y)+xz(x-z)}{y+z}$ $=$ $\sum (x-y) \left(\frac{xy}{y+z}-\frac{yx}{x+z}\right)$ $=$ $\sum \frac{xy(x-y)^{2}}{(x+z)(y+z)}\ge 0$


[quote="tchebytchev"]let $a,b,c$be positive real numbers such that $abc+a+c=b$find the greatest value of:
$\frac{2}{a^{2}+1}-\frac{2}{b^{2}+1}+\frac{3}{c^{2}+1}$[/quote]
It is a Veitnamese problem.
Let\[a=\tan \alpha ,b=\tan\beta\]


[quote="José"]Does any have a book of number theory, written by Vinogradov?????[/quote]

Vinogradov has a book on elementary number theory, with very hard problems tilted toward trigonometric sums and other areas of analytic number theory close to his own research.   I can't remember whether he uses calculus but if so it was nothing more complicated than Riemann (or Stieltjes) integrals.


Could we prove without calculus that if $ f(x)$ is continuous on a interval $ I$, then for any $ x_1,x_2\in I, x_1\neq x_2,$ and $ 0<t<1,$ we have

$ f\left(\frac{x_1\plus{}x_2}2\right)<\frac{f(x_1)\plus{}f(x_2)}2\Leftrightarrow f(tx_1\plus{}(1\minus{}t)x_2)<tf(x_1)\plus{}(1\minus{}t)f(x_2)$?

[quote="AstroPhys"][hide="HINT"]
Jensen's Inequality.
[/hide][/quote]That's not really a hint, ifai knows that's Jensen's... he is asking for a proof of Jensen's without using calculus.

The $ \Leftarrow$ part is easy by letting $ t\equal{}\frac12$. But, the other direction...

[hide="Hint"]Expand $ t$ in binary.[/hide]


probability
logarithms
function
parameterization
integration
limit
expected value

It's not algebra, but there isn't a topic for "other topics", which is where it really belongs.

How long, on average, will it take for a sample starting with a given amount of a radiosiotope to be [i]completely[/i] gone?

Added in edit:

The radioisotope has a "characteristic lifetime" of $L$. (The more familiar "half-life" is $L \ln2$.) We start with $n$ atoms of the radioisotope. For each atom, the probability that it is still present at time $t$ is $e^{-t/L}$. Each atom's decay is independent of all other atoms.

Question 1: What is the expected time for the decay of the last atom?

(As a plausibility check: we would guess that for large $n$, this number ought to behave something like $L \ln n$.)

Question 2: What is the standard deviation of the time of the decay of the last atom and how does it behave for large $n$?

Indeed.  I do object.  There are many complicating factors to your question.

Is your sample a pure isotope -- E.g., Plutonium-239 or Uranium-235?  Is it a mixture of isotopes of one element?  [Pu239 -- the one used for bombs -- has a half-life of about 24000 years, Pu241 has a half-life of about 14 years.  Pu233 has a half-life of about 20 minutes, Pu244 has a half-life of about 80 million years.]

Do you want to know when the last atom of the original sample has decayed or do you want to know when the last atom of the decay series has decayed into someting we consider "non-radioactive"?  [Pu239 can decay into U235, which has a half-life of about 700 million years.]  Even some of the elements we consider "stable" have enormously long half-lives.  Many radioactive isotopes have multiple decay modes.  Do you want to follow the principal decay-mode only, or do you want to follow all of the decay modes.

The short answer to your question matches the popular slogan:

[img]http://www.homestead.com/artacopia/files/PlutoniumIsForeverB.jpg[/img]

I mean for this to be a sample of a single isotope with one-step decay to a stable product (something like tritium or C-14 or P-32) and isolated so that there's no process that replenishes the original isotope. Assume only a single possible decay mode.

OK.  Assuming everything about the physical process is ideal, we will still need some additional definitions and characterizations.

Definitions:  I have my own ideas as to what "completely gone" and "average" mean.  But I think you should clearly specify what you mean by these terms.  Are you seeking a 3-digit approximation to the answer?  Will an unsolvable system of differential equations suffice?  How about an infinite series that converges slowly?  Or doesn't converge?  Or do you want a precise closed-form solution in terms of elementary functions?

Characterizations:  Consider C-14.  The quoted half-life is 5730 years.  This is probably a pretty good estimate, if you have a large number of atoms over a large period of time.  [Remember that a mole contains Avogadro's number of particles, or about 6.023 x 10^23 atoms.]  Is time continuous or does time step in quantums?  How long is a quantum?

By the law of large numbers, the classical definition of half-life is a single number, which is all you need for a good estimate.  But if you want to know when the very last atom will decay, I think we will need to know the PDF/CDF of decay vs time.

rcv said[quote]I think we will need to know the PDF/CDF of decay vs time.[/quote]

For a single atom, the decay time [i]must[/i] have an exponential distribution. This is the only real possibility. It is the only probability distribution that satisfies either of the following conditions:

1. It is a well-known continuous distribution on [0, $\infty$) that is completely determined by a single parameter, its mean. (Or its median, if you'd rather talk about half-life.)
2. Each atom has no memory of how long it has been in existence. You could put it this way: an atom of a radioisotope doesn't "wear out." Its decay is an accidental event that has the same probability of happening in any time interval of a given length, provided the atom is still there.

[quote="Kent Merryfield"]Question 1: What is the expected time for the decay of the last atom?[/quote]

I'll give Q1 a shot...

As you note, the only distribution without a "memory" is an exponential distribution.  Using your terminology, the decay pdf of a single atom is [tex]p(t)=\frac{1}{L}e^{-t/L}[/tex].  Integrating, the cdf that a single atom has decayed is [tex]c(t)=1-e^{-t/L}[/tex].

If we want to know the probability that one atom has decayed, the form is [tex]k=c(t)[/tex].  If we want to know the probability that all N atoms (of a sample of N) have decayed, the form is [tex]k=\big(c(t)\big)^N=\big(1-e^{-t/L}\big)^N[/tex].

We solve for t in terms of k.

[tex]t=-L~\ln(1-k^\frac{1}{N})[/tex]

We can find the median by setting k=0.5 and solving for t.

[quote="Kent Merryfield"]Question 2: What is the standard deviation of the time of the decay of the last atom and how does it behave for large $n$?[/quote]

In the previous post, I showed k as a function of t.

[tex]C(t)=k=\big(c(t)\big)^N=\big(1-e^{-t/L}\big)^N[/tex].

As t varies from 0 to infinity, k varies from 0 to 1.  This is the cdf of k vs t.  To compute the variance, we need the pdf of k vs t:

[tex]P(t)=\frac{d}{dt}C(t)=\frac{N}{L}\big(1-e^{-t/L}\big)^{N-1}\big(e^{-t/L}\big)[/tex].

The formula for variance is:

[tex]\sigma^2=\int_0^\infty P(t)(t-\mu)^2dt[/tex], where [tex]\mu[/tex] is the answer to Q1.

Having no computer algebra system, I think I'll stop here.  Somebody else can check my work and finish the integration.

Although the distribution for one atom is exponential, the distribution of the last decay - the cdf that you had in both of your posts - is not an exponential distribution for N > 1. Setting the cdf equal to 1/2 does produce the median, but I asked for the mean, not the median. Setting the cdf equal to 1/e does not produce the mean.

Your cdf is right, and I assure you that reasonable ways to express the answers to both questions can be found without resorting to a computer algebra system.

[quote="Kent Merryfield"]Question 1: What is the expected time for the decay of the last atom?[/quote]

I'll give Q1 another shot...

The probability that all N atoms (of a sample of N) have decayed is:

[tex]C(t)=\big(c(t)\big)^N=\big(1-e^{-t/L}\big)^N[/tex].

To compute the mean, we need the pdf:

[tex]P(t)=\frac{d}{dt}C(t)=\frac{N}{L}\big(1-e^{-t/L}\big)^{N-1}\big(e^{-t/L}\big)[/tex].

The formula for mean is:

[tex]\mu=\int_0^\infty t\;P(t)dt[/tex]

I am unable to find a closed form solution to this integral.  I expand the binomial and integrate term-by-term.  Now, I find a hypergeometric series, which is trivially evaluated at the limits of the integration.

[tex]\mu=\frac{N}{L}\int_0^\infty t \big(e^{-t/L}\big) \big(1-e^{-t/L}\big)^{N-1}dt[/tex]

[tex]\mu=\frac{N}{L}\int_0^\infty t \big(e^{-t/L}\big) \Bigg(\sum_{j=0}^{N-1} {N-1 \choose j}\big(-e^{-t/L}\big)^j\Bigg) dt[/tex]

[tex]\mu=\sum_{j=0}^{N-1} \Bigg(\frac{N}{L}{N-1 \choose j}\int_0^\infty t \big(e^{-t/L}\big) \big(-e^{-t/L}\big)^j dt\Bigg)[/tex]

[tex]\mu=\sum_{j=0}^{N-1} \Bigg(\frac{N}{L}{N-1 \choose j}\int_0^\infty t \big(e^{-t/L}\big) (-1)^j \big(e^{-t/L}\big)^j dt\Bigg)[/tex]

[tex]\mu=\sum_{j=0}^{N-1} \Bigg(\frac{N}{L}{N-1 \choose j}\big(-1\big)^j\int_0^\infty t   \big(e^{-t/L}\big)^{j+1} dt\Bigg)[/tex]

[tex]\mu=\sum_{j=0}^{N-1} \Bigg(\frac{N}{L}{N-1 \choose j}\big(-1\big)^j \Bigg[\frac{-L}{(j+1)^2}   \big(e^{-t/L}\big)^{j+1} \big(L+t(j+1)\big)\Bigg]_0^\infty \Bigg)[/tex]

[tex]\mu=\sum_{j=0}^{N-1} \Bigg(\frac{N}{L}{N-1 \choose j}\big(-1\big)^j  \frac{-L}{(j+1)^2}\Bigg[ \big(e^{-t/L}\big)^{j+1} \big(L+t(j+1)\big)\Bigg]_0^\infty \Bigg)[/tex]

[tex]\mu=-L\sum_{j=0}^{N-1} \Bigg(\frac{N}{L}{N-1 \choose j}  \frac{(-1)^j}{(j+1)^2}\Bigg[ \big(e^{-t/L}\big)^{j+1} \big(L+t(j+1)\big)\Bigg]_0^\infty \Bigg)[/tex]

All terms vanish in the limit as t approaches infinity.  Subtracting the terms at t=0, we have:

[tex]\mu=L\sum_{j=0}^{N-1} \Bigg(\frac{N}{L}{N-1 \choose j}  \frac{(-1)^j}{(j+1)^2} \Big( L \Big) \Bigg)[/tex]

[tex]\mu=L\sum_{j=0}^{N-1} \Bigg(N \; {N-1 \choose j}  \frac{(-1)^j}{(j+1)^2} \Bigg)[/tex]

The summations tally up to harmonic numbers, and the equation simplifies to:

[tex]\mu=L\;H_N[/tex], where [tex]H_N[/tex] is the Nth Harmonic number.  The first few values are:
[tex]N=1[/tex], [tex]\mu=L\times 1[/tex]
[tex]N=2[/tex], [tex]\mu=L\times 3/2[/tex]
[tex]N=3[/tex], [tex]\mu=L\times 11/6[/tex]
[tex]N=4[/tex], [tex]\mu=L\times 50/24[/tex]
[tex]N=5[/tex], [tex]\mu=L\times 274/120[/tex]

Once again, I apply your "plausibility check".  We use the definition of Euler's constant [tex]\gamma = \lim_{N\to\infty}\Big(H_N-\ln N\Big)[/tex].

[tex]\lim_{N\to\infty}\mu=L\times(\gamma + \ln N)[/tex]

[tex]\lim_{N\to\infty}\mu=L\ln N + L\gamma[/tex].

Now that I think I know the answer, I've been contemplating *why* we see the result.

Another way to view this problem is that we have a series of independent activities, which occur sequentially in time.

To begin with, we have N radioactive atoms.  If the amount of radioactive material were to remain constant, I think the number of decays per time interval would follow a Poisson process, and I think we would have a Poisson distribution.

Our situation is different, because the amount of radioactive material is diminishing.  In the beginning, we have N atoms of radioactive isotope.  Knowing the average lifetime, L, of this isotope, we know the average time until we have our first decay is L/N.

Once a decay occurs, we begin a new, independent activity.  We have N-1 atoms of the isotope.  The average time until we have the second decay is now L/(N-1).

Each time an atom decays, we start a new clock, with new parameters.  The average time until all isotopes have decayed is the sum of each of these independent activities, as N varies from N down to 1.  I.e., we have a sum of reciprocals, which give us the harmonic numbers, H_n.

This reasoning gives the same result as my previous post:

[tex]\mu=L \; H_N[/tex]

Using a similar line of reasoning, we should be able to compute the combined variance in a similar manner:

[tex]\sigma^2=\sum_{j=1}^N( \sigma_j^2 )[/tex], where [tex]\sigma_j^2=\frac{L^2}{j^2}[/tex] is the variance in time to the first decay in an exponential distribution, when there are j atoms in the sample.

[tex]\sigma^2={L^2}\sum_{j=1}^N( \frac{1}{j^2})={L^2}H_{N,2}[/tex], where [tex]H_{N,2}[/tex] is the Nth harmonic number of the second power.

[tex]\lim_{N\to\infty}\sigma^2={L^2}H_{N,2}={L^2}\zeta(2)={L^2}\frac{\pi^2}{6}[/tex], where [tex]\zeta[/tex] is the Reimann zeta function.

Recall that the standard deviation is the square root of the variance.

And my compliments, Professor Merryfield!  Whether my solution is correct or not, this is a very nice problem!

Congratulations, rcv. You have found the correct answers, and in your last two posts, you have found the cleanest arguments.

To recapitulate what you said, the time to the [i]first[/i] decay is given by an exponential distribution with mean $L/N$. Once the first decay has happened, we might as well be back at the beginning, just with one fewer atom. The various time intervals between decays are independent, so the variance of the sum is the sum of the variances.

I have one notational nit to pick with you. You said

$\lim_{N\to\infty}\mu=L\ln N + L\gamma$.

Although I know what you mean, you can't say it that way. A limit in $N$ cannot have an $N$ in it. Here's a better way to say what you mean:

As $N\to\infty, \mu=L\ln N + L\gamma + o(1)$.

Here's a related problem, called the "coupon collector" problem.  A store is giving away coupons of N different types.  A coupon is equally likely to be any of the N types.  On average, how many coupons do you need to collect until you have at least one of each type?

Good problem, Ravi. I'm quite familiar with it and its answer (and you can, just as in the radioisotope problem, also ask about the variance), so I'll leave it for others to answer.

Divide the whole process into $n$ stages. The $i$th stage consists of the steps after collected ($i-1$)th type until collected $i$th type. For each step during the $i$th stage, we have $i-1$ types and don't have $n-i+1$ types. Thus, in the $i$th stage, the probabilty of obtaining a new types is $(n-i+1)/n$.

Let $n_i$ denote the number of steps in the $i$th stage. thus, the number of all steps to get $n$ types is $n=\sum n_i$. Each random variable $n_i$ has a geometric distribution with probability of success $(n-i+1)/n$.
Thus, $E(n_i) = n/(n-i+1)$

By linearity of expectation,

\[ E(n) = E(\sum n_i) = \sum E(n_i) = \sum \frac{n}{n-i+1} = n \sum \frac{1}{n-i+1} = n\sum \frac{1}{i}\]

Just to be clear: in all of the sums in liyi's post, $i$ runs from $1$ to $n$, and we're abusing the letter $n$. This would look better if we called the number of tries needed to collect the $i$ th new coupon $X_i$ and the time to collect them all $X$, which is the sum of $X_i$. For large $n$, the expected value of $X$ behaves asymptotically like $n\ln n$.

Other than the notational quibbles, good job, liyi. Can you also say what the variance is?


sequence $d_1\ge d_2\ge \dots\ge d_n$is Graphic if and only if$\sum_{i=1}^nd_i$be even and

$\sum_{i=1}^kd_i\le k(k-1)+\sum_{i=k+1}^n\min\{k,d_i\}$

I think its very famous ,
But I don't have any solution for it.


continued fraction
inequalities unsolved
inequalities

[quote="Till"]Let $x\in ]0,1[$

Prove that exists $\frac{a}{b}$ rational, $a,b$ positive integers, $gcd(a,b)=1$, such that $|x-\frac{a}{b}|<\frac{1}{b^{2}}$[/quote]

Why not use the property of continued fractions.
Any continued fraction will satisfy (i think )
$\left| x-\frac{a}{b}\right|\leq \frac{1}{2b^{2}}<\frac{1}{b^{2}}$

(Actually is $x$ is rational then we cant use that inequality. however the statement is trivivally true if we take $a/b=x$)


You could waste a few hours and just explicitly solve it.

Actually a more general resul holds :

$ a_{n} \equal{} \sqrt {2 \plus{} \sqrt [3]{3 \plus{} .. \plus{} \sqrt [n]{n}}} < 2$ and to prove this I consider the following result :

$ k < k^k \minus{} (k \plus{} 1),\forall k \in \mathbb{N},k\geq 4$ .Having this in mind and the fact that $ \sqrt [n]{n} < n$ we obtain:

$ a_{n} < \sqrt {2 \plus{} \sqrt [3]{3 \plus{} \sqrt [4]{4^4 \minus{} 5 \plus{} ... \plus{} \sqrt [n \minus{} 2]{(n \minus{} 2)^{n \minus{} 2} \minus{} (n \minus{} 1) \plus{} \sqrt [n \minus{} 1]{(n \minus{} 1)^n \minus{} n \plus{} n}}}}} \equal{} \sqrt {2\plus{}\sqrt[3]{7}}< 2$

[hide="obs"]And if I remember well a more stronger result also holds:
$ \sqrt {1 \plus{} \sqrt {2 \plus{} \sqrt {3 \plus{} ... \plus{} \sqrt {n}}}} < 2,\forall n \in \mathbb{N^*}$
[/hide]


geometry
geometric transformation
reflection
angle bisector

[quote]2. A point D on side BC of triangle ABC is selected such that CD = 3 and BD = 2. A point E is selected on AC such that EC = 1. If AD is an angle bisector of BAC, and AB = 6, compute the value of DE.[/quote]

I'm trying to learn more about triangles and ive gone through the lesson and did the first question no problem, but this one stumps me. I applied the angle bisector theory like the answer says but then I lose it all from there. Here is the answer:

To tackle this problem, one first applies the Angle Bisector Theorem to obtain $\frac{3}{AC}= \frac{2}{6}$ from which AC = 9. One then reflects triangle ABD over AD to map B onto B’, giving DB’ = 2 and AB’ = 6. [b]Furthermore, EB’ = 2 by subtraction[/b]. One then applies Stuart’s Theorem to obtain $3DE^{2}+6 = 18+4$, from which one computes $DE = \frac{4\sqrt{3}}{3}$

What I dont understand is how EB' is found by subtraction?, I get the rest just now how they find EB' by subtraction, im looking at my diagram ive drawn and I just cant see it >_<

thanks for the replies  :)

well, if you reflect triangle abd over correctly you can see that ab lies on ac. since ae = 8 (from angle bisector theorem) and ab' = 6, then eb' equals 2.

if you reflect abd over it cant lie on AC though because DB' = 2


Given a triangle ABC. The medians AA1, BB1, CC1 intersect in points G. Show that the circulum centers of 6 triangles AB1G, AC1G, BC1G, BA1G, CA1G, CB1G lie on a circle.

(This property I found 20 years ago, but I dont see it in any book or other sources)

Namdung

well then, untill this is re-discovered in some old book, this will be called Namdung's Circle :)

Namdung, it is called "Floor van Lamoen's theorem" although you might have discovered it earlier than he did. Have a look at

http://forumgeom.fau.edu/FG2003volume3/FG200305.pdf

http://www.math.ust.hk/excalibur/v6_n1.pdf

... his problem was published in AMM in 2000, so I guess you are very unlucky Namdung :(, but don't worry there's always time to find out something new.

Hi all,

Thank you for showing me the sources. I'm not so unlucky, Valentin, although I discovered this property long time ago. I think is very well when this property was published in AMM. The beauty of mathematics can be delivered to all. Many thank to organiztors of this site, who provide me and other mathematics_likers chance to exchange our thought, our problems and our experiences in problem solving.

Namdung

you are most welcome :)
let's keep up the good work.


quadratics
function
symmetry
calculus
special factorizations
algebra

Let $ f(x)\equal{}2x^2\minus{}4(a\plus{}1)x\plus{}10a\plus{}1$ be the quadratic function for the constant $ a$.

(1) Find the value of $ a$ such that $ y\equal{}f(x)$ touches to the $ x$ axis.

(2) Find the value of $ a$ such that the minimum value of $ f(x)$ for $ \minus{}1\leq x\leq 3$ is $ \frac 79$.

[hide="number one"]
If the graph touches the $ x \minus{} axis$ then the function is in the form $ 2(x\minus{}k)^2$

$ \Rightarrow 2x^2 \minus{} 4kx \plus{} 2k^2 \equal{} 2x^2 \minus{} 4(a \plus{} 1)x \plus{} 10a \plus{} 1$

$ \Rightarrow k \equal{} a \plus{} 1 \qquad(1)$
$ 2k^2 \equal{} 10a \plus{} 1 \qquad(2)$

Sub (1) and (2)
$ \Rightarrow 2(a \plus{} 1)^2 \equal{} 10a \plus{} 1 \Leftrightarrow 2a^2 \minus{} 6a \plus{} 1 \equal{} 0$

$ \Rightarrow a \equal{} \frac {6 \pm \sqrt {36 \minus{} 8}}{4} \equal{} \frac {3 \pm \sqrt {7}}{2}$[/hide]

[hide="number 2"]
Complete the square;
$ 2\left(x \minus{} (a \plus{} 1)\right)^2 \plus{} 6a \minus{} 2a^2 \minus{} 1$

We want $ 6a \minus{} 2a^2 \minus{} 1 \equal{} \frac {7}{9}$

$ \Rightarrow a \equal{} \frac {1}{3}$ or $ \frac {8}{3}$

We also need $ \minus{} 1 \le x \le 3 \Leftrightarrow \minus{} 1 \le a \plus{} 1 \le 3$

$ \Rightarrow a \equal{} \frac {1}{3}$[/hide]

The answer of Q1 is correct, but that of $ Q2$ is not perfect.

[hide="Number 2"]
We can find the minimum value of $ f(x)$ in $ [a,b]$ by taking the minimum value among $ f(a),f(b)$, and other values of $ f(x)$ which $ f'(x) \equal{} 0$

$ f'(x) \equal{} 4x \minus{} 4a \minus{} 4 \equal{} 0 \implies x \equal{} a \plus{} 1$

$ f( \minus{} 1) \equal{} 14a \plus{} 7$
$ f(3) \equal{} 7 \minus{} 2a$
$ f(a \plus{} 1) \equal{} \minus{} 2a^2 \plus{} 6a \minus{} 1$

1) $ 14a \plus{} 7 \equal{} \frac {7}{9} \implies a \equal{} \minus{} \frac {9}{4}$
Then, $ f(a \plus{} 1)$ becomes the smallest.

2) $ 7 \minus{} 2a \equal{} \frac {7}{9} \implies a \equal{} \frac {28}{9}$
$ f(a \plus{} 1)$ becomes the smallest again.

3) $ \minus{} 2a^2 \plus{} 6a \minus{} 1 \equal{} \frac {7}{9} \implies a \equal{} \frac {1}{3}, \frac {8}{3}$

If $ a \equal{} \frac {1}{3}$, $ \minus{} 2a^2 \plus{} 6a \minus{} 1 \equal{} \frac {7}{9}$

If $ a \equal{} \frac {3}{8}$, $ \minus{} 2a^2 \plus{} 6a \minus{} 1$ does become the smallest, but is value is $ \frac {31}{32}$.

Answer: $ \frac {1}{3}$

[/hide]

I have not received perfect answer yet. :(

@FantasyLover: No calculus in the HS forums. And in this case, completing the square is actually faster than finding the derivative. :wink:

@kunny: Did you see my solution? I edited it in.

[quote="math154"][hide="Another Solution for 1"]
Alternatively, just set the discriminant equal to $ 0$ (guaranteeing that $ f(x)$ is tangent to the $ x$-axis), so $ 16(a \plus{} 1)^2 \minus{} 8(10a \plus{} 1) \equal{} 16a^2 \minus{} 48a \plus{} 8 \equal{} 0\implies2a^2 \minus{} 6a \plus{} 1 \equal{} 0$, and the rest is the same as your solution.
[/hide]
[hide="2"]
Since the minimum of the quadratic occurs when $ x \equal{} \minus{} \left(\frac { \minus{} 4(a \plus{} 1)}{2(2)}\right) \equal{} a \plus{} 1$ (easily seen by completing the square), one can see that if

$ \minus{} 2\le a\le2$, then the minimum is $ 2(a \plus{} 1)^2 \minus{} 4(a \plus{} 1)^2 \plus{} 10a \plus{} 1 \equal{} \minus{} 2a^2 \plus{} 6a \minus{} 1 \equal{} \frac79$

$ \implies9a^2 \minus{} 27a \plus{} 8 \equal{} (3a \minus{} 1)(3a \minus{} 8) \equal{} 0\implies a \equal{} \left\{\frac13,\frac83\right\}$; however, by the range, the only solution is $ a \equal{} \boxed{\frac13}$.

This is not complete, though.

If $ a > 2$, then the minimum occurs when $ x \equal{} 3$ (since we want the $ x$ to be as close to the axis of symmetry as possible), so we must have $ 18 \minus{} 12(a \plus{} 1) \plus{} 10a \plus{} 1 \equal{} \frac79\implies a \equal{} \boxed{\frac {28}9}$.

If $ a < \minus{} 2$, then the minimum occurs when $ x \equal{} \minus{} 1$ (since we want the $ x$ to be as close to the axis of symmetry as possible), so we must have $ 2 \plus{} 4(a \plus{} 1) \plus{} 10a \plus{} 1 \equal{} \frac79\implies a \equal{} \minus{} \frac49$, but this doesn't satisfy the range.
[/hide][/quote]

Now the problem has been solved completely.

Comment: Let's use $ D/4 \equal{} k^2 \minus{} ac$ for the quadratic equation:$ ax^2 \plus{} 2kx \plus{} c \equal{} 0\ (a\neq 0)$ and the fomula of root: $ \boxed{x \equal{} \frac { \minus{} k\pm \sqrt {k^2 \minus{} ac}}{a}}$


Please [b]USE [url=http://www.mathlinks.ro/Forum/search.php]SEARCH[/url][/b] from now on.

For example http://www.mathlinks.ro/Forum/viewtopic.php?highlight=bots&t=99267 or
http://www.mathlinks.ro/Forum/viewtopic.php?highlight=bots&t=97898


modular arithmetic
number theory
relatively prime
Hi

hard a bit
Show that there is a positive integer k such that, for every positive integer n, $k2^{n}+1$ is composite.

[hide]
By the Chinese Remainder Theorem, we can find a positive integer $k$ such that $k\equiv 2\pmod{641(2^{32}-1)}$ and $k\equiv 2^{33}\pmod{\frac{2^{32}+1}{641}}$. (It is a fact that $\frac{2^{32}+1}{641}$ is an integer not divisible by 641, and of course it's relatively prime with $2^{32}-1$; also
\[2^{32}-1=(2+1)(2^{2}+1)(2^{4}+1)(2^{8}+1)(2^{16}+1)\]
a product of pairwise relatively prime integers. Then we have
\[n\equiv 2^{j}-1\pmod{2^{j+1}}\Rightarrow k\cdot 2^{n}\equiv-1\pmod{2^{2^{j}}+1}\]
for each $j$ between 0 and 4 inclusive,
\[n\equiv 31\pmod{64}\Rightarrow k\cdot 2^{n}\equiv-1\pmod{641}\]
\[n\equiv 63\pmod{64}\Rightarrow k\cdot 2^{n}\equiv-1\pmod{\frac{2^{32}+1}{641}}\]
Since $n$ must fall into one of the 7 cases above, $k\cdot 2^{n}+1$ must always be divisible by at least one of the 7 factors, and $k\geq 2+641(2^{32}-1)$ so $k\cdot 2^{n}+1$ is always greater than each of the factors and is therefore composite.
[/hide]


it says "find the amplitude of $ f(x)\equal{}3\sin x\plus{}\cos x$"

then it says to relate the function to $ \sin {(x\plus{}y)}\equal{}\sin x \cos y\plus{}\sin y \cos x$

then it says to scale it and find a y so that $ \cos y\equal{}3A$ and $ \sin y\equal{}A$. then use a pythagorean identity to solve for A

They end up with $ f(x)\equal{}\sqrt{10} \sin (x\plus{}y)$, and the amplitude is $ \sqrt{10}$

i dont see the point of trying to find a y to make it a single sine, because now we have 2 variables in the function, and i dont see how we can just pull the $ \sqrt{10}$ out to get the amplitude if there is a y there.

I checked the book and although I just glanced at it, it said that $ y$ is a real number and it didn't really refer to it as a variable.


trigonometry
algebra
polynomial
complex numbers
algebra unsolved

Find the least positive integer $ n$ for which $ \cos\frac{\pi}{n}$ cannot be expressed in the form $ p\plus{}\sqrt q\plus{}\sqrt[3]r$
for some rational numbers $ p, q, r$.

[quote="math10"]Find the least positive integer $ n$ for which $ \cos\frac {\pi}{n}$ cannot be expressed in the form $ p \plus{} \sqrt q \plus{} \sqrt [3]r$
for some rational numbers $ p, q, r$.[/quote]

[hide="Partial work"]
$ \cos(\frac{\pi}{1})\equal{}\minus{}1$

$ \cos(\frac{\pi}{2})\equal{}0$

$ \cos(\frac{\pi}{3})\equal{}\frac 12$

$ \cos(\frac{\pi}{4})\equal{}\frac{\sqrt 2}{2}$

$ \cos(\frac{\pi}{5})\equal{}\frac 14\plus{}\frac{\sqrt 5}{4}$

$ \cos(\frac{\pi}{6})\equal{}\frac{\sqrt 3}{2}$

$ \cos(\frac{\pi}{7})$ is root of $ 8x^3\minus{}4x^2\minus{}4x\plus{}1\equal{}0$ and so $ 6\cos(\frac{\pi}{7})\minus{}1$ is root of $ x^3\minus{}21x\plus{}7\equal{}0$

It remains to prove that no solution of $ x^3\minus{}21x\plus{}7$ can be written as $ p\plus{}\sqrt q\plus{} \sqrt[3]r$

To be continued ...
[/hide]

[quote="pco"][quote="math10"]Find the least positive integer $ n$ for which $ \cos\frac {\pi}{n}$ cannot be expressed in the form $ p \plus{} \sqrt q \plus{} \sqrt [3]r$
for some rational numbers $ p, q, r$.[/quote]

[hide="Partial work"]
$ \cos(\frac {\pi}{1}) \equal{} \minus{} 1$

$ \cos(\frac {\pi}{2}) \equal{} 0$

$ \cos(\frac {\pi}{3}) \equal{} \frac 12$

$ \cos(\frac {\pi}{4}) \equal{} \frac {\sqrt 2}{2}$

$ \cos(\frac {\pi}{5}) \equal{} \frac 14 \plus{} \frac {\sqrt 5}{4}$

$ \cos(\frac {\pi}{6}) \equal{} \frac {\sqrt 3}{2}$

$ \cos(\frac {\pi}{7})$ is root of $ 8x^3 \minus{} 4x^2 \minus{} 4x \plus{} 1 \equal{} 0$ and so $ 6\cos(\frac {\pi}{7}) \minus{} 1$ is root of $ x^3 \minus{} 21x \plus{} 7 \equal{} 0$(*)

It remains to prove that no solution of $ x^3 \minus{} 21x \plus{} 7$ can be written as $ p \plus{} \sqrt q \plus{} \sqrt [3]r$

To be continued ...
[/hide][/quote]
hi pco.
My solution similary your solution but I you had prove that equation $ x^3\minus{}21x\plus{}7\equal{}0$ no solution can can be written as $ p \plus{} \sqrt q \plus{} \sqrt [3]r$ how(I had suppose equation (*) have solution such that problemand write them in (*),It is complex)

Let $ z\equal{}(\minus{}28\plus{}84\sqrt{3}i)^{1/3}\approx{4.4\plus{}2.9i}$ and $ 2$ other values. The polynomial $ p\equal{}8x^3\minus{}4x^2\minus{}4x\plus{}1$ has $ 3$ real roots ; among these roots $ cos(\pi/7)\equal{}\dfrac{z^2\plus{}2z\plus{}28}{12z}\approx{0.9}$. In generic case when the polynomial $ p$ has $ 3$ real roots the Cardano's formula gives these roots in a complex form (that is $ i$ appears explicitly); moreover there is no algebraic formulas without $ i$ !! Curiously Bombelli invented complex numbers in order to solve this problem and not  in order to solve equations of degree $ 2$.
Remark: Cardano was a lamentable robber:
http://en.wikipedia.org/wiki/Cubic_equation

[quote="loup blanc"]Let $ z \equal{} ( \minus{} 28 \plus{} 84\sqrt {3}i)^{1/3}\approx{4.4 \plus{} 2.9i}$ and $ 2$ other values. The polynomial $ p \equal{} 8x^3 \minus{} 4x^2 \minus{} 4x \plus{} 1$ has $ 3$ real roots ; among these roots $ cos(\pi/7) \equal{} \dfrac{z^2 \plus{} 2z \plus{} 28}{12z}\approx{0.9}$. In generic case when the polynomial $ p$ has $ 3$ real roots the Cardano's formula gives these roots in a complex form (that is $ i$ appears explicitly); moreover there is no algebraic formulas without $ i$ !! Curiously Bombelli invented complex numbers in order to solve this problem and not  in order to solve equations of degree $ 2$.
Remark: Cardano was a lamentable robber:
http://en.wikipedia.org/wiki/Cubic_equation[/quote]
No,I need a solution elementery and nice(my solution is complex)


trigonometry
integration
calculus
real analysis
function
abstract algebra
real analysis unsolved

Does the Fourier Sine transform of $ \frac {1}{x}$ exist? because its Fourier Sine transform may be given by the formula $ F(\omega) \equal{} \sqrt {\frac {2}{\pi}} \int_{0}^{\infty}\frac {\sin\omega x}{x}dx$ but we know the integral doesn't exist in the Lebesgue sense.
Is Fourier Sine transform defined only for odd functions? Why not for general functions?

Even i have the same doubt. We know that the above integral has meaning in Riemann sense,but an unpleasant situation occurs in the case of Lebesgue. How about the definition of Fourier transform? Is it defined in Riemann or Lebesgue sense?? Even so if the definition is in terms of Riemann sense the value of the integral is a constant. I think there is some loop hole in the above procedure. :roll:

1. The Fourier sine transform can be applied to "all" (well, all integrable) functions, not just even functions. But if you write $ f(x)=g(x)+h(x)$ where $ g$ is even and $ h$ is odd, the sine transform of $ f$ will equal the sine transform of $ h.$ In other words, the transform annihilates the even part, or the even part lies in the kernel of the operator. If you then repeat the transform to invert it, you get back $ h,$ the odd part, and not all of $ f.$

2. You're only on safe ground with Lebesgue integrable functions. Once you step outside of that, many different things can happen. One of the most productive ways to extend the Fourier transform (and its relatives) is to consider their action on (tempered) distributions.

$ \frac1x$ is not an integrable function, and not even a locally integrable function. But its principal value does define a valid distribution. The integral you're trying to compute is then the transform of this distribution. Note that your proposed $ F(\omega)$ does not tend to zero as $ \omega\to\infty,$ as would be expected (by the Riemann-Lebesgue Lemma) for the transform of an integrable function. But, then ... it isn't the transform of an integrable function.


logarithms
function
calculus
calculus computations

Can somebody show me an elegant way to prove the divergence of

$ \sum_{n \equal{} 1}^{\infty }\left( e \minus{} \left( 1 \plus{} \frac {1}{n}\right) ^{n}\right)$ $ \ ?$

Comparing with the Harmonic Series works but turns out to be real ugly. Thank you!

I don't see how to avoid comparing it to the harmonic series.

$ ln\left[\left(1\plus{}\frac1n\right)^n\right]\equal{}n\ln\left(1\plus{}\frac1n\right)\equal{}n\left(\frac1n\minus{}\frac1{n^2}\plus{}O(n^{\minus{}3}\right)$

$ \equal{}1\minus{}\frac1{2n}\plus{}O(n^{\minus{}2}).$

Then $ \left(1\plus{}\frac1n\right)^n\equal{}e\cdot\text{exp}\left(\minus{}\frac1{2n}\plus{}O(n^{\minus{}2})\right)\equal{}e\left(1\minus{}\frac1{2n}\plus{}O(n^{\minus{}2}\right).$

Then $ e\minus{}\left(1\plus{}\frac1n\right)^n\equal{}\frac{e}{2n}\plus{}O(n^{\minus{}2})$

and the series diverges by limit comparison to the harmonic series.

hello Kent Merryfield.

Can you show me :

$ \begin{array}{c} \left(1 \plus{} \frac1n\right)^n \equal{} e\cdot\text{exp}\left( \minus{} \frac1{2n} \plus{} O(n^{ \minus{} 2})\right)  \; \overset{ ?? }{\equal{}} \; e\left(1 \minus{} \frac1{2n} \plus{} O(n^{ \minus{} 2}\right) \\\\  \Downarrow ?? \\\\ e \minus{} \left(1 \plus{} \frac1n\right)^n \equal{} \frac {e}{2n} \plus{} O(n^{ \minus{} 2}) \end{array}$

Thank you !

brahman: In the first place, I'm using $ \text{exp}(x)$ as a synonym for $ e^x.$

$ e^x\equal{}1\plus{}x\plus{}O(x^2)$ for $ x$ near zero - that's the start of the Taylor series.

So $ \text{exp}\left(\minus{}\frac1{2n}\plus{}O(n^{\minus{}2})\right)\equal{}1\plus{}\left(\minus{}\frac1{2n}\plus{}O(n^{\minus{}2})\right)\plus{}O\left(\left(\minus{}\frac1{2n}\plus{}O(n^{\minus{}2})\right)^2\right).$

That last $ O$ term is just $ O(n^{\minus{}2}),$ and $ O(n^{\minus{}2})\plus{}O(n^{\minus{}2})\equal{}O(n^{\minus{}2}).$

Then $ e\minus{}e\left(1\minus{}\frac1{2n}\plus{}O(n^{\minus{}2})\right)\equal{}e\minus{}e\plus{}\frac{e}{2n}\plus{}O(n^{\minus{}2}),$ where we've used that a constant (such as $ e$) multiplied by $ O(n^{\minus{}2})$ is still $ O(n^{\minus{}2}).$

[quote="kunny"]$ \boxed{\frac {e}{2n \plus{} 2} < e \minus{} \left(1 \plus{} \frac {1}{n}\right)^n < \frac {e}{2n \plus{} 1}}$[/quote]

Can you show me how is this derived?

Here is the problem related to the inequality.

1989 Gakusyuin University entrance exam/Science

(1) For $ x>0$, prove that $ \frac{1}{x}\ln (1\plus{}x)>1\plus{}\ln \frac{2}{x\plus{}2}$.

(2) For positive integer $ n$, prove that $ e\minus{}\left(1\plus{}\frac{1}{n}\right)^n<\frac{e}{2n\plus{}1}$.

Kent Merryfield: thank you very much !

I've just forgot the expand: $ \exp \{ x\} \equal{} 1 \plus{} x \plus{} O(x^2)$. So, when $ x$ sufficient small, we can approximate $ \exp \{ x\}$ by $ 1 \plus{} x$ and do not respect $ O( x^2 )$. ok ?  :)

cheer!

Another way formally not involving the exponential function:
\[ \begin{aligned}
e\minus{}\left(1\plus{}\frac 1n\right)^n&\equal{}\sum_{k\equal{}0}^\infty \frac 1{k!}\left[1\minus{}\frac{n(n\minus{}1)\dots(n\minus{}k\plus{}1)}{n^k}\right]
\\
&\ge \frac 1{2!}\left[1\minus{}\frac{n(n\minus{}1)}{n^2}\right]\equal{}\frac 1{2n}\,.
\end{aligned}\]

[color=green]Moderator edit: never quote the post directly preceding yours in full; you answer to it by default :)[/color]
Thanks for the solution, it's the best I have seen so far.


is anyone here using a cd player in their state cheer? if anyone could allow our team (louisiana) to borrow it? thank you to everyone

Well, I do, but no, I don't trust you...

i don't mean borrow it, i mean i want to use it real quick


Let a,b,c are real numbers with $ a \ne 0$.

$ f(x) \equal{} ax^2 \plus{} bx \plus{} c$ such that $ |f(x)| \le 1$ with all values of $ x \in [ \minus{} 1;1]$ and $ (4a^2\plus{}3b^2)_{max}$.

Find $ a,b,c$.  :o

[quote="Potla"][quote="L_Euler"]Let a,b,c are real numbers with $ a \ne 0$.

$ f(x) \equal{} ax^2 \plus{} bx \plus{} c$ such that $ |f(x)| \le 1$ with all values of $ x \in [ \minus{} 1;1]$ and $ (4a^2 \plus{} 3b^2)_{max}$.

Find $ a,b,c$.  :o[/quote]

Er, I did not understand the question, could you please elaborate?
Especially, what do you mean by $ (4a^2 \plus{} 3b^2)_{max}$ written without any complete sentence? :huh:
Please rectify.[/quote]

Sr, my question is: Find a,b,c such that $ 4a^2 \plus{} 3b^2$ is maximum value, let $ f(x) \equal{} ax^2 \plus{} bx \plus{} c$ such that $ |f(x)| \le 1$ with all values of $ x \in [ \minus{} 1;1]$.  :(


A farmer has previously fenced a field in the shape of a trapezoid as shown. The farmer divides this field into exactly four congruent trapezoids. How many additional meters of fencing are needed. Express your answer to the nearest whole number.

-----------|
|                |
|                  |
|                    |
|----------------------

Top side is 40 Meter, left side is 40 meter, bottom side is 80 meter.
fourth  slant side is not known.

Anyone wants to help explain how to solve this.
Thanks.


pigeonhole principle
induction
number theory proposed
number theory

It's well known that if $ p$ is a prime number then the quantity $ x^2\plus{}y^2$ takes all residues $ \mod p$

Now prove that the quantity $ a_1^n\plus{}a_2^n\plus{}...\plus{}a_d^n$ where $ d\equal{}\gcd (n,p\minus{}1)$ takes all residues $ \mod p$

from lagrange lemma  $ x^d$ can make atleast $ \frac {p \minus{} 1}{(p \minus{} 1,d)}(mod p)$reminders.
so by couchy_davenport theorem $ \sum a_{i}^d$ can make all reminders.

[quote="sumita"]so by couchy_davenport theorem $ \sum a_{i}^d$ can make all reminders.[/quote]

Which sets you take as $ A,B$ in the application of Cauchy-Davenport theorem ?

let$ A$={$ x^n|x\in Z[p]$} but $ |A|\geq \frac{p\minus{}1}{(p\minus{}1,n)}\plus{}1$
now use cauchy_davenport for $ A_{1},.....A_{d}$ where $ A_{i}\equal{}A$

Nice ! Thank you very much for the solution . I am still wondering if we can avoid Cauchy Davenport theorem , just using pigeonhole principle like the case with two variables (maybe with some induction involving).

but you can use only simple induction to prove cauchy_davenport.


geometry
trigonometry
trapezoid
email
circumcircle
angle bisector
geometry unsolved

Let $ABC$ be an acute-angled triangle which is not isosceles. Consider the altitudes from the vertices $A$ and $C$ of triangle $ABC$. The bisector of the acute angle between these two altitudes intersects the line $AB$ at a point $P$ and intersects the line $BC$ at a point $Q$. Let $H$ be the orthocenter of triangle $ABC$, and let $N$ be the midpoint of the segment $AC$. The angle bisector of the angle $ABC$ intersects the line $HN$ at a point $R$. Prove that the quadrilateral $BPRQ$ is cyclic.

It's not going to be complete, but it will contain the main ideas.

First of all, some notations:

$M$ is the midp of $PQ$, $S$ is the second intersection of the circle $(ABC)$ and the one with diameter $BH$. $A^*, C^*$ are the projections of $A,C$ on the opposite sides of $ABC$. $B'$ is the antipode of $B$ wrt the circle $(BPQ)$ and $T$ is the pole of $PQ$ wrt the same circle. Also, $B$ is the antipode of $B$ wrt $(ABC)$.

What we need to show is that $H,B',B$ are collinear, because it's easy to show that $HN$ passes through $B$. A quick computation reveals $\frac {BH}{BB}=\cos A$, and it really is not hard to prove that $\frac {BM}{BT}=\cos A$, so the triangles $BMH, BTB$ are similar (because $\angle HBM=\angle BBT$), so $HM||BT$ and $\frac {HM}{BT}=\cos A$, so if $X=HB\cap BM$, then $X$ is on the segment $MT$ and $\frac {MX}{XT}=\cos A$, but $B'$ satisfies this (again, an easy computation based on the fact that $(B,B';M,T)=-1$).

$BO$ meets $HN$ at $E$. Easily $BE$ is the diameter of $(O)$ $(1)$  and $BR$ is the bisector of $\angle HBE$ $(2)$
$CH$ meets $(O)$ at $F$. We have $\angle FBA=\angle ACF=\angle HBA$ so triangle $FBH$ is isosceles . Thus $BH=BF$
We have $DQ/QC=DH/HC=BF/BE$ (triangle $HDC$ and $BFE$ are similar)$=BH/BE=HR/RE$ (because of (2))
But $HDCE$ is a trapezium (because of (1) and $HD \bot BC$) so $RQ//DH//EC$
This means $RQ \bot BC$
similarly $RP \bot AB$ so $B,P,R,Q$ are cyclic $q.e.d$

[quote="Huyền Vũ"]$ BO$ meets $ HN$ at $ E$. Easily $ BE$ is the diameter of $ (O)$ $ (1)$[/quote]

Someone just asked me (in an email) why this is the case. Here is the answer:

Let E' be the point diametrically opposite to B on the circumcircle (O) of triangle ABC. Then, BE' is a diameter of (O); hence, $ E^{\prime}\in BO$ and < BAE' = 90°, so that $ AE^{\prime}\perp AB$. On the other hand, $ CH\perp AB$ (since CH is an altitude of triangle ABC). Thus, AE' || CH. Similarly, CE' || AH. Thus, AE'CH is a parallelogram. Hence, its diagonals AC and HE' bisect each other. Thus, the line HE' passes through the midpoint of the segment AC. Since the midpoint of the segment AC is N, this means $ N\in HE^{\prime}$, so that $ E^{\prime}\in NH$.
Since $ E^{\prime}\in BO$ and $ E^{\prime}\in NH$, we have $ E^{\prime}\equal{}BO\cap NH\equal{}E$, and thus BE is a diameter of (O) (because BE' is a diameter of (O)).

  darij


Hello,

This is a problem from the project euler site that I've been having some trouble solving. I don't want a complete solution, just a few hints on how to approach these kind of problems.

I have to find out how many $ N$ digit numbers with no more than $ 3$ repeated digits exist.

I know that for $ N$ <= $ 3$ it's $ 9*N^(10)$, but I can't figure out how to go about counting for more...

Any help is much appreciated, thanks.

There are a couple of ways of approaching this problem. (Both cases involve fiddling around with leading 0s after the main calculations)

1) DP. The whole aim of DP is reducing to smaller cases. So (just explaining how I would think), lets say we know the first few digits of the number. What do you need to know to solve it from here?
[hide]All you need to know is how many 0s, 1s, .., 9s you  have left as possibilities, and how many digits you still need to use.[/hide]
[hide]Since at any point in time you only have 4 options per number (0 left, .. 3 left), and anywhere up to N digits left, thats 4^10 * N cases, which works fine for this problem.[/hide]

2) The other alternative doesn't use DP at all. If N=6 and you know you have 3 ones, 2 twos and a three, how many ways are there of arranging those 6 digits?
[hide]Simple combinatorics: 6!/(2!*3!*1!)[/hide]
If you ignore the order of the digits, there aren't very many options for choosing 0-3 of each digit with a total of 18 - you can use brute force to loop over each.

Let me know if you want more detail, I tried to leave most of the programming work out :)

For the DP solution, if I just have a recursive function that sets digits for each position, it's exactly the slow brute force solution.

So I was thinking about something like this
[hide]
You said there are only 4 options per number. So, maybe I can use something like cnt(i,j) = how many i digit numbers are there such that no digit occurs more than j times?

cnt(i,0) would be 0 for all i, cnt(1, j) would be 9 for all j and how would I get cnt(i,j) from this?
[/hide]

But that wouldn't work, because you wouldn't know whether adding a 1 would make j increase or not - as I said you need to know how many of each digit you've used, not just the maximum.

The reason this is faster than brute force is that the states 1132, 1312, 1213, 3211, etc are all handled by one case in the dp - the case where you've used two 1s, one 2, and one 3.

You can store how many of each digit you've used in a single bitmask - a number between 0 and 4^10 (the first two binary digits represent how many 0s you've used, etc).

Ok, I tried the following (I think this is what you talked about in your second method)

[hide]
I'm generating all possible configurations for each digit (0,1,2,3) in 4^10, such that their sum does not exceed N (and is equal to N at the end of a configuration) (if N is 3 you can't have 3 zeroes and 1 one for example). Then I added N!/nr0!*nr1!*...*nr9! where nri = how many i digits can I use for the current configuration.

I haven't accounted for numbers starting with a 0 yet. Could you explain a little about how this would be done? This seems to work if I consider numbers can start with 0.

EDIT: I figured it out. I made another function that returns the number of numbers with at most 3 digits and at most 2 zero digits (trailing zeros allowed) and subtracted this from the first number. Is there a simpler method?
[/hide]


Let ABCD be a convex quadrilateral with AB = BC = CD and $ \angle BAD \plus{} \angle ADC \equal{} 120 ^\circ$. If $ AC \cap BD \equal{} O$, prove that AO = OD.

This is just one part of problem 1 of the Balkan Mathematical Olympiad 2007 :wink: ,so it has been posted before.

More precisely look at here: [url]http://www.artofproblemsolving.com/Forum/viewtopic.php?p=827187#827187[/url]

To: CDP100

Attached, a nice solution of this easy problem.

Best regards,
sunken rock

Thank [b]CDP100[/b] very much. I used your post fos my student and I very like it.


geometry
rectangle
projective geometry
geometry solved

It's menalaus.

Let EH intersect BD at X, and let GF and BD intersect at Y. Then
DH/HA*AD/DB*BX/XD=-1=DG/GC*CF/FB*BY/YD,
and everything cancels to give
BX/XD=BY/YD, i.e. X=Y.

It does work with projective geometry as well:

Keep $E,G$ fixed, and move $F$ (i.e. move the line $FH$ so that it stays parallel to $AD$). You get a projective mapping $EH\mapsto GF$ from the pencil of lines through $E$ to the pencil of lines through $G$. The locus of the intersection $EH\cap GF$ is a line iff the line passing through $E,G$ is mapped to itself. This is easily seen to be true by making $F\to\infty$. We know that the locus of $EH\cap GF$ is a line, and we can see that it's $BD$ by making $F=B$ and then $F=C$, since in these two situations we have $EH\cap GF=B$ and $EH\cap GF=D$ respectively.

[quote="jhaussmann5"]Given rectangle ABCD, and points E, F, G, H on sides AB, BC, CD, DA, respectively, such that $EG \| AD$ and $HF \| AB$.  Prove that the lines FG, EH, and BD concur (or they are parallel).

I have a feeling there's an easy solution using one of the theorems from projective geometry, but I can't quite see it.[/quote]

Your feeling is pretty right. Since the quadrilateral ABCD is a rectangle, we have DC || AB. Together with HF || AB, this shows that the lines AB, DC and HF are all parallel to each other; thus, these lines pass through a common infinite point U. Similarly, the lines AD, BC and EG pass through a common infinite point V.

Now, by the Pappos theorem, applied to the collinear point-triplets (U; B; E) and (V; H; D), the points $BD\cap EH$, $EV\cap UD$ and $UH\cap BV$ are collinear. But $EV\cap UD=G$ and $UH\cap BV=F$. Thus, the points $BD\cap EH$, G and F are collinear. In other words, the point $BD\cap EH$ lies on the line FG. In other words, the lines BD, EH and FG concur. This solves the problem.

As this solution shows (and the solutions in the previous two posts also do), the quadrilateral ABCD need not be a rectangle; it is enough to assume that it is a parallelogram.

  darij

Thanks, everyone.  You guys are so smart.


I was looking around the site and saw a link for AoPS t-shirts. It said they were sold out. Are there plans for more?  I want one!

We are working on a way whizzy cool new one.  Hope to have it out by year end.

How are the shirts going? I would like to have one...

Oh heh I've asked about this in the forum before. Great to hear, rrusczyk! /me excited...

We're aiming for February for new TShirts.


abstract algebra
arithmetic sequence
complex numbers
group theory
algebra unsolved
algebra

Given sequence $ (u_n)$ satisfy: $ \large |u_{m\plus{}n}\minus{}u_{m}\minus{}u_{n}|<\frac{1}{m\plus{}n},\forall m,n\in\mathbb{N}^{*}$.
Prove that $ (u_n)$ is an arithmetic progression.

assuming that (u_n)means nth term of the sequence u
solving the inequation we get -(a-d)<1/m+n
inequation holds only for d<or equal to a

here d=common difference a= 1st term

looks like there is amaterial misstatement in question

The problem is fine. The only thing you could argue is that the conclusion isn't strong enough: if $ u_n \equal{} an\plus{}b$ for some $ a,b$ then $ u_{m\plus{}n}\minus{}u_m\minus{}u_n \equal{} \minus{}b$ so $ |b| < \frac{1}{m\plus{}n}$ forces $ b\equal{}0$. The sequence is not just an arithmetic progression, it has the simple form $ u_n \equal{} an$.

Also, it's not specified what kind of numbers the $ u_n$ are supposed to be - in fact, it doesn't matter much: they can be rational, real, complex, whatever. In the solution below you can assume that the $ u_n$ are complex numbers.

[hide="Solution."]
Let $ z_n \equal{} u_n\minus{}nu_1$. Then $ z_{m\plus{}n}\minus{}z_m\minus{}z_n \equal{} u_{m\plus{}n}\minus{}u_m\minus{}u_n\minus{}(m\plus{}n)u_1\plus{}mu_1\plus{}nu_1 \equal{} u_{m\plus{}n}\minus{}u_m\minus{}u_n$, so the sequence $ z_n$ satisfies the same condition

(1) $ |z_{m\plus{}n} \minus{} z_m \minus{} z_n| < \frac{1}{m\plus{}n}$ for all $ m,n \in \mathbb{N}$

but now we have $ z_1\equal{}0$ which makes things easier to understand. Using (1) with $ m\equal{}1$ we get

$ |z_{n\plus{}1}\minus{}z_n| < \frac{1}{n\plus{}1}$

so $ z_{n\plus{}1}$ is pretty close to $ z_n$ for large $ n$, which means that $ z_{n\plus{}17}$ can't be too far from $ z_n$ either. In fact, letting $ k$ be fixed positive integer,

$ |z_{n\plus{}k}\minus{}z_n| \equal{} |z_{n\plus{}k}\minus{}z_{n\plus{}k\minus{}1}\plus{}z_{n\plus{}k\minus{}1} \minus{} \ldots \plus{}z_{n\plus{}2}\minus{}z_{n\plus{}1}\plus{}z_{n\plus{}1}\minus{}z_n| \leq$

$ \leq |z_{n\plus{}k}\minus{}z_{n\plus{}k\minus{}1}| \plus{} |z_{n\plus{}k\minus{}1}\minus{}z_{n\plus{}k\minus{}2}| \plus{} \cdots \plus{} |z_{n\plus{}2}\minus{}z_{n\plus{}1}| \plus{} |z_{n\plus{}1}\minus{}z_n| <$

$ < \frac{1}{n\plus{}k\minus{}1}\plus{}\frac{1}{n\plus{}k\minus{}2}\plus{} \cdots \plus{}\frac{1}{n\plus{}2}\plus{}\frac{1}{n\plus{}1}  < \frac{k}{n\plus{}1}$.

So $ z_{n\plus{}k}\minus{}z_n$ is tiny for fixed $ k$ and large $ n$. However, using (1) again with $ m\equal{}k$ we get

(2) $ |z_{n\plus{}k}\minus{}z_k\minus{}z_n| < \frac{1}{n\plus{}k}$

which means that $ z_k$ is very close to that tiny $ z_{n\plus{}k}\minus{}z_n$, so it must be tiny itself. Formally,

$ |z_k| \equal{} |z_k \minus{} (z_{n\plus{}k}\minus{}z_n) \plus{} (z_{n\plus{}k}\minus{}z_n)| \leq |z_{n\plus{}k}\minus{}z_k\minus{}z_n| \plus{} |z_{n\plus{}k}\minus{}z_n| <$

$ < \frac{1}{n\plus{}k} \plus{} \frac{k}{n\plus{}1} < \frac{k\plus{}1}{n\plus{}1}$

which means that $ z_k$ must be 0: taking $ n$ arbitrarily large forces $ |z_k|$ to be arbitrarily small.

So $ z_k \equal{} 0$ for all $ k \in \mathbb{N}$, namely $ u_k \equal{} ku_1$ for all $ k$ and the original sequence is, indeed, an arithmetic progression. QED

[/hide]

if the sequence of their consecutive differences is constant?  really, the definition goes over to complex numbers perfectly well.

[quote="James Bond007"]Look I may be wrong but how can complex nos. be in A.P. :|[/quote]

What do you think an arithmetic progression is?

if $ x_n$ is a sequence of elements in any algebraic structure where it makes sense to subtract (say, an abelian group), then $ x_n$ is an arithmetic progression iff $ x_{m\plus{}1}\minus{}x_m$ is a constant, independent of $ m$. Some examples:

AP in $ \mathbb{Z}$: $ 7, 9, 11, 13, 15, 17, \ldots$

AP in $ \mathbb{R}$: $ \pi\plus{}e, \pi\minus{}e, \pi\minus{}3e, \pi\minus{}5e, \ldots$

AP in $ \mathbb{C}$: $ 2\plus{}i, 2i, \minus{}2\plus{}3i, \minus{}4\plus{}4i, \minus{}6\plus{}5i, \ldots$

AP in $ \mathbb{R}^3$: $ (3,4,9), (2,6,8\frac{1}{2}), (1, 8, 8), (0, 10, 7\frac{1}{2}), \ldots$

AP in $ \mathbb{Z}/7\mathbb{Z}$: $ 3, 6, 2, 5, 1, 4, 0, 3, 6, 2, 5, 1, 4, 0, \ldots$

The statement of the problem - and the proof - work in any setting where there is a norm $ |x|$ satisfying the triangle inequality. It applies for all the examples I just gave except the last one.


Can anyone prove the equation below:

         1/(m-a)=1/(m-1)+(a-1)/(m-1)(m-2)+(a-1)(a-2)/(m-1)(m-2)(m-3)+.......+ (a-1)!/(m-1)...(m-a).

     m,a is Nature Number and m>a.

by the way, is there any website discuss  expansion like that?

thx.

This is a nice exercise for induction. Proceed by induction on $a$. In the induction step use the hypothesis for $m$ replaced by $m-1$. (Note that $a+1<m\Longleftrightarrow a<m-1$.)

If we multiply both sides of the expression by $\frac{(m-1)!}{(a-1)!(m-a-1)!}$, we get
$\binom{m-1}{a-1}=\binom{m-2}{a-1}+\binom{m-3}{a-2}+\binom{m-4}{a-3}+\dots+\binom{m-a-1}{0}$,
which is a known identity called the [url=http://ptri1.tripod.com/]"Hockey Stick Pattern"[/url] in Pascal's Triangle. :)
(Of course, the identity can be proved by induction).


$ 30$ boys and $ 20$ girls are preparing for $ 2004$ Team Selection Test.They observed that any two boys have an even number of common acquaintances among girls.And exatly $ 9$ boys know an odd number of girls.
Prove that there exists a group of $ 16$ boys such that any girls attending the prepartion is known by an even number of boys from this group.

I have to apologize that the problem should be:[b]there exists a group of at least $ 16$ boys balabala...[/b]


Hey guys,

Did anyone get that crazy trig question (the last one) on the last OLYMON issue?

I couldn't get it either. It was just not my type of problem. It was too technical.  I bet that Peng and Yufei got this.

[quote="billzhao"]err ... never tried. Been too busy working on other things (like university applications) instead.[/quote]
How about Peng then? :?

Apparently there are only a dozen people actually doing Olymon.  Needless to say, participation is decreasing....I know that a ton of people do them, but very few bother to send them in.

Any reasons why participation is decreasing?

just never bothered, im sure others think that too

i think because december is much easier, participation will be way up.

Does anyone do Skoliad or anything from Crux/Mathematical Mayhem?  I sent in solutions once just for the fun of it.  My mom says they sent me a book as a prize.  (A book of old volumes of the same.  I have yet to see it, as it's in London and I'm here in Toronto.)  But as a result of being sent this book, I'm supposed to promote it.  Er, so... Send in your solutions!  (Don't bother with the rebuttals.  I know what you're going to say.)

I have a CRUX subscription, but I've never sent in anything.  I'll look into sending in some solutions to the Olympiad Corner later; maybe.

In the October issue or something, I see Yufei Zhao solving all (or almost all) of the Olympiad Corner probs (was it the Olympiad Corner?).  Dang.

I've only submitted to the Olympiad corner about twice, since it takes too long for it to be published (~2 years). Whereas the Problem/Solution section is only about a year.


function
vector
ratio
linear algebra
matrix
algebra proposed
algebra

Let $f_1, f_2, f_3 : R \rightarrow R$ be functions such that $a_1f_1 + a_2f_2 + a_3f_3$ is
monotonous for all $a_1, a_2, a_3 \in R$. Show that there exist real numbers
$c_1, c_2, c_3$, not all zero, such that
$c_1f_1(x) + c_2f_2(x) + c3f3(x) = 0$ for all real $x$.

you said $a_1f_1+a_2f_2+a_3f_3$ is monotonous.what monotonous means?
(is it mean that it is a fixed value or what?)  :?:

It means that the function is either increasing or decreasing on the whole of its domain.

A really nice problem :).

Fix four reals $x,y,z,t$ with $x\ne y,\ z\ne t$. The hypothesis tells us that $\sum a_i\frac{f_i(x)-f_i(y)}{x-y}$ and $\sum a_i\frac{f_i(z)-f_i(t)}{z-t}$ have the same sign for all triples of reals $a_i$ (here $0$ is considered to have either sign, depending on the situation). This is equivalent to the fact that the vectors $v(x,y)=\left(\frac{f_i(x)-f_i(y)}{x-y}\right)_i,v(z,t)=\left(\sum a_i\frac{f_i(z)-f_i(t)}{z-t}\right)_i$ are collinear (and their ratio is non-negative). Notice that this implies, in particular, that if for some $i\ f_i$ is not injective, then it's constant (the $i$'th component of $v(x,y)$ will be zero for some $x\ne y$, and then the $i$'th component of $v(z,t)$ will be zero for all $z\ne t$).

All of this applies to $(f_1^{(c)}=\sum c_if_i,f_2,f_3)$ instead of $(f_1,f_2,f_3)$ for any $c=(c_1,c_2,c_3)$. Fix any two distinct reals $x\ne y$. We can then find $c=(c_1,c_2,c_3)\ne 0$ s.t. $\sum c_if_i(x)=\sum c_if_i(y)=0$. The observation in the last paragraph applied to $(f_1^{(c)},f_2,f_3)$ shows that $f_1^{(c)}$ must be identically null, since it takes the value $0$ in two distinct points, $x$ and $y$.

A simpler solution  using vector spaces.
We can consider a vector $v = (f_1(x), f_2(x), f_3(x))$ for $x \in \mathbb{R}$.
The motivation for this was that we had to prove  the existence of $c_1, c_2, c_3 \in \mathbb{R}$ (All of $c_i \neq 0$), kind of equivalent to a vector subspace $(c_1, c_2, c_3)$ orthogonal to our original subspace $(f_1(x), f_2(x), f_3(x))$ which would give us $\sum_{i=1}^n c_if_i(x) =0 $ for all real $x$.
But this will hold only if we have $v$ to be a proper subspace in $\mathbb{R^3}$.
For this we have to use the monotonic part of the problem.
As usual, let us assume for a proof by contradiction that $v$ can have a span fully in $\mathbb{R^3}$.
As it is spans of all  $\mathbb{R^3}$, then we can easily find three reals $a_1,a_2,a_3$ in  $\mathbb{R^3}$ such that $v_1 = v(a_1), v_2 = v(a_2), v_3 = v(a_3)$ being linearly independent .
But then this would imply that the $3 \times 3 $ matrix $X$ with $X_{mn}= f_n(a_m)$ has linearly independent rows, inspite of being invertible matrix and spanning over $\mathbb{R^3}$, thereby giving the existence of $c_i$ such that $\sum_{i=1}^n c_iv_i = (0,1,0)$ making the function non monotonic.


vector
invariant
geometry
complex numbers
combinatorics solved
combinatorics

We attach to the vertices of a regular hexagon the numbers $1$, $0$, $0$, $0$, $0$, $0$. Now, we are allowed to transform the numbers by the following rules:

(a) We can add an arbitrary integer to the numbers at two opposite vertices.
(b) We can add an arbitrary integer to the numbers at three vertices forming an equilateral triangle.
(c) We can subtract an integer $t$ from one of the six numbers and simultaneously add $t$ to the two neighbouring numbers.

Can we, just by acting several times according to these rules, get a cyclic permutation of the initial numbers? (I. e., we started with $1$, $0$, $0$, $0$, $0$, $0$; can we now get $0$, $1$, $0$, $0$, $0$, $0$, or $0$, $0$, $1$, $0$, $0$, $0$, or $0$, $0$, $0$, $1$, $0$, $0$, or $0$, $0$, $0$, $0$, $1$, $0$, or $0$, $0$, $0$, $0$, $0$, $1$ ?)

Consider the centre of the hexagon O, and let the vertices be A,B,C,D,E,F.

Then notice that in our 3 allowed operations, the vector sum OA+OB+..+OF  remains constant. So it is obviously impossible to get the desired cyclic permutation.

[quote="Jacob Tsimerman"]Then notice that in our 3 allowed operations, the vector sum OA+OB+..+OF  remains constant.[/quote]

You probably wanted to say $a\cdot \overrightarrow{OA}+b\cdot \overrightarrow{OB}+c\cdot \overrightarrow{OC}+d\cdot \overrightarrow{OD}+e\cdot \overrightarrow{OE}+f\cdot \overrightarrow{OF}$, where a, b, c, d, e, f are the numbers attached to the vertices A, B, C, D, E, F. This solution was also given by some contestants; they spoke of complex numbers rather than vectors (so that instead of the vectorial sum $a\cdot \overrightarrow{OA}+b\cdot \overrightarrow{OB}+c\cdot \overrightarrow{OC}+d\cdot \overrightarrow{OD}+e\cdot \overrightarrow{OE}+f\cdot \overrightarrow{OF}$, they considered the complex invariant $a+b\varepsilon _{1}+c\varepsilon _{2}+d\varepsilon _{3}+e\varepsilon _{4}+f\varepsilon _{5}$, where $\varepsilon _{i}$ are the 6th roots of unity not equal to 1; I believe this expression is called Langrange resolvent or something similar).

In fact, there was the following story:

At the beginning of the exam, when we received the problems, I said: Curses, a problem on a regular hexagon but it has nothing to do with geometry! As an answer, Friedrich Feuerstein (another of the participants) shouted: Why not? You can solve it by complex numbers! This was, of course, meant as a joke, so I didn't even try to look out for a solution of this kind, but some others tried, and found the above very nice solution...

  Darij


function
induction
algebra proposed
algebra

Find all the functions $ f: \mathbb{Q}\rightarrow \mathbb{R}$ such that :

$ f(x\plus{}y\plus{}z)\equal{}f(x)\plus{}f(y)\plus{}f(z)\plus{}\sqrt[3]{f(x\plus{}y)f(y\plus{}z)f(z\plus{}x)}\ ,\ (\forall)x\in \mathbb{R}$ .

It resembles the identity $ (x\plus{}y\plus{}z)^3\equal{}x^3\plus{}y^3\plus{}z^3\plus{}3(x\plus{}y)(y\plus{}z)(z\plus{}x)$
So the only solutions must be $ f \equiv 0$ and $ f(x)\equal{}\frac{1}{3}x^3.$

Your solution is not complete :maybe: You did it intuitive .

$ P(0,0,0)$ implies $ f(0)\equal{}0$.
$ P(x,\minus{}x,0)$ implies $ f$ is odd function.
Suppose $ f(a)\ne0$ for some $ a\ne0$.

Compare $ P(0,a,a)$ and $ P(0,2a,0)$, we get
$ 2f(a)\plus{}\sqrt[3]{f(a)f(a)f(2a)}\equal{}f(2a)$, and then
$ f(2a)\equal{}c^3f(a)$, where $ c$ is the real root to $ x^3\minus{}x\minus{}2\equal{}0$.

Compare $ P(0,a,2a)$ and $ P(0,3a,0)$, we get
$ f(a)\plus{}f(2a)\plus{}\sqrt[3]{f(a)f(2a)f(3a)}\equal{}f(3a)$
Also,
$ P(a,a,a)$ gives $ f(3a)\equal{}3f(a)\plus{}f(2a)\equal{}(3\plus{}c^3)f(a)$

Combine the above two, we get
$ 3\plus{}c^3\equal{}1\plus{}c^3\plus{}\sqrt[3]{(3\plus{}c^3)c^3}$.
Contradiction with $ c^3\minus{}c\minus{}2\equal{}0$!

Hence, the only solution is $ f(x)\equal{}0$.

:maybe:

Let be $ x=y=z=0 \Rightarrow f(0)=0$

Let be $ y=-x,z=0\Rightarrow f(-x)=-f(x)$

Let be $ x=y\ ,\ z=0 \Rightarrow f(2x)=-f(x)$ or $ f(2x)=8f(x)$

Let be :

$ A=\{x\in \mathbb{Q}^*\ |\ f(2x)=-f(x)\}$

$ B=\{x\in \mathbb{Q}^*\ |\ f(2x)=8f(x)\}$

$ x\in A\Rightarrow f(2x)=-f(x)$ , and if $ x=y=z=0\Rightarrow f(3x)=0$

By induction $ \Rightarrow f(nx)=0\ ,\ (\forall) n\in \mathbb{N}$

$ x\in B\Rightarrow f(nx)=n^3f(x)\ ,\ (\forall)n\in \mathbb{N}\ (1)$

Let's prove (1) by induction .

Let be $ x=y\ ,\ z=(n-1)x$

$ \Rightarrow f((n+1)x)=2f(x)+f((n-1)x)+\sqrt[3]{f(2x)f^2(nx)}=2f(x)+(n-1)^3f(x)+\sqrt[3]{8f(x)n^6f^2(x)}=2f(x)+(n-1)^3f(x)+6n^2f(x)=(n+1)^3f(x)$

We can see that $ f=0$ is a solution so we must find $ f\neq 0\Rightarrow (\exists)u\in \mathbb{Q}\ ,\ u>0$ such that $ f(0)\neq 0$

We can't have $ u/3\in A\Rightarrow u/3\in B\Rightarrow f(u)=f(3\frac{u}{3})=27f(u)$

$ f(nu)=f(3n\frac{u}{3})=27n^3f(\frac{u}{3})$

$ \Rightarrow f(nu)=n^3f(u)\ ,\ (\forall)n\in \mathbb{N}$

Let be $ n\in \mathbb{N}^*$ . We can't have $ u/n\in \mathbb{A}\Rightarrow u/n\in \mathbb{N}$

$ \Rightarrow f(u)=f(n\frac{u}{n})=n^3f(\frac{u}{n})\Rightarrow f(\frac{u}{n})=\frac{1}{n^3}f(u)$

$ \Rightarrow f(\frac{m}{n}u)=\frac{m^3}{n^3}f(u)\ ,\ (\forall)m,n\in \mathbb{N}$

Let be $ p,q\in \mathbb{N}^*$ such that $ p/q=u$ and let be $ m,n\in \mathbb{N}^*$ arbitrars .

${ \Rightarrow f(\frac{m}{n})=f(\frac{mq}{np}u})=\frac{m^3q^3}{n^3p^3}f(u)=\left(\frac{m}{n}\right)^3\cdot \frac{1}{u^3}f(u)=a(\frac{m}{n})^3$ , where $ a=\frac{f(u)}{u^3}\in \mathbb{R}^*$

$ \Rightarrow f(x)=ax^3\ ,\ (\forall)x\in \mathbb{Q}\ ,\ x>0$ , but $ f(-x)=-f(x)$

Conclusion : Solutions are the functions $ f(x)=ax^3\ ,\ a\in \mathbb{R}$ .

alex2008, it seems you are working on
$ f(x\plus{}y\plus{}z)\equal{}f(x)\plus{}f(y)\plus{}f(z)\plus{}3\sqrt[3]{f(x\plus{}y)f(y\plus{}z)f(z\plus{}x)}$

NOT

$ f(x\plus{}y\plus{}z)\equal{}f(x)\plus{}f(y)\plus{}f(z)\plus{}\sqrt[3]{f(x\plus{}y)f(y\plus{}z)f(z\plus{}x)}$.

:|  :ewpu: My really bad , xxp2000 . You're right . I think i was blind . Thank you , xxp2000


I'm looking for a free Computer Algebra System (CAS) that works on a Windows platform to use with my high school calculus students next year. Some of them are unaware of the capabilities of CAS technology, and I would like to begin integrating some CAS activities with them in order to increase their fluency with technology.

The CAS should be free, have as simple an interface and syntax as possible, and yet be able to demonstrate to a high school student a decent range of the capabilities of a CAS (particularly, symbolic differentiation and anti-differentiation, symbolic solving of equations, graphing of implicit functions, and taylor series expansions). I would also like it to have some portability of skills to other (non-free) CAS systems that they may use later life.

I currently use PARI/GP. If you have any experience with this program, let me know how it compares to other programs as it is the only one that I have any familiarity with.

How about Maxima?.

[url=http://maxima.sourceforge.net/]The official Maxima website[/url]
[url=http://en.wikipedia.org/wiki/Maxima]Maxima[/url] - Wikipedia

Thanks for this suggestion. I'll download it and play around with it.


calculus
integration
calculus computations

$I_{n}$ =$\int_{0}^{1}x^{n}tan^{-1}xdx$

Find the limit of $4n.I_{4n}$ as n approaches  infinity


HCSSiM
summer program
PROMYS
geometry
function
algorithm

I am currently applying to both of these summer programs, but I have heard that PROMYS is harder, more intensive, prestigious, well-known, etc... than HCSSiM is. Can anyone who has had experience with (or knows about) both programs shed some light on the comparison between the two?

Thanks!

Have you received the IT yet from HCSSiM? I have not!!!! :mad:

I have no experience with PROMYS, but I certainly can say something about HCSSiM.

In terms of the stuff on that list that actually means anything, i.e. difficulty and "intensiveness":

8 hours each day are spent doing math, though plenty of people do more than that. Weekday schedules are as follows:

We wake up and eat breakfast in time to get to our classes, which meet from 8:30-12:30. For the first three weeks, the program of ~40 students is split up into three "workshops," in which we learned some Number Theory, Group Theory, Graph Theory, and a bunch of other stuff that I'm not remembering at the moment.

For the last three weeks, these four hours are split into a 2.5 hour "maxi" class, and a 1.5 hour "mini" class. The minis are each a week an a half long, so each person takes one maxi and two minis.

Last year's maxis included one on polytopes, one on mathematical origami, and one on probability.

Minis included ones on non-euclidean geometry, knot theory, topological graph theory, generating functions, diophantine equations, set theory, random walks, algorithms, Galois theory, Markov chains, and possibly some others.

Each workshop and maxi is taught by one "Senior Staff" member ("folks with Ph.D.s, y'know"),  and one or two "Junior Staff" members. (One Junior Staff member last year left three-quarters of the way through the program to officially receive his Ph.D. diploma. He is now teaching at Yale,) The staff members were some of of the best teachers I have ever had.

The classes, in my opinion, were taught on a very high level, with much emphasis on proof and mathematical rigor.

Oh, yeah, I was supposed to be going through the day. At 12:30, there was lunch, and then most afternoons we were free to do what we liked--some people played frisbee, some did more math, some just hung out and talked in the gazebo (Adam's gazebo). There was the occasional "quasi", or one-time informal class on things related or unrelated to mathematics.

At 5:00 (17:00), the program gathered for the"Prime Time Theorem", or an hour-long mathematical lecture by a staff member or guest lecturer.

At 6:00, we ate dinner.

From 7:30 to 10:30, there was problem session, in which people worked together on problems related to what they were learning in their workshop or maxi. The problems ranged in difficulty from the simple application of a technique we learned in class to the occasional open problem (which would be cruelly unspecified as such).

We would hand in our write-ups at 10:30 (and get them back with detailed comments usually at some point the next day), and go back to the "mods" (dorms) so as to be in our rooms by "quiet time", which was at 11:17.

This schedule naturally fluctuated. Sundays usually consisted of mostly down-time. Wednesdays (I think), there were math movies instead of the first half-hour or so of problem session. Saturdays, workshops ended early, or there were no minis, and instead there was some sort of activity.

I think it was a pretty "intensive" schedule, filled with pretty "hard" mathematics, though it was not at all a grind.

Now on to the stuff that shouldn't matter to you at all: It is quite well-known in the mathematics community. It has been around for >34 years, so it has its fair share of relatively well-known alumni/ae, for more info about that, see http://hcssim.org/alumns.php, and for more info about past faculty, see http://hcssim.org/faculty.php

My experience at HCSSiM was truly eye-opening, and I am probably not nearly doing justice to it by this description.

I also apologize for my many tense-shifts in the above description. (I was never sure whether I was describing the typical HCSSiM experience (i.e. present tense), or my particular one last year (i.e. past tense), so I just switched back and forth, which is absurdly terrible practice, but I hope you'll get over it).

@mathemonster: email them. I know someone who is applying who had received the IT.

PROMYS is a little more number-theory specific, though of course there are opportunities to learn more.  The counselors teach their own mini-courses at night and there are also second-year courses available for those who are interested.

As far as prestige, I really hate that word.  Don't go to a summer program just because you think it'll look good.  Among my friends at top colleges, the HCSSiM/PROMYS/Ross/Mathcamp split is pretty much even.  And people definitely know about HCSSiM.  If you really want to think in terms of college applications, just think about doing your best wherever you are and getting a good recommendation letter.

I, too, have gone to Hampshire (two years ago).  I would like to add that the junior staff member to whom I think yjneb is referring recently received the [url=http://www.siam.org/prizes/sponsored/konig.php]Dénes König Prize[/url].

In my year, we had a "Fools' Quasi", in which we worked (or attempted to work) on a piece of Grünbaum's conjecture, a generalization of the four-color theorem that was at the time an open problem.  Since then, counterexamples to the conjecture have been found on toruses with five holes or more, but it is still not known on which "small" toruses the conjecture holds.  In the Fools' Quasi, we actually proved two lemmas that were used to obtain a partial answer to this question for a single-holed torus.

Also, one of the quasi series sketched out most of an undergraduate complex analysis course in three sessions, each of which lasted an hour or two, if I remember correctly.

One of the most valuable parts of HCSSiM, I think, was the series of evening Prime-Time talks.  This allowed many different people the opportunity to tweak our minds, and exposed us to great breadth in a short period of time.  Two years later, I still think over things from prime time talks at odd moments.

Another good thing about Hampshire is the Program Journal (PJ), a weekly publication that chronicles the mathematical activity at HCSSiM, and some of the other activity.  Students edit the journal (the editing positions rotate), and student is expected to contribute at least on or two articles over the summer.  I cannot emphasize how important it is to learn to write mathematical things that your peers read.  There are many people who excel at things like ARML but who can't write at all.

I don't know where you're getting these notions about "prestige".  Perhaps you think that PROMYS is more "prestigious" because you think it isn't as silly as HCSSiM sometimes is.  Well, it probably isn't.  But HCSSiM does involve earnest, meaningful exploration of serious mathematics.  Seriously.  We just have fun in between.

Really, neither program is measurably "better" or "more prestigious" than the other.  There are probably very few people who know of one program but not the other; people who know about one of {HCSSiM, Ross, PROMYS, Mathcamp} know about all of them.

It's a matter of personal taste.  I'd pick Hampshire over PROMYS, but I know a few people who've been to PROMYS, and they'd probably say just the opposite.  I think that PROMYS has more fixed structure than HCSSiM.  But I've never been to PROMYS, so anybody from PROMYS, please feel free to add detail or correct anything I've said about it.

[quote="t0rajir0u"]I don't really remember there being many rules at PROMYS.[/quote]
You may be right, but I bet there were even fewer rules at Hampshire.  (For one thing, Hampshire is on a rural campus and PROMYS is in Boston.)  But maybe what I said was unjustified; I'll change that sentence to "I think PROMYS has more fixed structure."  I'm not sure if that's fair either, though.  I guess I'm trying to say that a very free spirit pervades HCSSiM.

[quote]The problem sets have the somewhat unusual property that they aren't intended to be completed.  The idea is to do as much as possible, but the end of every problem sets contains what I guess you could call "challenge" problems intended to keep those at the highest level at the program (which, for my year, was Jason Bland) busy.[/quote]
HCSSiM problem sets were usually like this, except that for us these were mostly open problems in disguise.  There were some problems that were hard standard results, such as proving that Liouville's number is transcendental.  I don't think that these were expected to be solved regularly, but occasionally people solved them.  (I remember this particular problem because I did solve it, though I ended up finishing the write-up a day or two after the problem session.)  In general, we were supposed to let no problem take up more than $ 1/e$ of the problem session, though there were many violations of this principle.  Occasionally there was a problem that appeared several times on a problem set to emphasize that it was important and that nobody had solved it yet.  Usually this ended either with some group solving it and presenting the next day, or a staff member presenting the solution or assisting a group that had gotten part way.

[quote]the last few problem sets were pretty ridiculous.[/quote]
We didn't really have sets like this---there was always something for everyone.

[quote]I spent most of the six weeks in my room and have regretted it ever since :oops:[/quote]
Yes, the social element is one of the most important parts of any summer program.  Be sure to spend time with other people, wherever you go this summer.

[quote="Boy Soprano II"]I guess I'm trying to say that a very free spirit pervades HCSSiM.[/quote]
You may be right.  I will say this about PROMYS, at least the students in my year, and it's the only thing I didn't like about the program:  they take Mafia more seriously than any group I have ever met.  :P

[quote="buzzer11"]Thanks for all the input, I think I know the general differences between the two camps now.

t0rajir0u, I didn't mean "prestige" as in college applications, I meant "prestige" as in high level, well organized, etc. (Of course, well known as well, but being well known is a sort of side effect of the aforementioned qualities.)

and mathemonster, I did receive the IT, on March 17th. You might want to contact them.[/quote]
i did, but as to not lose more time will you please email it to me (pm me for details) or pm me it.
Thanks sooo much  :)

[quote="t0rajir0u"][quote="buzzer11"]I meant "prestige" as in high level, well organized, etc. [/quote]
This is not at all what "prestige" means  :|[/quote]
 :blush:

mathemonster, I'll pm you the questions.

EDIT: never mind, it's probably easier to email.

[quote="t0rajir0u"][quote="Boy Soprano II"]I think that PROMYS is more structured and rule-oriented than HCSSiM.  But I've never been to PROMYS, so anybody from PROMYS, please feel free to add detail or correct anything I've said about it.[/quote]
I don't really remember there being many rules at PROMYS.   The biggest difference, at least from what you two have said, is that the main number theory course at PROMYS lasts the entire six weeks and the problem sets from that course are the "main course" of the program, so to speak.  We also get an opportunity to conduct a little mini-research project if we so chose, but I don't know much about that since I took a second-year course in Galois theory instead.

The problem sets have the somewhat unusual property that they aren't intended to be completed.  The idea is to do as much as possible, but the end of every problem sets contains what I guess you could call "challenge" problems intended to keep those at the highest level at the program (which, for my year, was Jason Bland) busy.  And the last few problem sets were pretty ridiculous.

Of course, there's also a periodic event known as "Mandatory Fun."  But I'm not really the one to talk to about the social life at PROMYS - I spent most of the six weeks in my room and have regretted it ever since :oops:[/quote]
Can you talk a little more about what you do at PROMYS after you finish NT? What is Galois Theory? Are the research projects high level (what can u do with just basic NT)? Also at these camps would u say u learn the NT of a non-major or a for majors class? I only ask b/c im doing college math soon and I don't want to take the NT for math majors if it will be redundant. Thanks  :D

[quote="mathemonster"]what you do at PROMYS after you finish NT?[/quote]
Number theory takes the whole six weeks.  There's no such thing as finishing number theory :P

[quote="mathemonster"]What is Galois Theory?[/quote]
[url=http://en.wikipedia.org/wiki/Galois_theory]Let me Wikipedia that for you.[/url]

[quote="mathemonster"]Are the research projects high level (what can u do with just basic NT)?[/quote]
PROMYS students are encouraged to collaborate actively with the counselors and staff.  What that means is that they're as high level as you can handle.

[quote="mathemonster"]Also at these camps would u say u learn the NT of a non-major or a for majors class?[/quote]
PROMYS definitely has the secret goal of turning all of its participants into math majors.  If there's one thing you don't have to worry about, it's the math not being hard enough.  You learn at least as much as a normal undergraduate course and there are plenty of opportunities (counselors, second-year courses, research) to learn arbitrarily more.  Trust me, if you aren't challenged I'll personally give you more stuff to do :P

[quote="buzzer11"]Also, about how many of the PROMYS questions should I answer? Are we expected to answer all of them?[/quote]
As many as you can, and no.

I plan to work my butt of so thats good. I'm not too great at contest math but when I have time to think im good (solving the app problems/USAMTS) Do the counselors normally suggest research projects? how many hours a day do u do NT and how many do u do research/galois theory etc?

[quote="mathemonster"]Do the counselors normally suggest research projects?[/quote]
I think the program does, but I'm not sure; again, I didn't do one.

[quote="mathemonster"]how many hours a day do u do NT[/quote]
The class is two hours long (if I recall).  The problem sets take however long you need :)

[quote="mathemonster"] and how many do u do research/galois theory etc?[/quote]
However long you want.  The difficulty (and hence time commitment) of either the projects or the second-year courses varies by year, project, and course, so it's hard to generalize.

[quote="t0rajir0u"]Trust me, if you aren't challenged I'll personally give you more stuff to do :P[/quote]

You will be a counselor there?

He applied, and I'm guessing (from his post) he was accepted.

Thank you for answering all of our questions, by the way!

[quote="buzzer11"]Are PROMYS students accepted on a first come, first served basis?[/quote]
As far as I know.  Exceptions might be made, but admissions are definitely rolling.

[quote="Smartguy"]You will be a counselor there?[/quote]
Well, I'm hoping.  I suppose that was presumptuous of me because I haven't actually been accepted yet  :oops:

[quote="buzzer11"]Hmm... I should probably get starting on my application then.  :blush:[/quote]
YES u should

[quote="buzzer11"]At least I'm on spring break... and the problems don't look too bad. Off to work.
You already turned yours in, right?[/quote]
yup i did it during my spring break in march  :P

Lucky, lucky, lucky.
btw, we have the same website, I just noticed. :P

btw i would recommend after u finish $ \geq 6$ problems u submit unless others are forthcoming b/c of the rolling admissions.

[quote="buzzer11"]Okay, I've done most of them, so I'll submit as soon as possible. Thanks for the advice. :)[/quote]
Hopefully I will see you there  :) U did all of them in 1 day?

Not all of them, I bs-ed some of the harder ones...

Triple post? :)

Haha I'm a bit nervous though... I have a feeling they won't like it very much.

those of you who went/are going to PROMYS, what's your purpose?
I love math, but I don't really want to STUDY pure math a lot and be a mathematician or that kind of staff.... The program sounds interesting, but number theory is hard for me. Do you think I will enjoy it?

I also worried that if I learned the stuff here, wouldn't it be boring to learn it in college again?

Not much time left this year, I will try....

[quote="wuyonglin2004"]those of you who went/are going to PROMYS, what's your purpose?
I love math, but I don't really want to STUDY pure math a lot and be a mathematician or that kind of staff.... The program sounds interesting, but number theory is hard for me. Do you think I will enjoy it?[/quote]
PROMYS is the experience that convinced me I wanted to study pure math.  If you aren't interestedy in number theory, you probably shouldn't go to PROMYS.

[quote="wuyonglin2004"]I also worried that if I learned the stuff here, wouldn't it be boring to learn it in college again?[/quote]
Why would you have to learn it again?

what do u want to be if not a mathematician?
why do u want to go


let AX,BY,CZ altitudes of acute triangle ABC and let K and M be points on the line segments XZ and BZ,prove that if the angles MAK and CAX  are equal,then the angle ZKM  is bisected by AK

Is $M$ by any chance on $YZ$ instead of $BZ$? It doesn't look right. Besides, something that made me think it's on $YZ$ is that if we put $K=X,\ M=Y$ then the conclusion will hold and the hypothesis is satisfied.

Indeed, you are right Grobber, M must lie on YZ.

The solution is rather simple. We need the following lemma:

[b]Lemma 1.[/b] Let ABC be a triangle, and P a point lying on the external angle bisector of the angle ABC, such that the points P and B lie in the same halfplane with respect to the line CA. Then, if < CPA = < CBA / 2, then P is one of the excenters of triangle ABC, namely either the C-excenter or the A-excenter.

[i]Proof.[/i] If P is either the C-excenter or the A-excenter, then it is easy to establish the equation < CPA = < CBA / 2. [In fact, if, for instance, P is the A-excenter, then < CPA = 180 - < PAC - < PCA = 180 - A/2 - (180 - (90 - C/2)) = 180 - A/2 - (90 + C/2) = 90 - A/2 - C/2 = B/2 = < CBA / 2. Similarly for the C-excenter.] Hence, we have found two points P lying on the external angle bisector of the angle ABC and satisfying < CPA = < CBA / 2. Now, the equation < CPA = < CBA / 2 determines a circle (or, to speak precisely, a circular arc, since we have restricted our point P to one halfplane only). The external angle bisector of the angle ABC is a line. A circle can intersect a line at two points at most. Hence, the only points P on the external angle bisector of the angle ABC satisfying < CPA = < CBA / 2 are the C-excenter and the A-excenter. This proves Lemma 1.

Now to the solution of our problem. Among the orthic triangle trivia every geometer should know, there is the equality < YZX = 180 - 2C. [In fact, since Y and Z lie on the circle with diameter BC, we have < YCB = 180 - < YZB, so that C = < YZA, and similarly C = < XZB, so that < YZX = 180 - < YZA - < XZB = 180 - 2C.] Thus, < YZX / 2 = (180 - 2C) / 2 = 90 - C. On the other hand, by our hypothesis, < MAK = < CAX = 90 - < ACX = 90 - C. Hence, < MAK = < YZX / 2, or, in other words, < MAK = < MZK / 2. Now, the line AB is the external angle bisector of the angle KAM. [In fact, C = < YZA and C = < XZB, as we have shown before, so that < YZA = < XZB. Thus, AB is the external angle bisector of the angle KAM.] Hence, the point A lies on the external angle bisector of the angle KAM and satisfies < MAK = < MZK / 2. Trivially, the points A and Z lie in one halfplane with respect to the line MK. Hence, after Lemma 1, the point A is either the M-excenter or the K-excenter of triangle MZK. Of course, A can be the K-excenter only (this is obvious from a halfplane consideration). Thus, A is the K-excenter of triangle MZK, and consequently, the line AK bisects the angle ZKM. This solves the problem.

  Darij

I used a spiral similarity. If we restrict ourselves to the case when $M$ and $K$ are on the rays $(ZY,\ (ZX$ respectively we won't need to worry about various cases. By using spiral similarities centered at $A$ we show that $\angle AMS=\angle AKT=\frac {\pi}2$, where $S$ is the intersection pt of $AK$ and $CZ$ and $T$ is the intersection pt of $AM$ and $CZ$. From here we find that the quadrilateral $MSKT$ is cyclic, so $\angle MTS=\angle MKS=\angle MKA$. On the other hand, $\angle MTS=\angle ATC=\angle AKZ$, so $\angle MKA=\angle AKZ$ Q.E.D.

I didn't write everything, but it was just routine stuff.


calculus
integration
inequalities
trigonometry
real analysis
real analysis unsolved

[b]5.[/b] Prove the inequality $\ds\int_{0}^{\frac{\pi}{2}}{\frac{{(\cos x)^{\sin x}}}{{(\cos x)^{\sin x}+(\sin x)^{\cos x}}}\,dx}<1.$
(A. Kukush)

We may change the varibale $x = \frac{\pi}{2}$ and summing the integrals $I = \frac{\pi}{4}$ where $I$ is this integral.


Harmonical progression $a_{1}\ ,\ a_{2}\ ,\ \ldots\Longleftrightarrow$ Arithmetical progression $\frac{1}{a_{1}}\ ,\ \frac{1}{a_{2}}\ ,\ \ldots$,
which means for any ${k\in N\ ,k\ge 2\ ,\ \frac{1}{a_{k}}}=\frac{\frac{1}{a_{k-1}}+\frac{1}{a_{k+1}}}{2}$ $\Longleftrightarrow$ $\frac{2}{a_{k}}=\frac{1}{a_{k-1}}+\frac{1}{a_{k+1}}\ .$

[quote="neelnal"]What is arithmetic, geometric, and harmonic progression?

I know the first two: arithmetic and geometric, but what is harmonic?

Arithmetic is like: 1,5,9,13,17 rt?
Geometric is like: 1,3,9,27,81 rt?

Not sure....

I was never really on good terms with knowing terms and definitions. I do not find it necessary on the tests I took like USAMO and AIME.[/quote]

yeah the 2 are right
i think harmonici is the mean obtained by taking the reciprocal of the arithmetic mean of the reciprocals of a set of nonzero numbers.

harmonic mean is reciprocal of arithmatic mean of reciprocals


advanced fields
advanced fields unsolved

we know that $ L^p$ is complete i.e.  every cauchy sequence is convergence (riesz fischer theorem).prove by this theorem $ R^p$ is complete.

Maybe you should define what $ R^p$ is, this is not a standard symbol.

uhh, $ L^{3/2}$ is well defined, $ R^{3/2}$ maybe not so much.

Maybe this should mean $ \mathbb{R}^n$ with the $ p$-norm. Then everythings clear, because $ (\mathbb{R}^n,\|\cdot\|_p)\equal{}L^p(\Omega,A,\zeta)$ with $ \Omega: \equal{}\{1,\dots,n\}$, $ A: \equal{}\mathcal{P}(\{1,\dots,n\}$ and $ \zeta$ is the counting-measure.


[quote="RohanSingh"]Let Rand(a,b) generates all the numbers between a and b (both inclusive) with equal probability.  How to implement R(a,b) using R(0,1).[/quote]

Could you explain what exactly do you want to do?

ok, there is a function Rand() which generates random numbers

what is R() ?

Please read R(a,b) as Rand(a,b) i.e. random number generator between a and b both inclusive. There was a confusion in R(a,b) and Rand(a,b) in the last mail. They are same.

[quote="blahblahblah"]if $R(0,1)$ generates random numbers in $(0,1)$, then $a+(b-a)R(0,1)$ generates random numbers in $(a,b)$.[/quote]

It gives either a or b not the intermediate numbers.

[quote="blahblahblah"]Huh?  Does $R(0,1)$ only output $0$ or $1$?[/quote]

yes, R(a,b) generates all the integers between a and b (both inclusive).

Actually  $a+(b-a)*R(0,1)$ works to get a random number in the range $[a,b]$ if $R(0,1)$ is inclusive. Think about the transformations to the range of $R(0,1)$ that go on.

[quote="RohanSingh"]yes, R(a,b) generates all the [u][b]integers[/b][/u] between a and b (both inclusive).[/quote]

Are you sure? I think that the function $Rand(0,1)$ generates [u][b]real[/b][/u] numbers, not only integers

Notice that if we use $Rand(0,1)$ only we have exactly two possibilities  thus only two numbers to get at last

What does it mean to sum from $a$ to $b$ when $a$ and/or $b$ are not integers?  My first post in this thread is correct.

[quote="oooooh ya"]$a+ \sum_{i=a}^{b} r(0,1)$[/quote]

I think that I understood the problem right now.

[quote="RohanSingh"]Let $R(a,b)$ generates all the [b][color=red]integer[/color][/b] numbers between $a$ and $b$ (both inclusive) with equal probability.
How to implement $R(a,b)$ using $R(0,1)$?[/quote]

In the above sentence we should clarify that $a,b$ are [b]integer[/b] numbers

The  solution given by [b][color=blue]blahblahblah[/color][/b] was correct, because we didn't know yet that $R(0,1)$ has only integer values ([color=blue][b]RohanSingh[/b][/color] told it later)

But, now we know that $R(0,1) \in \{0,1\}$ and $R(a,b) \in \{a, \cdots, b\}$

I liked the solution given by [color=blue][b]oooooh ya [/b][/color] very much,
because $f(a,b)=a+ \sum_{i=a}^{b} r(0,1)$ generates numbers in $\{a,\cdots, b\}$ .

But there is a problem.
This distribution is a [url=http://mathworld.wolfram.com/BinomialDistribution.html][color=red][b]binomial distribution[/b][/color][/url], not [b]uniform[/b]

For example, the only chance to get $\sum_{i=a}^{b} r_k=a$ is when all $r_k$ are set to zero

This is only one chance in a total of $2^{b-a+1}$ cases.

So, the problem is [b]still unsolved [/b]...

[hide="My opinion is that this problem has not  a solution"]
For example $a=1, b=3$
We want to define the function $R(1,3)$, which generates random integer numbers  in $\{1,2,3\}$, with equal probability

So, the probability for each value is $\frac{1}{3}$

We are allowed to use only the function $R(0,1)$, say $k$ times.

The total number of all the posible events is $2^k$ which is not divisible by 3, hence [u]no solution[/u][/hide]

[color=blue]I thought it again; there exists a solution[/color]

In my previous post I was thinking in a math way.
But this is programming, so we can do more things

$R(a,b)$ simplifies to $R(0,n)$, by using the formula:

$R(a,b) = a+R(0,n),$ where $n=b-a$

Take the binary representation of $n: \ n=(n_k \cdots n_2n_1n_0)_2$

so, $n= \sum_{i=0}^{k}{n_i2^i}$

$R(0,n)=m =(m_k \cdots m_2m_1m_0)_2$

We want to find the binary digits of a number $m$, such that $0\leq m\leq n$

Each of $m_i$ should be $0$ or $1$. So it can be found by $R(0,1)$.

So the function we are searching for is $R(0,n) = \sum_{i=0}^{k}{R(0,1) \cdot 2^i}$, where $k=ceil(log_2n)$

The only think that we should take care of is that, if $R(0,n)$ happens to be greater than $n$, then we recall $R(0,n)$

[code]
do {r = R(0,n);} while (r>n);
q=r+a;
[/code]

$r \in \{0, \cdots, n\} \Rightarrow q \in \{a, \cdots, b\}$

So the output has the uniform distribution


How do you solve these kind of questions?

> What is the remainder when $ 5^{123456789}$ is divided by $ 7$?

> How many 3-digit multiples of 3 are there with distinct digits?

I think you use mod math for the first one, but if you do, can you please explain in detail the process? Because I know what mod is, but I'm not really sure how to use it....

Thanks!

I'm not sure if #1 should be here-actually, I'm not sure if modular arithmetic should be on this forum at all.
Whatever.
[hide="#1"]Look up [url=http://www.artofproblemsolving.com/Wiki/index.php/Fermat%27s_Little_Theorem]Fermat's Little Theorem[/url]. (If you want something more general, look up the totient function. Now, FLT states that for all a and p such that gcd(a,p)=1, $ a^{p\minus{}1}\equiv1\pmod{p}$. So, we have $ 5^6$ has a remainder of 1 when divided by 7. Now, we find the remainder when 123456789 is divided by 6 (so then we can just raise 5 to that power and find it (mod 7). Anyway, you find it is 3, so our answer is $ 5^3\pmod{7}$, which is 6.

Or you could just notice that $ 5^3$ is -1 (mod 7), and 3 divides 123456789, and 123456789 is odd and so the whole thing is -1 (mod 7), so 6.[/hide]

#2 is just some casework.

Okay, thanks. But I still don't get # 2.........

[quote="shentang"]Use the divisibility rule for 3 and brute force it.[/quote]

What do you mean "brute force" it?

Essentially, guess and check. Brute force is just trying (and failing) until you get the right answer, mostly used because there isn't a formula to work with.

[quote="isabella2296"]I see. Thanks!  :)[/quote]

#2 means -
How many multiples of 3 between 100 and 999 are there that have no digits repeated in them?

345 - works
333 - doesn't work, well duh, you repeated 3 3 times!

We know what it means, just need a method of finding the answer... :P

Correct me if I'm wrong, but couldn't you just do 9 x 8 x 7 for #2? You can have 1-9 for the hundreds digit, 0-9 for the tens digit minus the digit used for the hundreds, and 0-9 for the ones digit minus the digits used for the tens and hundreds. That would compute to 504 numbers.

And where do multiples of three fit in there? That's only calculation of all 3-digit numbers with distinct digits!

Oops, I didn't see the multiples of 3 part :blush: .

hmm no idea how mods work but someone once told me that 5 to the power of lots ends in 125 so u could find out the remainder when u divide 125 by 7....meh it works most of the time... i'm not sure if it works all the time :D

There are $ 300$ three-digit multiples of $ 3$.  (since there are $ 900$ three-digit numbers and every third one is a multiple of $ 3$).

As xpmath pointed out, you can break these down into cases:
(1) three-digit numbers where every digit is distinct (the answer)
(2) three-digit numbers where exactly two of the digits are the same
(3) three-digit numbers where each digit is the same

For (3), there are exactly $ 9$ such numbers ($ 000$ is not allowed), and they are all multiples of $ 3$.
For (2), you can examine subcases:

If the repeated digit is $ 1$, then the sum of the digits is $ 1 \plus{} 1 \plus{} x$, where x is the other digit.  The other digit must be $ 1$, $ 4$, or $ 7$ for the number to be a multiple of $ 3$.  But the other digit can't be $ 1$, because then it would fall into case (3).

So, the other digit is either $ 4$ or $ 7$.  For each of those choices, there are $ 3$ possible orderings: for example, $ 114$, $ 141$, $ 411$.

So there are $ 6$ multiples of $ 3$ where $ 1$ is the repeated digit and the third digit is different.

If $ 1$, $ 2$, $ 4$, $ 5$, $ 7$, or $ 8$ is the repeated digit, the logic is the same and there are $ 6$ multiples of $ 3$.

If $ 0$ is the repeated digit, then the other digit is $ 3$, $ 6$, or $ 9$ and the only possible ordering is $ x00$ (a three-digit number cannot start with $ 0$), so there are $ 3$ multiples of $ 3$.

If $ 3$ is the repeated digit, then the other digit is $ 0$, $ 6$, or $ 9$.  If the other digit is $ 0$, then there are only two possible orderings: $ 330$ and $ 303$.  If the other digit is $ 6$ or $ 9$ then all orderings are ok.  So there are $ 8$ multiples of $ 3$.

The above case for $ 3$ is similar for $ 6$ and $ 9$ ($ 8$ multiples of $ 3$).

So there are $ 6 \times 6 \plus{} 3 \plus{} 8 \times 3 \equal{} 63$ numbers in case (2).

Then the number of numbers in case (1) is $ 300$ (the number of the three-digit multiples of $ 3$) - $ 63$ (the number of three-digit multiples of $ 3$ with exactly two digits the same) - $ 9$ (the number of three-digit multiples of $ 3$ with all digits the same) = $ \fbox{228}$.

I wrote a computer program to count the numbers, the output is attached.  You can see that there are $ 228$ numbers.

Thank you, but this was a post from a long time ago and I know how to solve them now.