calculus
integration
trigonometry
derivative
calculus computations

We were given a Volterra type integral equation in an exam:
$u(x) = \tan^{-1}(x)-\int_{0}^{x}x t u(t) dt$

As usual, i tried to convert it to an ordinary DE, which was supposed to come out something fairly easy to handle. But...

$u'(x) = \frac{1}{1+x^{2}}-\left( \int_{0}^{x}u(t) dt+x^{2}u(x) \right)$
$u''(x) =-\frac{2x}{(1+x^{2})^{2}}-\left( x u(x)+2x u(x)+x^{2}u'(x) \right)$

or

$u''(x)+x^{2}u'(x)+3x u(x) =-\frac{2x}{(1+x^{2})^{2}}$

The instructor confirmed that DE conversion should go smoothly. So, it there some kind of trick that i fail to see, or this DE is [i]not[/i] easily solved!? I doubt this's a question that can be solved within 15 mins.

One possibility: rather than taking a second derivative, use the expressions for $u$ and $u'$ to eliminate the integral $\int_{0}^{x}tu(t) dt$.  Then your equation involves no second derivative, maybe is easier to solve?

:edit: No, still seems hard.  Dunno.  Also, you have a missing $t$ in your expression for the first derivative.

Here's what I got:

$u'(x) = \frac{1}{1+x^{2}}-\int_{0}^{x}tu(t) \ dt-x^{2}u(x)$

$xu'(x)-u(x) = \frac{x}{1+x^{2}}-\tan^{-1}x-x^{3}u(x)$

$u'(x)+u(x)\left(\frac{x^{3}-1}{x}\right) = \frac{1}{1+x^{2}}-\frac{\tan^{-1}x}{x}$

Then we have an integrating factor of $\frac{1}{x}e^{x^{3}/3}$, but I can't integrate the right hand side of the equation. (Neither could Mathematica, so either I made a mistake or there probably doesn't exist an elementary solution).

[quote]Also, you have a missing $t$ in your expression for the first derivative.[/quote]
Ups. A typo. Rest goes fine, however.

It's possible that i've misread the question --it was written on the blackboard, and i, who is far-sighted, was sitting somewhere behind!


1) How many different ways can three players be picked from four people?

2) How many different ways can nine players  be picked from ten people?

3) How many different ways can (n - 1) players be picked from (n) people?

Using combinations, we get : [hide]4C3 = 4; 10C9 = 10, so nC(n-1) = n[/hide]

[hide="Solution..."]1) 4 choose 3, or four.

2) 10 choose 9, or ten.

3) n choose (n-1), or n. [/hide]


geometry
geometric transformation
rotation
Euler
circumcircle
3D geometry
vector

Does anyone remember the equation for Euclidean's Line?

Are you perhaps trying to say Euler's Line?

(Euclidean is an adjective derived from the name of Euclid, an ancient Greek mathematician.)

And if so, are you referring to the line (axis) that represents the axis for the one rotation that represents a series of 3d rotations? That may not be clear. If you rotate something over the y axis, and then over the x axis, then over the z, then over the y some more (or any other combination), there exists an axis of rotation and an angle of rotation which will yield the result from the original orientation.  It's sometimes represented with quaternions, which are a 4 dimensional extension of the complex numbers. It's really rather beautiful. If that's what you're talking about, I've written a series of tutorials (with a programming focus, but it covers the math somewhat) [url=http://www.cprogramming.com/advtutorial.html]here[/url]. Scroll down to "Rotations in Three Dimensions by Confuted and Silvercord"

I think hes referring to the Euler line that goes through all those silly points to do with triangles and circumcircles and nine point circles and all that stuff :P I never learnt that one to memory..

Sorry, yeh, I mean Euler's Line. I got to practice typing slower and checking what I'm typing.

i thought Euler's line passed through the centroid, orthocenter and circumcenter, dividing them in 1:2 ratios. Whats this stuff about axis of rotation?

I have no idea what that rotation bit was about.  Euler's line is a line determined by the three vertices of every triangle, which passes through the circumcenter, orthocenter, centroid, and nine-point center as well as "a number of other important triangle centers."  (Quote from mathworld, mathworld.wolfram.com/EulerLine.html)  The "equation" depends very much on what kind of system you are using, especially since it depends on the three vertices of the triangle.  So what exactly are you asking for?

Sorry to bump.

Orient a cube on a set of 3d axes (X,Y,Z) so that the normal from each face lies along an axis, and so its center is at the origin.

Now rotate the cube some random angle over the X axis, then some random angle over the Y axis, then a third random angle over the X axis. You'll have some new orientation of the cube relative to the axes.

It's possible to go from orientation 1 to orientation 2 with only one rotation over some arbitrary axis (a 3d vector, not necessarily aligned with X, Y or Z).

It's never going to come up on a contest, but if you're interested, click my link from before and read the Quaternion tutorial.


I've attached my sample final. I've made it through to number 12. Can someone check it out to see how I did? I've tried to look up and understand 13-16 but still having trouble. Thanks in advance,
MA120 Statistics
HW Assignment #16 Name __________________________________

Fill in the blank or indicate the correct answer (A, B, C, or D).

Use the following sample data to answer questions 1 through 5:

11, 11, 16, 6, 10, 12, 15, 7, 11,

_c____1. The mean, , of the data above is (to the nearest 1/10)
a. 9.0 b.9.9 c. 11.0 d. answer not listed

___c__2. The median of the data above is
a. 9.0 b. 9.9 c. 11.0 d. answer not listed

___c__3. The mode of the data above is
a. 9.0 b. 9.9 c. 11.0 d. answer not listed

4. The Mean Absolute Deviation (MAD) of this data is ______9.33___

5. The standard deviation of the data above is ______3.240______

The table below shows the frequency distribution for 12 students on a test with a maximum score of 20. Use this sample data to answer questions 6 through 8:

Score Frequency Midpoint Midpoint x Frequency midpoint squared x frequency
1-5 1 3 3 9
6-10 2 8 16 128
11-15 4 13 52 676
16-20 5 18 90 1620

total 12 42 161 2433

(i was given score and frequency only, i filled in the rest)

6. What is the mean score, , of the data in the frequency distribution above __13.417_______
7. The standard deviation of the scores in the frequency distribution above ___4.981________

8. The median score lies in which score interval? B
a. 1 – 5 b. 6 – 10 c. 11 - 15 d. 16 - 20

9. Nine horses are in a race and the top three winners, in order, are announced: Blitzer (1); Southern Cross (2); Smoke House (3). My Uncle Roger knows nothing about horses: What is the probability of him randomly picking three horses and winning the Trifecta? (i.e. the probability of picking those exact three horses in that exact order?) B
a. b. c. d. answer not listed

___b__10. Suppose that =, P(A and B) = .54, and . What is ?

a. 1.0 b. 0.36 c. 0.6 d. answer not listed

For questions 11 through 14 use the table immediately below. The table shows the number of drinkers and nondrinkers by gender among 220 people. Assume one person is chosen at random from the 220.

Drinkers Nondrinkers Totals

Male 60 40 100
Female 40 80 120
Totals 100 120 220

a 11. If a male is chosen at random, the probability that he is a drinker is

a. b. c. d. answer not listed

__d___12. If a drinker is chosen at random, the probability that the person is male is
a. b. c. d. answer not listed

_____13. If one person is chosen at random from the 220 in the table above, the events of “Drinker” and “Male” are

a. independent events;
b. dependent events;
c. mutually exclusive events;
d. none of the above

14. If one person is chosen at random: What is the probability the person will be Female OR a Nondrinker? P(F or N): ________

____15. Fantasy Pleasure Yacht Tours seat 13 passengers. From experience, they have learned that, on average, 85% of the passengers holding reservations for a cruise actually show up. If they book 15 passengers for a cruise, what is the probability that 13 or fewer passengers holding reservations will actually show up for the cruise?

a. less than 80% b. between 80 and 95%, inclusive c. more than 95% d. cannot be determined from information given

16. The average number of cars going through a toll booth is 6 per minute. If the booth can handle 12 cars per minute without forming a line. What is the probability there
will be a line at the toll booth? P(x > 12): _______

13. I believe the answer would be (a.) because you can have a male who is not a drinker or a drinker who is not a male; so the two events do not depend on each other.

14. There are 120 total females and 40 male nondrinkers, so P(F or N) is 160/220=8/11. (You could also say that there are 120 total nondrinkers and 40 female drinkers)

15 and 16. I have no idea.

As for the other 12: 1, 2, 3 are right, 4-7 i don't know, 8 should be (c.) because the median is between the sixth and seventh terms, which is in the 11-15 range.  My computer doesn't give me answer choices for questions 9-12.

Hope this helps.  :)

#15 involves a binomial distribution, and #16 a Poisson distribution. Both will require some numerical computation, but nothing that you can't do with a simple calculator.


number theory
least common multiple
greatest common divisor
AMC
USA(J)MO
USAMO
number theory unsolved

Let $ [a, b, ...]$ and $ (a, b, ...)$ denote the lowest common multiple and greatest common divisor, respectively, of the positive integers  $ a, b, ...$. For all such positive integers,

(a) Is it true that $ (a, b)(c, d) \equal{} (ac, bd)?$

(b) Is it true that $ \frac{[a, b, c]^{2}}{[a, b][b, c][c, a]} \equal{} \frac{(a, b, c)^{2}}{(a, b)(b, c)(c, a)}?$

(a) false: $ (1,2)(2,1)\neq (2,2)$
(b) old USAMO question. it's true and can be solved by basic properties of min and max

Hi pleurestique.

I've searched !989 - 2009 USAMO in Resources but can't find it.

that's because it's even older than that. I think it's from '72.


calculus integration function algebra domain vector

It's a line integral. Someone on physicsforums put it nicely: "A line integral is the integral of a function of 2 or more independent variables along a given path between 2 points in the domain of definition."

Here it actually means a surface integral and the circle means that is over a closed surface.
The charge Qint is the charge enclosed by this surface.

well nasu post is right.
It is actually the Gauss's law in electrostatics.
the whole image implies that the surface integral of electrostatics field (vector E) produced by any sources over any closed surface S enclosing a volume V in vacuum i.e. total electric flux over the closed surface in vacuum is
1/Eo times the total charge Q inside S.

Sorry my bad:)
im not in physics c yet- just calculus. /ignore my post.


inequalities
symmetry
quadratics
algebra solved
algebra

Is the following true: for every nonnegative a,b,c, we have (a^2+b^2+c^2)^2 greater than or equal to 3(ab^3+bc^3+ca^3) ?

We have done this before on the forum: the answer is affirmative.

Due to cyclic symmetry, you can assume $a=min(a,b,c)$, thus letting $b=a+x$, $c=a+y$, $x,y \geq 0$.  Then $(a^2+b^2+ c^2)^2 - 3(ab^2 + bc^3 + ca^2)$ becomes a quadratic in a with non-positive discriminant and positive lead coefficient, proving the inequality is true.

I should also add that this is posted in the wrong section.


Let $ z\equal{}x\plus{}yi$ be a complex number, $ x,y,w\in R$. If $ zw\plus{}2iz\minus{}2iw\plus{}1\equal{}0$ and $ |z|\equal{}\sqrt{3}$, then find $ |w\minus{}4i|$


Ummm...My brain isn't working right now.
There is a 50% chance of rain on Saturday. If there's rain on Saturday, then there's a 60% chance of rain on Sunday. If there's no rain on Saturday, then there's only a 40% chance of rain on Sunday. What is the probability of 2 days without rain this weekend? Express your answer as a common fraction.

I fail at probability. :blush:

[hide]The probability it doesn't rain on the first day is $ \frac {1}{2}$.  And, if it doesn't rain on Sat, the probability it rains on Sun is $ \frac {2}{5}$, so the probability it doesn't rain is $ \dfrac{3}{5}$. Our desired probability, that we have two days of no rain, is equal to $ \dfrac{1}{2}\ast\dfrac{3}{5} \equal{} \boxed{\dfrac{3}{10}}$[/hide]

Edit: Oops, thought I was in another forum :P

woops posted wrong question....
sorry :blush:

The answer is 30%.

There is a probability of 50% that it will NOT rain on Saturday and a 60% chance of it NOT raining on Sunday. Multiply 50% and 60% and you get 30%. So the percentage of it NOT raining on either Saturday or Sunday is 30%.  :lol:

wrong. first of all, the question wants a fraction. secondly, 50% of rain on Sat. means 50% no rain. and if no rain, then 40% of rain on Sunday, which means 60% no rain on Sun. There is no rain only if these 2 cases apply, 50%*60%=30%=3/10 i think. i mightve failed though...

EDIT: I SHOULD LEARN TO READ!

The answer key said 3/10. I got 1/5 too..

[quote="the problem"]only a 40% chance of rain on Sunday[/quote]

man i fail

No, there's a 2/5 chance of rain on Sunday if it doesn't rain on Saturday. So 3/5 chance it won't rain on Sunday if it doesn't rain on Saturday.

Multiply 1/2 by 3/5 to get the probability it won't rain at all on that weekend. So the answer is 3/10

All it means is .3x.5 or (1/2)x(3/5) which equals [b]0.3 or (3/10) or 30%[/b]


Assume that the set of positive integers is descomposed into $r$ disjoint subsets. Prove that one of them, say $A$, has the following property: There exists a positive integer $m$ such that for any $k$ one can find $a_{1},...,a_{k}$ in $A$ with $0 < a_{j+1}-a_{j}\leq m$ ($1\leq j \leq k-1$)

Compare to http://www.mathlinks.ro/viewtopic.php?t=147917 ? :wink:


This is for BEGINNERS, so if you don't think you're a beginner, give a beginner a chance please! Thank you

Prove that the product of an  digit number and an  digit number is either an  digit number or an  digit number.

Spoiler(Don't read it, solve the problem):

[hide]We know 10^j is a 1 followed by j 0's, so 10^j is the smallest (j + 1) digit number. So, we call the m-digit number M and the n-digit N. So:

10^(m-1) < = M < 10^m and

10^(n-1) < = N < 10^n, since we know all values are positive, multiplying, we get:

(10^(m-1))(10^(n-1)) < = MN < (10^m)(10^n)

10^(m+n-2) < = MN < 10^(m+n)

10^(m+n-2) is an (m+n-2)+1 or an (m+n-1) digit number, and 10^(m+n) is an the smallest (m+n+1) digit number. So the product MN is greater than or equal to the smallest (m+n-1) digit number and smaller that the smallest (m+n+1) digit number which means the product MN can range from the smallest (m+n-1) digit number to the largest (m+n) digit number.

[/hide]

[hide]For m, you have 10^(m-1) minimum digits, and 10^m (One greater than max digits). For n, you have 10^(n-1) and 10^n(One greater than max). 10^(m-1) * 10^(n-1) = 10^(m+n-2). 10^n * 10^m = 10^(n+m). However, this is one digit too large, so the max digits of the product is 10^(n+m-1). So you have either n+m-1 digits in the product, or n+m digits.[/hide]

In his proof PorkChop assumed the numbers were postive. i think it works for negative numbers though

When multiplying numbers, you don't actually think about if they're negative or not. You multiply the absolute value of the numbers and then you multiply their signs. But, assuming they are positive still acounts for all numbers. For example, in my proof, there are 4 cases that arrive:
I - neither are negative
II - M is negative
III - N is negative and
IV - both are negative.
So, for I, it stays the same, for II, we say M = -M' where M' is positive(the absolute value of M) which means MN = (-M')N=(-1)(M'N). Yeah, so this argument works for the rest and shows we need only consider them to be positive.


If $x,y\in(1,3)$ show that $|(x-2)(y-2)|<1$.

Edit: ups.. i think it's obiouvsly  :oops:

No, because $x,y$ could never take $1$ and $3$ values.

The terms $(x-2)$ and $(y-2)$ will both always be less than 1 or greater than -1. So it follows that the absolute value of their product will always be less than 1.

[quote="DanK"]Won't that always be equal to 1?[/quote]

He put the equation in interval notation, it means all reals that are < 3 and > 1, its not saying that x and y are either 1 or 3.

you can always distribute the absolute value bars, and it is obvious that each individiual is less than 1, so product is less than 1


I don't know if you can call this a "problem" but I'm wondering this greatly.

On the past, I used to be able to type codes on Texer at AoPS and copy the image to Word and use it. Now, when I try it, the image is black unless I save it. I don't feel like saving every tiny thing I write to use on Word (I mainly try to use these images for the ones that I can't type on Word; and my computer is too slow to put Texer).

Any idea why? I use Firefox by the way.

I would guess this is a local issue (i.e. something on your computer, either your FireFox or your copy of Word, or even your OS).

It happens to me too. Its because the Texer outputs transparent images.

Hmm, I guess there isn't really an answer to this problem then? Blah...

I don't know, maybe I'll try on my IE but I tend to discourage myself from doing so because IE gets more virus than Firefox (Firefox's A LOT safer... I'm not sure why the distinction should occur but who knows).

If anyone else has any idea to this, please let me know.

Firefox has changed the way it copies html content. That's all.

Have you tried using Word's built in Equation Editor for your math formulas?

Lol, why use that instead of just writing the documents in $ \text{\LaTeX}$ to begin with?

A) Its in a weird font
B) no inkscape vector drawings
C) it doesn't print pdfs correctly all the time
D) latex is way easier when coming to complex equations. for example, when writing up usamts solutions, its way harder to use word's eqn editor because you have a number of equaions that's too tedious to do in word.

I didn't mean to start a holy war between LaTeX and equation editor.

My statement of equation editor was purely in response to copy/pasting from TeXer, nothing else. Equation Editor is definitely better than copy/pasting pixelated images. If he wants to write his entire document in LaTeX, that's fine by me.

Well, I think I stated somewhere that my computer is slow enough that I cannot install LaTeX. Maybe when I get new one, I might but who knows.

And as much as I interested in this "war" between why you can't just add LaTeX, I was more interested in getting the answer (which was just wrong with Firefox) so since I got it, well, I guess I'm good now.

I don't know if I can change the way Firefox copies html images (like go to the Settings?). I don't know.

Mmm instead of right clicking the image and clicking "copy image", select the image so that it's blue and do Control+C and paste into word.  This is because word doesn't like transparent images from the clipboard when pasted for some reason, and when you select it and copy, word is actually fetching the image from the server so it's ok. :dry:

As a side note, Word 2007's equation support is really really awesome, and it supports most latex symbols...

^^ that works for me.

Also, I second the notion that 2007 has the best equation formatting evar.

[quote="7h3.D3m0n.117"]Haha I didn't download the TeXer, so I'm always using the site's Test Forum as a method of copying and pasting (through print screening and paint editting) to make documents. Isn't always clean - but it works. And the notion of starting a holy wars (kudos, levans) brought to my mind of mathematicians starting up their own religion  :ninja:

Will using the site's TeXer on IE work?[/quote]
I thought the point of the TeXer was that you didn't have to download anything.

[quote="levans"]I didn't mean to start a holy war between LaTeX and equation editor.[/quote]No worries I can start it :D Use $ \text{\LaTeX}$ to create your Math documents (and even your Math Presentations with the beamer package). It's free, looks great and you can always use it again.

ccy, thanks a lot! That helped me A LOT... Sweet deal.  :lol:


If $x$ is a real number, $[x]$ is defined to be the greatest integer less than or equal to $x$ (e.g. $[3.6] = 3$). Find all positive values of $x$ such that $\frac{1}{[x]}+\frac{1}{[3x]}= x-[x]$

${\lfloor x\rfloor }$

just correcting the latex code.

[hide="Cases"]Let:
$k \in \mathbb{Z},\; 0 \leq z < 1/3$

We have three distinct cases:
$I. \; x=k+z$
$II. \; x=k+z+1/3$
$III. \; x=k+z+2/3$[/hide]

[hide="Solution"]
$I.$ produces:

$\frac{4}{3k}=z \implies kz=4/3$

Note that for all $k>4$, there is $z$ value within the appropriate range, and there are thus an infinite number of solutions of this form. $x=k+\frac{4}{3k}\; \forall k\in \mathbb{Z}^{\geq 4}$

$II.$ produces:

$\frac{4k+1}{3k^{2}+k}=\frac{1}{3}+z$

which produces the two solutions $(k,z)=\left( 3,\frac{1}{10}\right), \; \left( 2,\frac{13}{42}\right) \implies x=\frac{103}{30}, \; x=\frac{37}{14}$

$III.$ produces:

$\frac{4k+2}{3k^{2}+2k}= \frac{2}{3}+z$

which produces the solution $(k,z) = \left( 2, \frac{1}{21}\right) \implies x = \frac{19}{7}$

Thus, the solution set is $x \in \{ \frac{37}{14}, \frac{19}{7}, \frac{103}{30}, k+\frac{4}{3k}\; \forall k\in \mathbb{Z}^{\geq 4}\}$
[/hide]

[quote="The Zuton Force"][hide="Cases"]Let:
$k \in \mathbb{Z},\; 0 \leq z < 1/3$

We have three distinct cases:
$I. \; x=k+z$
$II. \; x=k+z+1/3$
$III. \; x=k+z+2/3$[/hide]

[hide="Solution"]
$I.$ produces:

$\frac{4k}{3}=z$

which produces $(k,z)=(0,0)$ as its only solution. However, this returns $x=0$, which is an extraneous solution.

$II.$ produces:

$\frac{4k+1}{3k^{2}+k}=\frac{1}{3}+z$

which produces the two solutions $(k,z)=\left( 3,\frac{1}{10}\right), \; \left( 2,\frac{13}{42}\right) \implies x=\frac{103}{30}, \; x=\frac{37}{14}$

$III.$ produces:

$\frac{4k+2}{3k^{2}+2k}= \frac{2}{3}+z$

which produces the solution $(k,z) = \left( 2, \frac{1}{21}\right) \implies x = \frac{19}{7}$

Thus, the solution set is $x \in \{ \frac{37}{14}, \frac{19}{7}, \frac{103}{30}\}$
[/hide][/quote]

You've missed some.  Like $79/15$.  I don't understand your logic for case 1, and I'm pretty sure there are an infinite number of solutions for at least that case.  I haven't looked at the other cases yet.

Sorry, I had a typo in there. I think it's fixed now.


In triangle $ABC$, and angle $A=45^{o}$. Let $D$ on $AC$ that $AC$and $BD$ is perpendicular, and let $E$ on $AB$ that $AB$ and $CE$ is perpendicular. Let $X$ that is midpoint of $AB$, and let $Y$ that is midpoint of $BC$, and let $O$ is the circumcenter of triangle $ABC$. Prove that $DE,XY,BO$ intersects at one point.

Since $O$ is the circumcenter, points $B, Y, O, X$ lie on one circle. What's more, as $\angle BAC=45^{o}$, $O$ lies on the circumcircle of quadrilateral $BCDE$. Hence $\angle XOB=\angle XYB=\angle ACB=180^{o}-\angle DOB$ what implies that points $D, O$ and $X$ are collinear. So $\angle XOE=180^{o}-\angle DOE=\angle DCE=45^{o}=\angle XDB$ whence $OE$ is parallel to $BD$. Using Ceva in $\triangle DXB$ we obtain that lines $DE, XY$ and $BO$ intersect at one point.

Of course, we don't have to use Ceva's theorem... :D


for image:
http://img25.imageshack.us/i/111ym.gif/

how we divide the area of the image above into 9 areas, which each of area has a same size and shape?

please answer with picture

Can you give us dimensions? It is impossible unless we know the ratio between the length and width and the pointy thing at the right.

[quote="PowerOfPi"][b]Can you give us dimensions?[/b] It is impossible unless we know the ratio between the length and width and the pointy thing at the right.[/quote]
no :D  :D   :D

[b]Please anybody, don't answer this question, [size=150]this is mathematics competition's problem[/size] and the competition is still. Rzburton try to cheating[/b]

http://www.kaskus.us/showthread.php?t=2658419

@rzburton : shame on you!


[color=blue]Given that[/color] [color=red]$a+b+c=0$ [/color][color=green]prove the following equality:[/color] [color=green]$a^{3}+b^{3}+c^{3}=3abc$[/color]  :lol:

[hide="Hint"]Easiest to substitute $c=-(a+b)$[/hide]


group theory
abstract algebra
superior algebra
superior algebra unsolved

1- Prove that if $ G/Z(G)$ is nilpotent, then $ G$ is too.
2- Find a group $ G$ which is not nilpotent and a normal subgroup $ N$ of it such that $ G/N$ and $ N$ are nilpotent.

1: Presumably, you are aware of the characterization of nilpotent groups in terms of the upper central series, or higher centers? If so then this should be fairly simple: the upper central series of $ G$ is basically the same as that of $ G/Z(G)$ with an added step.

2: Consider $ S_3$.

You can look at Chapter 5 in the book Abstract Algebra of R.B.Ash at http://www.math.uiuc.edu/~r-ash.


function
real analysis
integration
real analysis unsolved

Hello,

I am trying to solve a problem using generating functions and I am stuck on a certain step. Basically, I have defined my generating function to be

$ A(x) \equal{} a_{0} \plus{} a_{1} x \plus{} a_{2} x^{2} \plus{} a_{3} x^{3}\cdots$

where the a_i's are the coefficients of the sequence I am interested in. At some point I obtain generating functions where the coefficients are raised to some power i, where i is a positive integer. For instance, if i=2, I get

$ A_{2}(x) \equal{} a_{0}^{2} \plus{} a_{1}^{2} x \plus{} a_{2}^{2} x^{2} \plus{} a_{3}^{2} x^{3}\cdots$

I am not sure whether this is possible, but does anyone know how to express

$ A_{i}(x) \equal{} a_{0}^{i} \plus{} a_{1}^{i} x \plus{} a_{2}^{i} x^{2} \plus{} a_{3}^{i} x^{3}\cdots$

in terms of $ A(x)$?

Thanks for the help!

Edit: rewrote the expression in Latex.

For a general sequence there aren't any nice tricks that I know of, but if the sequences you're working with are of some special type it might be possible to say something.  What problem are you working on?

The only thing I can think of is to consider the values on the unit circle and represent $ A_2$ as a convolution of $ A_1$ with itself (i.e., to write $ A_2(z)\equal{}\int_{\mathbb T}A_1(z/w)A_1(w)\,dm(w)$ where $ \mathbb  T$ is the unit circumference and $ m$ is the Lebesgue measure on $ \mathbb T$ normalized by $ m(\mathbb T)\equal{}1$) but I do not think it may be of much use (though, what do I know about your problem? :P)

That method fedja gives is essentially replacing the $ z$-transform usually used for generating functions with a Fourier transform. There's a general principle of transform methods that pointwise multiplication on one side is convolution on the other, but it's not always easy to find both versions of convolution. For generating functions $ \sum a_nz^n$, convolution on the additive structure of the nonnegative integers is a common and useful operation, but there is no obvious choice of convolution on the function side.

Thank you very much for your responses!

I have no idea whether fedja's contribution could work, as I have never studied convolution before... (I read the entry in Wikipedia though and it looked very interesting, so thank you fedja for introducing me to the concept.)

If it helps at all, I am trying to express

$ \frac {A_{i \plus{} 1}(x)}{2} \minus{} \frac {A_{i}(x)}{4}$

in terms of $ A(x)$. I am looking for an explicit formula for a recursively defined sequence and could, of course, extract a formula for $ a_{n}$ at this stage. However, the form obtained at this point is useless, so I am hoping to further manipulate the expressions until I can get something fruitful.

Anyway, perhaps the fact that the expression above involves a difference of generating functions will help...

Even if you have a method that is really complicated, please don't hesitate to post it; I'm glad to learn about new math anyday.

The most useful information to us would be how $ a_n$ is defined in particular.

I'll just say this: if you know anything about generating functions, you know something about convolution. This is a convolution: $ \sum_n x^n\sum_k a_kb_{n\minus{}k}$


calculus
integration
trigonometry
function
derivative
calculus computations

(1) Evaluate $ \int_0^{\frac{\pi}{2}} (x\cos x\plus{}\sin ^ 2 x)\sin x\ dx$.

(2) For $ f(x)\equal{}\int_0^x e^t\sin (x\minus{}t)\ dt$, find $ f''(x)\plus{}f(x)$.

#1.

[hide]
$ \int_{x\equal{}0}^{\pi/2} (x \cos x \plus{} \sin^2 x)\sin x \, dx \equal{} \int_{x\equal{}0}^{\pi/2} \frac{x}{2} \sin 2x \plus{} (1\minus{}\cos^2 x)\sin x \, dx$

$ \equal{} \left[\minus{}\frac{x}{4} \cos 2x\right]_{x\equal{}0}^{\pi/2} \plus{} \int_{x\equal{}0}^{\pi/2} \frac{\cos 2x}{2} \, dx \plus{} \int_{u\equal{}1}^0 \minus{}(1\minus{}u^2) \, du$

$ \equal{} \frac{\pi}{8} \plus{} \left[\frac{\sin 2x}{4}\right]_{x\equal{}0}^{\pi/2} \plus{} \left[\frac{u^3}{3} \minus{} u\right]_{u\equal{}1}^0$

$ \equal{} \frac{\pi}{8} \plus{} \frac{2}{3}$.
[/hide]

(1) seems straightforward. Expanding the integrand, $ x \sin x \cos x \equal{} \frac {1}{2} x \sin (2x)$ can be integrated by parts and using $ \sin^{2}x \equal{} 1 \minus{} \cos^{2}x$ to integrate $ \sin^{3}x$, I get $ \frac {\pi}{8} \plus{} \frac {2}{3}$.

#2.

[hide]
$ f(x) \equal{} \int_{t \equal{} 0}^x e^x \sin (x \minus{} t) \, dt \equal{} \int_{t \equal{} x}^0 \minus{} e^{x \minus{} t} \sin t \, dt \equal{} e^x \int_{t \equal{} 0}^x e^{ \minus{} t} \sin t \, dt$.

Therefore

$ f'(x) \equal{} f(x) \plus{} e^x (e^{ \minus{} x} \sin x) \equal{} f(x) \plus{} \sin x$,

$ f''(x) \equal{} f'(x) \plus{} \cos x \equal{} f(x) \plus{} \sin x \plus{} \cos x$,

$ f(x) \plus{} f''(x) \equal{} 2f(x) \plus{} \sin x \plus{} \cos x$,

and since

$ \int_{t \equal{} 0}^x e^{ \minus{} t} \sin t \, dt \equal{} \minus{} e^{ \minus{} x}\cos x \plus{} 1 \plus{} \int_{t \equal{} 0}^x e^{ \minus{} t} \cos t \, dt$

$ \equal{} \minus{} e^{ \minus{} x}\cos x \plus{} 1 \minus{} e^{ \minus{} x}\sin x \minus{} \int_{t \equal{} 0}^x e^{ \minus{} t} \sin t \, dt$,

we obtain

$ f(x) \equal{} \frac {e^x}{2}\left(1 \minus{} e^{ \minus{} x}(\sin x \plus{} \cos x)\right)$,

from which it follows that

$ f(x) \plus{} f''(x) \equal{} e^x$.
[/hide]

Surely there must be an easier way to solve this problem?  Surely it would have been more simple if the task was to evaluate $ f''(x) \minus{} f(x)$.

That's correct.

My solution is almost same as yours. :lol:

As you can see I was hoping to find a way to evaluate the expression without calculating the integral.  It would have been possible if we wanted to find $ f''(x) \minus{} f(x)$.  But it did not work and I ended up doing the integral anyway.  :(

Why don't just use the simple formula (since everything is nice enough)

\[ \frac{d}{dx}\int_0^x g(t,x)dt \equal{} g(x,x) \plus{} \int_0^x \frac{\partial}{\partial x}g(t,x)dt.\]

Then we get, with $ g(t,x)\equal{}e^t \sin(x\minus{}t)$ and $ f(x)\equal{}\int_0^x g(t,x)dt$,

\[ f'(x)\equal{}\underbrace{g(x,x)}_{\equal{}0} \plus{} \int_0^x e^t\cos(x\minus{}t)dt \\
f''(x)\equal{}\underbrace{e^x\cos(x\minus{}x)}_{\equal{}e^x} \plus{} \int_0^x \minus{} e^t\sin(x\minus{}t) \equal{} e^x \minus{}f(x)\]
so $ f(x)\plus{}f''(x)\equal{}  f(x) \plus{}e^x \minus{} f(x) \equal{}e^x$ which shows that we can avoid the integration.

[quote="Hormander"]Why don't just use the simple formula (since everything is nice enough)
\[ \frac {d}{dx}\int_0^x g(t,x)dt \equal{} g(x,x) \plus{} \int_0^x \frac {\partial}{\partial x}g(t,x)dt.\]
[/quote]

Could you teach the fact in detail? :oops:

Thank you for reply.

Is [url=http://en.wikipedia.org/wiki/Leibniz_integral_rule]this?[/url]

We ca aslo write
$ \begin{array}{l}
 f(x) \equal{} \int_0^x {{e^t}} \eta \mu (x \minus{} t)\;dt\mathop  \equal{} \limits_{dt \equal{}  \minus{} du}^{x \minus{} t \equal{} u}  \minus{} \int_x^0 {{e^{x \minus{} u}}} \eta \mu u\;du \equal{} {e^x}\int_0^x {{e^{ \minus{} u}}} \eta \mu u\;du \Leftrightarrow  \\
 {e^{ \minus{} x}}f\left( x \right) \equal{} \int_0^x {{{\left( { \minus{} {e^{ \minus{} u}}} \right)}^\prime }} \eta \mu u\;du \Leftrightarrow {e^{ \minus{} x}}f\left( x \right) \equal{}  \minus{} {e^{ \minus{} x}}\eta \mu x \plus{} \int_0^x {{e^{ \minus{} u}}} \sigma \upsilon \nu u\;du \Leftrightarrow  \\
 {e^{ \minus{} x}}f\left( x \right) \equal{}  \minus{} {e^{ \minus{} x}}\eta \mu x \minus{} \int_0^x {{{\left( {{e^{ \minus{} u}}} \right)}^\prime }} \sigma \upsilon \nu u\;du \Leftrightarrow  \\
 {e^{ \minus{} x}}f\left( x \right) \equal{}  \minus{} {e^{ \minus{} x}}\eta \mu x \minus{} {e^{ \minus{} x}}\sigma \upsilon \nu x \plus{} 1 \minus{} \int_0^x {{e^{ \minus{} u}}} \eta \mu u\;du \Leftrightarrow  \\
 {e^{ \minus{} x}}f\left( x \right) \equal{}  \minus{} {e^{ \minus{} x}}\eta \mu x \minus{} {e^{ \minus{} x}}\sigma \upsilon \nu x \plus{} 1 \minus{} {e^{ \minus{} x}}f\left( x \right) \Leftrightarrow  \\
 2{e^{ \minus{} x}}f\left( x \right) \equal{}  \minus{} {e^{ \minus{} x}}\eta \mu x \minus{} {e^{ \minus{} x}}\sigma \upsilon \nu x \plus{} 1 \Leftrightarrow  \\
 f\left( x \right) \equal{} \frac{{{e^x} \minus{} \eta \mu x \plus{} \sigma \upsilon \nu x}}{2} \\
 \end{array}$

Yes, it's the formula when we differentiate a function that the limits of integral are variable of $ x$.

Thanks, but We Japanese high school students don't study partial differentiation.

How about this in Korea?

Korean high school students don't study partial differentiation either.


The rules are about the same as rem's original one (I will let you know details), but questions will be easier and more combinatorics oriented. Start registering!

i sign up. But bubka don't  fill this forum with spam and create something like you did in the games factory where you made 3 tug of wars.
And btw  I don't think it's very good to start a new game while the previous one is still on because math battle 1 is far from finished. ;)

count me in.
so why don't we just wait until that math battle ends?

Fine but hurry up and get over with it. I will be off to the IMOTC on May 7 and return on June 2. I may get a chance to sneak in some hours of AoPSing, but then again I may not! So I will post the problems, hand over the solutions to some neutral person, and go off!

I think the other is still going on so I will postpone this a bit more. Keep registering but this won't start in a hurry. And if I don't post anything at all between May 7 and May 14, somebody else may take charge of this. I won't mind ...


function
algebra
polynomial
number theory proposed
number theory

Let $ p$ be a prime number. Prove that every function $ f: \{0,1,\ldots,p\minus{}1\} \to \{0,1,\ldots,p\minus{}1\}$
can be represented by a polynomial $ p(x) \equal{} a_0\plus{}a_1x\plus{}\cdots\plus{}a_{p\minus{}1}x^{p\minus{}1} \bmod p$ (in sense that the coefficients have been taken $ \bmod p$).

declare $ f(x)$ to be such that
$ f(x) \equal{} a_0(x\minus{}1)(x\minus{}2)..(x\minus{}n\plus{}1) \plus{} a_1(x\minus{}0)(x\minus{}2)..(x\minus{}n\plus{}1) \plus{}
.. a_{n\minus{}1}(x\minus{}0)(x\minus{}1) .. (x\minus{}n\plus{}2)$

where $ b_i \equal{} (i\minus{}0)(i\minus{}1) .. (i\minus{}(i\minus{}1))(i\minus{}(i\plus{}1)) .. (i\minus{}n\plus{}1) (mod p)$
and $ a_i \equal{} inverse of b_i * f(i) (mod p)$
i guess $ p$ is required so that the inverse exists

What's "$ n$" ? Do you mean "$ p$" ? Furthermore why does the inverse of $ b_i$ exist? I think that you have to prove that $ (b_i,p) \equal{} 1$  for $ i \equal{} 0,\ldots,p \minus{} 1$.

sorry , by n i mean p
$ b_i \equal{} (i\minus{}0)(i\minus{}1) .. (i\minus{}(i\minus{}1))(i\minus{}(i\plus{}1)) .. (i\minus{}p\plus{}1) (mod p)$
since none of $ i\minus{}k$ is divisible by $ p$ , $ b_i$ will not be divisible by $ p$ , so $ (b_i,p) \equal{} 1$
and hence its inverse will exist

Just state the general theorem:
For any field $ K$ and any points $ (a_0,b_0), (a_1,b_1), (a_2,b_2), ..., (a_n,b_n) \in K^2$ with different $ a_i$ there is a unique polynomial $ f$ of degree at most $ n$ such that  $ f(a_i)\equal{}b_i$ for all $ i$.


calculus
integration
number theory unsolved
number theory

Find all integral pairs $ \ (x,y)$ satisfy:
      $ \ x\plus{}y^{2}\plus{}d^{3}\equal{}xyd$
   where $ \ d$ is $ \gcd(x,y)$.


This is not hard. At first, since the number arrays $\left(a^2;\;b^2;\;c^2\right)$ and $\left(b+c;\;c+a;\;a+b\right)$ are oppositely sorted (in fact, if $b\geq c$, then $b^2\geq c^2$ and $c+a\leq a+b$, while if $b\leq c$, it is the other way round), we can apply the Chebyshev inequality to obtain that

$a^2\left(b+c\right)+b^2\left(c+a\right)+c^2\left(a+b\right)\leq\frac13\left(a^2+b^2+c^2\right)\cdot\left(\left(b+c\right)+\left(c+a\right)+\left(a+b\right)\right)$
$=\frac13\left(a^2+b^2+c^2\right)\cdot 2\left(a+b+c\right)$,

so that $\left(a^2+b^2+c^2\right)\left(a+b+c\right)\geq\frac32\left(a^2\left(b+c\right)+b^2\left(c+a\right)+c^2\left(a+b\right)\right)$. On the other hand, we know that $a^2+b^2+c^2\geq\frac13\left(a+b+c\right)^2$. Thus,

$\left(a^2+b^2+c^2\right)^3=\left(a^2+b^2+c^2\right)^2\cdot\left(a^2+b^2+c^2\right)\geq\left(a^2+b^2+c^2\right)^2\cdot\frac13\left(a+b+c\right)^2$
$=\frac13\cdot\left(\left(a^2+b^2+c^2\right)\left(a+b+c\right)\right)^2\geq\frac13\cdot\left(\frac32\left(a^2\left(b+c\right)+b^2\left(c+a\right)+c^2\left(a+b\right)\right)\right)^2$
$=3\cdot\left(\frac{a^2\left(b+c\right)+b^2\left(c+a\right)+c^2\left(a+b\right)}{2}\right)^2=3\cdot\left(\frac{\left(a^2b+b^2c+c^2a\right)+\left(ab^2+bc^2+ca^2\right)}{2}\right)^2$
$\geq 3\cdot\left(a^2b+b^2c+c^2a\right)\left(ab^2+bc^2+ca^2\right)$

by the AM-GM inequality. And we are done.

  darij

Here is my solution:

IF we normalize $a^2+b^2+c^2=3$, then we need to show that
\[ (a^2b+b^2c+c^2a)(ab^2+bc^2+ca^2)\leq9.  \]
By AM-GM inequality,
\[ (a^2b+b^2c+c^2a)(ab^2+bc^2+ca^2)\leq\left(\frac{a^2b+b^2c+c^2a+ab^2+bc^2+ca^2}2\right)^2.  \]
So it remains to prove that
\[ a^2(b+c)+b^2(c+a)+c^2(a+b)\leq 6.  \]
Now if we use the inequality
\[ \frac{x^2+y^2}2\geq\Bigl(\frac{x+y}2\Bigl)^2,  \]
which is easily verified, it's sufficient to show that
\[ a^2(b^2+c^2)+b^2(c^2+a^2)+c^2(a^2+b^2)\leq 6.  \]
or $a^2b^2+b^2c^2+c^2a^2\leq 3$ over $a^2+b^2+c^2=3$. This is true since
\[ 3a^2b^2+b^2c^2+c^2a^2)\leq(a^2+b^2+c^2)^2.  \]
We are done :lol:

Is it nice? ;)

Sorry for a mistake in the last step.

To prove
\[ a^2(b+c)+b^2(c+a)+c^2(a+b)\leq6 \]
we write the left hand as
\[ a^2(b+c)+b^2(c+a)+c^2(a+b)=(a+b+c)(a^2+b^2+c^2)-(a^3+b^3+c^3)=3(a+b+c)-(a^3+b^3+c^3). \]
So the rest is to prove that
\[ a^3+b^3+c^3+6\geq3(a+b+c). \]
But this is true by AG,
\[ a^3+1+1\geq 3a,\;\; b^3+1+1\geq 3b,\;\; c^3+1+1\geq3c. \]

Nice one
I think we can prove the strong one:
$4(a^2+b^2+c^2)^3 \ge 3(a^3+b^3+c^3+3abc)^2$

[quote="pvthuan"]Yes, Zhaobin, save it for our book.

The folloiwng is also harder:

Find the maximum value of
\[ f=(a^2b+b^2c+c^2a)(ab^2+bc^2+ca^2),  \]
where $a,b,c$ are nonnegative numbers such that $a+b+c=1$.[/quote]

we claim that $(a^2b+b^2c+c^2a)(ab^2+bc^2+ca^2)\leq \frac{1}{64}(a+b+c)^6$

But we can use an intermediate step which is

$(a^2b+b^2c+c^2a)(ab^2+bc^2+ca^2)\leq \left(\frac{a^2(b+c)+b^2(a+c)+c^2(a+b)}{2}\right)^2$ by AM-GM .And the rest is just schur .

Sorry, pvthuan.
The original ineq is imediately shown by expansion and Muirhead's.

Yes, I know that, but AM-GM is more familiar to students. Murhead is something too strong.

I thinks Muirhead's and AM-GM is quite same, if a problem is solved by m., then it will be solved by AM_GM, too, but Muirhead's helps us faster.

I mean in school curriculum, students are not used to Muirhead.

Muirhead implies the following:
\[ x^3+y^3+z^3\geq x^2y+y^2z+z^2x. \]
But we also have it by AG.

By AM-GM, we have
\[ x^3+x^3+y^3\geq 3x^2y. \]
Adding the other two, we get the desired one.


Find the area of an equilateral triangle inscribed in a circle of radius 12.

(is there an alternative way instead of using trig?)

Hint:
Use the fact that the 2/3 the median of the equilateral triangle is the circles radius.

And also, the median of a triangle is the height in an equilateral triangle.

So since 2/3 the median is 12, the median is ______. Since the median is the height, the height is _____. Therefore, the side lengh of the triangle is _______ (use a bit of algebra), and then the area is _______.

OK try to visualize the following:

Draw radii from the center of the circle to the vertexes of the triangle.  This trisects the 360 degrees in the middle, making each interior angle 120 degrees.  Bisect the 120's in half, leaving 30-60-90 triangles.  Assuming you can apply special triangles, you know the chords/edges of the triangle are each $ 12 \sqrt {3}$.  The formula for the area of an equilateral triangle with side length x (which can easily be derived if you don't know it), is ${ \frac{\sqrt{3} x^2}{4}}$.  So if $ x = 12 \sqrt {3}$, the area is $ 108 \sqrt {3}$.

This should be correct.

Use the fact that the radius is 2/3 the median of an equilateral triangle, and that the ratio between the sides of a triangle with angles 30-60-90 is $ 1: \sqrt{3}: 2$,

[geogebra]a3963fc0695ee19b2a9b0e16957926510e8a99fa[/geogebra]


function
real analysis
real analysis unsolved

Let $ f : [a,b] \longrightarrow \mathbb{R}$ be a monotone funcrion.Show that the set of discontinuous points of $ f$ is countable.

[quote="alekk"]more generally, suppose that the function has a right and a left limit at every point. Then prove that the set of discontinuity points is at most countable.[/quote]

How do we proceed?  :(  Do we need to know any thing other than the definitions of discontinuity and countable sets?

Thanks  :D

[quote="knoppix"]You can match each of points of discontinuity with an interval on OY axis.

These intervals can be choosen pairwise disjoint.

Then take a rational number in every interval;
the number of all intervals is not bigger then the cardinality of $ \mathbb{Q}$[/quote]

I can vaguely see where this leads to. You mean to say that every discontinuity is in "effect" for an interval, and there are only countably many pairwise disjoint intervals on the real line.

Why do we need monotonicity then?
Probably an example with a non-monotonic function with uncountable discontinous points will be illuminating  :maybe:

Thanks for your hint,
I am still thinking  :lol:

[quote]Why do we need monotonicity then?[/quote]
To ensure that the intervals are disjoint.

The function "$ f(x)\equal{}1$ if $ x$ is rational, $ f(x)\equal{}0$ if $ x$ is irrational" is discontinuous at every point.

A long time since my last post.

Proof of alekk's more general assertion:
Suppose the contrary, i.e. the set of discontinuous points is uncountable.
Consider the jump at each point of discontinuity. Since the set of discontinuous points is uncountable, there exists a real number $ m$ s.t. the jumps of uncountably many points exceed $ m$.
Note that this uncountable set of points has an accumulation point. We can then construct a monotone sequence $ x_n$ converging to this point, of which the images $ f(x_n)$ do not form a Cauchy sequence.


To multiply two complex numbers $a + bi$ and $c + di$, we could use the identity
\[ (a + bi) (c + di) = ac - bd + (ad + bc) i \, .  \]
Computing the right-hand side seems to require 4 real multiplications.  Show that we can actually compute the right-hand side using only 3 real multiplications.

1) First we find $abcd$.
2) Then we find $ac$, from which we can get $bd = \frac{abcd}{ac}$.
3) Lastly, we multiply $ad$, from which can get $bc = \frac{abcd}{ad}$.

:D Does that work?

Sorry, I count $a b c d$ as 3 multiplications by itself ($a \cdot b \cdot c \cdot d$).

Also, I forgot to say that each division counts as a "multiplication" too.  Otherwise, we could multiply for free with cheapos like $xy = \frac{x}{1/y}$.

The procedure I had in mind does not use division.


linear algebra
matrix
search
function
algebra
polynomial
integration

Find the number of ways to arrange four a, three b and three c in a line so that no two of same kind are adjacent.
e.g one such arrangement is as follows: ababacacbc

This is the coefficient of $ a^4 b^3 c^3$ in half the sum of the entries of

$ \left[ \begin{array}{ccc} 0 & b & c \\
a & 0 & c \\
a & b & 0 \end{array} \right]^{10}$

which should not be too hard to compute if you write it as the difference of a diagonal and rank-$ 1$ matrix, but I am curious about the following generalization:

Given an alphabet $ w_1, ... w_n$, how many words of length $ l$ are there such that each letter $ w_i$ is used $ \lambda_i$ times, where $ \sum \lambda_i \equal{} l$, and in addition there is specified a finite list of strings that no word can contain as a substring?

With no restriction on the number of times a letter can be used, this sequence [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?search_id=1466862670&t=260064]satisfies a linear recurrence[/url]; with no restriction on forbidden substrings, it's a multinomial coefficient.  At least [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?t=265241]one instance[/url] of this problem has a nasty generating function although it is not too hard to write down the sequence itself.  I think in general such problems can be understood as walks on infinite lattices ending at certain points, but I am not aware of good general techniques for talking about such walks.

Alternately, one can define a sequence of polynomials as above that solves this problem and ask whether there is a good way to isolate single coefficients or families of coefficients in a multivariate generating function, which I don't think there is.  Even in the two-variable case, isolating the coefficients $ a_n$ of the terms $ x^n y^n$ in an arbitrary generating function is at least as hard as computing Hadamard products.

We can give an equivalent but different-looking answer using recursions.  Specifically, let $ f_1(x, y, z)$ be the number of such words ending in a that contain $ x$ copies of a, $ y$ of b and $ z$ of c, and similarly for $ f_2, f_3$.  Then we have the relations $ f_1(x, y, z) \equal{} f_2(x \minus{} 1, y, z) \plus{} f_3(x \minus{} 1, y, z)$, $ f_2(x, y, z) \equal{} f_1(x, y \minus{} 1, z) \plus{} f_3(x, y \minus{} 1, z)$ and similarly for $ f_3$.  Using the obvious symmetries ($ f_1(x, y, z) \equal{} f_1(x, z, y) \equal{} f_2(y, x, z) \equal{} \ldots$) makes it possible to compute the desired sequence fairly quickly.  (Actually, this makes it simple enough to write everything just in terms of $ f_1$ and save a little effort like that.)

One can tell that t0r and I are both right because our different methods lead to the same number ;)

[quote="JBL"](By the way, t0r, is it easy to get this data from your expression for the answer?  What operation gives you "sum all the entries of a matrix"?)[/quote]
Well, the denominator of the generating function's just going to be $ \det(I \minus{} tM)$, which presumably agrees with your answer (with the identifications $ x \equal{} at, y \equal{} bt, z \equal{} ct$).  As for the numerator, "sum all the entries" means multiplying by $ \left< 1, 1, 1 \right>$ and its transpose on the left and right, so generically it's just a matter of computing initial values, although there might be a better way using something like the MacMahon master theorem or known results on the Ihara zeta function.

Anyway, makar, the explanation is as follows:  consider a [url=http://en.wikipedia.org/wiki/Graph_theory]graph[/url] with vertices $ A, B, C$ which represent a choice of each letter.  We will give it weighted edges that represent the possible choices of next vertex, i.e. from vertex $ A$ we can only go to vertices $ B, C$ and we give those choices weights of $ b$ and $ c$ so that in the end result we can use the exponents of the weights to count how many times we passed each vertex.  Key concept: [url=http://en.wikipedia.org/wiki/Adjacency_matrix]adjacency matrices[/url] and their relationship to [url=http://mathworld.wolfram.com/Walk.html]walks on graphs[/url].

Accidentally, I recently saw this question in
Alexander Robertson, [i]A Problem in Combinatorics[/i], Proceedings of the Edinburgh Mathematical Society 1885, pp. 78-87.
The last page gives an explicit value for $ m$ a's, $ n$ b's, and $ p$ c's in a line as a sum of products of binomial coefficients.
You can find the paper at http://www.archive.org/details/proceedingsedin02socigoog .

  darij

Let $p_k(x)=\sum_{i=1}^k\frac{(-1)^i}{i!}\binom{k-1}{i-1}x^i$. Then the number of variegated permutations of the word $A_1^{k_1}A_2^{k_2}A_3^{k_3}\ldots A_n^{k_n}$ is \[\int_0^\infty e^{-x} \prod_{j=1}^n p_{k_j}(x)\ \mathrm{d}x\] where the effect of the integration is merely to replace every $x^i$ in the polynomial with $i!$. This is a fairly straightforward generating function solution using inclusion-exclusion.

Thus the number of variegated permutations of $\bf{SUCCESS}$ is \[\int_0^\infty e^{-x}p_3p_2p_1^2\ \mathrm{d}x=\int_0^\infty e^{-x}\cdot x^2(\tfrac{1}{12}x^5-\tfrac23x^4+\tfrac32x^3-x^2)\ \mathrm{d}x=96\] Similarly, the number of variegated permutations of $\bf{ANTIDISESTABLISHMENTARIANISM}$ is \[\int_0^\infty e^{-x}p_5p_4^2p_3^2p_2^2p_1^5\ \mathrm{d}x=3023024989286412633600\] The polynomials defined above can be presented as generalized Laguerre polynomials: $p_k(x)=(-1)^kL_k^{(-1)}(x)$.


algebra
polynomial
inequalities
search
Galois Theory
algebra proposed

In excellent russian book Prasolov: Mnogochleny on page 62
there is a following problem:

Prove that polynomial 1+x/1!+x^2/2!+...+x^n/n! is irreducible.

The solution is almost immediate by using Bertrand postulate and
prime p between n/2 and n. Im not sure if I missed something
but this doesnt seem to be so direct. What do you think about it?

How does it follow from Bertrand's postulate?

In Lang's Algebra there is the reference

J. Schur, Affektlose Gleichungen in der Theorie der Laguerreschen und Hermiteschen Polynome, [i]J. reine angew. Math.[/i] 165 (1931), pp 52-58.

In fact Schur shows that if $4\!\not\,\mid n$, then the Galois group over $\mathbb{Q}$ is $S_{n}$, and if $4\mid n$, then it is $A_{n}$.

[quote="Eigenray"]How does it follow from Bertrand's postulate?[/quote]

This is also my question. In the mentioned book it says something like this:
"by Eisenstein it is enough to find some p between n/2 and n (they apply
it on polynomial x^n+nx^{n-1}+...+n!) and such p exists by Bertrand so
we are done."
It looks very suspicious to me, and I suppose its some kind of mistake,
so I want that somebody confirm it.
Eigenray, do you know some proof of this problem? Is that Schur's result?
What is connection between Galois group and irreducibility?
Thank you!

Categorically, the "proof" is wrong. It is impossible to derive the irreducibility from only Eisenstein; one has to employ the more elaborate theory of $p$-adic Newton polygons (for suitably-chosen $p$, but Bertrand's postulate will not suffice for this choice: if I remember correctly, one of the proofs used the more general theorem of Sylvester that if $n > k$ then $(k+1)\cdots (k+n)$ has a prime factor bigger than $k$), mixed with estimates for the roots.

This mistake in Prasolov's book is a famous one. In fact, Myth and I discussed it in this thread: http://www.mathlinks.ro/viewtopic.php?search_id=413080592&t=19242


calculus
integration
logarithms
calculus computations

find
$ \int_{0}^{ \infty} \frac{1}{\sigma \sqrt{2\pi}} \exp\left(\minus{} \frac{(\ln x \minus{} \mu)^2}{2\sigma^2} \right)dx$

hello, for this integral we get as the result
$ e^{\frac{1}{2}\sigma^2\plus{}\mu}\cdot\text{ sign }(\sigma)$.
Sonnhard.


A bag contains 500 beads, each of the same size. but in 5 different colors. Suppose there are 100 beads of each color and i am blindfolded. What is the fewest number of beads i must pick to be absolutely sure there are 5 beads of the same color among the beads i have picked blindfolded?

[hide]Lets consider the worst case:
You have 4 beads of each of the 5 colors. By pigeonhole, if you add one more bead, that will make one color have 5 beads chosen. So 21[/hide]
I agree, this should go in Classroom Math

Whoops, I though there were 4 colours for some reason.  :blush:
And what happened to the forum?


Asymptote
function
geometry
circumcircle
analytic geometry
induction

using asymptote, how would you extend a line (say AB) to meet another line or a curve at a point (say X)?

Maybe this can help you: [[Asymptote:_Useful_functions]]  (not sure what exactly you are asking). :maybe:

like on the following page, on example 7:
[url]http://www.artofproblemsolving.com/Wiki/index.php/Asymptote:_Useful_commands_and_their_Output[/url]

how would you extend AI to meet the circumcircle and get the coordinates of that point of intersection?

[quote="Valentin Vornicu"]I don't know any commands but I myself would compute a sequence of points on the ray $ (AI$ as follows: $ A_1 \equal{} 2I \minus{} A$ is the symmetric of $ A$ with respect to $ I$. By induction the point $ A_n \equal{} 2^nI \minus{} (2^n \minus{} 1)A$ is on the same line, being the symmetric of $ A$ with respect to $ A_{n \minus{} 1}$. We can go as far as we want on that line. So pick a high $ n$, and then do the intersection points command.[/quote]

uhh.. could you give some code as an example?

I just gave you the code above. You can easily do any other points on the line, but using midpoints made the math easier.


Ξεκινάω ένα νέο τοπικ. Και επειδή το επίπεδό μας είναι πολύ καλό βάζω κάτι δύσκολο.
αυτή η άσκηση που θα βάλλω έχει τεθεί στο φόρουμ αλλά εκεί οι λύσεις και οι απαντήσεις είναι δυσνόητες οπότε λύστε παρακαλώ εδώ τηνάσκηση και μην κάνετε παραπομπή σε κάποιο τόπικ. θα ήθελα και τη βοήθεια των κ. Nickolas  και του κ.Στεργίου.

θεωρούμε ένα σύστημα μεταλλικών σφαιρών απείρου πλήθους με κέντρα σε όλα τα σημεία $(a,b,c)\in Z^3$. Λέμε ότι το σύστημα είναι ευσταθές, αν η θερμοκρασία κάθε σφαίρας ισούται με το μέσο όρο των θερμοκρασιών των $6$ πιο γειτονικών της σφαιρών. Υποθέτουμε ότι η θερμοκρασία κάθε σφαίρας είναι μεταξύ των $0$ και $1$ βαθμών. Αν το σύστημα των σφαιρών είναι ευσταθές, να αποδείξετε ότι όλες οι σφαίρες έχουν την ίδια θερμοκρασία.

Αυτό το θέμα είχε τεθεί στην Μεσογειαδα το 2003, ατυχής στιγμή. Μάλλον πολύ ατυχής γιατί απο όσο ξέρω (και φαντάζομαι) δεν το έλυσε κανείς.
Θα ήθελα πολύ να δω μια "ολυμπιακή" λύση σε αυτό το παρα πολύ δύσκολο πρόβλημα. Η επίσιμη λύση που είχαν προτήνει το 2003 δεν ήταν στοιχειώδης. Μπορώ να σας την γράψω εάν θέλετε, αλλα το θεωρώ άσκοπο. Και αν θυμάμε καλά ούτε οι λύσεις που έδωσαν στο φορυμ είναι στοιχειώδεις.
Καλή προσπάθεια.   ;)

Στέργιο αν δεν σου είναι κόπος μπορείς να δώσεις την επίσημη λύση?με ενδιαφέρει. Ψάξτε λίγο όλοι σας παρακαλώ την άσκηση και μετά αν δεν έχετε κάτι καλό θα δώσω μια δική μου λύση σε αυτό το πολύ ωραίο πρόβλημα. Τα λέμε

[quote="Anto"] Η επίσιμη λύση που είχαν προτήνει το 2003 δεν ήταν στοιχειώδης. Μπορώ να σας την γράψω εάν θέλετε, αλλα το θεωρώ άσκοπο. Και αν θυμάμε καλά ούτε οι λύσεις που έδωσαν στο φορυμ είναι στοιχειώδεις.
Καλή προσπάθεια.   ;)[/quote]

se glitono apo ton kopo! :) mia megethinsi thelei kai fainetai mia xara

Ευχαριστώ πολύ αλλά πολύ στριφνή λύση ρε παιδιά, πολύ περίεργη. Ας προσπαθήσουμε λοιπόν για κάτι καλύτερο.

[quote="silouan"] Ψάξτε λίγο όλοι σας παρακαλώ την άσκηση και μετά αν δεν έχετε κάτι καλό θα δώσω μια δική μου λύση σε αυτό το πολύ ωραίο πρόβλημα. Τα λέμε[/quote]

enas apo tus logus pu espeusa na steilo tin episimi apantisi einai gia na do diaforetiki lisi!
tha mporuses na grapseis ti lisi su?

Στέλνω τη λύση μου. Γαλέε πήρες το ΡΜ?

:huh: fovamai oti einai lathos i apodeiksi su. ekei pu les oti apo tis perioxes me kentro $x_6,x_7$ epetai oti oi termokrasies einai ises exeis kanei "ipervasi"

edit : $x_2,x_3$ ennousa.

ap' oti exo katalavei xrisimopeis kati san epagogi stin apodeiksi su. dld pairneis ena sxima(kivos+ merikes korifes) kai prospatheis na apodeikseis oti oles oi korifes sto sxima exun tin idia thermokrasia. gia na to deikseis auto theoreis diplana paromoia sximata pu theoreis oti isxiei auto pu pas na apodeikseis. auto omos den exei eksasfalistei (kai dn nomizo oti mporei na eksasfalistei). Me alla logia, i poreia su se auto to provlima einai: Theoro to plegma $x_1$,to plegma $x_2$,k.o.k Tha deikso oti to plegma $x_n$ ikanopoiei tin tade sinthiki. Gia na deikseis to teleutaio xrisimopoieis tin protasi gia kapoia plegmata(sti lisi su ton $x_2,x_3$) dld epagogi. alla dn exeis deiksei oti iparxei ena plegma pu ikanopoiei auto pu les kai epomenos i "epagogi" auti dn exei vasi.
An oi korifes itan peperasmenu plithus(as pume mesa se mia sfaira), kati tetoio tha mporuse na itan epiteuksimo.
Elpizo na egina katanoitos.

[quote="Anto"]Poy einai i lisi gia tin ipoia sizitate?  :?[/quote]

4-5 posts pio pano! :P

Den mporo na bro tin lisi gia tin opia milate... Mporei na exei kapoio problima o browser mou... :(

gia opoiadipote metathesi $\pi$ tu sinolu $\{1,2,..,n\}$ esto $d(\pi)$ to athroisma
$|\pi(1)-1|+|\pi(2)-2|+...+|\pi(n)-n|$ kai esto $i(\pi)$ o arithmos ton αντιστροφών tis metathesis $\pi$. Me alla logia, to  $i(\pi)$ metraei ta zeugaria $1\leq i<j\leq n$ tetoia oste $\pi(i)>\pi(j)$. Na deixtei oti $i(\pi)\leq d(\pi)$.

Poli oraio problima!
Grafo parakato tin lisi mou :
I apodeiksi einai me epagogi pano stin timi i(p). An i(p)=0 i 1 to apotelesma einai profanes.
Esto p metathesi diaforetiki tis tautotas. Tote esto $A_{p}=\{k/p(k)>k\}$. Exo oti $A_{p}=0$ mono kai mono otan p einai i tautotitiki metathesi. Esto oti $k_{0}=max (A_{p})$ tote $p(k_{0} +l)\leq k_{0}+l$.
An isxuei i isotita $p(i)=i$ gia kathe $i > k_{0}$ tote exoume antifasi.(giati ?)
Ara iparxei elaxisto z, oste $p(k_{0}+z)<k_{0}+z$. Tote omos $p(k_{0}+z)\leq k_{0}$kai $p(k_{0})\geq k_{0} +z$. Tote theoro tin metathesi $p'$ i opoia antimetatheti tis times ton $p(k_{0})$ kai $p(k_{0} +z)$stin arxiki p. Kai apla efarmozo tin epagogiki ipothesi gia na telioso to epagogiko bima.
 Stergios


calculus
derivative
calculus computations

As $ x$ goes to $ \infty$, $ y$ goes to $ \minus{}\infty$. As $ x$ goes to $ \minus{}\infty$, $ y$ goes to $ 0$. So there should be a local maximum (I think) somewhere. Perhaps differentiation should find it.

hello, we have
$ f'(x)\equal{}\minus{}x\minus{}\sqrt{x^2\plus{}b^2}\plus{}(a\minus{}x)\left(1\plus{}\frac{x}{\sqrt{x^2\plus{}b^2}}\right)$
and we get
$ f'(x)\equal{}0 \Leftrightarrow \minus{}b^2(\minus{}2ax\plus{}a^2\minus{}b^2)\equal{}0$
and from here you can go on.
Sonnhard.


It sure is from Kvant, where else could Nitrolou take it from... i mean such a problem has got to be from Kvant... and we, Moldovans can find and understand Kvant problems :):):)

May be it is in Kvant  , but I saw it somewhere in an Ukrainean contest ....?

Does he have to ask only about one knight at a time? I mean, can he ask for information about two knights in the same question, for example?

Also, I assume he can't distinguish their colors :D

It's not that clear, you know. So he can ask about more than one knight?

yes,he can ask about more than one knight.
but I don't see something unclear there.

Ok, I got it (not that I have any idea about a solution :)). What was unclear was that I asked something in the form "$A$ or $B$?" and you answered "of course!", so I didn't exactly know what you meant :).

Sorry for this useless discussion.. :D

[quote="nytrolou"]There are n knights in a kingdom. The knight can be white or black.
If a knight is white it means that he tells only truth, if it's black then he always lies.
All knights have full information about each other.
A socialist wants to know the tipe of each knight. He can ask questions. The answers to his questions can be only 'yes' or 'no'.
In which case the socialist can find out the type of all knight in less questions if
i)he asks all his questions to only one knight or
ii)he chooses another person to ask every time ???[/quote]

The answer is that it doesn't actually matter.

First we prove that (i) is optimal:

The reason is that by asking only one knight I can always model asking another knight by saying:

"What would you say that <insert some other knight> would answer to the following question: ...?"

Note that if the knight you are asking is black, you are asking him what he [i]would[/i] say, but since he [i]would[/i] lie but is also lying [i]right now[/i], in the end he tells you a "true" statement.

Now we prove that (ii) is optimal:

Just as for (i), I can ask "What would you say that <insert original knight> would answer to the following question: ...?"

Thus since (i) is optimal and (ii) is optimal, (i) and (ii) are both equal and so it doesn't matter.

It's interesting to note that one can deduce the answer in at most n questions by asking whether a known true statement is true or not.

It`s probably an easy variation on a famous problem from some russian Olympiad. The original problem is: there are $2n+1$ knights but black ones can say truth or lie. Prove that the least number of question for a socialist to know the color of each knight is $3n$. (the socialist can only ask to some knight the color of another knight).

 I dont know how to prove this is the least number but i know it´s very hard and beatifull.


algebra
polynomial
quadratics
algebra unsolved

Let $\epsilon$ be the $n^{th}$ root of unity. Also let $a_i$, $i=\{0,1...,n-1\}$ be n real numbers such that
$a_0+a_1\cdot\epsilon+a_2\cdot\epsilon ^2 +...+a_{n-1}\cdot\epsilon ^{n-1} =0$
Prove that $a_0=a_1=...=a_{n-1}$

I dont think it is true, something similar holds when $n$ is prime and the $a_i$ are rationals but if dont, then we can construct many polynomials of degree $n-1$ such that $\lambda$ is a root of them, since the minimal polynomial of $\lambda$ over the rationals is the nth cyclotomic polynomial, and over the reals it is a quadratic one! so what did you mean?

Apparently, he forgot a number of conditions: $n$ is a prime and $a_i$ are rationals.

I would say the missing condition is $a_0 \leq a_1 \leq ... \leq a_{n-1}$, since this or something equivalent to this was an IMO problem a long time ago

Edit: I found it: IMO 1963, problem 3

Cool!

Let $S=a_0+a_1\cdot\epsilon+a_2\cdot\epsilon ^2 +...+a_{n-1}\cdot\epsilon ^{n-1}$. Suppose $S=0$ and consider \[(\epsilon-1)S=(a_{n-1}-a_0)-(a_1-a_0)\epsilon+(a_2-a_1)\epsilon^2+...+(a_{n-1}-a_{n-2})\epsilon^{n-1}=0.\] If one of the numbers $a_i-a_{i-1}\neq 0$ ($i=1,2,...,n-1$), then we have \[|S|>|a_n-a_0|-|a_1-a_0|-...-|a_{n-1}-a_{n-2}|=0.\] Contradiction.

P.S. This trick was used in the following nice theorem on irreducibility.

[b]Theorem.[/b]
Let $a_1\geq a_2\geq ...\geq a_n$ are natural numbers, $n\geq 2$. Then the polynomial \[x^n-a_1x^{n-1}-a_2x^{n-2}-...-a_n\] is irreducible.


Let a convex polygon $ P$ be contained in a square of side one.  Show that the sum of the squares of the sides of $ P$ is less than or equal to $ 4$.

If any vertex of the convex polygon lies in the interior of the square, then we may pull that vertex outward in a direction that lengthens both of the sides attached to the vertex. Hence we may assume that all of the vertices lie on the edges of the square. If three vertices lie on the same edge, then we may increase the sum of the squares of the edges simply by deleting the middle vertex, since $ (x\plus{}y)^2>x^2\plus{}y^2.$

So there are no more than two vertices per edge of the square and no more than 8 vertices overall. Label the vertices as $ (a,0),(b,0),(1,c),(1,d),(e,1),(f,1),(0,g),(0,h)$ with $ a<b,c<d,e>f,g>h$ and all of these numbers in $ [0,1].$ The sum of the squares is then

$ 2(a^2\plus{}b^2\plus{}c^2\plus{}d^2\plus{}e^2\plus{}f^2\plus{}g^2\plus{}h^2)\minus{} 2ab\minus{}2cd\minus{}2ef\minus{}2gh\minus{}2b\minus{}2d\minus{}2e\minus{}2g\plus{}4$

This quadratic expression can be shown to be positive definite, since $ 2a^2\minus{}2ab\plus{}2b^2$ and similar expressions are positive definite. Hence, any extreme points at anything other than extreme placements of the variables result in minima rather than maxima. The most extreme placement of the variables is $ a\equal{}c\equal{}f\equal{}h\equal{}0,b\equal{}d\equal{}e\equal{}g\equal{}1,$ in which case the value of the expression is $ 4.$ This amounts to exactly replicating the square as our convex polygon.


geometry
ratio
trigonometry
angle bisector

In triangle ABC, points D and E are on AB and AC respectively, and angle biscetor AT intersects DE at F and BC at T.  If AD=1, DB=3, AE=2, and EC=4, compute the ratio AF:AT

Using mass points (but remember this is my way of mass points, and I'm not sure, but it's probably a slightly inefficient form.  But you get the picture).

[hide="Solution"]

Let $AE=3*y$, $EC=4*y$, $AD=x$, and $DB=3*x$

Therefore, at Point A, $3*x=4*y$  $\rightarrow$ $y=\frac{3}{4}*x$

Point C is $3*y$ and Point B is $x$

Therefore, Point T is $3*x+y$ $\rightarrow$ $\frac{13}{4}$

Then $AF=\frac{13}{4}*x$ and $FT=3*y$

Then ${\frac{AF}{AT}=\frac{\frac{13}{4}}{3+\frac{13}{4}}}=\frac{13}{5}$

[/hide]

Um, wait mathgenius-how can AF be bigger than AT-and I asked someone about it and they used laws of cosines and angle bisector ratios and they got 5/18, although I dont know the correct answer.

[hide="Easy Solution"]

I got $\frac{5}{18}$ too.

First use the angle bisector theorem twice, $DF: FB = 1: 2$ and $BT: TC=4: 6$.

I used area ratios like so.
I'm looking for $[ATC]$.

$[AFC] : = K$
$[ADC] = \frac{3}{2}K$
$[ABC] = \frac{4}{1}[ADC] = 6K$
$[ATC] = \frac{3}{5}[ABC] = \frac{18}{5}K$

Now, we're looking for $AF/AT = [ATC]/[AFC] = \boxed{\frac{5}{18}}$
[/hide]


Prove that $ (2n)!/2^n n!$ is an integer for all n>=0.

Thank you.

[hide="My Solution"]
We can prove this by induction. Our base case $ n \equal{} 0$, yields $ 1/1 \equal{} 1$, which is an integer. Now let us assume that for some integer $ n \equal{} k$ that this expression is an integer. We have $ \frac {(2k)!}{2^{k}\cdot k!} \in \mathbb{Z}$. Now we must prove that $ n \equal{} k \plus{} 1$ is an integer.

$ \frac {(2k \plus{} 2)!}{2^{k \plus{} 1}\cdot (k \plus{} 1)!} \equal{} \frac {(2k)!}{2^{k}\cdot k!}\cdot \frac {(2k \plus{} 1)(2k \plus{} 2)}{2\cdot (k \plus{} 1)} \equal{} \frac {(2k)!}{2^{k}\cdot k!}\cdot \frac {(2k \plus{} 1)(2k \plus{} 2)}{2k \plus{} 2} \\
\equal{} \frac {(2k)!}{2^{k}\cdot k!}\cdot (2k \plus{} 1).$

By our assumption, $ \frac {(2k)!}{2^{k}\cdot k!} \in \mathbb{Z}$ and we have $ 2k \plus{} 1 \in \mathbb{Z}$ because $ k \in \mathbb{Z}$, so it is clear that $ \frac {(2k \plus{} 2)!}{2^{k \plus{} 1}\cdot (k \plus{} 1)!} \in \mathbb{Z}$. Therefore, $ \frac {(2n)!}{2^{n}\cdot n!} \in \mathbb{Z}$ for $ n \equal{} k$ and $ n \equal{} k \plus{} 1$, so it holds for all nonnegative integers $ n$.
[/hide]

That is an excellant solution( a golden one as your username suggests).

Thank you.


$ \begin{array}{l}
 \sum\limits_{i \equal{} 1}^n {i^2 }  \equal{} \frac{{n(n \plus{} 1)(2n \plus{} 1)}}{6} \\
 \sum\limits_{i \equal{} 1}^n {i^3 }  \equal{} \left[ {\frac{{n(n \plus{} 1)}}{2}} \right]^2  \\
 \end{array}$

[quote="Nguyen Ngoc Linh"]Mathlinkers, can you help me? :D
Compute:
A=1^2 + 2^2 + 3^2 + ... + n^2
B=1^3 + 2^3 + 3^3 + ... + n^3
Somebody showed me solutions but they were really...unbelievable!!![/quote]

1)$ \frac {n(n \plus{} 1)(2n \plus{} 1)}{6}$

2)$ \left(\frac {n(n \plus{} 1)}{2}\right)^2$

If you want the proof I can give it to you. USING INDUCTION!

EDIT: Beaten  :)

The sum of the first $ n$ squares is $ \frac {n(n \plus{} 1)(2n \plus{} 1)}{6}$.

The sum of the first $ n$ cubes is $ \frac {n^2(n \plus{} 1)^2}{4}$.

To prove the squares formula, we can use induction. First we show that it works for our base case, 1.

$ \frac {1(1 \plus{} 1)(2(1) \plus{} 1)}{6} \equal{} 1$, which is correct. Now we have to show that if it works for $ k$, it will work for $ k \plus{} 1$.

So if $ 1^2 \plus{} 2^2 \plus{} \dots \plus{} k^2$ is $ \frac {k(k \plus{} 1)(2k \plus{} 1)}{6}$, then $ 1^2 \plus{} 2^2 \plus{} \dots \plus{} k^2 \plus{} (k \plus{} 1)^2$ is $ \frac {k(k \plus{} 1)(2k \plus{} 1)}{6} \plus{} (k \plus{} 1)^2$, which is $ \frac {k(k \plus{} 1)(2k \plus{} 1) \plus{} 6(k \plus{} 1)^2}{6}$, and this simplifies to $ \frac {(k \plus{} 1)(k \plus{} 2)(2(k \plus{} 1) \plus{} 1)}{6}$. QED.

To prove the cubes formula, we can use induction again. Like in the last proof, we show that it works for 1.

$ \frac {n^2(n \plus{} 1)^2}{4} \equal{} \frac {1^2(1 \plus{} 1)^2}{4} \equal{} 1$, so it works. Now we show that it works for $ k \plus{} 1$.

$ 1^3 \plus{} 2^3 \plus{} \dots \plus{} k^3 \plus{} (k \plus{} 1)^3 \equal{} \frac {k^3(k \plus{} 1)^2}{4} \plus{} (k \plus{} 1)^3$, which is $ \frac {k^2(k \plus{} 1)^2 \plus{} 4(k \plus{} 1)^3}{4}$, and this simplifies to $ \frac {(k \plus{} 1)^2(k \plus{} 2)^2}{4}$. QED.

EDIT: Beaten to it.
EDIT 2: Beaten to it twice. Well, I showed the proofs.

They are the formulas that guy showed me.Now I believe in them.You guys are really smart ( or I'm too stupid? ).
Anyway, (1 + 2 +...+n)^2 = 1 + 2^3 + ... + n^3
It's interesting ^^


Prove that for each square-free natural number $ k$, there are infinitely many pairs $ (m,n)$ with $ \binom{m}{2} \equal{} k\binom{n}{2}$.

[hide="Large hint"] Think Pell's. ;) [/hide]

[quote="pleurestique"]$ \binom{m}{2} \equal{} k\binom{n}{2} \iff (2m \minus{} 1)^2 \minus{} k(2n \minus{} 1)^2 \equal{} 1 \minus{} k$. the Pell equation $ x^2 \minus{} ky^2 \equal{} 1 \minus{} k$ has smallest solution $ (1,1)$, so it has infinitely many solutions $ (x_n,y_n)$, given by $ x_n \plus{} y_n\sqrt {k} \equal{} (a \plus{} b\sqrt {k})^n(1 \plus{} \sqrt {k})$, where $ (a,b)$ is the smallest solution of $ x^2 \minus{} ky^2 \equal{} 1$. we only need to check that infinitely many of these solutions have $ x,y$ both odd. note that $ x_n,y_n$ satisfy the recurrences $ x_{n \plus{} 1} \equal{} ax_n \plus{} by_nk$, $ y_{n \plus{} 1} \equal{} ay_n \plus{} bx_n$.

if $ k$ is even, it's clear that every $ x_n$ is odd. also, $ a$ is odd. if $ b$ is odd, then the parity of $ y_n$ alternates. if $ b$ is even, then all $ y_n$ are odd in light of $ y_{n \plus{} 1} \equal{} ay_n \plus{} bx_n$.

otherwise, $ k$ is odd. if $ b$ is even, then $ a$ is odd, so from the above recurrences we get that the sequence $ (x_n\pmod 2, y_n\pmod 2)$ goes $ (1,1), (1,1), ...$. if $ b$ is odd, then $ a$ is even, so the sequence $ (x_n\pmod 2, y_n\pmod 2)$ again goes $ (1,1), (1,1), ...$.[/quote]

that's my solution :)


Columbia
geometry
circumcircle
trigonometry
geometry unsolved

Given an acute triangle $ABC$, let $D$, $E$ and $F$ be points in the lines $BC$, $AC$ and $AB$ respectively. If the lines $AD$, $BE$ and $CF$ pass through $O$ the centre of the circumcircle of the triangle $ABC$, whose radius is $R$, show that:
\[\frac{1}{AD}\plus{}\frac{1}{BE}\plus{}\frac{1}{CF}\equal{}\frac{2}{R}\]

[quote="carlosbr"][color=blue] [size=150]$1^{st}$  Iberoamerican Olympiad[/size]
Villa de Leyva, COLOMBIA. [1985] [/color]

[color=blue]Problem 6 [/color]
Given an acute triangle $ABC$, let $D$, $E$ and $F$ be
points in the lines $BC$, $AC$ and $AB$ respectively. If the lines
$AD$, $BE$ and $CF$ Pass by $O$ the center of the circumcircle
of the triangle $ABC$, whose radio is $R$, show that
$\frac{1}{AD} + \frac{1}{BE} + \frac{1}{CF} = \frac{2}{R}$.

$\text{\LaTeX}{}ed$ by Carlos Bravo - [carlosbr][/quote]

[color=red][b]Lema. [/b](Gergonne) Given $\triangle ABC$ and a point $P$ in its plane, let $\triangle P_aP_bP_c$ be the cevian triangle of $P$ respect to $\triangle ABC$, then $\frac{PP_a}{AP_a} + \frac{PP_b}{BP_b} + \frac{PP_c}{CP_c} =1$ and $\frac{AP}{AP_a} + \frac{BP}{BP_b} + \frac{CP}{CP_c} =2$.[/color]

[b]Proof. [/b]By areas it follows $[BPC]/[ABC]=PP_a/AP_a$, $[APC]/[ABC] = PP_b/BP_b$, $[APB]/[ABC]=PP_c/CP_c$, which, when added up, we have

  $PP_a/AP_a+PP_b/BP_b+PP_c/CP_c=\frac{[BPC]+[APC]+[APB]}{[ABC]}=1$.

if we pay attention at $PP_a=AP_a-AP$, $PP_b=BP_b-BP$, $PP_c=CP_c-CP$ we get $\frac{AP}{AP_a} + \frac{BP}{BP_b} + \frac{CP}{CP_c} =2$. $\square$

So, using this we have:

$\frac{R}{AD} + \frac{R}{BE} + \frac{R}{CF} = 2$. and thus

$\frac{1}{AD} + \frac{1}{BE} + \frac{1}{CF} = \frac{2}{R}$. $\square$

I think this issue really simple, I resolved by methods similar to hucht.
On some mathematics journals and youth magajine have mentioned this problem.(it is only a lemma to sloved  problem that)

By $ \textbf{\textit{Sine}}$ law to $ \textbf{\textit{ABD}}\Delta$, $ \frac{\textbf{\textit{AB}}}{\textit{\textbf{Sin(B\plus{}90\minus{}C)}}}\equal{}\frac{\textbf{\textit{AD}}}{\textbf{\textit{Sin(B)}}}$. So $ \frac{\textbf{\textit{1}}}{\textbf{\textit{AD}}}\equal{}\frac{\textbf{\textit{Cos(C\minus{}B)}}}{\textbf{\textit{2RSinBSinC}}}\equal{}\frac{\textbf{\textit{1}}}{\textbf{\textit{2R}}}\cdot[\textbf{\textit{CotCCotB\plus{}1}}]$. Thus
$ \frac{\textbf{\textit{1}}}{\textbf{\textit{AD}}} \plus{} \frac{\textbf{\textit{1}}}{\textbf{\textit{BE}}} \plus{} \frac{\textbf{\textit{1}}}{\textbf{\textit{CF}}}$ $ \equal{}\frac{\textbf{\textit{1}}}{\textbf{\textit{2R}}} \cdot\textbf{\textit{[CotACotB\plus{}CotBCotC\plus{}CotCCotA\plus{}3]}}$. But we can show $ \textbf{\textit{CotACotB\plus{}CotBCotC\plus{}CotCCotA}}\equal{}\textbf{\textit{1}}$. Hence the result.

$ \textbf{\textit{Q.E.D.}}$ :)


Using only paths that follow the line segments and go downward, how many different paths go from A to Z?

I got 30 ways...but I am not sure..
EDIT: I think it's 54 now. The solution is at the bottom.

[quote="Nerd_of_the_Ages"]post your solutions, it will be much easier to look for mistakes or whether your solution is right[/quote]
Well, there's a way to do this problem, you know...(It's not counting all of them)
But if you insist I post it...Do you want me to?

[quote="DonkeyKong"]Do you want me to?[/quote]
[quote="Nerd_of_the_Ages"]post your solutions[/quote]

Eh.. I am glad I did this.. I got different answer.
I got $ \boxed{54}$
Tell me if this is wrong.

[quote="i_like_pie"]Shouldn't the 9's be 10's? That would make the 18 a 20, the 27's would become 30's, and the answer would be 60.[/quote]
Can you explain?
Hmm.. I don't get it.. I'll look it over again.. Thanks for catching my mistake.

The idea behind your solution is correct, but you messed up a little on the details. The number of ways to get to a point is the sum of the numbers of ways of getting to each of its tributaries.

There are 10 (1+3+6) ways to get to each of the side points from A. Then, there are 20 (10+10) ways to get to the lowest point in the middle [besides Z], and 30 (10+20) ways to get to each of the remaining points. Finally, there are 60 (30+30) ways to get to Z.

even though i got it right, can some1 pm me the solutions?


For $n \ge 3$, evaluate the summation

$\sum_{k=1}^{n}{n \choose k}k^{3}$

[hide="Hint"] This is the number of ways to pick a committee out of $n$ people, and then to pick a chairman, a vice-chairman, and a secretary (not necessarily distinct) within that committee. [/hide]
Can you generalize?

[hide="Remark"] It seems to me that the generalization involves Stirling numbers of the Second Kind. [/hide]

[hide]
We have the identity
\[\binom{n}{k}\binom{k}{m}=\binom{n}{m}\binom{n-m}{k-m}\]
To see this, the left side is equal to the number of ways of coloring $k$ out of $n$ squares, such that $m$ of the $k$ are red and the rest are blue. There are $\binom{n}{m}$ ways to first color the red squares, and $k-m$ of the remaining $n-m$ squares are selected to be colored blue. This gives the right side of the identity.

Now we can sum this identity over $k$ and get
\[\sum_{k}\binom{n}{k}\binom{k}{m}=\binom{n}{m}\sum_{k}\binom{n-m}{k-m}=2^{n-m}\binom{n}{m}\]
Now we just need to write $k^{3}$ in terms of binomial coefficients. Plugging in $k=1$, then $k=2$, then $k=3$ shows that
\[k^{3}=\binom{k}{1}+6\binom{k}{2}+6\binom{k}{3}\]
which makes our sum equal to
\[n\cdot 2^{n-1}+3n(n-1)\cdot 2^{n-2}+n(n-1)(n-2)\cdot 2^{n-3}\]
[/hide]

That is quite a nice solution :D  Care to tackle the generalization?

[hide="The intended solution"] I usually prefer transformative solutions to problems like these, but the combinatorial interpretation is quite elegant:

As I said in the hint, this is the number of ways to pick a (nonempty) committee out of $n$ people and then to pick a (not necessarily distinct) chairman, vice-chairman, and secretary.

[b]Case:[/b]  All three are the same person.  Then we can pick that person in $n$ ways, and the rest of the committee in $2^{n-1}$ ways (they are either in it or not), so there are $n \cdot 2^{n-1}$ ways.

[b]Case:[/b]  Two are the same person.  This can happen in three ways.  We pick two distinct people in $n(n-1)$ ways and the rest of the committee in $2^{n-2}$ ways for $3n(n-1) \cdot 2^{n-2}$ ways.

[b]Case:[/b]  The people are all distinct.  We can pick them in $n(n-1)(n-2)$ ways, and the rest of the committee in $2^{n-3}$ ways for a total of $n(n-1)(n-2) \cdot 2^{n-3}$ ways.

This gives the same terms as the transformative solution, but what I like about this solution is the way you see the reasoning behind their form (although the idea of expressing $k^{r}$ in terms of combinations of $k$ is also a very elegant way to tackle this problem; this is equivalent to expressing the number of ways to pick $r$ (not necessarily distinct) special positions in terms of how many of them are non-distinct, which is the substance of the generalization.  As I said, this probably involves Stirling numbers. )[/hide]

[hide="A generalisation"]
Let $\sigma(n,m): =\sum_{k=0}^{n}\binom{n}{k}\cdot k^{m}$; of course $\sigma(n,0)=2^{n}$. For any $n,k\geqslant 1$ we have $k\binom{n}{k}= n\binom{n-1}{k-1}$, so for $n,m\geqslant 1$:
\begin{eqnarray*}\sigma(n,m)&=& \sum_{k=1}^{n}\binom{n}{k}k^{m}\\ &=& n\sum_{k=1}^{n}\binom{n-1}{k-1}\left(k-1+1\right)^{m-1}\\ &=& n\sum_{k=0}^{n-1}\binom{n-1}{k}\left(k+1\right)^{m-1}\\ &=& n\sum_{k=0}^{n-1}\left(\binom{n-1}{k}\cdot \sum_{j=0}^{m-1}\binom{m-1}{j}k^{j}\right)\\ &=& n\sum_{k=0}^{n-1}\left(\binom{n-1}{k}\cdot \sum_{j=0}^{m-1}\binom{m-1}{j}k^{j}\right)\\ &=& n\sum_{j=0}^{m-1}\binom{m-1}{j}\sigma(n-1,j).\end{eqnarray*}
Using this recursive definition of $\sigma(n,m)$, we can evaluate $\sigma(n,3)$, as asked in the problem.
\begin{eqnarray*}\sigma(n,3) &=& n\left(\sigma(n-1,0)+2\sigma(n-1,1)+\sigma(n-1,2)\right)\\ &=& n\left(2^{n-1}+2(n-1)\sigma(n-2,0)+(n-1)\left(\sigma(n-2,0)+\sigma(n-2,1)\right)\right)\\ &=& n\left(2^{n-1}+2(n-1)2^{n-2}+(n-1)\left(2^{n-2}+(n-2)\sigma(n-3,0)\right)\right)\\ &=& n\left(2^{n-1}+(n-1)2^{n-1}+(n-1)\left(2^{n-2}+(n-2)2^{n-3}\right)\right)\\ &=& n^{2}(n+3)2^{n-3}. \end{eqnarray*}
It is the same reslut as [b]scorpius119[/b] gave. Of course we can evaluate an explicit formula for any given (especially small) $m$, but I think that deriving the formula in the general case may be very hard.
[/hide]

For $\sigma(n,k)$ with $k \leq5$ see also http://mathworld.wolfram.com/BinomialSums.html


quadratics
LaTeX
algebra
quadratic formula

On the last day of school, Mrs. Wonderful gave jelly beans to her class. She gave each boy as many jelly beans as there were boys in the class. She gave each girl as many jelly beans as there were girls in the class. She brought $ 400$ jelly beans, and when she finished, she had six jelly beans left. There were two more boys than girls in her class. How many students were in her class?

$ \textbf{(A)}\  26    \qquad
\textbf{(B)}\    28   \qquad
\textbf{(C)}\    30   \qquad
\textbf{(D)}\    32   \qquad
\textbf{(E)}\    34$

[hide="Solution"]Let there be $ b$ boys and $ g$ girls. Each of the $ b$ boys gets $ b$ jelly beans, so $ b^2$ jelly beans are given to the boys altogether. Each of the $ g$ girls gets $ g$ jelly beans, so $ g^2$ jelly beans are given to the girls altogether. Since Mrs. Wonderful started with $ 400$ jelly beans and is left with $ 6$, she gives away $ 400\minus{}6\equal{}394$ jelly beans. Hence, we have $ b^2\plus{}g^2\equal{}394$ and $ b\equal{}g\plus{}2$ (we are given that there are two more boys than girls). We can now solve by trial and error:

$ 10^2\plus{}12^2\equal{}244$

$ 11^2\plus{}13^2\equal{}290$

$ 12^2\plus{}14^2\equal{}340$

$ 13^2\plus{}15^2\equal{}394$

We see that there are $ 13$ girls and $ 15$ boys. Thus, there are $ 13\plus{}15\equal{}28$ students total in her class, or answer choice $ \boxed{\mathbf{(B)}}$.[/hide]

My solution is a bit uglier and less elegant.  I did (x+2)^2 + x^2 = 394. Then you could solve for x by basic quadratic formula (it makes it more ugly).

I guessed checked the problem. It might have been faster.

I started from C, and depending on what I got, I moved to B or D. (In this case, B)

I did the exact same thing as $ \$\text{\LaTeX}\$$! :)

Here is the rigorous way.

[hide]

There are b+2 boys and b girls. Each boy gets b+2 jelly beans and each girl gets b jellybeans. Thus, b^2+(b+2)^2 were the total number of jellybeans, or 394. Expanding, we get that 2b^2+4b-390=0. This might look ugly, but we can factor: (2b-30)(b+13)=0. we bet b=-13 or 15, so b=15. Thus, the answer is 15+13, or 28 (B)[/hide]

yay!!! I guessed 28..and I figured out I got it right!! YAY  :D  :D


A truck left Midville at 2:00 PM for Carmine traveling at 40 mph. At 3:15 PM a car left Carmine for Midville at 55 mph. The car and the truck pass each other at exactly 2 hours before the car reached Midville. How far is it from Midville to Carmine?

[hide]The truck is $ 50$ miles away from Midville at 3:15. The two vehicles will pass each other at $ 110$ miles away from Midville, which is $ 60$ more miles (1.5 more hours) away from where the truck is now. In this time, the car will travel $ 82.5$ miles, so the distance between Midville and Carmine is $ 110\plus{}82.5\equal{}\boxed{192.5\text{ miles}}$.[/hide]

[hide]at 3:15, when the 2nd car left, the 1st truck was 40*5/4=50 miles up on the road. they will meet 2 hrs, or 110 miles from Midville, which is 60 miles from where the truck is. in those 1.5 hrs, the car will have traveled 1.5*55=82.5miles. that makes the distance 110+82.5=192.5 miles[/hide]

uck, I don't feel like typing it up, but I got the same answer you guys got:
[hide="Answer"]192.5
[/hide]

[quote="i_like_pie"][hide]The truck is $ 50$ miles away from Midville at 3:15. The two vehicles will pass each other at $ 110$ miles away from Midville, which is $ 60$ more miles (1.5 more hours) away from where the truck is now. In this time, the car will travel $ 82.5$ miles, so the distance between Midville and Carmine is $ 110\plus{}82.5 \equal{}\boxed{192.5\text{ miles}}$.[/hide][/quote]

Yeah everyone is correct.  :)


analytic geometry
inequalities
pigeonhole principle
calculus
integration
probability
expected value

On the $ x,y$ coordinate plane, there is a finite set of line segments. Each line segment lies completely in the square bounded by $ (0,0)$, $ (0,1)$, $ (1,0)$, and $ (1,1)$, and the sum of the lengths of all the line segments is $ 18$.  Prove that there exists a straight line in the plane that crosses at least ten of the segments.

[hide]We will show that in fact, there exists such a straight line that is parallel to one of the axes ($ x$ or $ y$). Notice that the solution easily generalizes; if the sum of the lengths of the segments is $ 2n$, there exists a horizontal or vertical line crossing at least $ n\plus{}1$ of them, where $ n$ is a positive integer.

[b]Lemma.[/b] Consider a set of horizontal segments lying completely within the given unit square such that the sum of the lengths of the segments is 9. Then, there exists a vertical line that intersects at least 10 of them.
[b]Proof.[/b] Here, we use the assumption that the segments are closed; that is, their endpoints are part of the segment. Consider all vertical lines $ x\equal{}k$, where $ 0<k<1$. Note that the expected value of the number of segments the line passes through is 9, since the sum of the lengths of the segments is 9 and their $ x$-coordinates all lie in $ (0,1)$, an interval of size 1. Thus, if no vertical line intersects 10 or more of them, each of them intersect exactly 9 of them. Consider the vertical line $ x\equal{}\epsilon$, where $ \epsilon>0$. For a sufficiently small $ \epsilon$, all 9 horizontal lines intersecting $ x\equal{}\epsilon$ extend to the line $ x\equal{}0$. But they must be completely within the square, so they are open on the left side, contradiction. Therefore, this configuration is impossible, and we need some vertical line to intersect at least 10 of the horizontal segments.
---end lemma---

We now proceed to the main proof. For each segment, construct a right triangle with the segment as the hypotenuse, whose legs are parallel to the axes. To do this, pick one endpoint and draw the parallel to the $ x\minus{}$axis, and take the other, drawing the parallel to the $ y\minus{}$ axis, giving a right triangle. If the segment is horizontal or vertical, the triangle will be degenerate. Let the lengths of the legs be $ a_{i}$ and $ b_{i}$, where $ i\equal{}1,2,\ldots$, where the $ a_{i}$ is the length of the horizontal side and the $ b_{i}$ is the lengths of the vertical side, and let $ c_{i}$ be the length of the hypotenuse. Note that

$ \displaystyle\sum\sqrt{a_{i}^{2}\plus{}b_{i}^{2}}\equal{}\displaystyle\sum c_{i}\equal{}18$.

Also,

$ \displaystyle\sum\sqrt{a_{i}^{2}\plus{}b_{i}^{2}}\le\displaystyle\sum\sqrt{a_{i}^{2}\plus{}2a_{i}b_{i}\plus{}b_{i}^{2}}\equal{}\displaystyle\sum(a_{i}\plus{}b_{i})$,

since the lengths are nonnegative. Therefore, $ \displaystyle\sum(a_{i}\plus{}b_{i})\equal{}\displaystyle\sum a_{i}\plus{}\displaystyle\sum b_{i}>18$, and one of $ \displaystyle\sum a_{i},\displaystyle\sum b_{i}$ is greater than 9. Without Loss of Generality, let $ \displaystyle\sum a_{i}>9$. Now, by the lemma there exists a vertical line that intersects at least 10 of the horizontal edges of the right triangles. But this vertical line will intersect the hypotenuses as well, and thus the original segments. Therefore, the desired line exists, and we're done.[/hide]

[hide]Let there be $ n$ line segments in our finite set, labeled $ L_i$ for $ 0 < i \le n$.  Let each $ L_i$ have endpoints $ (x_i^0, y_i^0)$ and $ (x_i^1, y_i^1)$.  Finally, for each $ L_i$, define $ X_i$ and $ Y_i$ to be the quantities $ |x_i^1 \minus{} x_i^0|$ and $ |y_i^1 \minus{} y_i^0|$, respectively.  In other words, $ X_i$ and $ Y_i$ are the lengths of the projections of $ L_i$ onto the $ x$ axis and the $ y$ axis, respectively.  Note that the length of segment $ L_i$ is $ \sqrt{X_i^2 \plus{} Y_i^2}$, so we have \[ \sum_{i\equal{}1}^n \sqrt{X_i^2 \plus{} Y_i^2} \equal{} 18.\]

Now, assume for the sake of contradiction that no line crosses more than 9 of the $ L_i$ segments.  Then clearly, we must have $ \sum_{i\equal{}1}^n X_i < 9$, because otherwise, there would exist a vertical line crossing 10 of the $ L_i$ Similarly, we must have $ \sum_{i\equal{}1}^n Y_i < 9$.

Thus, because $ \sqrt{a^2 \plus{} b^2} \le a \plus{} b$ for all positive $ a$ and $ b$ (simply square both sides and rearrange to obtain $ 0 < 2ab$), we have

\[ \sum_{i\equal{}1}^n \sqrt{X_i^2 \plus{} Y_i^2} \le \sum_{i\equal{}1}^n X_i \plus{} Y_i,\]
so
\[ 18 \le \sum_{i\equal{}1}^n X_i \plus{} Y_i < 18,\]

which is a contradiction, so there must exist some line crossing more than 9 of the segments.[/hide]
I just stated Catalyst's lemma without proof...   :huh:  Is such a complicated explanation necessary, or is that generally the way such statements are proven?

My proof was essentially the same as Catalyst's but I just used the Triangle Inequality to show that $ \sum a_i \plus{}\sum b_i \geq \sum c_i$...

SIGH SO EASY!

Darn, should have thought of that.

Can anyone extend that argument to prove that the same thing holds even when the segments do not have to lie strictly within the square (i.e. they can touch the square boundary)?  I'm asking this because me humongous proof is much longer than and very different-looking from this one (although now I can see how in essence the arguments stem from the same principle), but my proof does extend to the non-strict case also.

EDIT:
Yes.  Construct a right triangle with a horizontal and a vertical leg at each segment as above, allowing degeneracy.  Let $ H$ be the sum of the lengths of the horizontal legs and $ V$ that of the vertical legs.  In the non-strict version, $ H \plus{} V \geq 18$.  If equality does not hold, then either $ H > 9$ or $ V > 9$ (without loss of generality say the former).  Then the expected value of the number of segments a vertical line through the square hits is greater than $ 9$, so one of them hits $ 10$.

If equality does hold, then all the segments are either vertical or horizontal, and in this case we have either $ H \geq 9$ or $ V \geq 9$ (without loss of generality the former).  If equality does not hold, then it is the same as above.

If equality does hold, then both $ H \equal{} 9$ and $ V \equal{} 9$ must hold.  Then the expected value of the number of [i]horizontal[/i] segments that a vertical line through the square will hit is $ 9$.  Suppose for the sake of contradiction that no line hits ten segments.  Then suppose some vertical line hit $ 8$ or fewer segments.  Then, because there are finitely many segments, there would be an entire real interval of vertical lines which hit $ 8$ or fewer segments, which would make the expected value of the number of segments a vertical line hits macroscopically less than $ 9$, a contradiction.  Therefore no vertical line hits $ 8$ or fewer segments, i.e., each vertical line hits exactly $ 9$ segments.

Then just take a vertical line that passes through one of the vertical segments, and it hits ten.

So that's it.  My two-and-a-half page proof with pretty diagrams was completely unnecessary.

[quote="mustafa"]So would it be legit to say that if two lines are identical, they cross each other?[/quote]
The question speaks of lines crossing [i]segments[/i].  I think that a line crosses its subsegments.

[quote]SO EASY![/quote]
The problem is not easy; the solution just seems easy because it is simple.

So here is a generalization that seems natural to me :  given an arbitrary bounded, connected, closed (or open) region $ \mathcal{R}$ of the plane and an integer $ n$, how do we determine the least positive real $ S$ such that given any finite collection of segments in $ \mathcal{R}$ whose total length is $ S$, there is some line that passes through at least $ n$ of these segments?

Okay, fine.

SIGH EASIER THAN MY SOLUTION.

See attached.

Wow, my random musings on the problem (which i did not write up) actually led to a solution (i was in no way close, though)
ps: very nice problem & solution

Though, as an alum, I'm not required to take the Quiz, I spent a good part of one random morning (car ride to school + much of my first 50-minute class) thinking about this problem, but I did not realize that the segments were not allowed to have endpoints on the box.

My main mode of thinking was to try to use pigeonhole to prove there must be some line through the box for which the lengths of the projection of the line segments onto that line added up to greater than 9 (and, of course, with endpoints on the box, it's quite easy to make the projections of the segments onto the axes both have total lengths of exactly 9, so the real solution would not work). In doing so, I ran into trying to solve some tough trigonometric inequalities. I'm quite disappointed to see how the stipulation that endpoints may not be on the box trivializes (relatively speaking) this problem.

[quote="Darmani"]
I ran into trying to solve some tough trigonometric inequalities. I'm quite disappointed to see how the stipulation that endpoints may not be on the box trivializes (relatively speaking) this problem.
[/quote]

Was there something wrong with my extension of the expected value argument?

[quote="benzi455"]
Construct a right triangle with a horizontal and a vertical leg at each segment as above, allowing degeneracy.  Let $ H$ be the sum of the lengths of the horizontal legs and $ V$ that of the vertical legs.  In the non-strict version, $ H \plus{} V \geq 18$.  If equality does not hold, then either $ H > 9$ or $ V > 9$ (without loss of generality say the former).  Then the expected value of the number of segments a vertical line through the square hits is greater than $ 9$, so one of them hits $ 10$.

If equality does hold, then all the segments are either vertical or horizontal, and in this case we have either $ H \geq 9$ or $ V \geq 9$ (without loss of generality the former).  If equality does not hold [b](i.e., if $ \mathbf{H > 9}$)[/b], then it is the same as above.

If equality does hold, then both $ H \equal{} 9$ and $ V \equal{} 9$ must hold.  Then the expected value of the number of [i]horizontal[/i] segments that a vertical line through the square will hit is $ 9$.  Suppose for the sake of contradiction that no line hits ten segments.  Then suppose some vertical line hit $ 8$ or fewer segments.  Then, because there are finitely many segments, there would be an entire real interval of vertical lines which hit $ 8$ or fewer segments, which would make the expected value of the number of segments a vertical line hits macroscopically less than $ 9$, a contradiction.  Therefore no vertical line hits $ 8$ or fewer [b]horizontal[/b] segments, i.e., each vertical line hits exactly $ 9$ [b]horizontal[/b] segments.

Then just take a vertical line that passes through one of the vertical segments, and it hits ten.
[/quote]

(proofread and put edits in bold)

Thanks, that's pretty nice. Triangle inequality does remove all the trigonometric stuff.

Yes, there is a problem: I'm not sure having a segment pass through another parallel segment counts as an intersection. That's a small problem though -- just take an "almost-vertical" segment instead.

Also, the expectation value does kinda obscure the proof. I prefer to think of it as mapping the unit segment to the integer of the number of segments a vertical segment through that point would intersect, with the total integral being 9. (Well, actually that's not what I prefer to think of it as. That's just what you get if you turn the handwavy idea of "every point the horizontal projections have length density less than 9, there must be some other point whose horrizontal projections have length density greater than 9 -- and length densities must be integral" in my brain into rigorous math. And what's in quotation marks isn't really what I'm thinking -- thought are rarely easily articulable.)

Hmm.  I would say that overlapping counts as intersecting, but of course that is a subjective matter.

Anyway, I don't "trust" expected value too much either.  Your process sounds kind of like what I did: There are finitely many segments, so projecting them onto the x-axis defines a partition of the interval $ [0, 1]$.  Clearly no subinterval can contain parts of ten or more different segments, so they all have to contain parts of exactly nine segments.  The PDF I attached a while ago has a diagram for this, but it also contains a very long process that was not necessary at all, since the only necessary cases in that proof were $ \phi \equal{} 0$ and $ \phi \equal{} \pi/2$.


Which did you think was the hardest problem? I thought #1 was the hardest, but maybe that's because I got it wrong and I wrote 4 pages on my solution to it..  :|

I agree.  I blew through #2 to #5, but #1 was insane!  I'm still not sure if my solution works...

Same here, because it was the only problem that I got incorrect. :oops:

I thought 4 took the longest (maybe because I did it last, considering its length :D )

Again, #4 was the hardest for me. And again, I'll probably get a 24, because I forgot the 0 case on number 4. :roll: Hopefully, they won't deduct for that.

#4 was the hardest for me, if "hardest" is defined as "the last one i solved and i didn't really like the question at all".  well, it's not that there was anything especially hard about the question, but i just had trouble figuring out how to approach it.

i liked #5 the most, just because i like questions with weirdly-defined functions.

I thought that 2 was the hardest because I didn't get it, but I think that 5 was probably the hardest, and best.

#3 took me forever, but only because I didn't see the elipse, I solved it using trig equations and tons of substitutions.  No wonder it took four pages.

Number one was the hardest for me because I suck at that kind of stuff.  I just never feel sure of myself.

I thought number 4 was almost too easy; I kept checking it to make sure my super-simple solution was actually currect, but I ended up getting it right anyway.

#1, because I misread it and thought you were coloring the vertices, not the edges!

#4 was also pretty hard.

Wow, #3 wasn't hard?

Never for the many days when I worked on #3 have I thought of an ellipse. In fact, I don't know anything about foci so I have to thank USAMTS for cueing that to me.

Wow :rotfl: . I thought 1 and 4 were the easiest ones, and they're ranked the hardest.

Yeah... I didn't even start #4 until the day before the deadline, and it didn't take me more than 25 minutes.

I suppose number 4.  I solved the other problems very quickly, but with number 4 nothing was coming to me, so I had to force myself to sit down and reason it out.  There were no difficult steps, but it was tedious.


$x=y^{6}$ give only one positive root $y=3$, therefore $x=3^{6}.$.


[quote="espark52"]integers a,b,c,and d are positive perfect squares, and $a+b=c+d$ and $a<c<b$. wat's the least possible value of b?[/quote]
[hide]
If we write down all the squares from 1 to 100, we have

1 4 9 16 25 36 49 64 81 100

What we're looking for is a difference between 2 squares repeated.

After some quick searching, we see that 49-25 = 24 and 25 - 1 = 24. So a + b = c + d becomes 1 + 49 = 25 + 25

a is 1, b is 49, c is 25. So our answer is 49.[/hide]

[hide]
After some guess and check:
25+25=50
and 49+1=50
So, the answer is 49.[/hide]

Is there another solution?It seems like a problem which can only be solved using yucky guess and check.I remember suffering with it during the school round this year...

[quote="easyas3.14159..."]Is there another solution?[/quote]

The numbers representible as a sum of two squares is a very important set to consider in number theory.  It's [b]very closely related[/b] to the set of possible hypotenuses of integer right triangles.  (You can figure out the connection for yourself ;) )

In any case, the thing to realize here is that $a+b = c+d$ is a number representible as a sum of two squares in [b]two different ways.[/b]  Now, either you've memorized from experience that $50$ is the smallest such number, in which case this problem is trivial (:P) or you use this amazing fact, which I will not prove:

[b]Claim:[/b]  Every number representible as a sum of two squares in two ways is a product of two numbers expressible as a sum of two squares in one way.

Equivalently, this amazing algebraic identity:

$(a^{2}+b^{2})(c^{2}+d^{2}) = (ac \pm bd)^{2}+(ad \mp bc)^{2}$

There is [b]very little[/b] guessing you need to do to arrive at the answer of

$50 = (1^{2}+2^{2})(1^{2}+3^{2}) = (1 \cdot 1+2 \cdot 3)^{2}+(1 \cdot 3-2 \cdot 1)^{2}= (1 \cdot 1-2 \cdot 3)^{2}+(1 \cdot 3+2 \cdot 1)^{2}$

:)

[quote="espark52"]integers a,b,c,and d are positive perfect squares, and $a+b=c+d$ and $a<c<b$. wat's the least possible value of b?[/quote]

[hide]
Both $c$ and $d$ are $25$, $a$ is $1$, and $d$ is $49$. The problem does not state that the numbers have to be distinct. Also, $a<c<b$, because $1<25<49$. Therefore, the smallest value for $b$ is $49$.[/hide]

[size=75][color=darkred]Please try not to type text in LaTeX when it is possible to just use regular text. Thanks.
-nebula42[/color][/size]