If $ x\in \mathbb {N}$, and

the product of all digits of $ x \equal{} x^2\minus{}10x\minus{}22$ , then $ x\equal{}?$

Similar to [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?t=278554]this Question[/url]

[hide="I think"] [b]answer should be 12 [/b] [/hide]

[quote="PKMathew"]If $ x\in \mathbb {N}$, and

the product of all digits of $ x = x^2 - 10x - 22$ , then $ x = ?$[/quote]

[hide]
Let ${ x = \overline{x_nx_{n - 1}\cdots x_0}}$

the product of all $ x$'s digits $ c = x_nx_{n - 1}\cdots x_0$

$ x - c = (10^nx_n + 10^{n - 1}x_{n - 1} + \cdots + 10x_1 + x_0) - x_nx_{n - 1}\cdots x_0$

$ = x_n(10^n - x_{n - 1}x_{n - 2}\cdots x_0) + 10^{n - 1}x_{n - 1}\cdots + 10x_1 + x_0$

Since $ 0\le \forall x_i\le 9$ then $ 10^n - x_{n - 1}x_{n - 2}\cdots x_0 > 0$

$ \therefore c < x$

Let $ x^2 - 10x - 22 = c$

Then $ x^2 - 10x - (22 + c) = 0$

$ \implies x = {10 \pm \sqrt {10^2 + 4(22 + c) }\over 2}$

$ \implies x = 5 + \sqrt {47 + c}$ only.

Since $ x,c \in \mathbb{N}$ and $ x > c$

$ \therefore$ the suitable solutions to $ (x,c) = (12,2)$ only.
[/hide]

The max of the product of the digits of x is $ 9^{log x\plus{}1}$, but $ x^2\minus{}10x\minus{}22>9^{log x\plus{}1}$ for $ x>16$


integration
calculus
algebra
partial fractions
real analysis
real analysis unsolved

Hi there, I am trying to solve the following for T(t), however the 4th power is throwing me off:

A* dT(t)/dt= -B*T(t)^4 +C

Any help would be much appreciated! Thank you :)

Treat it as separable: $\frac{dT}{C-BT^4}=dt$, so $t=\int\frac1{C-BT^4}\, dT$
There is no guarantee that you will be able to find a reasonable expression for $T$ in terms of $t$, but you do have a good inverse.

The integration will require partial fractions expansion, and the roots aren't nice.


Twelve students are to be divided among Mr. Mirus's and Ms. Batty's classes. No teacher is to have more than 8 students. How many different groups of students could be in Mr. Mirus's class?

http://www.artofproblemsolving.com/Forum/viewtopic.php?t=213384&sid=dbff8a19a10cc304553cf52bac31001f  says 5
i put 5, when reviewing says 4422

and don't lock/delete this thread either please.

Personally, I got 3498 as my answer. This was my reasoning:

Since each teacher can have no more than 8 students, Mr. Mirus can have no more than 8 and no less than 4. So, Mr. Mirus must have 4, 5, 6, 7, or 8 students. Each of these can be determined by:

$ \binom{12}{8}$ for 8 students
$ \binom{12}{7}$ for 7 students
$ \binom{12}{6}$ for 6 students
$ \binom{12}{5}$ for 5 students
$ \binom{12}{4}$ for 4 students

So, the answer would be:

$ \binom{12}{8}$ + $ \binom{12}{7}$ + $ \binom{12}{6}$ + $ \binom{12}{5}$ + $ \binom{12}{4}$

which is:

$ 495 \plus{} 792 \plus{} 924 \plus{} 792 \plus{} 495$
$ \equal{} \fbox{3498}$

I can only determine that there is an error in the answer provided by AoPS For the Win. I believe that the problem-solver added another $ 924$ to the answer, thus duplicating
$ \binom{12}{6}$
and getting $ 4422$ as his or her answer.  :lol: If anyone finds an error in my reasoning, please rectify it by PMing me and adding a post.  :D


inequalities
number theory unsolved
number theory

Show that an integer whose decimal represeentation is

a00...00b

where a and b are digits in the range 1,2,3,.....,9
and there is at least one zero, cannot be a perfect square

Some cases:

Case 1: $b=1, 4, 9$

Case 2: $b=2, 5, 6, 8$

Case 3: $b=3, 7$

The number is $10^na+b$, with $n$ at least $2$. Now in case 3, $10^na+b \equiv b \equiv 3 \mod{4}$, so it can't be a perfect square.

In case 2, if $b=2, 6$ then the number is divisible by $2$ but not $4$ so it's not a square. If $b=5$ it's divisible by $5$ but not $25$. If $b=8$ and $n \geq 4$ the number is divisible by $8$ but not $16$; so we can manually check the numbers with $n=2, n=3$ to see they aren't perfect squares.

Case 1 is left. Here we have $b=k^2$, so assume $10^na+b=m^2$. Then $10^na=2^n5^na=(m+k)(m-k)$. Now since $m+k, m-k$ differ by at most $6$ (because $k$ is at most $3$) we must have $5^n-6 \leq 2^na$, which leads to a contradiction for large $n$, and small cases can be done by hand.

Thanks for the help.
Just a few questions...

All perfect squares are 0 or 1mod4, thats where that comes from right?

The number is divisible by 2 but not 4, so it's not a perfect square. I don't follow. Same with 5, 25 and 8, 16.
Can you embellish slightly?

And would you say this is the only method to show?

[/code]

also, how do you get the inequality at the end.
The 2 terms multiplied, differ by at most 6. But how then have you got this inequality.

When you write a number as a product of prime powers, it's a square iff all the exponents are even. So there's no $k$ such that 5 divides $k^2$ but 25 doesn't, or such that 8 divides $k^2$ but 16 doesn't. For the inequality, note that since $k$ is 1, 2, or 3, if $m+k, m-k$ share a factor it also divides their difference $2k$; now $2k$ is not divisible by 5 so all the powers of 5 must belong to one factor. From there it's easy.


1)A particle P is moving on a circle under the action of only one force acting always towards fixed pt O .Find ratio of
[img]http://alt1.artofproblemsolving.com/Forum/latexrender/pictures/6/1/0/610ed516819795a0deb9587770443128996104c7.gif[/img]

I am not great at physics, but in 2) Why should we get different acclerations for the 2 blocks? After all, cant a string be considered a spring within elastic limits?

server error
which ratio do we hav to calculate in 1??
most likely ans is 1:2 or 2:1

2)well i'll think
after breaking the elastic force shud be different

ans to 1st -> 2 tan theta
2nd -> 25 : 24

@hell , i had thought quite the same :)

ok , first is done

in the second the answer has come some how , but the fact is i am not satisfied , so do try it out  :)

ive got the answer as 25:24 somehow but using my imaginary concepts! :(
could any of u all give me the correct solution i wanna see how close am i ?
 :P

[hide="My attempt"]
spring force don't change instantaneously but tension does change.
also since masses are same,we just need to find ratio of Resultant Forces in fig 1 and 2
so we need to find tension/spring force for each of situations

[b]Before string/spring was cut[/b]
we have $ 2F sin37\equal{}2g$        (for both 1 and 2)
so,$ F\equal{}\frac{5g}{3}$

[b]after cutting of spring/string[/b]
spring force will not change,but tension will change in fig 2
i can't infer what will be the new tension
probably question requires rotational mechanics
waiting for you all to answer :D
[/hide]

This is how the answer came

IN the second case , as soon as the string is cut ,
the box moves towards left like in a circular motion , so
it will have tangential acceleration -> g cos 37=4g/5

In the first case ,
before the spring is cut
->
2kx cos  53 = mg

Now , just after the spring is cut , the spring that is uncut
pulls the box towards itself with a force

kx = mg /[2 cos 53] = ma
hence
a = g/[2 cos 53] = 5g / 6

So the ratio is 24 : 25

[hide]Doubt -> where is the component of a due to g man !!??[/hide]

plz explain ur doubt again :(

the thing is that when we r putting
kx = ma,
a is the net acc that is produced by gravity and spring force :wink:

No , what i mean is that kx is what will pull the mass towards itself , but mg would also pull it downwards
(Uptil now total weight was balanced but mg is not balanced now no ?? )

as far as i know,
kx = ma ,is obtained when the block comes to rest
that means block will be pulled by gravity, fall down ,balanced by spring i.e. kx=ma
 :mad:
but then how can we take "x" same in both cases(before cutting and after) :(  :huh:

before going any further , are u talking about instantaneous acclerations only ?

[quote="slogger"]
Now , just after the spring is cut , the spring that is uncut
pulls the box towards itself with a force

kx = mg /[2 cos 53] = ma
hence
a = g/[2 cos 53] = 5g / 6
[/quote]
i ve understood ur doubt
and there's a speck in ur solution

a due to spring=5g/6  ....in the dir of string
a due to gravity=g.......downwards
angle betw them = $ (\theta \plus{} 90^0)$

applying vector addition
$ a_{net} \equal{} \sqrt {{\frac {5g}{6}}^2 \plus{} g^2 \plus{} 2(\frac {5g}{6})(g)cos(\theta \plus{} 90^0)}$
$ \theta \equal{} 37^0$
which give u a=5g/6 :D
so the answer remains same :P  :P


xirtamax wrote:The roots of x4 - x3 - x2 - 1 = 0 are a, b, c, d.
Find p(a) + p(b) + p(c) + p(d), where p(x) = x6 - x5 - x3 - x2 - x.

Explain you answers thoroughly.

[hide]

a6 - a5 - a2 = a2(a4 - a3 - 1) = a2*a2 = a4.

Thus, p(a) = a4 - a3 - a = a2 + a + 1.

So (p(a) + p(b) + p(c) + p(d)) is the sum of the zeros of (x4 - x3 - x2 - 1) plus the sum of their squares plus 4.  The sum of the roots is 1.  The sum of the roots taken two at a time is -1.  So the sum of their squares is 3.  So our answer is 8.[/hide]

JBL said:
[quote]
The sum of the roots taken two at a time is -1. So the sum of their squares is 3.
[/quote]

Could you explain that?

Yep, sorry.  We have (a + b + c + d) = 1, so if we square both sides, we get (a^2 + b^2 + c^2 + d^2) + 2(ab + ac + ad + bc + bd + cd) = 1.

We know that the second part of that is equal to 2*(-1).  So that gives us that the sum of the squares of the terms is 3.  We get the -1 from the coefficient of the polynomial.


analytic geometry
graphing lines
slope
calculus
integration

I will move it from Olympiad Section to Getting Started.

Of the equation of the line?
There are two ways you can do this:
$m$ is the slope of the line and $b$ is the y-intercept (where the line crosses the y axis)
$y = mx +b$
$y = -\frac{4}{7}x + b$
You can then substitute in the points you know to find b:
$-2 = -\frac{4}{7}(-1) + b$
$-2 = \frac{4}{7} + b$
$-\frac{18}{7} = b$
Substitue this back into the original equation:
$y = -\frac{4}{7}x - \frac{18}{7}$
Or
$y - (-2) = -\frac{4}{7}(x - (-1))$
$y + 2 = -\frac{4}{7}x - \frac{4}{7}$
$y = -\frac{4}{7}x - \frac{4}{7} - 2$
$y = -\frac{4}{7}x - \frac{18}{7}$

Snowstorm, standard form is actually:

Ax+By=C

The form you used is slope-intercept form.

oops it did say standard form didnt it
$\frac{4}{7}x + y =  -\frac{18}{7}$

Actaully, in standard form, you can't have fractions for the first or second coefficiant, so it would be $4x+7y = -18$.

[b]
Can you tell me what you learn at school?
Because my textbook tells me the standard equation is Ax+By+C=0 and therefore the answer is 4x+7y+18=0.[/b]

Standard form is Ax+By+C= 0. At least, that's what my dad and teachers have taught me.

Folks, there are infinitely many possible representations for a line in the form Ax + By + C = 0 -- just double all of A, B and C to get another representation.  If you're going to say, "require A, B and C to be integral," you'll have to decide what to do about the line $\sqrt2 x + \sqrt3 y + \sqrt5 = 0$.  There is no way you can make a requirement on A, B and C like that.

[quote]Hey guys,
I need help figuring out the breakdown to finding the standard form of...

Slope -4/7, through (-1, -2). Please explain so that I can get this in the future. Thanks!

-Erik[/quote]
  If slope is m and it goes through (x_1,y_1) then the standart form is y-y_1=m*(x-x_1)
for m=-4/7,(-1,-2) we have 7*y+4*x+18=0


[hide]If it's possible to derive one from the other, then they are the same.

$s=\frac{n}{n+1}$

$sn+s=n$

$sn-n=-s$

$n(s-1)=-s$

$n=\frac{-s}{s-1}$

Peter is wrong.[/hide]

Here is another way, the same answer, but a slightly different process:
[hide] Take the second equation and take the recipical of boths sides.  Therefore, $\frac{1}{n}=\frac{s-1}{s}\Rightarrow 1-\frac{1}{s}=\frac{1}{n}\Rightarrow 1-\frac{1}{n}=\frac{1}{s}\Rightarrow \frac{n-1}{n}=\frac{1}{s}$.  Taking the recipicals of boths sides again, we find that $s=\frac{n}{n-1}\ne\frac{n}{n+1}$. Therefore, the answer is no.  [/hide]

[quote="Interval"]Peter says that the following equations are two ways to write the SAME formula.  Decide whether or not you agree with Peter.  Explain how you made your decision.

s = n/(n + 1)  and  n = s/(s - 1)[/quote]

[hide]or you could let $n=1$ which means $s=\frac{1}{2}$ from te first equation.

when $s=\frac{1}{2}$, $n=-1$ so they arent equal.  [/hide]

[quote="Interval"]Peter says that the following equations are two ways to write the SAME formula.  Decide whether or not you agree with Peter.  Explain how you made your decision.

s = n/(n + 1)  and  n = s/(s - 1)[/quote]
solve for $n$ in the first equation. you will see that $n=\frac{s}{1-s}$, which is actually the opposite of the second equasion. therefore it is not the same.

Again, great replies and tips.  I am collecting notes for my June math state exam.

Thanks!


$ 15)$ If $ f(g(x)) \equal{} x$ and $ f(x) \equal{} \frac {x}{x \plus{} 1}$, find $ g(x)$.

The choices were x/x+1, -x/x+1, -1/x+1, x/1-x, and NOTA.

The choices confused me, so I really didn't know how to set it up to find the answer.

On my paper, I put $ x \equal{} \frac {x}{x \plus{} 1}$ and solved, and then didn't know what to do after.. or if even doing that step was part of the process.

$ \displaystyle f(g(x))\equal{}\frac{g(x)}{g(x)\plus{}1}\equal{}x\Rightarrow g(x)\equal{}xg(x)\plus{}x\Rightarrow g(x)\equal{}\frac{x}{1\minus{}x}$

He's saying $ f(x)$ and $ g(x)$ are inverses, so you find $ f^\minus{}1(x)$ to get $ g(x)$.  Do this by switching $ f(x)$'s with $ x$'s in the expression $ f(x)$ and solving for $ f(x)$.

$ f(g(x))$ just means for all x values you sub in $ g(x)$

so $ f((g(x)) = \alpha$ but after subbin in $ g(x)$ for $ x$ then $ f(g(x)) = \b$

equate the 2 expressions and make g(x) the subject.


Given a $3$ by $11$ rectangular array of dots, how many triangles can be formed whose vertices are dots in the array?

. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .

[hide="Very unsure"]There are 33 dots, so $\binom{33}3$ is the total number of possibilities.

There are also 506 possibilities that give a straight line.

So is it $5456-106=5350$???

[/hide]

Nope, sorry  :(

This was on one of my practice tests for team, and I'm not the one who did this problem. We got it correct, but I didn't know how they got it.

Is what I got even close to what the real answer is?  :(  :D

[hide="what I did..."]
There are $\binom{33}{3}$ potential triangles, since there are 33 points.  Then subtract $3\binom{11}{3}$ and $11\binom 3 3$ for the ways you can choose 3 in a row or column.  But you can have diagonals that cross.  There must be one vertex in each row, and must have an integer length from top to middle (in terms of columns), so the length from top to bottom points is even.  You can move such a diagonal across the columns $11 - n$ ways where $n$ is such a length.  You can also "flip" the diagonal across the axis of the middle row, doubling the amount.  Since the set of lengths is $(2,4,6,8,10)$, we have to subtract $2(9+7+5+3+1) = 50$.  Then the answer is $4900$.
[/hide]

[quote="ch1n353ch3s54a1l"][quote="Farenhajt"][hide="Idea"]One vertex can be in one row and two vertices in another row, or each vertex can be in its own row.

First case gives $3\cdot 2\cdot 11\cdot{11\choose 2}=3630$ (rows can be chosen in $3\cdot 2$ ways because the order matters, and the dots can be chosen in $11\cdot{11\choose 2}$ ways)

Second case gives $11^3-55=1276$ (we discount $55$ straight lines that spread across three rows)

Total $3630+1276=4906$

Is this correct?[/hide][/quote]

o.0
The answer's
[hide]$4900$  :huh: [/hide][/quote]

Oh, I miscounted the straight lines in Part 2 - there's $5\cdot(6+5)+6=61$ of them, so my answer should be $3630+11^3-61=4900$

[hide]
First you take the case where there is a vertex in each row.

In the one row there are $11$ positions for one vertex to be in.

In the second row there are $11$ positions for another vertex to be in.

In the third row there are only $10$ positions for the third vertex to be in, because the $11 th$ position would result in a straight line instead of a triangle.

This would yield $11 \times 11 \times 10$ or $1210$ triangles.

The second case would be where there are two vertices in one row and one in either
of the other two rows.

In the row that contains two vertices there are $_{11}C_2$ ways to place the them.

$_{11}C_2 = \frac{_{11}P_2}{2!} = 55$

For each of the other two rows there are $11$ possible positions to place the third vertex.

so for, say, the bottom row had two vertices in it then there would be $55$ different ways to place the vertices.

Then for each way there is in the bottom row to place the two vertices there are $11$ ways in the middle row and $11$ ways in the top row.

So if you would put the third vertex in the middle row then that would result in $55 \times 11$ or $605$ triangles.

Likewise, if you put the third vertex in the top row then that would also result in $605$ triangles.

Therefore if there were two vertices in the bottom row, that would produce $1210$ triangles.

Now take the cases where there are two vertices in the middle and top rows.

They would each produce $1210$ triangles.

So the total number of triangles possible would be $(4)(1210) = 4840$ triangles.

[/hide]

[quote="ch1n353ch3s54a1l"]I [i]guess[/i].

I don't think it's $\binom{33}{3}$. The triangles have lines in dimension $10\times2$ because there aren't length $11\times3$ lines, there are just $11\times3$ dots.

How did you get the number of lines? Did you just count?[/quote]

I got the number groups of dots that produce a line, so any 3 in the first row would, so thats $\binom{11}{3}$.  Since there are 3 rows, I multiplied that by 3.

Also, if you choose three dots in the same column, there will be a straight line, so that's 11.

Where did I miscount?  :?

The problem did not specify that degenerate triangles shouldn't be included.


Determine the number of ways ion which [b]x[/b] and [b]y[/b] can be selected from the set of the [b]first 25 natural numbers [/b]such that $x^{4}-y^{4}$  is divisible by 25.

[hide="Hint"] Calculate the fourth powers $\bmod 25$.  There should only be five of them. [/hide]

Hmm........for x^4-y^4 to be divisible by 25,x and y can be:
1)distinct multiples of 5.This gives 5*4=20 combinations
2)3 and 4,so 1 more to the tally.
3)Now no more non multiples of 5 are possible.........so  guess 21 is the answer


group theory
abstract algebra
logarithms
real analysis
real analysis unsolved

Prove or disprove:

The set $ S \equal{} \{ 2^a3^b | a,b \in Z, b \geq 0\}$ is dense in $ R^\plus{}$

It can be priven that a nontrivial subgroup of $ (\mathbb{R}, \plus{} )$ is either cyclic or it is dense in $ \mathbb{R}$.  Taking the logarithm of the elements of $ \{2^a3^b|a,b\in\mathbb{Z}\}$, we have $ L \equal{} \{a \plus{} b\log_23|a,b\in\mathbb{Z}\}.$  Since $ L < (\mathbb{R}, \plus{} )$ and it is not cyclic, then it is dense in $ \mathbb{R}$. $ \Box$

EDIT: I misread the question, and so I did not asnwer the original question.

Yes the problem here is that $ a$ cannot be negative...

Take logs, then the set $ \{[b\log_23] \,|\, b\in \mathbb{N} \}$ is dense in $ [0,1)$ by Kronecker's theorem since $ \log_23$ is irrational.
Now let $ \epsilon>0, x \in \mathbb{R}^\plus{}$ and take $ a,b$ such that $ |\log_2 x\minus{}(a\plus{}b\log_23)|< \epsilon \Longleftrightarrow 2^{a\minus{}\epsilon}3^b<x<2^{a\plus{}\epsilon}3^b$.
Now let $ \epsilon\to 0$.


[quote="risinglegend"]In each of the following, let x denote the unknown. Derive an equation involving x:
(a) When a certain number is increased by 7, the result is 18.
(b) When a number is decreased by 2 and the result multiplied by 3, the final result is 24.
(c) When 5 is subtracted from a certain number and the result multiplied by 7, the final result is 63.
(d) When a certain number is subtracted from 24 and the result divided by 5, the final result is 4.
(e) The sum of three consecutive numbers is 63.
(f) One number is bigger than the other number by 3 anmd the sum of those two numbers is 43.
(g) Six times of a certain number is 16 more than twice the number.
(h) The length of a rectangle is 5 metres more than its width and the perimeter of the rectangle is 32 metres.
(i) The length of a rectangle is twice its width and the perimeter is 54 metres.[/quote]

[hide]$x+7=18$

$3(x-2)=24$

$7(x-5)=63$

$\frac{24-x}{5}=4$

$x+x+1+x+2=63$

$x+x+3=43$

$6x=16+2x$

$2x+2(x+5)=32$

$2x+2(2x)=54$[/hide]

Now for another challenge. Someone solve all of the equations I put up!  :)

This reminds me of a pre-alg textbook...

Shouldn't this be in homework section?

[quote="magixter"]There's a homework section?[/quote]
http://www.artofproblemsolving.com/Forum/index.php?f=300[/quote]


abstract algebra
advanced fields
advanced fields unsolved

Is it true that the blow-up of $ \mathbb{P}^2$ at a point is  $ \mathbb{P}^{1}\times\mathbb{P}^{1}$?
Seems true when drawing a picture but weird.

It is true that the blow-up is a $ \mathbb P^1$ bundle over $ \mathbb P^1$, but it is not $ \mathbb P^1\times\mathbb P^1$

I'll think about good reasons.

Ok, if you know something about ruled surfaces, or intersection theory or are willing to do a little believing, then
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Fact 1: The diagonal in $ \mathbb P^1\times\mathbb P^1$ has self intersection 2.

Fact 2: All curves on the blow-up of $ \mathbb P^2$ at one point are linearly equivalent to $ aH \plus{} bE$ for some integers $ a,b$ (that depend on the curve), where $ H$ is the pullback of the hyperplane line bundle $ \mathcal O(1)$ on $ \mathbb P^2$ via the blow-up map and $ E$ is the exceptional divisor. We have the intersection relations $ H^2 \equal{} 1$, $ HE \equal{} 0$ and $ E^2 \equal{} \minus{} 1$.

If $ \mathbb P^1\times\mathbb P^1$ and the blow-up are isomorphic, then $ (aH \plus{} bE)^2 \equal{} 2$ for some integers $ a,b$. But $ (aH \plus{} bE)^2 \equal{} a^2 \minus{} b^2$ and the last is never 2: a square is 0 or 1 mod 4, thus the above difference has only the options 0,1 and -1=3. There is no 2.
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
If you know more about ruled surfaces, then $ \mathbb P^1\times\mathbb P^1 \equal{} \mathbb P(\mathcal O_{\mathbb P^1}^2)$ whereas the blow-up is $ \mathbb P(\mathcal O_{\mathbb P^1}\oplus\mathcal O_{\mathbb P^1}( \minus{} 1))$ and the corresponding ruled surfaces are isomorphic if and only if the rank two bundles $ \mathcal O^2$ and $ \mathcal O\oplus\mathcal O( \minus{} 1)$ differ by tensor product with a line bundle on $ \mathbb P^1$. But line bundles on the projective line are all of the form $ \mathcal O(m)$ for some $ m$. And it is not hard to prove that $ \mathcal O^2 \equal{} \mathcal O(m)\oplus\mathcal O(m \minus{} 1)$ is impossible (take global sections in this equality)
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
With less intersection theory. Assume that $ A \equal{} \mathbb P^1\times\mathbb P^1$ is isomorphic to B=($ \mathbb P^2$ blown-up at a point).
Let $ a,a'$ be some distinct lines on $ A$ of the form $ \mathbb P^1\times x$ and $ b,b'$ be distinct lines of the form $ y\times\mathbb P^1$.
$ a,a'$ don't meet, so their images in $ B$ both intersect the exceptional divisor of the blow-up. That is because otherwise they project to non-intersecting curves on $ \mathbb P^2$ via the blow-up map and this doesn't happen. Similarly for $ b,b'$.

But then the four lines $ a,a',b,b'$ project to 4 distinct curves through the point $ t$ that was blown-up.
It is obvious but not extremely obvious that these four curves are actually lines and then because the blow-up separates tangent directions through $ t$, the lines $ a,a',b,b'$ should have been disjoint, but it is clear that $ a$ cuts $ b$ and $ b'$.
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------
I think that for all line bundles on the blow-up, one can show that $ H^1$ is 0, whereas $ \pi_1^*(\mathcal O)\otimes\pi_2^*(\mathcal O( \minus{} 2))$ should have nonzero $ H^1$ by Kunneth, where $ \pi_i$ are the projection maps $ \mathbb P^1\times\mathbb P^1\to\mathbb P^1$.

Note that you can't distinguish the surfaces by their motive.


Valentin,
in this thread ([url=http://www.mathlinks.ro/Forum/viewtopic.php?t=22978]www.mathlinks.ro/Forum/viewtopic.php?t=22978[/url]), you suggest searching for problems on this site before posting.  But I have found that this is not easy.

For example, variables can change, and phrasing can change.  And currently, formulas in LaTeX can't be searched, though you once mentioned that you are working on this.  Even when I want to find a problem that I know was posted here, if I don't remember the exact statement, it can be hard to track it down again.  Do you have any concrete suggestions for searching?

[quote="RC-7th"][quote="Valentin Vornicu"]In that thread I was referring searching (for now) for well known problems which have names (as Beatty sequences, ISL problems, etc.) or you know the Olympiad and year when the problem was proposed.

We are continuously developing our site for better use for our users, but we are now putting an emphasis on security of data, so any other *cosmetical* upgrades will take place much slower (although they do happen, as you could see with the newer collapsible cats :D).[/quote]

I once commented on how the site lacked encryption, and you replied with something along the lines of "it doesn't matter". How come there's an emphasis on security now?[/quote]There are two different issues here security and encryption of data. The site (AoPS part) is encrypted where it needs to be.

On the Forum part, because it is a public service, needs no encryption of the data (it is seen afterwards anyway!). However we need more security to prevent temporar inoperability of the site due to different matters, and also to protect user data (such as email adrress or location), which is available to the rest of the users, from spambots, worms and other such threats that propagate using public forums.


Solve the inequation: \[3^{x^{2}-4}+\left(x^{2}-4\right)\cdot 3^{x-2}\ge 1\]


The attached diagram will help to define square-circle tiles.

Suppose we have 9 circles with radius 1 arranged on the $xy$-plane.  Call the circles $C_{(x,y)}$, where $x,y\in\{-1,0,1\}$ ($x$ and $y$ are not necessarily distinct), and $(x,y)$ is the center of circle $C_{(x,y)}$.  The center of the yellow circle, $C_{(0,0)}$, is at $(0,0)$.

Square-circle tiles are tiles that can form circles with radius 1 (like the yellow circle) and squares with side 1 (like the square with dark lines, vertices $(0,0),(1,0),(1,-1),(0,-1)$).  There are three different kinds of tiles.  Call them "bloated squares" (there are four in a circle and one in a square), "half diamonds" (there are eight in a circle and four in a square), and "arrowhead triangles" (there are 12 in a circle and four in a square).  All three of them shown in the yellow circle, $C_{(0,0)}$.

Compute the area of each of the three square-circle tiles.

I hope this problem is clear enough.

[hide]Call the area of each bloated square $b,$ the area of each half diamond $d,$ and the area of each arrowhead triangle $a.$

It can easily be shown that the intersection of two semicircles is $\frac{x^{2}\left(2\pi-3\sqrt{3}\right)}{6}.$ This means $2a+b+d=\frac{2\pi-3\sqrt{3}}{6},$ or $12a+6b+6d=2\pi-3\sqrt{3}.$

The area of a square is $x^{2},$ so $4a+b+4d=1.$

The area of a circle is $\pi r^{2},$ so $12a+4b+8d=\pi.$

Now we have 3 equations and 3 variables to solve for, but $b$ always comes out negative. :([/hide]

Well, I guess you did something wrong.
[hide="My First Step"]Find the area of the square without one half-diamond.[/hide]

[hide]The intersection of two semicircles is supposed to be ${x^{2}\left(4\pi-3\sqrt{3}\right)\over6},$ not what I said before. Now the system can be solved.[/hide]


function
induction
vector
group theory
abstract algebra
superior algebra
superior algebra unsolved

Hi all,

A stupid question ... define the multiplicative function $g(n)$ by $g(p^k) := (p^k-1)(p^k-p) \cdots (p^k-p^{k-1})$ on the prime powers (and distribute it multiplicatively on the positive integers). If $G$ is a finite group of order $n$, is it necessarily true that $|\mathrm{Aut} \, G|$ is a divisor $g(n)$? Probably I'm missing something very obvious, but somehow I got stuck on this right now :( ... I'll return thinking on that later, but will appreciate any help in the meantime. Is that what I'm trying to prove true at all?  :?

Thanks!  :)

Nevermind, I figured it out myself. The assertion is true for finite $p$-groups, but false in general (for example, it fails even for $S_3$, of course -- silly me :blush:). However, what is important to me, the prime divisors of $|\mathrm{Aut} \, G|$ are always a subset of those of $g(n)$ -- that is what I actually needed!   :D

[quote="vess"]the prime divisors of $|\mathrm{Aut} \, G|$ are always a subset of those of $g(n)$[/quote]

I think I can prove that every prime dividing $|\mathrm{Aut} \, G|$ also divides $|G|\cdot g(|G|)$ for soluble groups $G$, and this suffices for [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?highlight=groups++order&t=47371]this other problem of yours[/url], so I'm posting it :).

We can prove the assertion by induction on the order of the soluble group $G$. It's obviously true for finite-dimensional vector spaces over $\mathbb Z_p$ for prime $p$ (so we can assume that $G$ is not of this form), and all other soluble groups have non-trivial proper characteristic subgroups (there is a characterization of finite groups with no characteristic subgroups: they must be direct products of several copies of the same simple group). Let $H$ be such a subgroup of $G$, and let $f$ be an automorphism of $G$ of prime order $p$.

If $f$ does not fix $H$ pointwisely, then we can regard it as an automorphism of $H$ of prime order, and the conclusion follows by the induction hypothesis. We may thus assume that $H$ is fixed pointwisely. Now, since $H$ is fixed, $f$ induces an obvious automorphism $\bar f$ of $G/H$. If it's not trivial, then again, the conclusion follows by the induction hypothesis. We can thus also assume that $\bar f$ is trivial. This means that $t_x=x^{-1}f(x)\in H,\ \forall x\in G$. Now let $x$ be any element of $G$ not fixed by $f$. We have $t_x\cdot f(t_x)\cdot f^{(2)}(t_x)\cdot\ldots\cdot f^{(p-1)}(x)=x^{-1}\cdot f^{(p)}(x)=x^{-1}\cdot x=1$. On the other hand, we have $f(t_x)=t_x$, since $t_x\in H$ and $H$ is fixed pointwisely. This means that $t_x^p=t_x\cdot f(t_x)\cdot f^{(2)}(t_x)\cdot\ldots\cdot f^{(p-1)}(x)=1$, and, since $t_x\ne 1$, $p$ is the order of $t_x$, an element of $G$, so $p\ |\ |G|$.


abstract algebra
Galois Theory
superior algebra
superior algebra solved

Prove that G/N  is Abelian if and only if aba^-1b^-1 is an element of N for all a, b in G. (sorry for the notational trouble...basically if ab(a inverse)(b inverse) is an element of N.)

$G/N$ is abelian, iff
$(Na)(Nb) = (Nb)(Na)$ for all $a,b \in G$, iff
$N(aba^{-1}b^{-1}) = N$ for all $a,b \in G$, iff
$aba^{-1}b^{-1} \in N$ for all $a,b \in G$

that is a fundamental property of derived groups [url]http://en.wikipedia.org/wiki/Derived_group[/url]
when you ever study galois theory you'll need it

if you wanna make the nice notations,write this between dollar signs : a^{-1} b^{-1}a b

then you will get : $a^{-1}b^{-1} a b$


The scientists in a laboratory company raise amebas to sell to schoolsfor use in biology classes. They know that one ameba divides into twoamebas every hour and that the formula t = log_2 N can be used todetermine how long in hours, t, it takes to produce a certain numberof amebas, N. Determine, to the nearest tenth of an hour, how long it takes to produce 10,000 amebas if they start with one ameba.

um again this seems like homework.

Plugging in values $\log_{2}10000=\frac{\log 2}{\log 10000}$. Use calculator to find

For all who plan to read this reply, I am NOT posting homework questions.  I am NOT in high school.  I have not been in high school in over 20 years.  I am studying math on my own preparing for a state test.  Got it?


If a < b, show that a < (a + b)/2 < b.  The number (a + b)/2 is called the ARITHMETIC MEAN of a and b.

..

[hide]Left side of the inequality..

$a<\frac{a+b}{2}$
$2a<a+b$
$a<b$

By definition this is true

Right side of the inequalty

$\frac{a+b}{2}<b$
$a+b<2b$
$a<b$

By definition this is true

Therefore the inequality $a<\frac{a+b}{2}<b$ holds when $a<b$[/hide]

This is also a duplicate post by you. Did you realize that they were the same question but different titles?

I'll take your word for it and lock this one.


algebra
polynomial
topology
geometry
analytic geometry
search
superior algebra

Please explain me what does it mean: point $ (u,v)$ is a generic point of the curve $ C$ given by $ p(x,y)\equal{}0$. Also help to understand this phrase: "Thus each irreducible component projects generically onto $ C$". What does it mean "projexcs generically"? And one more question: what does it mean that two curves $ C_1($given by $ p(x,y)\equal{}0)$ and $ C_2($ given by $ q(x,y)\equal{}0)$ have a common irreducible component?

The third question I can answer:  two curves have a common irreducible component if there exists an irreducible polynomial $ r(x, y)$ such that $ r | p, r | q$.  Hence the graphs of $ p(x, y) \equal{} 0$ and $ q(x, y) \equal{} 0$ both contain the graph of $ r(x, y) \equal{} 0$.

Edit:  According to [url=http://en.wikipedia.org/wiki/Generic_point]Wikipedia[/url], a generic point $ (u, v)$ has the property that its Zariski closure is the entire curve $ C$, or something along those lines.  Are you familiar with the Zariski topology?

[quote="puuhikki"]Generic point is introduced in Liu's book:

Let $ x,y$ be points of a topological space  $ X$. We say that $ y$ is a specialization of $ x$ or that $ x$ specializes to $ y$ if $ y\in \overline{\{x\}}$, the closure of $ \{x\}$. We say that $ x\in X$ is a generic point of $ X$ if $ x$ is the unique point of $ X$ that specializes to $ x$.[/quote]
Thanks for the answer, but can you explain me what does it mean in the terminology of the curves?

I'm not a specialist of an algebraic geometry but I guess you can replace "topological space $ X$" by "curve $ C$" and "$ X$" by "$ C$" in the definition. And project generically is explained in http://www.msri.org/publications/books/Book39/files/zoe.pdf But maybe you are looking something else as Chatzidakis uses some model theory in his paper.

If a curve $ C$ is given by $ p(x,y)\equal{}0$, there are usually two fields involved: a small field $ k$ over which $ p$ is defined (e.g. $ k\equal{}\mathbb{Q}$), and a large field $ K$, usually algebraically closed, such that the curve consists of points whose coordinates are in $ K$ (e.g $ K\equal{}\mathbb{C}$). It is always extremely important to keep those fields in mind. The curve defined by $ X^2\plus{}Y^2\equal{}\minus{}1$ is empty in $ \mathbb{Q}^2$ or $ \mathbb{R}^2$, but has lots of points in $ \mathbb{C}^2$.

If $ C \subset K^2$ is a plane curve defined by a polynomial $ p(x,y)\equal{}0$ were $ p \in k[x,y]$ is a polynomial defined over $ k$, then a $ k$-generic point of $ C$ is a point $ A \equal{} (u,v) \in K^2$ such that every polynomial $ q \in k[x,y]$ which vanishes at $ A$ vanishes on all of $ C$. In other words, the Zariski closure of $ A$ is $ C$.

For example, consider the curve $ C$ defined by $ y\minus{}x^2\equal{}0$ in $ \mathbb{R}$. A $ \mathbb{Q}$-generic point is, for example, the point $ A\equal{}(\pi, \pi^2) \in \mathbb{R}^2$ since any polynomial $ q$ [i]with rational coefficients[/i] which satisfies $ q(\pi,\pi^2)\equal{}0$ must actually vanish at every point of the form $ (z,z^2)$, or in other words it must be divisible by $ y\minus{}x^2$.

Of course this is no longer true if we switch the base field to also be $ k\equal{}\mathbb{R}$, since then for example the polynomial $ q\equal{}x\minus{}\pi$ vanishes at $ A$ but doesn't vanish on $ C$. It is always important to keep the fields in mind.

|Randomgraph, thank you very much for a very useful answer. I have another question: what does it mean that $ u$ and $ v$ are interalgebraic?

A quick Google search for "interalgebraic" brings up some papers related to model-theoretic aspects of field theory, but I've never encountered the term - sorry.

I think you are asking possibly if they are algebraicly dependent or independent?


algorithm
algebra
polynomial
quadratics
blogs
Rational Root Theorem
system of equations

Does anyone have any algorithms or methods to factor? I have no idea where to start. For example, how would one factor $ 6x^4\plus{}23x^3\plus{}27x^2\plus{}13x\plus{}6$. Yes, I know the answer (having made it up), but how would you do this? What do you look for and what are the steps? Thank you for helping me with this! :lol:

[i]General[/i] polynomial factoring over the integers is not that easy.  Some good techniques are outlined [url=http://en.wikipedia.org/wiki/Polynomial_factorization#Practical_techniques]here[/url].  On the other hand, "contest" polynomials can usually be handled fine by [url=http://en.wikipedia.org/wiki/Rational_root_theorem]the rational root theorem[/url] and/or observations about symmetry.

Edit:  Perhaps a demonstration is in order.

[hide="With just RRT"] The possible rational roots are of the form $ \minus{} \frac {\text{Divisor of 6}}{\text{Other divisor of 6}}$.  (Clearly no positive roots are possible).  $ \minus{} 2$ works; we get the factorization

$ (x \plus{} 2)(6x^3 \plus{} 11x^2 \plus{} 5x \plus{} 3)$.

$ \minus{} \frac {3}{2}$ also works; we get the factorization

$ (x \plus{} 2)(2x \plus{} 3)(3x^2 \plus{} x \plus{} 1)$.

Deciding whether a quadratic polynomial factors over the integers is straightforward: it happens if and only if the discriminant is a square.  Here it is negative.  (This leads to the alternate very straightforward characterization:  $ ax^2 \plus{} bx \plus{} c$ factors over the integers if and only if $ x^2 \plus{} bx \plus{} ac$ does.  This can be more useful for small examples if you are familiar with a lot of factorable quadratics.) [/hide]
RRT works on "contest" polynomials because it makes detecting linear factors easy and "contest" polynomials tend to be built up from linear factors.  On the other hand, if a fourth-degree polynomial factors into two irreducible quadratics (for example), RRT is useless.  One must then resort to either setting up the relevant system of equations or applying the finite-field method (which I am not sure is appropriate for this forum).

shouldnt it be
(x+2)(2x+3)(3x^2+x+1) instead of (3x^2 +2x+2) at the end?

:oops: I seem to have forgotten how to divide by $ 2$.

t0rajir0u, considering the extensive work of your blogs, you don't need to know how :P


Here's a solution.

[hide]Begin by finding convenient values for x.
$x=16$ looks good:
\[0=240p(16) \Rightarrow p(16)=0\]
Now trying $x=1$,
\[(-15)p(2)=0 \Rightarrow p(2)=0\]
This infers that $(x-2)(x-16)$ is a factor of $p(x)$.
Then solve for the general $p(x)=f(x)(x-2)(x-16)$
\[(x-16)(2x-16)(2x-2)f(2x)=16(x-1)(x-2)(x-16)f(x)\]
\[(x-8)f(2x)=4(x-2)f(x)\]
Now try $x=8$, which gives $f(8)=0$ and $x=2$, so $f(4)=0$.
Again f(x) must have linear factors $(x-4)(x-8)$, so we can say $f(x)=h(x)(x-4)(x-8)$
So in the equation above
\[(x-8)h(2x)(2x-4)(2x-8)=4(x-2)h(x)(x-4)(x-8)\]
\[h(2x)=h(x)\]
Since this gives infinitely many equal values of the function $h(x)$, it can be defined as a constant $c$.
Therefore \[p(x)=c(x-2)(x-4)(x-8)(x-16)\]
That was cool![/hide]


Here's the question, can anyone help me ? thx in advance!

[img]http://img213.echo.cx/img213/4813/56xd.jpg[/img]

These are standart theorems belonging rather to analysis than to algebra.


Answer: $\left(\frac{389}{401}\right)^{10}>\frac58.$
We have $\frac{389}{401}>\frac{385}{400}=\frac{77}{80},$ hence it suffices to prove that $\left(\frac{77}{80}\right)^{10}>\frac{50}{80},$ that is, $77^{10}>50\cdot 80^9.$
This follows from the AM-GM inequality applied to the numbers $50, 80,80,\ldots ,80$ (9 times $80$) since $\frac{50+9\cdot 80}{10}=77>\sqrt[10]{50\cdot 80^9}.$


function
number theory open
number theory

The following problem is an old conclusion and there are some its solutions. Please send to me!
The function $ x^2 \plus{} y^2 \equal{} 2p$( with $ p$ is a prime and $ p \equal{} a^2 \plus{} b^2$, $ a, b$ are two primes, $ a > b$) have only positive integer roots $ (x,y) \equal{} (a \plus{} b,a \minus{} b),(a \minus{} b,a \plus{} b)$.

Locked, see http://www.mathlinks.ro/Forum/viewtopic.php?t=170553 .


[quote="zhu rh"]a,b,c,d are positive real numbers and a+b+c+d=4 ,then find out the minimum value of (1) ∑a^2+(abcd)^5(2) (∑a^2)^(0.5)+(abcd)^5[/quote]
Do you mean?:
if we know $ a\plus{}b\plus{}c\plus{}d\equal{}4$,then find out the minimum value of
1)$ \sum a^{2}\plus{}(abcd)^{5}$
2)$ \sqrt{\sum a^{2}}\plus{}(abcd)^{5}$

I think this is quite a good and hard problem,can anyone help?


advanced fields
advanced fields unsolved

Let $ f : S^{1}\to S^{1}$ be an $ m$-degree cover. Prove that $ f$ is conjugate to the map $ E_{m}: R/Z\to R/Z$, $ x\to mx$(mod 1) .

It is a special case of fundamental theorem of Hopf, which says two maps with the same degree are conjugate.


calculus
integration
derivative
quadratics
calculus computations

How would you approch this integral?

$\int_1^3x\ln(x)dx$

I rewrote it as we can't evaluate $\ln(x)$

$\int_1^3x\ln(x)\cdot 1dx$

Then i ignored $x$ and concentrated on $\ln(x)\cdot 1$.

$\int_1^3xdx\cdot [\ln(x)\cdot x]_1^3-\int_1^3\frac{1}{x}\cdot x$

When i was done working with that part, i had this left

$1,30\cdot \int_1^3xdx$

And my result:

$\int_1^3x\ln(x)dx=2,59$

I have a feeling there is something fundamental i have misunderstood in this integration by parts. I have tried looking at what Xevarion told me about integration by parts in another post, but that didn't help me - maybe i misunderstood something there :(

It is right to try to eliminate the $\ln(x)$. Make sure you write out all of your steps in detail; then it is easier to see where there is a mistake (if you make one).

We take $u = \ln(x)$ and $dv = xdx$, so $v = \frac{x^2}{2}$ and $du = \frac{1}{x}dx$.

Integration by parts says

 $\int_a^b udv = \left[uv\right]_a^b - \int_a^b vdu$

In this case we have

$\int_1^3 x\ln(x)dx = \left[\frac{x^2}{2}\ln(x)\right]_1^3 - \int_1^3 \frac{x^2}{2}\frac{1}{x}dx$

which is just

$[\frac{9}{2}\ln(3) - 0] - [\frac{9}{4} - \frac{1}{4}] = \frac{9}{2}\ln(3) - 2 \approx 2.944$

unless I've made some mistake in calculations.

edit: Actually, t seems to me that you tried to do two parts of the integrand separately. The idea isn't to do that, it's to integrate one part and do the derivative of the other part at the same time, not integrate one part and then the other. Make sure you write out your steps carefully, and see what you've chosen for $u$ and $dv$. Always $udv$ should be equal to $f(x)dx$ (where $f(x)$ is the integrand).

I hope this helps  :)

Sometimes i would ask for a better textbook. When it makes an example on how to work with the formulas it only show a pretty simple task while we are left with the hard ones :D In Denmark we say $F'=f$ and $G'=g$ instead of $u$ and $v$, so our formula is like this:

$\int_a^bf(x)\cdot g(x)dx=[f(x)\cdot g(x)]_a^b-\int_a^bf'(x)\cdot G(x)dx$

But basically it should be the same - however, i might sometimes get a little confused looking at the ameircan system :)

So i see what my problem was here. I choose $v=\ln(x)$ and $u=x$, but now i can see how much easier it is doing it the other way around with $u=\ln(x)$ and $v=x$. However, i think i still might have a problem.

How do you go on with this part of the integration from here?

$\int_1^3 \frac{x^2}{2}\cdot \frac{1}{x}dx$

Could you help me going on from here, plz. Thx so far though.

Just do a bit of algebra. That's $\frac x2$ inside the integral.

Oh my, it must be the time of the day. Just forgot i was allowed to do this, but thx for your help to both of you. I've got the same result now.

However i've got yet another problem (believe it or not). This is an equation i need to solve, but i don't know where to start on this one. Never seen an equation with integrals.

$\int_1^x(t+4)dt=1$

Don't worry about it. Just integrate the integral on the LHS the way you'd do any definite integral, and plug in the bounds. Then you'll have a nice quadratic in $x$, which is easy to solve.

Oh, yes, that was pretty simple. Only problem here was to recall how to find the roots of a polynomium (as the following task was a third degree integral equation) :) But no bigger problems with these two tasks. Thx for your help.


function
integration
inequalities
calculus
derivative
trigonometry
real analysis

Find the Fourier serie of the function on the interval:
\[ f(x)\equal{}1\minus{}\mid x \mid\] \[ \minus{}2 \leq x \leq 2\]

Which part do you need help with?  Computing the coefficients?
You know that
$ c_{n}\equal{}\frac{1}{2\pi}\int_{\minus{}\pi}^{\pi}F(t)e^{\minus{}int}\ dt$
So we have
$ c_{n}\equal{}\frac{1}{2\pi}\int_{\minus{}\pi}^{\pi}e^{\minus{}int}\ dt\minus{}\frac{1}{2\pi}\int_{\minus{}\pi}^{\pi}\left|t\right|e^{\minus{}int}\ dt$.
Now just evaluate $ c_{n}$ and you have your series.

tanx for your help.actually this problem was the begining,i just wanted to know who is interested in Fourier series,so i can trade problems,ideas and ... with him.
anyway i will send more problem,more defficult problems and i will be glad if you share your opinion and solution!! :lol:

To start with: the function jensen described is periodic of period $ 4,$ not $ 2\pi.$ JRav has his formulas stuck on periodic of period $ 2\pi.$

For a function of period $ P,$ we have the following:

$ F(t)\equal{}\sum_{k\equal{}\minus{}\infty}^{\infty}\widehat{f}(k)e^{2\pi ikx/P}$ where $ \widehat{f}(k)\equal{}\frac1P\int_a^{a\plus{}P}f(x)e^{\minus{}2\pi ikx/P}\,dx.$

The $ a$ in the above expression will be chosen for convenience.

(Also, behind the too-bold equal signs above lie two centuries of theorems about what you can and can't say about convergence under what conditions - for the moment, I'm assuming that we have nice enough functions for things to work.)

As for actually computing these, I often ask whether the function itself or one of its derivatives is easier to deal with. We do have the formula that $ \widehat{f'}(k)\equal{}\frac{2\pi ik}{P}\widehat{f}(k).$

The function described above, $ f(x)\equal{}1\minus{}|x|$ on $ [\minus{}2,2],$ continued to be periodic of period $ 4,$ is a continuous "zig-zag wave." It's clear from the appearance of the graph that $ f$ has mean value zero, so $ \widehat{f}(0)\equal{}0.$ Now take its derivative:
\[ f'(x)\equal{}\begin{cases}1,&0<x<2\\ \minus{}1,&\minus{}2<x<0\end{cases}\]
(It doesn't matter that the classical derivative doesn't exist everywhere, as long as we can recover $ f$ by integrating $ f'.$)

Now, find the Fourier coefficients of $ f',$ which is an easier task than finding those for $ f$ directly.

For my own sake, I'm going to carry the process one step further, stepping into the world of "weak" or "distributional" derivatives: $ f''(x)\equal{}\minus{}2\delta(x)\plus{}2\delta(x\minus{}2).$

$ \widehat{f''}(k)\equal{}\frac{1}{P}\int_{\minus{}1}^3 (\minus{}2\delta(x)\plus{}2\delta(x\minus{}2))e^{\minus{}\pi ikx/2}\,dx$

$ \equal{}\minus{}\frac24\plus{}\frac{2e^{\minus{}\pi ik}}4\equal{}\frac12\left((\minus{}1)^k\minus{}1\right)\equal{}\begin{cases}\minus{}1,&k\text{ odd}\\0,&k\text{ even}\end{cases}.$

Then, for $ k\ne 0,$ we have $ \widehat{f}(k)\equal{}\left(\frac{P}{2\pi ik}\right)^2\widehat{f''}(k)\equal{}\minus{}\frac{4}{\pi^2}\widehat{f''}(k)$

$ \equal{}\begin{cases}\frac{4}{\pi^2k^2},&k\text{ odd}\\0,&k\text{ even}\end{cases}.$

Some notes: $ f$ was real and even, which causes $ \widehat{f}$ to be real and even, and means that if we want to switch to cosines and sines, we will be able to write the series entirely in terms of cosines. $ f$ is continuous but not differentiable, although we do have that $ f'$ is a pretty nice, if discontinuous, function. (Technically, I observe that $ f'$ is of bounded variation.) Given this, the fact that $ \widehat{f}(k)\equal{}O(k^{\minus{}2})$ is unsurprising. (The smoother $ f$ is, the more rapidly $ \widehat{f}(k)$ decays as $ k\to\infty.$)

We can write $ f(x)\equal{}\frac{4}{\pi^2}\sum_{k\in\mathbb{Z},k\text{ odd}}\frac{e^{\pi ikx/2}}{k^2}$

$ \equal{}\frac{4}{\pi^2}\sum_{k>0,k\text{ odd}}\frac1{k^2}\left(e^{\pi ikx/2}\plus{}e^{\minus{}\pi ikx/2}\right)$

$ \equal{}\frac{8}{\pi^2}\sum_{m\equal{}0}^{\infty} \frac{\cos\left(\frac{(2m\plus{}1)\pi x}2\right)}{(2m\plus{}1)^2}.$

The series converges absolutely and uniformly by the Weierstrass $ M$-test, and it converges to $ f.$ Try setting $ x\equal{}0$ for an interesting sum identity.

[quote="JRav"]To be honest with you, I just learned how to compute Fourier series, literally on Thursday.  So I'm not really sure how competent I am with them.[/quote]
it doesn't matter.I'm sure we can help each other.We can share our Ideas.You can teach me something and may be I can tell you somthing that helps you.Just participate,that's All.anyway thank you!!!

[quote="Kent Merryfield"]Try setting $ x\equal{}0$ for an interesting sum identity.[/quote]
Doing that yields
$ \sum_{k\equal{}0}^{\infty}\frac{1}{(2k\plus{}1)^{2}}\equal{}\frac{\pi^{2}}{8}$,
which is pretty well-known.

There are several other ways to re-derive that identity, including residues.


Hi, I know that you guys have an active marathon here.

However, I cannot visit this website daily so I might not be able to update problems.

Nevertheless, I have a lot of problems that I created for my school's math club, and I know that a lot of you guys want practice, so is it alright if I post them seperately in different threads (so that I can post them all at once without updating daily)?

In a marathon: we just solve the previously posted problem and post a new one, so just post there.

Also, what level problems are you talking about?


[quote="now a ranger"]Figures 0,1,2, and 3 consist of 1,5,13 and 25 nonoverlapping unit squares, respectively. If the pattern were continued, how many nonoverlapping unit squares would be in figure 100?[/quote]

[hide]I can't see the picture, but the numbers fit to the quadratic $2x^{2}+2x+1$. So there would be $2 \cdot 100^{2}+2 \cdot 100+1=20201$ squares in the hundredth figure, if the quadratic fit is correct.[/hide]

(EDIT: Shifted over the equation b/c i misread the problem.)

[quote="rnwang2"][quote="cincodemayo5590"][quote="now a ranger"]Figures 0,1,2, and 3 consist of 1,5,13 and 25 nonoverlapping unit squares, respectively. If the pattern were continued, how many nonoverlapping unit squares would be in figure 100?[/quote]I can't see the picture, but the numbers fit to the quadratic $2x^{2}-2x+1$. So there would be $2 \cdot 100^{2}-2 \cdot 100+1=19999999801$ squares in the hundredth figure, if the quadratic fit is correct.[/quote]
Check your equation.[/quote]

Oh oops, I thought it said figures 1,2,3. I'll shift it over by one. Thanks.  (And wow, I definitely typed something wrong into the calculator to get that huge number as my final answer. Lol.)

An easier formula is: $n^{2}+(n+1)^{2}$, which can be seen if you have the diagram.

[quote="Alex Chen"]how do u do polynomials to get equations like that?[/quote]

We know the polynomial will be of the form $y=ax^{2}+bx+c$.  So plugging in the data points from above:

$(0,1)$
$(1, 5)$
$(2, 13)$
$(3, 25)$

$1 = a(0^{2}) = b(0)+c$

$\boxed{1 = c}$

So it will be of the form $y = ax^{2}+bx+1$.  Now we plug in the next data point:

$5 = a+b+1$
$\boxed{a+b = 4}$

And the next:

$13 = 4a+2b+1$
$\boxed{6 = 2a+b}$

So taking this with the other boxed equation, we have $a=2$ and $b=2$.  We found $c=1$ earlier, so we know our polynomial is:

$y=2x^{2}+2x+1$

stupidityismygam, i dont think your generalization is correct

Earlier you said $c = 1$, which is correct...

BTW, the diagram is:

1 square.
1 square surrounded by 4 (one on each side)
those 5 with 8 more surrounding it (one on top of each of the outside four, and one in between of each of the outside four squares)

etc.


I was told that the energy density of a spherical shell of radius $R$ is

\[ D=\frac{\epsilon_{0}E^{2}}{2},  \]

where $E$ is the electric field.  However, when I tried to derive it, I came up with something a bit different.  Here's what I got:

\[ D=\frac{U}{A}=\frac{QV}{2A}=\frac{kQ^{2}}{2RA}=\frac{kQ^{2}}{2R\left(4\pi R^{2}\right)}=\frac{kQ^{2}}{8\pi R^{3}}.  \]

I got $V$ from

\[ V=-\int\limits_{\infty}^{R}\frac{kQ}{r^{2}}\,dr=\frac{kQ}{R}.  \]

Can someone see what I am doing wrong?  Thank you.

The quantity $D = \frac{\epsilon_0 E^2}{2}$ has dimension

$[D] = [\epsilon_0] \cdot [E]^2 = \frac F m \cdot \frac{V^2}{m^2} = \frac{(F \cdot V) \cdot V}{m^3} = \frac{C \cdot V}{m^3} = \frac{J}{m^3}$

i.e., it is energy per volume, while the quantity you are calculating has dimension $\frac{J}{m^2}$, i.e., energy per surface.


USA(J)MO
USAMO
inequalities
floor function
modular arithmetic
pigeonhole principle
Hi

Let $p$ be a prime number and let $s$ be an integer with $0 < s < p.$ Prove that there exist integers $m$ and $n$ with $0 < m < n < p$ and

\[ \left \{\frac{sm}{p} \right\} < \left \{\frac{sn}{p} \right \} < \frac{s}{p}  \]

if and only if $s$ is not a divisor of $p-1$.

Note: For $x$ a real number, let $\lfloor x \rfloor$ denote the greatest integer less than or equal to $x$, and let $\{x\} = x - \lfloor x \rfloor$ denote the fractional part of x.

[hide="if direction"]
There are always $p-1$ values that $\left\{\frac{ms}{p}\right\}$, $\left\{\frac{ns}{p}\right\}$, and $\frac{s}{p}$ can take. For positive integer $a>0$:

\[ \begin{array}{c|c|c|c|c|c} \left\{\frac{a}{p}\right\} & \frac{1}{p} & \frac{2}{p} & \cdots & \frac{p-2}{p} & \frac{p-1}{p}\\\hline a \pmod {p} & 1 & 2 & \cdots & p-2 & p-1\\ \end{array}  \]

Let $A_i$ be the "pigeonholes" that $\left\{\frac{a}{p}\right\}$ can be in; i.e. $\left\{\frac{sm}{p}\right\} \in A_1\iff sm\equiv 1 \pmod {p}$.

Now consider the cases:

[b]Case 1:[/b] $ks=p-1$ for some integer $k$ (in other words $ks\equiv -1 \pmod {p}$)

Notice that $ks=p-1\iff p\equiv 1 \pmod {s}$.

Let $\left\{\frac{sm}{p}\right\}\in A_a$ and $\left\{\frac{sn}{p}\right\}\in A_b$. Then $sm\equiv a\pmod {p}$. We can subtract $ap$ from the RHS to get $sm\equiv a(1-p)\pmod {p}\iff m\equiv -\frac{a(p-1)}{s} \pmod {p}$ or $m=p-\frac{a(p-1)}{s}$. Similarly, $n=p-\frac{b(p-1)}{s}$. (It is clear that $m$ and $n$ are both integers in this case.) But since $a<b$, this means that $m>n$, a contradiction.

Therefore if $p\equiv 1 \pmod {s}$ (or $s|(p-1)$), then there is no solution.

[b]Case 2:[/b] $ks\ne p-1$ for any integer $k$ (in other words $ks\not \equiv -1 \pmod {p}$)

Yeah I can't remember how to do the "only if" direction. I'll remember eventually (I hope).
[/hide]

My solution (kinda hard to follow I think...)

[hide="Solution"]
In terms of modular arithmetic, we have

$sm \mod p < sn \mod p < s$

Since $p$ is prime, we must have an $a$ such that $s \cdot a \equiv -1 \equiv p-1 \mod p$.  Let $f(x)$ be $ax+1$ reduced modulo $p$.  So

$s f(x) \equiv s(ax + 1) \equiv sax + s \equiv s - x \mod p$
$s f(1) \equiv s - 1 \mod p$
$s f(2) \equiv s - 2 \mod p$
$s f(3) \equiv s - 3 \mod p$
...
$s f(s) \equiv s-s \equiv 0 \mod p$.

Suppose $s \cdot a$ is actually equal to $p-1$ (ie s is a factor of $p-1$).  Then $f(1) < f(2) < f(3) <\cdots < f(s-1)$.  So $f(x)$ increases between 1 and s-1, but $s f(x) \equiv s-x \mod p$ decreases, so our inequality is impossible.

Now if $s \cdot a \neq p-1$.  Then $a > \frac{p-1}{s}$.  So as $x$ goes from 1 to $s-1$, it must decrease at some point; say $f(k) > f(k+1)$.  Take $m = f(k+1)$ and $n = f(k)$.  So $m < n$, but $sm \mod p = s-k-1$ and $sn \mod p = s-k$ and $s-k-1 < s-k$.  So $sm \mod p < sn \mod p < s$ and we are done.
[/hide]

BTW: The last line in the problem statement should say $\{ x \} = x - \lfloor x \rfloor,$ not $x = x - \lfloor x \rfloor$.

Another Solution (notice how I define a and b):

[hide]

(I'll assume you know how the fractional part function is related to modular arithmetic.)

Define modular inequalities as follows:
$x < y \mod p$ iff there are integers $r_x$ and $r_y$ such that $x \equiv r_x \mod p$, $y \equiv r_y \mod p$ and $0 \le r_x < r_y < p$.

Note the fact that if $w \equiv x \mod p$ and $z \equiv y \mod p$ and $x < y \mod p$ then $w < z \mod p$.

Notice that our inequality of fractional parts becomes a modular inequality, in particular:

$sm < sn < s \mod p$

As well, we have the key inequality $m < n$.

Now define a and b $> 0$ and $< p$ such that:

$m \equiv a s^{-1}$ and $n \equiv b s^{-1}$

where $s^{-1}$ is the multiplicative inverse of s mod p. Notice that for any a and b we can find a corresponding m and n, and vice versa, so the problem is equivalent to finding a and b.

We now have

$0 < a < b < s < p$   (1) (this is a normal inequality as the numbers are between p and 0)

$a s^{-1} < b s^{-1} \mod p$   (2)

We now divide into two cases, Case A (only if) and Case B (if):

Case A:
Assume s|p-1

Then we have $\frac{(p-1)^2}{s}$ is an integer, and because $(p-1)^2 \equiv 1 \mod p$, $\frac{(p-1)^2}{s} \equiv s^{-1} \mod p$

By this, we have:

$a s^{-1} \equiv \frac{a(p-1)^2}{s} \equiv (p-1) \frac{a(p-1)}{s} \equiv \frac{pa(p-1)}{s} - \frac{a(p-1)}{s} \equiv p - \frac{a(p-1)}{s} \mod p$   (3)

and similarly:    $b s^{-1} \equiv p - \frac{b(p-1)}{s} \mod p$   ()

Now, notice that because $0 < a < b < s$, we have:

$0 < \frac{a(p-1)}{s} < \frac{b(p-1)}{s} < p$, which means that:

$0 < p - \frac{b(p-1)}{s} < p - \frac{a(p-1)}{s} < p$

By the definition of modular inequalities and by (3) and (4), this must mean that:

$b s^{-1} < a s^{-1} \mod p$

This contradicts (2), so there are no such a and b (and therefore no such m and n) if s|p-1

Case B:

Assume that s does not divide p-1 and that there are no a and b.

Notice that the sequence:

$s^{-1}$, $2 s^{-1}$, ... $(s-1) s^{-1}$

Must be decreasing mod p (think modular inequalities), for if it were to increase at any point, we could find such an a and b. Also note that this sequence exists, as if $s \le 2$, then s|p-1.

Notice that, in terms of residues between 0 and p, this sequence starts at $s^{-1}$, drops by $p-s^{-1}$ $s-2$ times, and ends up at $(s-1)s^{-1} \equiv 1 - s^{-1} \equiv p + 1 - s^{-1} \mod p$. This happens as long as the sequence is decreasing mod p, that is, as long as the sequence doesn't "fall through a multiple of p."

So, if this sequence is decreasing (ie there are no a and b), we can write:

$\frac{s^{-1} - (p + 1 - s^{-1})}{p - s^{-1}} = \frac{2s^{-1} - p - 1}{p - s^{-1}} = s-2$.

PS: This is as far as I got on USAMO  :( , I didn't see how to finish it, I just BSed the end. Hope I'm lucky during grading...

Anyway, we add 2 to both sides and get:

$s = \frac{2s^{-1} - p - 1}{p - s^{-1}} + 2 = \frac{2s^{-1} - p - 1 + 2p - 2s^{-1}}{p - s^{-1}} = \frac{p-1}{p - s^{-1}}$

This means s divides p-1! This contradicts our assumption that s does not divide p-1. So, when s does not divide p-1, we must be able to find a and b and therefore m and n that satisfy the inequalities.

Thus our proof is complete; we have shown that if s|p-1, then we cannot find such m and n, and if s does not divide p-1, we can find such m and n.

QED
[/hide]

we have to show that when we list the numbers $1s, 2s, ..., (p-1)s$ reduced $\pmod p$, some two of the elements of $\{1, ..., s-1\}$ occur in increasing order from left to right IFF $s$ doesn't divide $p-1$.

1) assume $sk = p-1$ for some $k$. then

$s(k+1) \equiv s-1 \pmod p$

$s(2k+1) \equiv s-2 \pmod p$

...

$s((s-1)k+1) \equiv 1\pmod p$

(and $(s-1)k+1 \leq p-1$)

so when we list $1s, 2s, 3s, ..., (p-1)s$ reduced $\pmod p$, the numbers $\{1, ..., s-1\}$ occur in decreasing order.

2) assume $s$ doesn't divide $p-1$. let $a \in \{1, ..., p -1\}$ be the unique value in that set for which $as \equiv p - 1 \pmod p$. in particular, notice that $a \geq 2$ (because if $a = 1$, then $s = p-1$). then

$s(a+1) \equiv s-1 \pmod p$,

$s(2a+1) \equiv s-2 \pmod p$,

...

$s((s-1)a+1) \equiv 1 \pmod p$

but since $s$ doesn't divide $p-1$, $as \geq p+p-1 = 2p-1$, so $(s-1)a+1 = sa-a+1 \geq 2p-1-(p-1)+1 = p + 1$. so let $j \in \{1, ..., s-1\}$ be the smallest value for which $ja + 1 > p - 1$ and let $b \in \{1, ..., p-1\}$ be the unique value in that set for which $ja + 1\equiv b \pmod p$. (notice that $j > 1$ because if $j = 1$ we'd have $a+1 = p$, in which case $s = 1 | p-1$.) then $b < a$ because of the way we defined $j$. then setting $m = b, n = a+1$ completes the proof.

if s does not divides p-1

[hide]then define 0<m<p and ms==1(mod p)
define n as the smallest positive integer such that n>m and ns(mod p)<s
(n is well-defined because s does not divides p-1)
so {ms/p}=1/p<{ns/p}<s/p[/hide]

if s divides p-1, then my solution is the same as the official solution

I was wondering if this worked for the if direction

[hide="if"] As $ (s,p) \equal{} 1$, we can always find an $ m$ so that $ sm\equiv1\pmod{p}$.

Now, $ n\in\{{m \plus{} 1, m \plus{} 2, ...p \minus{} 1\}}$ so $ sn$ is congruent $ \pmod{p}$ to one of $ s \plus{} 1, 2s \plus{} 1, ...sp \minus{} s$.
Assume that all $ s \plus{} 1, 2s \plus{} 1, ...sp \minus{} s$ are less than $ p$. However, this means $ s(p \minus{} 1) < p$. But, since $ s\ne{1}$ because $ s\not |{(p \minus{} 1)}$, $ s(p \minus{} 1) > p$. Hence, not all of the possible $ n$ are less than $ p$.
Thus, we know that there exists some $ k$ so that $ ks \plus{} 1\pmod{p} > (k \plus{} 1)s \plus{} 1\pmod{p} < s\pmod{p}$, unless $ s|(p \minus{} 1)$. In other words, we can always find some $ n$ so that $ sn\pmod{p} < s$. Additionally, as $ sm\equiv{sn}\pmod{p}$ implies $ m\equiv{n}\pmod{p}$, this is impossible as $ m$ and $ n$ cannot have a difference that is a multiple of $ p$ for this problem. Thus, $ sm\pmod{p} < sn\pmod{p}$.

Thus, we have shown that it is always possible to find $ m,n$ such that $ 0 < m < n < p$ and $ sm\pmod{p} < sn\pmod{p} < s$, which completes the if part of the problem.[/hide]

I've been having much more trouble with this problem than any other USAMO #1, so I will probably have a mistake in the above solution. Furthermore, I realize that I am not a good solution writer, so I would appreciate any suggestions as to how to improve my solution.

Thank you!

For any integer $a$, let $[a]$ denote the value of $a$ reduced modulo $p$, and let $s^{-1}$ be the inverse of $s$ modulo $p$. Observe that $\left \{ \frac{k}{p} \right \} = \frac{[k]}{p}$ for all integers $k$, so it is sufficient to show that there exist integers $m,n$ with $0<m<n<p$ and $[sm] < [sn] < s$ if and only if $s \not| p-1$.

Let $b_i = [i s^{-1}]$ for integers $1 \leq i \leq s-1$. Observe that for any integer $k$ with $0 < [ks] < s$, ${b_{[ks}} \equiv (ks) s^{-1} \equiv k \pmod{p}$. Hence, if $0 < [ms] < [ns] < s$, then $m < n$ if and only if $b_m < b_n$. Hence, there do not exist integers $m,n$ with $0<m<n<p$ and $[sm] < [sn] < p$ if and only if $b_{s-1} < b_{s-2} < \ldots < b_1$.

We claim that $\min(b_1, b_2, \ldots, b_{s-1}) = \lfloor \frac{p}{s} \rfloor + 1$. For $0 \leq k \leq s-1$, let $a_k = \lfloor \frac{kp}{s} \rfloor + 1$. Let $U$ be the set of all integers $u$ less than $p$ with $0 < [us] < s-1$. since $0 < a_1 < a_2 < \ldots < a_{s-1} < p$, and that $kp < s a_k < kp + s$ for $1 \leq k \leq s-1$, $U = \{a_1, a_2, \ldots, a_{s-1}\}$. On the other hand, it is clear that $U = \{b_1, b_2, \ldots, b_{s-1}\}$ as well, so $\{a_1, a_2, \ldots, a_{s-1}\} = \{b_1, b_2, \ldots, b_{s-1}\}$; in particular the smallest element of $\{b_1, b_2, \ldots, b_{s-1}\}$ must equal the smallest element of $\{a_1, a_2, \ldots, a_{s-1}\}$, which is $\lfloor \frac{p}{s} \rfloor + 1$, so our claim is proven.

If $s | p - 1$, then we claim that $b_i = (s - i) (\frac{p-1}{s}) + 1$. Since $0 < (s-i)(\frac{p-1}{s}) + 1 < p$, and
\[ s((s-1)(\frac{p-1}{s}) + 1) = (s-1)(p-1) + s \equiv 1-s+s \equiv 1 \pmod{p}, \]
we indeed have $b_i = (s - i) (\frac{p-1}{s}) + 1$, whence $b_{s-1} < b_{s-2} < \ldots < b_1$, so the only if direction of the problem is proven.

If $s \not | p - 1$, we claim that $b_{s-1} \neq \min(b_1, b_2, \ldots, b_{s-1}) = \lfloor \frac{p}{s} \rfloor + 1$, whence we could not have $b_{s-1} < b_{s-2} < \ldots < b_1$. If $b_{s-1} = \lfloor \frac{p}{s} \rfloor + 1$, then
\[ s-1 \equiv s b_{s-1} = s + s \lfloor \frac{p}{s} \rfloor \pmod{p}, \]
so
\[ p-1 \equiv s \lfloor \frac{p}{s} \rfloor \pmod{p}. \]
Since $p-1$ and $s \lfloor \frac{p}{s} \rfloor$ are both less than $p$, we must have
\[ \frac{p-1}{s} = \lfloor \frac{p}{s} \rfloor = \frac{p}{s} - \left \{ \frac{p}{s} \right \}, \]
whence $s | p - 1$, which is a contradiction.

Apologies for the revive - Could I get some feedback on this solution? Does it have any aspects that could be improved upon? I feel like it is simpler than the official solution I have.

[hide]Multiplying the given inequality by $p$, we have
\[ms\pmod{p} < ns\pmod{p} < s.
\] The first $p$ multiples of $s$ clearly have different remainders $\pmod{p}.$ Consider the multiples $a_1, a_2, a_3, ..., a_s$ that leave remainders of $1, 2, 3, ..., s \pmod{p}.$ We can see that the inequality does not hold if and only if $a_1 > a_2 > a_3 > \cdots > a_s.$ We will show that this happens if and only if $s| p-1.$

It is obvious that if $s| p-1,$ then $a_i=a_{i+1}+p-1,$ so we are done here.

If $s \nmid p-1,$ then the first multiple of $s$ greater than $p$ is not $a_{s-1},$ so $a_i < a_{s-1}$ for some $i<s-1.$ Therefore, $a_1 > a_2 > a_3 > \cdots > a_s$ does [b]not[/b] hold, so the given inequality does hold.[/hide]

[quote="va2010"]I dun think you can multiply by p on the first two terms[/quote]

Why not? $p \times \left\{\frac{sm}{p}\right\}$ is indeed equal to $ms\pmod{p}.$

It's equivalent to $ms \bmod p < ns \bmod p < s$, where $x \bmod p$ means the remainder when $x$ is divided by $p$, by slight abuse of notation. We will assume $s \ge 2$ for simplicity, since the case $s = 1$ is clear.

For any $x \in \{1, 2, \dots, s-1\}$ we define $f(x)$ to be the unique number in $\{1, \dots, p-1\}$ such that $s \cdot f(x) \bmod p = x$. Then, $m$ and $n$ fail to exist exactly when \[ f(s-1) < f(s-2) < \dots < f(1). \]

We give the following explicit description of $f$: choose $t \equiv -s^{-1} \pmod p$, $0 < t < p$. Then $f(x) = 1 + (s-x) \cdot t \bmod p$. So our displayed inequality is equivalent to \[ (1+t) \bmod p < (1+2t) \bmod p < (1+3t) \bmod p 	< \dots < (1+(s-1)t) \bmod p. \] This just means that the sequence $1+kt$ never ``wraps around'' modulo $p$ as we take $k=1,2,\dots,s-1$.

Since we assumed $s \ne 1$, we have $0 < 1+t < p$. Now since $1+kt$ never wraps around as $k=1,2,\dots,s-1$, and increases in increments of $t$, it follows that $1+kt < p$ for all $k = 1, 2, \dots, s-1$. Finally, as $1+st \equiv 0 \pmod p$ we get $1+st=p$.

In summary, $m$, $n$ fail to exist precisely when $1 + st = p$. That is of course equivalent to $s \mid p-1$.

@v_Enhance could you elaborate on the final part of your proof? ("$1+t<p$ means $1+(s-1)t<p$.  But $1+st\equiv0\pmod{p}$, so $1+st=p$.)
Thanks!

[hide="Solution"]The if direction is quite direct: we have that $sm\equiv r_1(\mathrm{mod}\ p),\ sn\equiv r_2(\mathrm{mod}\ p)$ with $0<r_1<r_2<s$. Suppose that $s|p-1$. Then we would have
$$p-m\equiv (p-1)m\equiv  \dfrac{p-1}{s} r_1 (\mathrm{mod}\ p), \ p-n\equiv (p-1)n\equiv  \dfrac{p-1}{s} r_2 (\mathrm{mod}\ p)$$
which is a contradiction because $0<p-n<p-m<p$ while $0<\dfrac{p-1}{s}r_1<\dfrac{p-1}{s}r_2<p$.

For the only if part, let $0<a_i<p$ such that $sa_i\equiv i (\mathrm{mod}\ p)$ for $1\le i\le s-1$. Suppose that the statement does not hold; this implies that $a_1>a_2>...>a_{s-1}$. Note that
$ sa_{i-1}\equiv i-1(\mathrm{mod}\ p),\ sa_i\equiv i(\mathrm{mod}\ p)$ and $a_{i-1}>a_i$, hence $sa_{i-1}\ge sa_i+p-1$. Summing up the relations, we get that $sa_1\ge sa_{s-1}+(p-1)(s-2)$.
Note that $sa_{s-1}\equiv s-1 (\mathrm{mod}\ p)$ and $sa_{s-1}\ge s>s-1$; if $sa_{s-1}=p+s-1$, we get that $s(a_{s-1}-1)=p-1$, therefore $s|p-1$, a contradiction; we thus infer that $sa_{s-1}\ge s-1+2p$, so $$sa_1\ge sa_{s-1}+(p-1)(s-2)\ge sp+1\Rightarrow a_1\ge p+\dfrac{1}{s}>p$$
which yields a contradiction.[/hide]

Let $a'$ be the remainder when $a$ is divided by $p$. First observe that the initial condition is equivalent to $(sm)'<(sn)'<s$.

We will first prove the if statement. Let $m$ be the smallest positive integer such that $(ms)'<s.$ This is equivalent to $p\le ms\le p+s-1$. Clearly there is only one value of $m$ that satisfies these conditions. However, $ms\neq p+s-1$ since $s$ does not divide $p-1$. Also, $ms\neq 0$ since $s\neq 1$. Therefore, $(ms)'<s-1$. Also, since $s$ does not divide $p$, there is an integer $0<n<p$ such that $(ns)'=s-1$. Therefore, we have found integers $m$ and $n$ that satisfy the conditions.

We will prove the only if statement by showing that if $s$ is a divisor of $p-1$ then it is impossible to find such integers $m$ and $n$. Let $sk=p-1$. Then $(s(k+1))'=s-1<(s(2k+1))'=s-2<\cdots <(s((s-1)k+1)'$ and $k+1<2k+1<\cdots <(s-1)k+1$. Since there is a unique $0<i<p$ such that $(si)'=j$ for $0<j<p$, then the result follows. $\Box$

[hide=Solution]
1. The condition means that
$$S = \frac{1}{s}, \frac{2}{s}, \frac{3}{s}, \dots, \frac{s-1}{s}$$
is not a decreasing sequence $\pmod p$, i.e. each term is taken $\pmod p$. (Here $\frac{1}{s} = s^{-1} \pmod p$.)

2. Thus we want to prove that it is a decreasing sequence if and only if $s | p-1$.

3. Let $s | pk - 1$ for $k = -p^{-1} \pmod s$. Notice that $k < s$.

4. Then $T = \frac{pk-1}{s}, \frac{2(pk-1)}{s}, \frac{3(pk-1)}{s}, \dots, \frac{(s-1)(pk-1)}{s}$ is an increasing sequence of integers when taken $\pmod p$. But $\frac{pk-1}{s} < p$, so in fact this is an increasing sequence whose terms are all less than $p$. [hide=Why?] Let $t_i$ be the first term of the sequence greater than or equal to $p$. Then $i \ge 2$ and $t_i - p < t_{i-1}$ because $t_i = t_{i-1} + \frac{pk-1}{s}$, so $t_i < t_{i-1} \pmod p$, contradiction. [/hide] Then $\frac{(s-1)(pk-1)}{s} < p$, so $(s-1)(pk-1) < sp$. This is valid for $k = 1$, or that $s | p - 1$; so suppose $s$ does not divide $p - 1$ and $k > 1$. Then $k \ge 2$, so
$$(s-1)(2p-1) < sp$$
$$2ps - 2p - s + 1 < ps$$
$$ps - 2p - s + 1 < 0$$
$$(s - 2)(p - 1) < 1$$
This is clearly a contradiction since $s$, which does not divide $p - 1$, is at least $3$ for $p \ge 3$, and if $p = 2$ then $s = 1$, still contradiction. This the problem is complete.
[/hide]

This was a pretty silly problem. Also, why do they have to make Day 1 all number theory?

Anyway, here is my solution (probably not significantly distinct)

[i]Case 1[/i] Let $s \mid p-1$

In this case, let $k=\frac{p-1}{s}$
Evidently, we see that the set of residues $\{1s,2s,...,(p-1)s\}=_{\bmod p} \{s,2s,...,sk(=p-1),s-1,2s-1,...,sk-1(=p-2),s-2,...\}$ and thus, our condition cannot hold.

[i]Case 2[/i] Let $s$ not divide $p-1$

In this case, we show that our desired $m,n$ indeed exist. If $r(x,p)=r$ such that $x \equiv r \bmod p$ and $r \in \{0,1,2,...,p-1\}$.

Clearly, we want $r(sm,p) < r(sn,p)<s$ and for this, let $k$ be the integer such that $sk<p<s(k+1)$.
Now, since $s$ is not a divisor of $p-1$ we see that $sk<p-1<p<s(k+1)$

Choose $m=k+1$ and we notice that $1 \le r(sm,p) \le s-2$ and so we miss the residue $s-1$. Let $n$ be the number in $\{1,2,...,p-1\}$ such that $sn \equiv s-1 \bmod p$ then clearly, $0<m<n<p$ which satisfy our condition.

This solves the problem.

[hide=Solution Sketch (kinda gross)]
Note that the given condition is equivalent to $s^{-1}, 2s^{-1} \ldots (s-1)s^{-1}$ not being decreasing. Therefore, it suffices to show that $s^{-1}, 2s^{-1} \ldots (s-1)s^{-1}$ is decreasing if and only if $s$ is a divisor of $p-1$.

Let $s' = p -s^{-1}$. Note that each addition of $s^{-1}$ is equal to subtracting $s'$, and that there are $s-2$ such additions. For our sequence to remain decreasing, each of these subtractions must decrease our value, meaning that our value must stay positive (or it will not loop over fully and therefore increase). Our condition is therefore equivalent to $s^{-1} > (p - s^{-1})(s-2) \implies s^{-1} > p(\frac{s-2}{s-1})$.

Now, to show that this condition is equivalent to $s$ dividing $p - 1$, note that if $s$ does divide $p - 1$, then $s^{-1} = p - \frac{p-1}{s}$, and substituting this into our given equation proves the "if" direction. To prove the "only if" direction, note that $s^{-1}$ is at least $\frac{2p - 1}{s}$, and more substitutions and some algebra proves the "only if" direction, completing our proof.
[/hide]

Here is my solution.

Let \(p=sq+r\) where \(q,r\) denote the quotient when \(p\) is divided by \(s\). Note \(s\mid p-1\iff r=1\), and that \(r>0\).

We can find that the \(k\) such that \(0<\left\{\dfrac{sk}{p}\right\}<\dfrac{s}{p}\) satisfy  \(k=\left\lceil\dfrac{tp}{s}\right\rceil\) for \(1\le t \le s-1\).

When \(r=1\), note that \(k=\left\lceil\dfrac{tp}{s}\right\rceil=\left\lceil\dfrac{t(sq+1)}{s}\right\rceil=tq+\left\lceil\dfrac{t}{s}\right\rceil=tq+1\), so the sequence of valid \(k\) yield \(\left\{\dfrac{sk}{p}\right\}=\left\{\dfrac{stq+s}{p}\right\}=\dfrac{s-t}{sq+1}\).

Finally, if we pick \(t_m, t_n\) corresponding to values of \(m, n\), we get \(m<n\iff t_m < t_n\iff \dfrac{s-t_m}{sq+1}>\dfrac{s-t_n}{sq+1}\), so no \(m,n\) exist.

Now, when \(r > 1\), note that when \(t=1\), \(k=\left\lceil\dfrac{p}{s}\right\rceil=q+1\), so \(\left\{\dfrac{sk}{p}\right\}=\left\{\dfrac{s(q+1)}{p}\right\}=\dfrac{s-r}{p}<\dfrac{s-1}{p}\). Thus, we can select \(m=q+1\) and \(n\) such that \(\left\{\dfrac{sn}{p}\right\}=\dfrac{s-1}{p}\) (which exists) to get a valid construction.

Let $a\%b$ denote the remainder when $a$ is divided by $b$. It is clear that the problem is equivalent to showing that there exist $m$ and $n$ less than some prime $p$ such that $$sm\% p<sn\% p<s$$ iff $s|p-1$. This means that the residues $s, s-1, \cdots 1$ can not appear in a decreasing fashion. We will show that they are strictly decreasing iff $s|p-1$, which implies the desired conclusion.
s
Let $p=as+b$ where $p\% s=b$. We have the first few terms to be $$s, 2s \cdots, as, as+s-p=s-b, \cdots $$
The sequence $s, s-1, s-2, \cdots$ can not appear in this order if $s-b \ne s-1$, or if $b\ne 1$, so this shows that it is only possible to have a strictly decreasing sequence if $s|p-1$.

Now I will show that if $s|p-1$ we always have a decreasing sequence: let $sk=p-1$. We can easily see that our sequence becomes $$s, 2s,\cdots, ks=p-1, s-1, 2s-1, \cdots ,p-2, s-2, \cdots ,p-s$$ where the first block of $k$ residues is $s, 2s, \cdots, ks$ and the following blocks of $k$ residues are one less than the corresponding terms. This means that the sequence of the leading terms of each of these $k$ blocks is $s, s-1, s-2, \cdots, 1$, which is strictly decreasing.

Remark that $\{x\} = 0$ iff $x$ is an integer, so $\left\{\frac{sm}{p}\right\}$ cannot be an integer. We show that the negation of the given condition is true iff $s\mid p-1$. Rewrite the negation of the given condition as follows: for all integers $0 < a < b < s$ with $sm\equiv a\pmod{p},sn\equiv b\pmod{p}$, we have $m>n$. Then, let $1/s\equiv t\pmod{p}$. Then, the negation of the given condition is equivalent to the statement that for all integers $0<a<b<s$ with $at\equiv m\pmod{p},bt\equiv n\pmod{p}$, we have $m>n$. Now, consider the list
\[\{0t,1t,2t,\dots, st\}.\]
We take $0t$ reduced modulo $p$ to be $p$ for convenience. This list is an arithmetic progression modulo $p$ with common difference $t$ that must satisfy the property that $at$ reduced modulo $p$ is larger than $bt$ reduced modulo $p$ for any $a<b$. Since $t<p$, the existence of any $a$ such that $at>kp>(a+1)t$ for some $k$ would give $(a+1)t$ reduced modulo $p$ greater than $at$ reduced modulo $p$, absurd. Thus, $0t-st\equiv p-1\pmod{p}$ must be equal to $p-1$, so $t\mid -st \mid p-1$ and thus $-st=p-1$. This implies $s\mid p-1$ as desired, so we have shown that the negation of the given existence condition holds iff $s\mid p-1$.

The problem is equivalent to showing that
$$s^{-1}, 2s^{-1}, 3s^{-1}, \dots, (s-1)s^{-1}$$
taken mod $p$ is strictly decreasing iff $s \mid p-1$. This is trivial$^{\mathrm{TM}}$.

[hide = Solution]
Let $a;b$ denote the remainder when $a$ is divided by $b$ . The condition may now be expressed as follows[quote = Rephrased Condition]Let $p$ be a prime number and let $s$ be an integer with $0 < s < p.$ Prove that there exist integers $m$ and $n$ with $0 < m < n < p$ and $$sm;p < sn;p < s$$ iff $s$ is not a divisor of $p - 1$[/quote]

[color=#741B47][b]Claim. [/b][/color] For a fixed prime $p$ and a fixed integer $0 < s < p $, $sm;p$ may take on any positive integer value less than $p$ for an integer $0 < m < p$

[i][color=#A64D79]Proof. [/color][/i] Suppose there exist two integers $0 < m < m' < p$ such that $sm;p = sm';p$ . This implies $sm \equiv sm' \pmod{p} \to s(m' - m) \equiv 0 \pmod{p}$. However, we have that $0 < s < p$ and $0 < m' - m < p$ meaning that both are relatively prime to $p$, contradiction. Hence, each integer $0 < m < p$ results in a unique value for $sm;p$, which implies the claim $\square$

Now we will show that all $s$ which aren't a divisor of $p - 1$ work. Take $m$ to be the first integer such that $sm > p$ . We clearly have $sm;p < s$. Now if $sm;p = s - 1$, then we have $sm = p + s - 1 \to s(m - 1) = p - 1$, or $s|p - 1$ contradiction. Hence, $sm;p < s - 1$. Now we take $n$ to be the integer such that $sn;p = s - 1$, which exists by the previous claim and is greater than $m$ by the way we defined $m$ $\square$

It is left to show that all divisors of $p - 1$ fail. Let $sc = p - 1$. Now partition the first $p - 1$ positive integers into $$(1, 2, 3, \cdots c) \cup (c + 1, c + 2, c + 3, \cdots , 2c) \cup \cdots \cup (p - c + 1, p - c + 2, \cdots , p - 1)$$ Notice that each of the first integers in the subsets map to $s, s - 1, s -  2, \cdots , 1$ . By the previous claim we have that each of the first $p - 1$ integers maps to a unique value, meaning that we have all possible values of $sm;p < s$ descend. Thus, we have $sm;p < sn;p$ iff $m > n$, contradiction $\square$

I didn’t think of inverses at all somehow.
The main observation is that the fractional parts are merely a distraction, and the problem is just modular arithmetic.
Let $1,2, \dots, p-1$ be $a_1, a_2, \dots, a_{p-1}$ respectively.
Also let $sa_1, sa_2, \dots, sa_{p-1}$ when reduced modulo $p$ be $b_1, b_2, \dots, b_{p-1}$ respectively.
[color=#f00]Claim :[/color] All $b_i \equiv{x} \mod{s}$ are “together” for all $x \in \{0, 1,2, \dots, s-1\}$
[i]Proof.[/i] Look at the largest $b_i \equiv{x} \pmod{s}$. Let $b_i=ns+x$. Note that
$$sa_i \equiv{ns+x} \pmod{p}$$
$$\implies s(a_i-n) \equiv{x} \pmod{p}$$
$$\implies b_{i-n} \equiv{x} \mod{p}$$
After $b_{i-n}$ these keep increasing by $s$, so we’d have covered all permissible numbers with the same modulo $s$.
It’s easy to prove that, if $s \mid p-1, b_1, b_2, \dots b_{p-1}$ are arranged as $s,2s, \dots, ks=p-1, s-1, \dots, sk-1) , \dots$, so if we keep a note of all these less than $s$, we see that they are arranged as $s-1, s-2, \dots, 1$.
For the backward direction, we want all $b_i$s less than or equal to $s$ to be arranged as $s, s-1, s-2, \dots, 1$.  Let $p=sl+r, p \leq r <s$. Now, let their be $l$ numbers in the subsequence involving $s$. Note that $a_{l+1} \equiv{sl+s} \equiv{-r} \pmod{p}$. Therefore, $b_{l+1}=p-r=p-1 \implies r=1$. Finally, we get $p=sl+1 \implies s \mid p-1 \blacksquare$

A solution for the "only if" part:
Let $f(x)$ be the remainder of $sx$ in the division by $p$. It's easy to see that the problem is the same as asking for integers $m,n$ such that:
$$f(m)<f(n)<s$$
for $m<n$. Let $g$ be the inverse function of $f$. If there exists $a<b<s$ such that $g(a)<g(b)$, taking $m=g(a)$ and $n=g(b)$ we have
$$f(g(a))=a<b=f(g(b))<s.$$
Then, such $m$ and $n$ doesn't exist only when:
$$g(s-1)<g(s-2)<\dots<g(2)<g(1).$$
If $s\mid p-1$: We have that $s=\frac{p-1}{k}$ for some $k$. See that, for $j\leq s$, $1+jk\leq p$ and $f(1+jk)\equiv s+j(p-1)\equiv s-j\pmod{p}$, which implies that $f(1+jk)=s-j$, since $0\leq s-j<p$. Therefore, we have $g(s-j)=1+jk$ and it's easy to see that:
$$g(s-1)<g(s-2)<\dots<g(1)$$
and we have that if such $m,n$ exists, $s\nmid p-1$. $\blacksquare$

For any $x \in \mathbb Z$, note that
$$ \left\{ \frac{sx}{p} \right\} < \frac{s}{p} \iff \left\lfloor \frac{s(x-1)}{p} \right\rfloor < \left\lfloor \frac{sx}{p} \right\rfloor $$
Now for each $1 \le t \le s-1$, let
$$f(t) = \left \{ \frac{sx}{p} \right\}$$
where $1 \le x \le p-1$ satisfies
$$ t = \left\lfloor \frac{s(x-1)}{p} \right\rfloor < \left\lfloor  \frac{sx}{p} \right\rfloor $$
Clearly all of $f(1),\ldots,f(s-1)$ are distinct. Our problem is equivalent to showing $\exists$ $1 \le a < b \le s-1$ with $f(a) < f(b)$ iff $s \nmid p-1$. Note that first thing is equivalent to the sequence $f(1),\ldots,f(s-1)$ being not equal to $s-1,\ldots,1$. This is easily equivalent to $f(1) = s-1$, which is clearly equivalent to $s \mid p-1$, as desired. $\blacksquare$

The condition is equivalent to $$sm \bmod p < sn \bmod p < s.$$ First, suppose that $s \mid p-1$; let $p-1=ks$ for some integer $k$. Then $$(nk+1)s \equiv s+nks \equiv s-n \pmod p,$$ so the residues less than $s$ form a strictly decreasing sequence in the complete residue system given by $\{sk \mid 0 \leq k \leq p-1\}$. This means if $sm < sn < s$ under modulo $p$, then $m>n$ by our conclusion, contradiction.

Now, let $s \nmid p-1$. Let $k_i \equiv \frac is \pmod p$ for $1 \leq i \leq s$. Then because $k_1 - k_s \leq p-2$, it follows that there exists an index $i$ such that $$k_i - k_{i+1} \leq \frac{p-2}{s-1} < \frac{2(p-1)}s.$$ For this choice of $i$, $$s(k_i - k_{i+1}) < 2(p-1) \text{ and } s(k_i - k_{i+1}) \equiv -1 \pmod p.$$ So the quantity in fact equals $p-1$, which implies $s \mid p-1$, contradiction.

Felt a bit easy, fake solve or  :w00t:
Observe that $\left \{ \frac{x}{p} \right \} \in \{ \frac{1}{p},\frac{2}{p},...,\frac{s-1}{p} \}$ which is only possible if $x \equiv 1,2,...,s-1 \mod p$ and $s\neq 1,2$. Hence, rewrite equation as
 \begin{align*}
  &sm \equiv x \mod p \\
  &sn \equiv y \mod p \\
  &0<x<y<s<p\\
  &n<m<p
 \end{align*}
 Is true only and only if $ s \nmid p-1$

  Assume otherwise that $s \mid p-1$. Hence $\exists k \in \mathbb{N}: \frac{p-1}{s}=k$
    We have $ \frac{p-1}{k}m \equiv -\frac{m}{k} \equiv x \mod p \Rightarrow m \equiv -kx \mod p$. Similarly, $ n \equiv -ky \mod p$
Observe that $-kx>-ky$ but since $m<n<p$, that is impossible, hence  such  $k$ should not exist.

  Now, we will show that $s \nmid p-1$ works.
  Observe that $ms \equiv 1 \mod p \Rightarrow m \equiv \frac{1}{s} \mod p$  exists since $\gcd(s,p)=1$. Note that $m \neq p-1$. Then $n \in \{m+1,m+2,...,p-1\}$  , then $sn \equiv s+1,2s+1,3s+1,...,(p-1)s+1 \mod p$.Since $(p-1)s+1> p$, there is at least  one pair of residues such that  $ ks+1> (k+1)s+1 \mod p$ ( basically finishes the circle and goes back to start). Since we are adding one $s$,  $(k+1)s+1  <s \mod p$, which means we can choose that $n$ for such $m$  $\square$.

Mocking USAMO 2006 Day 1 result on p1: 73 minutes, 14 seconds (nub time :c)
[b]If part:[/b] $s \not \; \mid p-1$
Since $s \ne 1,2$ and $s<p$ we get $\gcd(s,p)=1$ so $\{0,s,2s,...,(p-1)s \}$ makes a complete residue system $\pmod p$.
Now let $0<\ell<p$ such that $s\ell \equiv -1 \pmod p$ then note that $\{s((s-1)\ell+1),...,s(2\ell+1),s(\ell+1) \}$ makes a residue system from $1$ to $s-1$ in $\pmod p$, now since $s \not \; \mid p-1$ we get that $s\ell \ge 2p-1$ so $s\ell-\ell > p-1$ is equivalent to $2p-1>p+\ell-1$ which is true hence we get that $(s-1)\ell>p$ (as $p$ is prime so $(s-1)\ell=p$ is imposible) so now we have the existence of this constant $a$ that satisfies that its the minimun positive integer that satisfies $a\ell>p$ (it could be $s-1$ ofc), now let $a\ell+1-pm$ the residue of $a\ell+1$ in $\pmod p$ so we nee $\ell+1>a\ell+1-pm$ which is equivalent to $pm \ge p>(a-1)\ell$ but this holds becuase of the definition of $a$, now if $\ell=p-1$ we have that $s \equiv 1 \pmod p$ so $s=1$ which is not possible hence $\ell+1<p$ which means that from both facts we got it follows the existence of the $m,n$ requied in the problem thus we are done.
[b]Only if part:[/b] We already have the existence of $m,n$
Assume FTSOC that $s \mid p-1$ then let $\ell'$ such that $s\ell'=p-1$ now as $\{s((s-1)\ell'+1),...,s(2\ell'+1),s(\ell'+1) \}$ makes a residue system from $1$ to $s-1$ in $\pmod p$ and $(s-1)\ell'<s\ell'=p-1$ we have that such $m,n$ cannot exist which is a contradiction, hence $s \not \; \mid p-1$ as desired.
Since we did both parts we are done :D

Sketch:
[hide]
Note that $s, 2s, 3s, \dots ps$ spans a complete residue set modulo $p$. Thus the fractional parts ${\frac{si}{p}}$ as $i$ ranges from $0$ to $p-1$ spans ${\frac{1}{p}}, {\frac{2}{p}}, {\frac{3}{p}}, \dots {\frac{p-1}{p}}$ and $0$. If $s|p-1$, then we hit the first $s-1$ fractional parts in reverse order. Otherwise, we will hit $\frac{s-1}{p}$ after some earlier fractional part.
[/hide]

I think this is my first ever USAMO problem solution. Yay!!! :wow: Journey into olympiads :yup:[hide=sol]If $p=2,$ then $s=1,$ but this means that $1=s \mid p-1 = 1.$ Indeed, the inequality is not true because it reduces to $m < n < s.$

Otherwise, $p$ is odd so $p-1$ is even, meaning $s \ne 2$ (and $s \ne 1$ is trivial) so $s \ge 3.$

Lemma: for integers $x,m,$ we have that the residue of $x$ mod $m$ is equal to $m \left\{ \frac{x}{m} \right\}.$ Let this residue be $0 \le r < m.$ Then $x=km+r$ for some integer $k.$ The expression becomes $ m \left\{ k + \frac{r}{m} \right\} = m \left\{ \frac{r}{m} \right\}.$ Since $0 \le \frac{r}{m} < 1,$ this simply becomes $r.$ Thus, the lemma is proven.

Let $t$ be the inverse of $s$ mod $p.$ Then we set $m=t,n=2t.$ Multiplying all by $p,$ we see that the desired inequality is equivalent to $p \left\{ \frac{ms}{p} \right\} < p \left\{ \frac{ns}{p} \right\} < s.$ We have $ms = st \equiv 1 \pmod{p},$ so the first term is $1.$ We have $ns = 2st \equiv 2 \pmod{p},$ so the second term is $2.$ The inequality reduces to $1<2<s,$ and we already know that $s \ge 3,$ so we are done.[/hide]

Note that $\left\{ \frac{sm}{p} \right\} = \frac{x}{p}$ where $x \equiv sm \pmod{p}$. Similarly $\left\{ \frac{sn}{p} \right\} = \frac{y}{p}$ where $y \equiv sn \pmod{p}$.

Now assume $s \mid p - 1$. Then let $st = p - 1$. Then consider $s(t+k)$ for some $0 < k < s$. Clearly we have,
\begin{align*}
s(t+k) \equiv  sk - k \pmod{p}
\end{align*}
Thus multiples of $s$ would cover the residue class modulo $p$ in the following cycles sequentially,
\begin{align*}
&\{s, 2s, \dots, p - 1\}\\
&\{s - 1, 2s - 1, \dots, p - 2\}\\
&\vdots\\
&\{1, s + 1, \dots, p - s\}
\end{align*}
From this it can clearly be observed that no valid $m$, $n$ pair exists.

Now for the other direction. Assume that $s \nmid p - 1$. Then say $sk$ is the largest $k$ such that $sk < p$. Then note that if $s(k+1)$ and $s-1$ are congruent modulo $p$ we have,
\begin{align*}
s(k+1) &\equiv s - 1 \pmod{p}\\
sk &\equiv - 1 \pmod{p}
\end{align*}
which in turn would imply that $s \mid p - 1$ contradiction. Hence we can set $m = k + 1$. Then take $n$ such that $sn \equiv s - 1 \pmod{p}$ which clearly exists as $\gcd(s, p) = 1$. Also $m < n$ from our conditions so this works.


analytic geometry
graphing lines
slope
quadratics

there are two shelters in a meadow, in the points A(2,1) and B(3,4). From a lake near from there two groups of mountaineers have marked two rectilinear paths, so that this two paths form an 90º angle between the two shelters and the lake. In which point is the lake, if it is known that is on x-y=2?

[hide]First, call the spot of the lake (x,y).  The slope of the lines (x,y) (2,1) and (x,y) (3,4) are $\frac{y-1}{x-2}$ and $\frac{y-4}{x-3}$.  Since they're perpendicular, $\frac{y-1}{x-2}$=$\frac{x-3}{4-y}$.  Then, since x=y+2, $\frac{y-1}{y}=\frac{y-1}{4-y}$.  This means y=4-y or y=2.  Subsequently, if y=2, then x=4.  Of course, this avoids the obvious answer of (3,1), but if cross-multiplication was employed after the subsitution, a quadratic would have been set up.  Rearranging the sides so one of them is zero, (y-1)(4-2y)=0.  Therefore, y could also equal 1 and x=3.  The answers are (4,2) and (3,1).[/hide]

I did this quickly and came up with $\left(4,2\right)$ and $\left(3,1\right)$.

$\left(3-x\right)\left(2-x\right)+\left(4-y\right)\left(1-y\right)=0$

then substitute $y=x-2$ and solve.


probability symmetry calculus integration

1. Let X and Y be random points in the unit interval [0, 1] (uniform and independent).
Find the standard deviation of the distance between X and Y .

2. Let X and Y be independent and identical Exponential random variables.
Find the cdf and pdf of X/Y
(b) Does E(X/Y ) = (EX)/(EY)?

3. A group of n people (n greater than 2) decide to play an exciting game of Rock-Paper-Scissors. As you may recall, Rock smashes Scissors, Scissors cuts Paper, and Paper covers
Rock. Usually this game is played with 2 players, but it can be extended to more players as follows. If exactly 2 of the 3 choices appear when everyone reveals their choice, and one beats the other, the game is decisive: the players who chose
a win, and the players who chose b lose. Otherwise, the game is indecisive and the players play again. For example, with 5 players, if one player picks Rock, two pick Scissors, and two
pick Paper, the round is indecisive and they play again. But if 3 pick Rock and 2 pick Scissors, then the Rock players win and the Scissors players lose. Assume that the n players independently and randomly choose between Rock,
Scissors, and Paper, with equal probabilities. Let X, Y,Z be the number of playerswho pick Rock, Scissors, Paper, respectively in one game.

(a) Find the joint pmf of X, Y,Z.
(b) Find the probability that the game is decisive. Simplify your answer (it should not involve a sum of many terms). (Hint: using symmetry, the probability can be written as 3 times a certain sum.)
(c) What is the probability that the game is decisive for n = 5? What is the limiting probability that a game is decisive as n approaches infinity? Why?

4. A stick of length L is broken into 3 pieces by choosing 2 random points X and Y on the stick uniformly and independently, and breaking the stick at those 2 points. What is the probability that the 3 pieces can be assembled into a triangle?
(Hint: Set up an integral, or interpret the problem geometrically: since (X, Y ) is uniform on a certain set, the probability of a subset is proportional to its area. You may find it helpful to first condition on whether or not X < Y .)


vector
parameterization
group theory
abstract algebra
calculus
integration
invariant

All notations follow Bourbaki, so may look  a bit different. But for many experts here, this should not be a problem.  :)

$ G$ is a Lie group, $ u$ is a non-zero vector in Lie algebra $ g_{e}$. And define $ v: R\to G$ by $ v(t)=exp(tu)$, this is one-parameter subgroup of $ G$ coresponding to $ u$. (where exp is exponential map and it well known that $ v(0)=e$).
It is well known that $ v(t)$ is the integral curve of the invariant field $ X_{u}(s)=s \bullet u$, i.e. $ v'(t)=X_{u}(v(t))=v(t) \bullet u$.

$ f: G\to R$ is $ C^{\infty}$, it is also well known that $ X_{u}$ is a differencial operator and act on $ f$, i.e.
$ X_{u}\bullet f$ is another $ C^{\infty}$ function $ G\to R$. It is defined by $ (X_{u}\bullet f)(s)=<d_{s}f, X_{u}(s)>$.

Now given $ f: G\to R$ is $ C^{\infty}$, and put $ g(t)=f(v(t))$. We calculate $ g'(t)$:
$ g'(t)=<d_{v(t)}f, v'(t)> = <d_{v(t)}f, X_{u}(v(t))> = (X_{u}\bullet f)(v(t))$

Then by simple calculation, we have:
the mth derivative of $ g(t)$ is $ g^{(m)}(t)=(X_{u}^{m}\bullet f)(v(t))$, where $ X_{u}^{m}$ means
composition of action $ Xu$ m times.

So we obtain the Taylor expansion of $ f(exp(tu))$, $ R\to R$:

$ f(exp(tu))=\sum_{m=0}^{\infty}\frac{t^{m}}{m!}(X_{u}^{m}\bullet f)(e)$.

Now remember exponential map is a local homeomorphism, so given a basis $ (u_{i})_{1\leq i\leq n}$ for $ g_{e}$, there is a homeomorphism: $ G\to R^{n}$ defined by $ w(t_{1},...,t_{n})=exp(\sum_{i=1}^{n}t_{i}u_{i})\to (t_{1},...,t_{n})$. This forms a chart in a nbh of $ e \in G$. So $ f(w(t_{1},...,t_{n}))$ is a smooth function $ R^{n}\to R$,

My question is why we can expand this function by, (write $ X_{u_{i}}=X_{i}$)

$ f(w(t_{1},...,t_{n}))=\sum_{m=0}^{\infty}((\sum_{i=1}^{n}t_{i}X_{i})^{m}\bullet f))(e)$ ?

am I supposed to prove that the 1st order partial derivative w.r.t $ t_{1}$ at $ (t_{1},...,t_{n})$ is:

$ \frac{\partial}{\partial t_{1}}f(w(t_{1},...,t_{n})) (t_{1},...,t_{n}) =(X_{i}\bullet f) (w(t_{1},...,t_{n}))$ ?
My book claims this follows easily from one-dim case, I tried to prove it in many ways, but can't get it. Please help.

I think $ f$ must be an analytic function for such an expansion to work.

Define a function $ h$ of one real variable $ v$ by $ h(v)=f(w(vt_{1},\dots,vt_{n}))$. Under the analyticity assumption we have $ h(1)=\sum_{m=0}^{\infty}\frac{1}{m!}\frac{d^{m}h}{dv^{m}}(0)$. But $ \frac{d}{dv}=\sum_{i=1}^{n}t_{i}X_{i}$ by the chain rule.

[quote="mlok"]I think $ f$ must be an analytic function for such an expansion to work.[/quote]

sorry, I forgot to mention these expansions are formal, no garatee of convergence, so analytic is not needed.

[quote] Define a function $ h$ of one real variable $ v$ by $ h(v)=f(w(vt_{1},\dots,vt_{n}))$. Under the analyticity assumption we have $ h(1)=\sum_{m=0}^{\infty}\frac{1}{m!}\frac{d^{m}h}{dv^{m}}(0)$. But $ \frac{d}{dv}=\sum_{i=1}^{n}t_{i}X_{i}$ by the chain rule.[/quote]

 :clap2: I tried many ways: from geodesics to defination of tangent space, and even tried to show
$ exp(u+v)=exp(u)exp(v)$ (which is not correct generally). Only get myself more confused.

This works. Let me write out the details:
Define a function $ h$ of one real variable $ \xi$ by $ h(\xi)=f(w(\xi t_{1},\dots,\xi t_{n}))$ for fixed $ (t_{1},...,t_{n})$. Let $ u=\sum_{i=1}^{n}t_{i}u_{i}$. So $ h(\xi)=f(exp(\xi u))$.
          Using the given results of one-dim case,  we have $ h'(\xi)=(X_{u}\bullet f)(exp(\xi u))$.
Note $ X_{u}(s)=s \bullet u=s \bullet (\sum_{i=1}^{n}t_{i}u_{i})=\sum_{i=1}^{n}t_{i}s\bullet u_{i}=\sum_{i=1}^{n}t_{i}X_{i}$ since $ s \bullet x$ is linear in $ x$.

So $ h'(\xi)= ((\sum_{i=1}^{n}t_{i}X_{i}) \bullet f) (exp(\xi u))$
So $ h'(0)= ((\sum_{i=1}^{n}t_{i}X_{i}) \bullet f) (e)$

As for higher derivatives, still using one-dim case: $ h^{m}(\xi)=(X_{u}^{m}\bullet f)(exp(\xi u))$
so $ h^{m}(\xi)= ((\sum_{i=1}^{n}t_{i}X_{i})^{m}\bullet f) (exp(\xi u))$

[quote="mlok"]Yes, but what about that $ \frac{1}{m!}$ in Taylor's formula?[/quote]

this is from Dieudonne's Treatise on analysis, formulor (19.9.2).
By checking the context, this should be a typo, this book missed this term.


I can't get the alignment right for a base number multiplication problem.

I'm trying to make it look like this with all the numbers in columns. but in the pdf, all the digits are shifted to one side or another

Can someone please tell me what the code is for this?:help:

yeah its octal (sry) but I dont know how to get it to look all aligned like that

Normally the [url=http://tug.ctan.org/cgi-bin/ctanPackageInformation.py?id=xlop]xlop package[/url] is great for is but it won't do octal yet until version 0.3 is out which is supposed to be soon. Meanwhile
[code]$\begin{array}{llll}
& 1 & 6 & 5 \\
\times & & 2 & 4 \\
\hline
& 7^3 & 2^2 & 4 \\
3^1 & 5^1 & 2 \\
\hline
4 & 4 & 4 & 4
\end{array}$[/code]looks like
\[ \begin{array}{llll}
& 1 & 6 & 5 \\
\times & & 2 & 4 \\
\hline
& 7^3 & 2^2 & 4 \\
3^1 & 5^1 & 2 \\
\hline
4 & 4 & 4 & 4
\end{array}\]


[quote="xscapezaer"](1996 National Team #4)

How many ways are there to write seven-element data lists of integers in numerical order to fit the following criteria: the mean is 20; the median is 21; the mode is 22 and unique; and the range is 10?[/quote]

[hide]
case 1: there are 2 22's

we have _ _ _ 21 22 22 _
if the last one is a 23 then we have 13 _ _ 21 22 22 23, whose sum is 101 so we need 39 more. The only way to do this within the restrictions is 19, 20, since 18, 21 results in 2 21's, then 22 is not a unique mode.
if the last one is a 24 then we have 14 _ _ 21 22 22 24, whose sum is 103, so we need 37 more. We can have 17, 20 or 18, 19.
if the last one is a 25 then we ahve 15 _ _ 21 22 22 25, whose sum is 105, so we need 35 more. We can have 16, 19, or 17, 18.
if the last one is a 26 then we have 16 _ _ 21, 22, 26, whose sum is 107, so we need 33 more. This, and every case above 26, is impossible.

so for case 1 we have 5 such sets

case 2: 3 22's

we have 12 _ _ 21 22 22 22, with sum 99, so we need 41 more. we can do this in only one way, 20, 21.

so for case 2 we have 1 such set

6 sets in total[/hide]


Έστω ημικύκλιο με διάμετρο $ AB$ και ακτίνα $ 2$. Κατασκευάζουμε τετράγωνο $ PQRS$ μέσα στο ημικύκλιο με $ P,Q$ πάνω στο ημικύκλιο και $ R,S$ πάνω στο $ AB$. Είναι το εμβαδόν του τετραγώνου μικρότερο ή μεγαλύτερο από το μισό του εμβαδού το ημικυκλίου?

Νομίζω κάπως στοιχειώδης είναι αυτή... αλλά ίσως να μην έχω καταλάβει κάτι στην εκφώνηση :)
[hide]Με συμμετρία και ένα Πυθαγόρειο, καταλήγεις στην ανισότητα $ \pi < 16/5$. Αν είναι γνωστή η τιμή του $ \pi$ τελείωσες. Aλλιώς, πάλι δεν έχεις πρόβλημα γιατί είναι πολύ χαλαρή η προσέγγιση... ακόμα και με το Αρχιμήδειο $ \pi < 22/7$ τελείωσες :)[/hide]

Cheerio,

Durandal 1707

[quote="Durandal"]Με συμμετρία και ένα Πυθαγόρειο, καταλήγεις στην ανισότητα $ \pi < 16/5$. Αν είναι γνωστή η τιμή του $ \pi$ τελείωσες, αλλιώς, είναι και πάλι δεν έχεις πρόβλημα γιατί είναι πολύ χαλαρή η προσέγγιση... ακόμα και με το Αρχιμήδειο $ \pi < 22/7$ τελείωσες :)

Βέβαια, [color=red]ίσως απλώς να μην έχω καταλάβει κάτι στην εκφώνηση [/color]:)

Cheerio,

Durandal 1707[/quote]

Μόλις έγραφα και εγώ απάντηση (<=> π μικρότερο του 3,2) αλλά με πρόλαβες.

Ναι, νομίζω και εγώ ότι το πρόβλημα είναι πολύ εύκολο για να μπει στο subforum ΟΛΥΜΠΙΑΔΕΣ, οπότε μου πέρασε από το μυαλό μήπως δεν έχω καταλάβει κάτι στην εκφώνηση. Ας μας διευκρινιστεί.

Τάκης

nai stoixeiodeis einai oi luseis. aplos tin vrika sto crux kai nomiza pos tha eixe endiaferon. :(