quadratics
geometry
trapezoid
number theory
relatively prime
Pythagorean Theorem
algebra

Circles $C_1$ and $C_2$ are externally tangent, and they are both internally tangent to circle $C_3$. The radii of $C_1$ and $C_2$ are $4$ and $10$, respectively, and the centers of the three circles are all collinear. A chord of $C_3$ is also a common external tangent of $C_1$ and $C_2$. Given that the length of the chord is $\frac{m\sqrt{n}}{p}$ where $m,n,$ and $p$ are positive integers, $m$ and $p$ are relatively prime, and $n$ is not divisible by the square of any prime, find $m+n+p$.

[hide="Solution!"]
Let $O_1, O_2$ be the centeres and $r_1 = 4, r_2 = 10$ the radii of the circles $C_1, C_2$, $O_1O_2 = r_1 + r_2 = 14$. Let the common external tangent  of $C_1, C_2$ meet the center line $O_1O_2$ at a point H. Let $T_1, T_2$ be the tangency points of the circles $C_1, C_2$ with their common external tangent. From the similar right angle triangles $\triangle HO_1T_1 \sim \triangle HO_2T_2$,

$\frac{r_2}{r_1} = \frac{O_2T_2}{O_1T_1} = \frac{HO_2}{HO_1} = \frac{HO_1 + O_1O_2}{HO_1} = 1 + \frac{O_1O_2}{HO_1}$

$HO_1 = O_1O_2 \cdot \frac{r_1}{r_2 - r_1} = r_1 \cdot \frac{r_2 + r_1}{r_2 - r_1}$

and by Pythagorean theorem for the right angle triangle $\triangle HO_1T_1$,

$HT_1 = \sqrt{HO_1^2 - O_1T_1^2} = r_1 \sqrt{\left(\frac{r_2 + r_1}{r_2 - r_1}\right)^2 - 1} = 2r_1\ \frac{\sqrt{r_1r_2}}{r_2 - r_1}$

Let O be the center and $r = r_1 + r_2 = 14$ the radius of the circle $C_3$. Since $O_1O = r - r_1 = r_2$,

$HO = HO_1 + O_1O = r_1 \cdot \frac{r_2 + r_1}{r_2 - r_1} + r_2 = \frac{r_1^2 + r_2^2}{r_2 - r_1}$

Let the common external tangent $T_1T_2$ of the circles $C_1, C_2$ intersects the circle $C_3$ at points A, B, so that the points H, A, B follow on the tangent in this order. Let T be the midpoint of the chord AB. Then $HT = \frac{HA + HB}{2}$. Since the angle $\angle HTO = 90^\circ$ is right, the right angle triangles $\triangle HOT \sim \triangle HO_1T_1$ are similar, $\frac{HT}{HT_1} = \frac{HO}{HO_1}$ and

$HA + HB = 2 HT = 2 HT_1 \cdot \frac{HO}{HT_1} = \frac{4 \sqrt{r_1r_2}}{r_2 - r_1} \cdot \frac{r_1^2 + r_2^2}{r_1 + r_2} =$

$= 4 \sqrt{r_1r_2}\ \frac{r_1^2 + r_2^2}{r_2^2 - r_1^2} = \frac{232 \sqrt{10}}{21}$

The power of the point H to the circle $C_3$ is equal to

$HA \cdot HB = (HO - r)(HO + r) = HO^2 - r^2 =$

$= \frac{(r_1^2 + r_2^2)^2 - (r_1 + r_2)^2(r_2 - r_1)^2}{(r_2 - r_1)^2} = \frac{4 r_1^2 r_2^2}{(r_2 - r_1)^2} = \frac{1600}{9}$

Substituting $HB = \frac{1600}{9 HA}$ or $HA = \frac{1600}{9 HB}$ into the formula for HA + HB leads to the same quadratic equation for HA or HB:

$63 x^2 - 696 x \sqrt{10} + 11200 = ax^2 + bx + c = 0$

Since HA, HB are the 2 roots of this quadratic equation, their difference is

$AB = HB - HA = \frac{\sqrt{b^2 - 4ac}}{a} = \frac{\sqrt{696^2 \cdot 10 - 4 \cdot 63 \cdot 11200}}{63} =$

$= \frac{8\sqrt{29^2 \cdot 10 - 7 \cdot 700}}{21} = \frac{8\sqrt{3510}}{21} = \frac{8\sqrt{390}}{7}$[/hide]

Please hide your answer. :dry: The point of these problems is not just for one person to solve them, but for others to try, as well.

Hmm.I got a different answer.

[hide]
Define $D$ and $C$ to be he center of the 2 internal circles. Therefore we have $CD=10+4=14$
Define $A$ and $B$ to be the points where the chord is tangent the 2 circles. On $C_2$ $A$, and on $C_1$ $b$.
Entend $DC$ and where it intersects $C_3$ will be $G$ and $H$.
Define $E$ and $F$ to be the places where the chord intersect $C_3$
Let $2a$  be the chord that passes through $D$ and is perpendicular to $CD$.
Therefore, we have $a^2=GD*DH=10*18=180$
We have $a=6\sqrt{5}$
Let $2b$ be the chord that passes through $C$ and is perpendicular to $CD$.
Therefore, $b^2=CH*GC=4*24=96$
Let $I,J,K$ and $L$ be points on $C_3$ where $2a$ and $2b$ intersect. $I$ and $J$ by 2a and $K$ and $L$ by $2b$
By Pythagorean Theorem, $AB=2\sqrt{58}$
We have:
$AI*AJ=80$, and also $BK*BL=80$ as well.
Let $EA$ and $BF$ be $z$ and $t$, respectively.
We have: $t(2\sqrt{58}+z)=80$ and $z(2\sqrt{58}+t)=80$,
Subtracting both equations from each other it reveals that $z-t=0$, therefore $z=t$
Substitute $t$ with $z$ and we have:
$z(2\sqrt{58}+z)=180$.
Solving the quadratic we get $z=\sqrt{138}+\sqrt{58}$
We want to find $EF= AB+2z=2\sqrt{138}$.
Therefore, $m+n+p=141$
And we are done.
[/hide]

[quote="JesusFreak197"]At first glance, I'm inclined to think that you messed up, since they would not have written it in fraction form if the answer wasn't in fraction form.[/quote]

Hmm. Maybe I did, but i think my method was correct... O well maybe a clculation mistake..

[quote="yetti"][quote="jimhu"]Define $D$ and $C$ to be he center of the 2 internal circles. Therefore we have $CD=10+4=14$
Define $A$ and $B$ to be the points where the chord is tangent the 2 circles. On $C_2$ $A$, and on $C_1$ $b$.
Entend $DC$ and where it intersects $C_3$ will be $G$ and $H$.
Define $E$ and $F$ to be the places where the chord intersect $C_3$
Let $2a$  be the chord that passes through $D$ and is perpendicular to $CD$.
Therefore, we have $a^2=GD*DH=10*18=180$
We have $a=6\sqrt{5}$
Let $2b$ be the chord that passes through $C$ and is perpendicular to $CD$.
Therefore, $b^2=CH*GC=4*24=96$
Let $I,J,K$ and $L$ be points on $C_3$ where $2a$ and $2b$ intersect. $I$ and $J$ by 2a and $K$ and $L$ by $2b$
By Pythagorean Theorem, $AB=2\sqrt{58}$[/quote]
The segment length of the common external tangent of 2 tangent circles $C_1, C_2$ with radii $r_1 = 4, r_2 = 10$ is indeed calculated by Pythagorean theorem, but it is equal to $AB = 2\sqrt{r_1r_2} = 2 \sqrt{40} = 4\sqrt{10}$.

[quote="jimhu"]We have:
$AI*AJ=80$, and also $BK*BL=80$ as well.[/quote]
I have no idea, how you got this or what is the purpose of knowing these products. Not only are they different from each other and neiter is equal to 80, but the points I, J, A are not collinear and the points K, L, B are not collinear either, so that $AI \cdot AJ$ or $BK \cdot BL$ are not powers of the points A, B to the circle $C_3$.

[quote="jimhu"]Let $EA$ and $BF$ be $z$ and $t$, respectively.
We have: $t(2\sqrt{58}+z)=80$ and $z(2\sqrt{58}+t)=80$,
Subtracting both equations from each other it reveals that $z-t=0$, therefore $z=t$.[/quote]
This should have stopped you, because it is obviously impossible for $r_1 \neq r_2$. It does not make sense to go through the rest. You MESSED UP. The answer $EF = \frac{8 \sqrt{390}}{7}$ (in your notation) is correct. Not only I checked it carefully the first time around, after you came up with a different result, I checked it again by drawing the figure with the Sketchpad.

Yetti[/quote]

Thanks.. Yea I msessed up...

here is my solution:

   The centers of circles C1 and C2 are on the diameter of C3.

   Consider the trapezoid formed by diameter of C3, common external tangent of C1

   and C2 and radii of C1 and C2 to tangency points.  Drop perpendiculars

   from tangency point X of C1 and C2  and from center O of C3 onto the

   common tangent line.  Perpendicular from X will pass through the trapezoid's

   diagonals intersection point and will have length  a = 2*r1*r2 / (r1+r2).

   The distance to this perpendicular from the shorter base of trapezoid ( radius of

   C1=4)  is equal to the distance from the longer base of trapezoid (radius r2=10)

   to the perpendicular from center  of C3 ( radius = 4+10).

   Thus the length of perpendicular p  to the midpoint of the tangent cord can be found

   from       a - r1 = r2 - p

   Now the length of tangent chord  is nicely calculated using Pythagorean theorem.

   The answer obtained by other approach in post #2 is correct, although one should

   keep in mind that this is an intermediate topics problem in High school forum.

   Thank you.

   M.T.

[quote="jimhu"]Yes, here's my "fixed" solution which is the easiest of them all...
[hide]
The radius of $C_3$ is 14. Let the centers of circles $C_1$ and $C_2$ be $A$ and $B$.
Let the point where $C_1$ and $C_2$ tangent to the chord be $C$ and $D$, respectively.
Let $E$ be the point where a segment is drawn through $A$ to $BD$.
Let $F$ be the center of $C_3$.
Let $G$ and $H$ be endpoints of the chord from the side of $C_1$ to the side of $C_2$, respectively.
The segment passing through $F$ perpendicular to $AE$ is 30/7 because similar triangles
The segment perpendicular to $GH$ through point $F$ is $6+30/7$.
Radius $AD=14$ and leg of length $6+30/7$ makes right triangle.
By Pythagorean Thereom,  $CD=8\sqrt{390}/7$.
$m+n+p=405$.
[/hide][/quote]

Very nice. E is the point where a [b]perpendicular[/b] segment is drawn through A to BD. You still have some typos in the solution - the segment perpendicular to GH through the point F is $r_1 + 30/7 = 4 + 30/7$ and $GH = 8\sqrt{390}/7$, not CD. It really pays off to be accurate.

Yetti

Sorry for bring up this post again.

I'm confused about how mcrawford derives FG=10/14(10-4) from the trapezoid on the math jam where FG is parallel to the two bases. Can anyone explain how this works? Thanks!

Extend the common external tangent to meet the line which contains all the centers of the three circle. Then, Use similar triangle

Here's what I did.  Correct me if I screwed up anywhere...
[hide]Draw them so that the equation of $C_3$ is $x^2+y^2=196$, with the center at $(0,0)$.  Circles $C_1$ and $C_2$ are drawn so that their equations are $(x+10)^2+y^2=16$ and $(x-4)^2+y^2=100$.  The point of tangency is at $(-6,0)$, so the chord’s equation is $x=-6$.  So if we plug it in to the equation of $C_3$, we get $(-6)^2+y^2=196$, or $y^2=160$.  So $y=\pm4\sqrt{10}$.  So the length is $8\sqrt{10}$.  So the answer is $8+10+1$ or $\boxed{019}$.[/hide]

I got $ 8\sqrt{10}$ if I draw the chord (green) of $ C_3$ *between* circles $ C_1$ and $ C_2$.  This chord meets the requirement of being externally tangent to both circles.  However, if I draw the chord (blue) of $ C_3$ so that it is tangent to circles $ C_1$ and $ C_2$ at two different points, then I get an answer of $ \frac{8\sqrt{390}}{7}$, which agrees with the answer key.  Why is the green chord incorrect?

Thanks!

A common external tangent is what the blue line is. The green line is not called a common external tangent. Rather, it is known as a common internal tangent.

I would like to say that if we extend the chord so that it intersects the extended diameter of the circle, then we can easily construct similar triangles and win.

Please don't revive extremely old threads like this one.


Find all f:R to R such that:
  f(x+y) + f(y+z) +f(z+x) >= 3f(x+2y+3z) for all x,y,z in R

y=z=0 give $f(0)\ge f(x)$
x=y=-z give $f(2x)\ge f(0)$.
Therefore $f(x)=const=f(0) \ \forall x$.

Are you sure ,Rust ?

f(2x) >= f(x) why we have f(x) is constant

1. $f(x)\le f(0) \ \forall x$.
2. $f(x)\ge f(0) \ \forall x \ (x-\ is \ 2x)$.
Therefore $f(x)=f(0) \ \forall x$.


summer program
MathPath
geometry
3D geometry
MATHCOUNTS
AMC
USA(J)MO

I went to MathPath in 2007 and can answer your question about the difficulty of MathPath classes.

The "History of Mathematics," one hour a day, is easy to understand and requires almost no advanced knowledge.

The guest lecture, which is given by several different speakers every day, is harder because some things like multiplying six digit numbers by each other mentally (Conway), Alternating Prime Matrices (Bressoud) and cutting a cake into pieces (not as easy as it sounds - Prof. Su)

The 50-minute breakout classes (two a day) are of flexible difficulty - you get to sign up for your classes for a week and each class is rated from 1 to 5 stars. Examples: Ramsey Theory, 5 stars; Rubik's Cube for Dummies, 1 star; Hyperbolic Geometry part 1, 2 stars.

The "Writing Mathematics," is a 30-minute class where solutions to the qualifying quiz are discussed and you are taught how to write solutions to mathematical problems.

I would also like to mantion another fun class: Problem Solving Breakouts. This is the same as regular breakouts except the classes prepare students for certain competitions. Examples: MathCounts, 1 star; USAMO, 4 stars.

Finally, the difficulty of all the activities (meals, trips, soccer [my favorite]) is not difficult, but instead very fun.

See you in Vermont!

Meh, I didn't go... Last Year, but I'm going this year.

the things at mathpath can change though, but I think those are the general things

Eh....
I thought you can pick all of your classes?

You can ask specific questions about difficulty or topics to be covered at the Math Jam, this evening.  Camp Founder, Dr. Thomas will be there, along with other officials and alumni.  They should be able to answer all your questions.

eh take all of zeitz's classes...he pwns

I'm pretty sure that in the Math Jam they said that Zeitz wouldn't be there this year.

[quote="dingzhou"]would this camp be good for people trying to get in the usamo and maybe a bit beyond?[/quote]

It will help some.  I know many of those who enter USAMO are former MathPath students.

What about people who just enjoy math, but maybe aren't as good as others?

I'm pretty sure that the classes have different difficulty levels, so you could just sign up for the easy classes if you think you're not that great at math.

There are many kids like this at MathPath.  Many have trouble during the first week because they feel "stupid" compared to other kids.  However, after about a week or so they fit right in.  If you know beforehand that there might be kids better than you at math, then you'll do fine.

The breakout sessions have different levels and you'll undoubtedly find one that is appropriate for your skill level.  Heck, even I understood some of them!

When I went to MathPath, because I thought I did poorly on the quiz, I believed that I would be completely blown away by others mathematically. I was pretty scared, actually, because I thought I wouldn't be able to keep up with anything. This turned out not to be the case at all. I did very well on the placement test (well, it was a bunch of MathCounts-like problems, an integral, and an AHSME problem which I was programmed to do), and learned a lot.

The difficulty of a class in stars, also, is not a good indicator of how interesting it is, or how much you will learn. I took a few easy classes in my first week (* Combinatorics, ** MathCounts even though I didn't sign up for it), and learned a thing or two (all right, maybe I didn't actually learn much in the Chapter MC class...), and found classes such as **** Inequalities, **** Problem Solving, and *** Linear Algebra just as interesting/fun.

Not to mention also the same day I pwned the placement test, I managed to get my glasses sucked into the Pacific Ocean, but that's another story.

Paul Zeitz (Dr. Z) will not be at MathPath next year. But his classes were fun.

THere was talk of only having two longer breakouts instead of three short ones....

If you can barely solve any of the MathPath quiz problems, would it be a bad idea to try to get into MathPath, or if I can go, go to the camp?

You should definitlely try to apply if you feel that you will learn something from attending MathPath. Last year the cutoff for the Quiz was about 3 or 4 problems.


Just got an acceptance letter form Georgia Tech. It feels really good to get accepted.  :lol:
Anybody hear from GT or any other colleges for that matter?

In at Michigan State!  :D
I'm visiting their campus next week (and I might get a personal tour of the math department while I am there).

[quote="zanttrang"][quote="PTynan89"]Has anyone gotten their decision letter from Caltech yet?[/quote]
I just received my acceptance today - I live in NorCal.  Probably it will take a few more days for other parts of the country.[/quote]

man, now i'm getting a little nervous about the caltech letter.

Also got my letter today.  :lol:  I'm from Michigan.


quadratics induction factorial function search algebra polynomial

okay, say i have a list of numbers (for ease, let's say the triangular numbers): 1, 3, 6, 10, 15, 21, etc, etc... how do you go about finding the equation that describes this list?? like, how do u arrive at x(x+1)/2??

i know the part about finding second differences, and that means its a quadratic, but i dunno how to go farther than that...

thanks

The most common method for this would be induction, but there are many ways....

You make a guess, and then prove it works for both k and k+1, and hence working for all values.

hmm, I don't think i answered your question... you look really hard at it? :)

Well, its often very difficult to do this with atypical sequences. For example, given the numbers 2403, 1298, 83, 18, 6563, ..., how would one possibly guess that the sequence can be described by (x^2 - 7)^4 + 2 ?

Wait. I don't understand the point of this thread. I mean, when will we ever need to recognize patterns like that right out of the blue? And even if we did need to recognize patterns, there would always be a context so we can try induction or algebraic simplification.

First you practice with a lot of easy ones like 3, 5, 9, 15, etc.
Then you try harder ones like the triangular numbers. If you did the first steps enough times, you begin to realize that there are different types of sequences such as factorial sequence.

Quite frankly the "sixth sense" that I talked about somewhere else is the only thing you can rely on for a problem like this...
My goal is to find the equation for all primes ([b]2[/b],3,5,7,11...)

I know of a way to cheat on sequences, but it's too complicated so I forgot...Does anyone know of a formula by Einstein (or some other famous person) which can figure out the formula to a sequence instantly?

To darkquantum
Sequences are everywhere. Combinations, the least amount of steps it takes to do something, and on and on and on...
It's just that no one bothers to make a formula for it since it's too obvious...

I shall impress the concept further: 1 is not prime!  8-) Otherwise, the notion would violate the fundamental theorem of arithmetic, as then integers could not be uniquely expressed as a product of powers of primes.

Just remember the proper definition of a prime: a prime has exactly two factors. Easy. (not the fake definition you get taught when you first learn about primes, that they are divisible by 1 and itself. Thats just easier to remember for most people).

Usually when you solve a problem and you get a sequence, you can tell where the sequence came from. Thus maybe you know a recursion or something. Then you can use generating functions or whatever you want to figure out what its closed form is. If you have a sequence of random numbers, look it up in Sloane's Encyclopedia of Integer Sequences.

[quote]If you have a sequence of random numbers, look it up in Sloane's Encyclopedia of Integer Sequences.[/quote]

Yeah, at http://www.research.att.com/~njas/sequences/

never mind, i figured it out...

look up 'finite differences' on google or sumthing

basically, find the degree of the equation that generates that sequence (for example, let's say its a cubic), then just have something like ax^3 + bx^2 + cx + d, and plug in x = 1, 2, 3, 4, 5, etc, etc, and solve for a, b, c, and d using the  1st, 2nd, and 3rd differences...

anyways, search on google for a more in depth explanation, but this works, as long as you reach a common difference at some point...

I'll try to address the question which was posted first.
If you wanna find how to prove n(n+1)/2 there is an interesting combinatorics argument thats pretty elegant. Can you think of a possible combinatorics identity that could come into use? I know it sounds pretty whizack but you gotta think hard on this one...

that method works for polynomials, but what about a sequence like ln n? A table of differences won't help there.

"better" definitions of a prime:

let p be a prime.

one potential definition: (primality)

if p | ab, then p|a or p|b.

second definition (irreducibility)

if p = ab, one of a, b is a unit

a unit is an element of a ring which has a multiplicative inverse


Tom is twice as old as Harry was when Harry was one-third as old as Tom will be when Tom is as old as Harry is now. If the difference in their ages is 666, how old is Harry?

[hide]
let $H$ be Harry's age now

If we go backwards in the statement:
"...when Tom is as old as Harry is now."
Tom's age is $H$
"...when Harry was one-third as old as Tom will be ..."
$\frac{1}{3}H$
"Tom is twice as old as Harry was..."
Tom's age is $\frac{2}{3}H$

Since the difference between their ages is 666:
$H - \frac{2}{3}H = 666$
$\frac{1}{3}H = 666$
$H = 1998$

Is Harry 1998 years old?
[/hide]

EDIT : Darn, one minute after. And I thought I was going to get the first reply. >_>

[quote="chess64"][hide]Let's say Harry is $h$ years old. Then Tom's age is $2h/3$. Hence $h-2h/3 = 666$, so $h=\boxed {1998}$.[/hide]

The whole problem seems unrealistic, though... :huh:[/quote]
unrealistic......tom and harry are not neccessarily humans ;)  anyway 1998 is correct.

Er...name an animal that can live for 2000 years, please. (Or a plant if you prefer [or even bacteria]) :D

An animal that can live for 2000 years: humans if you freeze them in a freezer for 2000 years than wake them up
plant: easy any tree
bacteria  :?


geometry
number theory proposed
number theory

An integer which is the area of a right-angled triangle with integer sides is called [i]Pythagorean[/i]. Prove that for every positive integer $n > 12$ there exists a Pythagorean number between $n$ and $2n.$


modular arithmetic
number theory
least common multiple
Divisibility
IMO Shortlist

I've found $ \boxed{n = 2^{1988}}$.

Since $ m^n\equiv 1\pmod{2^{1989}}$ holds $ \ \forall m\in \mathbb{N}$,  $ n$ has to be the $ \textrm{lcm}$ among every $ \textrm{ord}_{2^{1989}}(m_i)$ which means $ \big(n, \textrm{ord}_2^{1989}(m)\big)\not = 1$.

Being $ \textrm{ord}_{2^{1989}}\vert \phi (2^{1989}) = 2^{1988}\Rightarrow n = 2^{a}, \ a\in \mathbb{N}$.

Again to the congruence: $ m{}^2{}^a - 1\equiv \underbrace{(m - 1)(m + 1)(m^2 + 1)(m^4 + 1)\cdots (m{}^{2{}^{a - 1}} + 1)}_{2^a \ \textrm{factors}}\equiv 0\pmod{2^{1989}}$

If there exist two of this factors (except "$ m - 1$" which we cannot evaluate with the others) such that $ m{}^{2{}^{k}} + 1\equiv m{}^{2{}^{j}} + 1 \pmod{2^{1989}}$ or we get to the absurd $ m\equiv 0\pmod{2^{1989}}$ or for example, $ m{}^{2{}^i}\equiv 1 \pmod{2^{1989}}$. Now, since $ m{}^{2{}^i} - 1\vert m{}^{2{}^a} - 1$ we get what we wanted. We exclude now this case and suppose that all the remainder are different (always excluding "$ m - 1$").

We know that all the remainder will be even, since $ m$ is odd. So, all die possibile remainder are $ 2^{1988}$.

To be sure that there is a "$ 0$" in those factors, $ 2^a\ge 2^{1988}$ so, $ n = 2^a = 2^{1988}$.

Is it right?

let $ a$ be greatest number $ 2^a\parallel{}m\minus{}1$.
then prove that $ 2^{1889}\parallel{}m^{1889\minus{}a}\minus{}1$.

you con refer to imo compendium book.if you can 't tell me ican write the solution for you.

[quote="orl"]Let $ m$ be a positive odd integer, $ m > 2.$ Find the smallest positive integer $ n$ such that $ 2^{1989}$ divides $ m^n \minus{} 1.$[/quote]
I think that this problem statement is a bit ambiguous (or I am not understanding properly). I have also got the ans $ 2^{1988}$ (like EUCLA).
But the solution in IMO compendium gives a bit general result. They says that $ 2^{1989 \minus{} s}$ if $ s \leq 1989$, and $ n \equal{} 1$ if $ s > 1989$ where $ s \in \mathbb{N}$ is the maximal integer satisfying $ m \equiv \pm 1\pmod { 2^s}$.

Now my question is, which answer is correct? Though the solution of IMO compendium is more precise, I think that the problem just asks for the smallest $ n$ which works for [b]every[/b] $ m$.

[quote="Moonmathpi496"]I think that the problem just asks for the smallest  which works for [b]every[/b] $m$.[/quote]
Yes, this interpretation seems to be the correct one.

But I don't think the answer is $2^{1988}$. Note that when $2^{1989}$ is replaced with $2^3$, then $n=2^1$ suffices. Similarly with $2^4$, then $n=2^2$ suffices. Then we can use induction:
EDIT: Took me a while to realize that it wasn't actually induction  :oops_sign:

If $m$ is odd, then $m^2=8x+1$ for some $x\in\mathbb{N}$. Thus

\[m^{2^{1987}}=(8x+1)^{1986}\equiv 1\bmod{2^{1987}}\]

from the Binomial Theorem. But I'm not sure how to show that this is the minimum such $n$...

Hint : Show that $3^{2^{n-3}} \equiv 1 + 2^{n-1} \pmod{2^n}$ by applying induction for $n \ge 3$.

You can use LTE when m=3. It yields the desired result.


find the distance between points a and b.
A(-4,3)
B(-7,8)

[hide="Hint"]$d=\sqrt{(x-x)^2+(y-y)^2}$[/hide]

actually, because $x$ and $x$ could be taken to be the same value, you should write it:

hint:
[hide]$d = \sqrt{(x_{2}-x_{1})^2+(y_{2}-y_{1})^2}$[/hide]

but i'll let someone else solve it ;)

i didn't know how to do subscript.sry :blush:

subscript goes like this:

x_{1}

becomes

$x_{1}$

thanks, and you can post the answer if you want to.

[hide]
$\sqrt{(-7-(-4))^2+(8-3)^2}$ = $\sqrt{34}$

It would've been nice if $y_{2} - y_{1}$ was 4, so the distance would've been 5.  [/hide]

This is the Basics Forum. Most people don't even know what an incenter is, probably.

[quote="cezar lupu"]come on, what's this? At least you could ask which are the incentre coordonate if A(a,b) ,B(b,c),C(c,a).[/quote]
that's a little hard

ok then do the circumcenter. that's easier

[hide="Click to view my answer"]
[tex]\vec{AB}(-3;5)[/tex]
Therefore [tex]AB = \sqrt{(-3)^2 + 5^2} = \sqrt{34}[/tex].[/hide]

[quote="gr8sk8r"]correct. now for a continuation. what is the midpoint between A(-4,3) and B(-7,8)

[hide="hint"]this time, no hint[/hide][/quote]
[hide="???"]$(-\frac{3}{2},\frac{5}{2})$?[/hide]


try finding an elegant solution to this one

find the sum of reciprocals of the products of the numbers in all the non empty subsets of
{1,2,3,4..........................................2007}
enjoy

[hide]
$\left(1+\frac{1}{1}\right)\left(1+\frac{1}{2}\right)\cdots\left(1+\frac{1}{2007}\right)=\left(\frac{2}{1}\right)\left(\frac{3}{2}\right)\cdots\left(\frac{2008}{2007}\right)=2008$
Subtract one because I'm not supposed to include the empty subset
$2008-1=\boxed{2007}$
[/hide]

tjhance, how did you get that first equation?

[hide="my solution, very simple"]
Let's look at the results from smaller sets to see if we can set up some sort of general equation for a set of the first $n$ natural integers. We can shorten the time to calculate each slightly by removing 1 from the set and then doubling the result and incrementing it by one.

\begin{eqnarray*}\{1\}&\rightarrow& 1 \\ \{1,2\}&\rightarrow& 2\cdot\frac{1}{2}+1 = 2 \\ \{1,2,3\}&\rightarrow& 2\cdot(\frac{3}{6}+\frac{2}{6}+\frac{1}{6})+1 = 3 \end{eqnarray*}

Hmm. See a pattern? The answer is therefore $\boxed{2007}$.[/hide]

[quote="worthawholebean"]tjhance, how did you get that first equation?

[/quote]
$(1+x_{1})(1+x_{2})(1+x_{3})(\dots) = 1+Sum \ of \ (products \ of \ all \ possible \ combination \ of \ x_{1},x_{2},x_{3}\dots )$


This inequality is well-known
      Sa(b-c)^2+Sb(c-a)^2+Sc(a-b)^2 >=0 (well-known as SOS inequality)
  but my question is how to find Sa,Sb,Sc???? and when we can apply this SOS inequalty???
                                                                                THANK YOU

Sa,Sb,Sc is sum .If don't understand you can know that Sa=x;Sb=y;Sc=z


limit
calculus
derivative
function
trigonometry
calculus computations

If $ f: D\rightarrow \mathbb{R}$ is differentiable at $ c \in D$ and if $ c\plus{}\frac{1}{n} \in D$ for all $ n \in \mathbb{N}$, how would I show that $ f'(c) \equal{}\lim n({f(c \plus{}\frac{1}{n}) \minus{}f(c)})$?

Also, could someone explain how the existence of this limit does not imply the existence of the derivative?

Thanks

Note: $ \lim_{x\to a}g(x)\equal{}L$ if and only is $ \lim_{n\to\infty}g(x_n)\equal{}L$ for all sequences $ x_n$ such that $ x_n\ne a$ but $ \lim_{n\to \infty}x_n\equal{}a.$

The "for all" is very important here, but even without that, the existence of the function limit will imply the existence of the sequence limit for [i]some[/i] such sequence.

For the counterexample, consider

$ f(x)\equal{}\begin{cases}\sin\left(\frac{\pi}{x}\right),&x\ne 0\\0,&x\equal{}0\end{cases}.$


calculus
integration
limit
real analysis
real analysis solved

Hi, I need to solve this defined integral:
[img]http://www.geocities.com/paolayeye/riemann.jpg[/img]
Please post all the steps. I really need it, ¡s urgent!

only using riemann sum, that's the problem :S

Using integral by parts,

$\int_5^2 xe^x dx=\left[xe^x\right]_5^2 -\int_5^2 e^x dx=\cdots =e^2-4e^5$

What is the integral? I cannot see the picture.

We partition $[a,b]$ into $n$ equal parts. $x_i=a+\frac{(b-a)i}{n}$
$\int_a^b xe^xdx = \lim_{n\to\infty} \sum_{i=1}^{n} \left(a+\frac{(b-a)i}{n}\right)\exp\left(a+\frac{(b-a)i}{n}\right) = \lim_{n\to\infty}\left(ae^a\sum_{i=1}^{n} e^\frac{(b-a)i}{n} + e^a\sum_{i=1}^{n} \frac{(b-a)i}{n}e^\frac{(b-a)i}{n}\right)$

We need to simplify the sum, hence we need to find a closed form for
$S = ye^y + 2ye^{2y} + \cdots + nye^{ny}$
Multiply it by $e^y$, we have
$e^yS = ye^{2y} + \cdots + nye^{(n+1)y}$
Substract the latter one from the previous one,
$(1-e^y)S = y(e^y + e^{2y} + \cdots + e^{ny}) - nye^{(n+1)y} = ye^y\frac{1-e^{ny}}{1-e^y}-nye^{(n+1)y}$
hence
$S = ye^y\frac{1-e^{ny}}{(1-e^y)^2} - \frac{nye^{(n+1)y}}{1-e^y}$

Thus the sum can be simplified into (let $\delta = \frac{b-a}{n}$)

$
ae^ae^\delta\frac{1-e^{n\delta}}{1-e^\delta}  + e^a\left(\delta e^\delta \frac{1-e^{n\delta}}{(1-e^\delta)^2} - \frac{n\delta e^{(n+1)\delta}}{1-e^\delta} \right)
$

We have $\lim_{n\to\infty} \frac{\delta}{1-e^\delta} = -1$ and $\lim_{n\to\infty} e^ae^{n\delta} = e^b$

Finally we can find out the limit, which is $e^a(1-a)-e^b(1-b)=e^b(b-1)-e^a(a-1)$

Basically, it's shorter to prove the fundamental theorem of calculus  :P

After all, what should we do to this problem? Isn't this problem a simple calculation? :mad:

well..he wants to use Riemann sum, that is to say, he wants to use the definition of definite integral..

thanks for the help guys!! , liyi thanks a lot!!!!!!!!!!!!! :)


Can someone give me some help here:  studying for an exam in a couple of days.  Show there is no continuous function of $ \mathbb{R}$ onto the countable product of open intervals.

[hide="Hint"]
You cannot exhaust $ (0,1)^{\aleph_0}$ by countably many compact sets (the coordinate functions should attain their minima on those compact sets and you can create a sequence that tends to $ 0$ faster than any countable family of sequences of positive numbers) ;).
[/hide]


Is it true that for every odd number not divisible by 5, there's a multiple of that number that can be written with only 1's? What's the proof?

Yes it is true. Because the number is odd and not divisible by $ 5$, it is coprime with $ 10$. Now, look at numbers $ 1, 11, 111,....$. By Pigeonhole Principle, as there are finitely many remainders that can exist for that particular number $ a$, and infinitely many numbers made up of only $ 1$s then there will exist two numbers made up of only $ 1$s giving the same remainder when divided by $ a$. Subtracting the smaller of them from the larger gives a number divisible by $ a$ of form:
$ B \equal{} 111...11100...000$, but as $ a$ is coprime with $ 10$ and $ B$ is divisible by $ a$, so the part of $ B$ without all the zeros at the right end is still divisible by $ a$ so we get a number of form $ 111...111$ divisible by $ a$ QED.

Use Euler function
$ x_{n}\equal{}\frac{10^{n}\minus{}1}{9}$
For each $ \gcd(a,10) \equal{} 1$ we can chose n such that $ a|x_{n}$(Example $ n \equal{}\varphi(9a)$


AMC
USA(J)MO
USAMO
combinatorics proposed
combinatorics

A maths exam has two papers, each with at least one question and $28$ questions in total. Each pupil attempted $7$ questions. Each pair of questions was attempted by just two pupils. Show that one pupil attempted either nil or at least $4$ questions in the first paper.

No interest in this one. I believed that because is very similar to IMO 2005 it will attract many solvers, but I failed :blush:


hello, do you mean $ 7\sqrt{2}x^2\minus{}10x\minus{}4\sqrt{2}$
Sonnhard.

probably. How would you factor it? I got up to $ 7x(x\sqrt{2}\minus{}2) \plus{} 4(x\minus{}\sqrt{2})$. I don't know if you can go any further with it...

modular..., which level do u study in? middle school?

yea im in 8th grade.

EDIT: Yea i think i found how to factor it more. $ 7x\sqrt{2}(x\minus{}\sqrt{2}) \plus{} 4(x\minus{}\sqrt{2}) \equal{} (7x\sqrt{2}\plus{}4)(x\minus{}\sqrt{2})$.

[quote="modularmarc101"]probably. How would you factor it? I got up to $ 7x(x\sqrt {2} \minus{} 2) \plus{} 4(x \minus{} \sqrt {2})$. I don't know if you can go any further with it...[/quote]

Since $ x\sqrt {2} \minus{} 2 \equal{} \sqrt {2}(x \minus{} \sqrt {2})$, expression above turns into:

$ 7\sqrt {2}x(x \minus{} \sqrt {2}) \plus{} 4(x \minus{} \sqrt {2})$.

Thus, the factorization of the original expression is $ (7\sqrt {2}x \plus{} 4)(x \minus{} \sqrt {2})$.

Answer: $ (7\sqrt {2}x \plus{} 4)(x \minus{} \sqrt {2})$

EDIT: Bleh, beaten.


[quote="236factorial"]How many three-digit positive integers are divisible by 5 and 11?[/quote]

[hide]The LCM of 5 and 11 is 55 so the numbers we desire are three-digit numbers that are divisible by 55. And those are:

110, 165, 220, 275, 330, 385, 440, 495, 550, 605, 660, 715, 770, 825, 880, 935, 990

That makes $\boxed{17}$[/hide]

Did you seriously go and list/find every multiple of 55 that's between 100 and 999? :dry:

[hide]  If a number is divisible by 5 and 11 it is divisible by 55.

Smallest 3-digit number divisible by 55:

$55 \cdot 2 = 110$

Largest 3-digit number divisible by 55:

$55 \cdot 18 = 990$

$18 - 2 + 1 = \boxed{17}$ such numbers. [/hide]

[hide]LCM of 5 and 11 is 55.

2 numbers for every 100 except for the 5's so it's 18-1=[size=200]17[/size][/hide]


you can prove it using calculus or the Taylor series for 2^x.

I don't know any elementary way of doing this. :(

[quote="Attila the Hun"][quote="Virgil Nicula"] [b]Prove that[/b]

$ 0\ \le\ x\ \le\ 1\ \implies\ 1 + x^2\ \le\ 2^x\ .$

$ 1\ \le\ x\ \le\ 2\ \implies\ 2^x\ \le\ 1 + x^2\ .$[/quote] [b]You can prove it using calculus or the Taylor series for 2^x.
I don't know any elementary way of doing this.[/b] :([/quote]

I met it when I tried to solve the system $ \{\begin{array}{c} x + \sqrt {2^y - 1} = 2 \\
 \\
y + \sqrt {2^x - 1} = 2\end{array}$ without derivatives ...


pigeonhole principle
calculus
integration
summer program
Mathcamp

Solve:

 Prove that some integral power of 2 has the decimal expansion which starts with the digits 2004:

2^n = 2004...

Using pigoenhole principle.

This is a specific case of a much more general question: Given some string of digits S (here S = 2004) does there exist some n such that a^n begins with S, for a given a that is not a power of 10 (here a = 2)? The answer is yes, and, in fact, infinitely many such powers exist. I've outlined a proof of this bellow, which I owe to Brenda the Mathcamp Mentor.

[hide]

It's fairly easy to see that, if some power of a does start with the string S,

then the following equality must hold:

S.10^t :le: a^n < S.10^(t+1), taking log base 10 gets

t + log(S) :le: n.log(a) < t + log(S + 1)

In any given case, S and a are given and t and n are both integers.

Imagine what this equality looks like if we write it out on the number line for all values of t (i.e. all integers).

Between every t and t + 1, there are the two corresponding values of

t+ log(S) and t + log(S + 1) - the question is, does an integral multiple of log(a) lie between any such pair of these values.

We use the Pigeon Hole principle to answer yes.

So, using your good visual imagination, wrap the aforementioned number line around a circle with unit circumference. Every integer will fall on the same point. Also, t + log(S) and t + log(S + 1) will all fall on the same point regardless of t; call these points p and q, respectively. Now, calling the integral multiples of log(a) our pigeons, our question is, must at least one pigeon land in the hole between p and q.

Lemma: At least two integral multiples of log(a) fall within a distance of q - p of each other. If we stake out our circle with arcs of length q - p, then the only way for this lemma to be false would be if no two multiples of log(a) fell in the same such arc. The only way for this to happen would be if all of the multiples of log(a) continuously fell on the same set points that were spaced apart by a distance greater than q - p. Otherwise, if all of the multiples did not fall on the same points, by PHP, eventually one would fall within a distance of q - p from another. But, the only way for the multiples of log(a) to always fall on the same points around this circle with circumference 1, is if log(a) was rational. The only way for log(a) to be rational is if a is a power of 10, but that was precluded in the setup of the problem.

End lemma.

Let the first of these two multiples within q - p of each other be i.log(a) and the second be (i + j)log(a). Then, consider the sequence of multiples given by (i + r.j)log(a) for r an integer. Each will be a distance less than

q - p from the one preceding it, and thus, eventually, (i + r.j)log(a)  will lie between p and q. In fact, since we can keep increasing r as much as we want, infinitely many such multiples will lie between p and q. Thus infinitely many powers of a begin with the string S.

Q.E.D.

[/hide]

Of course, this gives us no way to actually find these powers; and, indeed they are very large. 2^53 is the first power of 2 to start with a 9, for example. But nonetheless, the proof of such powers' existence is there. Yay!


Find all functions $ f: \mathbb R\longrightarrow \mathbb R$  such that for each $ x,y\in\mathbb R$:
$ f(xf(y)) \plus{} y \plus{} f(x) \equal{} f(f(x \plus{} y)) \plus{} yf(x)$

Let $ f(0) \equal{} k$

x=0 gives $ 2k \plus{} (1 \minus{} k)y \equal{} f(f(y))$

__________________________

x=1 gives $ f(f(y)) \plus{} y \plus{} f(1) \equal{} f(f(1 \plus{} y)) \plus{} yf(1)$

$ 2k \plus{} (1 \minus{} k)y \plus{} y \plus{} f(1) \equal{} 2k \plus{} (1 \minus{} k)(1 \plus{} y) \plus{} yf(1)$

$ 2k \plus{} (1 \minus{} k)y \plus{} y \plus{} f(1) \equal{} 2k \plus{} (1 \minus{} k)y \plus{} (1 \minus{} k) \plus{} yf(1)$

$ y \plus{} f(1) \equal{} (1 \minus{} k) \plus{} yf(1)$

----y=0 gives $ f(1) \equal{} (1 \minus{} k)$

----$ y \equal{} yf(1)$

----y=1 gives $ f(1) \equal{} 1$ so $ 1 \minus{} k \equal{} 1$ <--> $ k \equal{} 0$

_____________________

Therefore $ f(f(y)) \equal{} 2k \plus{} (1 \minus{} k)y \equal{} y$

$ f(xf(y)) \plus{} y \plus{} f(x) \equal{} x \plus{} y \plus{} yf(x)$

$ f(xf(y)) \plus{} f(x) \equal{} x \plus{} yf(x)$

y=1 gives

$ 2f(x) \equal{} x \plus{} f(x)$

$ f(x) \equal{} x$

Checking the solution:

$ xy \plus{} y \plus{} x \equal{} x \plus{} y \plus{} xy$

$ 0 \equal{} 0$

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

Q.E.D. :P


calculus integration Harvard college MIT

does iit show the question paper of iitjee. I have heard somewhere that iitjee qp comes as memory based.

iitjee is an exam conducted by iits(13 or 14of them,i forgot)where noobs like me and u score about 50% and the rest of the world scores 80% or so so
and u pray for miracles to happen in the result.. :)and u clear the cut off u get a seat in one of the iits and thts it i guess

[quote="sumanth0811"]thts it i guess[/quote] and thats not it  :mad:

u find that wether u can prgrm is immaterial for cs some muggu from kota gets it but he doesn't know how to operate a comp.

u find tht ur passion for electronics is immaterial for eee and someone who cant even solder gets it.

u find tht u like chem but cant get chemical engineering (like me) bcoz someone who got 10 marks more than u took it, and now he is sulking bcoz he wanted mechanical and he doesn't like chemistry.

and u r sitting with paper and pulp engineering in roorkee  :rotfl:

good one sagar!!!

well uve got 2 mug neway.......
mugging is a must,since u ought 2 no the theory for solving the problems......
basically from all the people who manage 2 mug , the more intelligent ones get in.......
n as i type here, there are people in kota and ramaihaa(or watever it is) who are mugging at present  :rotfl:  :rotfl:
so ttis very tough   :P

[quote="franklampard8"]good one sagar!!!
basically from all the people who manage 2 mug , the more intelligent ones get in[/quote]
thnk u :lol:

the hardworking ones make it and not those who blindly mug.

[hide]
m prakash sir must be telling u to study 12 hrs a day.
i always felt his advice was crap and never studied for more than 6 hrs.
if i had paid heed to his advice, i wudn't have ended up wit this shtty score in jee
[/hide]

I want question paper of iitjee 2009 exam. Are the question paper shown by iit after exams?

eh have you tried the google. It is a very good site.

[quote="Sagar_Vaze"]
m prakash sir must be telling u to study 12 hrs a day.
i always felt his advice was crap and never studied for more than 6 hrs.
if i had paid heed to his advice, i wudn't have ended up wit this shtty score in jee
[/quote]

Cliched.

well mugging...

i m bio guy
ppl expect me to mug lik hell

and i m no good :(

and i can do nething which doesnt requires mugging :)

[quote="Conjurer"]
Dont let posts like above, the white tiger, 5 point someone, slumdog millionaire et cetera give you a false impression of the sub continent's best technical institute.

[/quote]

The sub-continent's? You mean amongst those poor countries like Afghan, Sri Lanka, Bangladesh, Pak etc. IITs are the best in terms of brain-value and competition!

Here are a few pics I, erm... stole...  :oops:

You cannot score anything by mugging in JEE ,maybe in inorganic but thats all. What else is worth mugging? The formulas? The solution maybe simple as just applying a formula but still the question is so framed that you have to give a thought atleast.

@Rajiv: I didnt get you! Are you saying IIT sux now?

probably not mugging but u need loads of hardwork, solving millions of sums of maths f.i in integration

[hide]
i am so weak in maths that i cudn't solve an indefinite integral from my hsc boards  :rotfl:
[/hide]

and no one knows what happens at time of exam.
i know one guy from my batch (i will not name him here) who is extremely hardworking and intelligent having solved all arihant level 3 stuff....clearing rmo with gr8 marks....getting gr8 percentile in fitjee....he used to even advise me to not waste my time like some wise man[hide]if he reads it, he'll surely know i am talkin abt him, bt most probably he is studying for bits than visiting aops[/hide] all sirs belived he wud make them proud. in the end he is scoring 250 in jee  :rotfl:
[hide]
i think i was pleased when i heard this  :ninja:
[/hide]

@sagar_vaze
don't be mean!!
JEE unfortunately is  like 1-day or 20-20 match.
Actually they should conduct series of tests over 2 yrs and take the average score as JEE score!!

No, imagine the kind of stress it would bring to students! I guess, the JEE is all right, but you should have the oppurtunity to apply to IIT with your other achievements like olympiads, national sports, poetry etc. the way you do in other countries and get admitted before JEE actually takes place.
THAT should take into account whether you can operate a computer like a geek, whether you can solder with an artist's finesse, whether you can contribute to the world of mechanics or you are better off doing paper and pulp.....
JEE should still be retained simply coz not everybody gets equal opportunities.

[quote="nuclear_alchemist"]No, imagine the kind of stress it would bring to students! I guess, the JEE is all right,[/quote]
I don't get it: I could have diarrhea on the day of the JEE; all that two years of slogging would be flushed down the toilet (perhaps that wasn't the right figure of speech).

[quote]but you should have the oppurtunity to apply to IIT with your other achievements like olympiads[/quote]

True. The olympiads seem to get the cold shoulder. I can't recall the last time an IMO medalist's picture appeared on the front page of TOI. China seems to (marginally) get this right. Look at the number of IMO/IOI gold medals they get.

[quote]national sports, poetry etc.[/quote]
Yeah, so you can throw a ball into a hoop? Come join our finest technical institutes!

[quote="Rajiv"][hide="Sagar,"]you seem to be a Brahmin to the core, like I?[/hide][/quote]

yo a proud kobra (konknastha brahmin) complete with the trademark fair skin and pointed chin,nose of kobras  :D
[hide]
although i don't have those grey eyes a marathi person wud expect frm 'ghare-gore kobras'  :(
[/hide]

Hey! Is [i]Kobra[/i] the official alias for you [i]Koknasta[/i]s? I have heard that so many times before. I have same features, fair skin, pointed chin, sharp cheekbones and a thin frame.

KBs are [i]kanjus[/i], there's no debating that!

sorry ur out, i can't find ur surname here http://www.kokanastha.com/htm/p_surname.htm  :rotfl:

and yeah i'm extremely kanjus too, got a reputation abt being so :wink:
[hide]
perhaps i'll find it even more difficult to find a date in iit, since nowadays girlz run after money only :mad:
[/hide]

i thot u meant that wen u said u have that fair skin nd sharp cheekbone etc

we bamans sound like neo-nazis no wonder other communities hate us in india  :rotfl:

[hide]
as if we care  :P
[/hide]

Yet, the noblest jobs in India were done by [b]us[/b]. Tilak and Godse to name the best!

u idolize godse too like me :omighty:
cool to find such a person, coz nowadays one gets to see only those gandhigiri brainwashed sissies

u must read the buk 'may it please your honour' by n v godse. it's absolutely fantastic. it's his court statement. exposes the true nature of that [hide="so called father of nation"]evil maniac[/hide] and his [hide="chamcha"]prime minister[/hide]

'mi nathuram godse boltoy' was present on youtube. if you don't find it a cousin of mine has downloaded it. i can send it to you wen i visit him.

Great! I'll for hunt it!

[hide]Lunch time, see you later![/hide]

 :(

[quote="rituraj007"][quote="Rajiv"]Nehru was an a**! [i]Hindi Chini bhai-bhai![/i] They visited the Ordinance factory in Pune before going to war against us. I'll read this book! I was planning to watch [i]Me Nathuram Godse boltoy[/i] at Bal Gandharva but they told me I need to be $ 18$.[/quote]
it seems u hav not seen adult movies earlier :rotfl:[/quote]

itz not a movie, itz a play which chronicles godse's life and his gr8 sacrifice fr india's gud

and bal gandharva is a famous theater in pune which is infested with jobless and useless old ppl who hv nothing better to do than watch plays and show-off their hypothetical artistic side :rotfl:

good..it seems similar to a english story i read this yr (i dont even remember the name :rotfl: )

What are the criteria for branch change in IITs?
Will getting through IOITC help me change my branch to comp sci or math and computing?

criteria is gpa during 1st yr and i've heard they also take ur previous branch into account  :o


calculus
integration
number theory proposed
number theory

Nice, but unfortunately, exactly the method I used for solving the problem with integer parts from oral Ecole MInes (that I posted some time ago and after a solution  ;) )  works here. Too bad, otherwise it would have been nicer...

For $m=n+1$ it is easy to find that the sum is $\frac{1}{2}$.

[quote="AYMANE"]Is something wrong in this exercice?
If {km/n} and [km/n] are the integral part
Take m=n+1  :?
I thing you miss n>m.[/quote]Nothing is wrong in this exercise. $x = [x]+\{x\}$ for any real number $x$.

[quote="AYMANE"]m=4 and n=3
And the sum is 1/6-1+2=7/6!
Help me[/quote]You are not doing the computations correctly.

Thank you i thought that {} means integral part .
Sorry :blush:

Let $r_a$ be the only integer from $0,1,2,3...,n-1$ such that $n|a-r_a$.

We always have: $\left[\frac{mk}{n}\right]=\frac{mk}{n}-\frac{r_{mk}}{n}=r_{mk}$ mod 2, since $m$ is even and $n$ is odd.

We also have that $\left\{\frac{mk}{n}\right\}=r_{mk}/n$

and finally we have that: $m,2m,3m,4m.....(n-1)m$ is a complete set of residues modulo $n$. Using this the problem is easy...and only computations are left...

Notice that $mk=qn+a$ where q and a are nonnegative integers ,since m is even and n is odd,so we can know that for even numerator we have +     odd numerator we have -   Then we can get answer $\frac{1}{2}$

[quote=Valentin Vornicu]Let $m,n$ be co-prime integers, such that $m$ is even and $n$ is odd. Prove that the following expression does not depend on the values of $m$ and $n$:
\[ \frac 1{2n} + \sum^{n-1}_{k=1} (-1)^{\left[ \frac{mk}n \right]} \left\{ \frac {mk}n \right\} . \]

[i]Bogdan Enescu[/i][/quote]
Easy problem, Here's my solution:-   I will prove that the fixed value is $\tfrac{1}{2}$.Indeed note $mk\equiv n$ forms a complete residue set(except 0 trivially) on ranging $k$ from $1$ to $n-1$.Hence $$ \sum^{n-1}_{k=1} (-1)^{\left[ \frac{mk}n \right]} \left\{ \frac {mk}n \right\} =  \sum^{n-1}_{k=1} (-1)^{\dfrac{mk-mk\mod n}{n}} \left(\dfrac{mk \mod n}{n}\right)= \sum^{n-1}_{k=1} (-1)^k\left(\dfrac{k}{n}\right)=\dfrac{n-1}{2n}$$
Thus $\dfrac{n-1}{2n}+\dfrac{1}{2n}=\dfrac{1}{2}$ so we are done.$\blacksquare$
.


If two numbers are randomly chosen without replacement from $ \{1, 2, 3, 4, 5\}$, what is the probability their sum is greater than their product? Express your answer as a common fraction.

[quote=gauss1181]One of the two numbers must be 1 in order for that to happen.

Probability is just $ \frac{4}{C(5,2)}\equal{}\frac{4}{10}\equal{}\boxed{\frac{2}{5}}$.[/quote]

I know this might sound dumb, but where did you get the 4?

The cases with 1: $(1,2), (1,3), (1,4), (1,5)$

4 cases with 1's so 4 is on top


The masters round winner is not announced until the awards ceremony (which should be tonight), so no-one will know until then, if you're really interested, you could ask people who watched it, there usually are 2 people who are clearly favorites... (it seems every year it's always one person with the better presentation, and one with the better math)

who was in the masters round?
and who were the favorites. Im guessing it must be Bobby or David .

Im guessing bobby will win masters round. but david yang might have a pretty good chance too.

Think top 4 are david, bobby, max schindler, + calvin deng

actually I was told that max Schindler from Missouri won.

where did u hear that?

They havnt announced the results yet but do u mean that his presentation was the best?

Favorites (according to others): Me+ Max...

But I thought I failed...

I think Max is going to win...

[quote="pythag011"][quote="jonathanchou711"][quote="mathlete5"]Max Schindler won Masters.[/quote]

Which has been restates multiple times.

The masters round isn't hard? I've heard it's kind of advanced. Well maybe that's just me. I'm not that bright.[/quote]

It's not that hard; it's basically all about presentation. (And apparently going overkill rigor isn't a good idea on masters round :()

It did REALLY walk you step by step. (Heh, though I had seen negative bases before since I was bored and decided to try to find a lot of representations (binary representation, Zeckendorf representation, etc, etc)

Dude max was just hilarious in general in that masters round :O

Yeah, ALL the stuff could be solved using mathcounts level techniques. (Though that's not saying THAT much, since you can prove some very hard theorems using "elementary" techniques. However, the solutions ARE pretty... intuitive.)[/quote]

What did max do to make himself so funny?

[quote="jonathanchou711"][/quote][quote="pythag011"][quote="jonathanchou711"][quote="mathlete5"]Max Schindler won Masters.[/quote]

Which has been restates multiple times.

The masters round isn't hard? I've heard it's kind of advanced. Well maybe that's just me. I'm not that bright.[/quote]

It's not that hard; it's basically all about presentation. (And apparently going overkill rigor isn't a good idea on masters round :()

It did REALLY walk you step by step. (Heh, though I had seen negative bases before since I was bored and decided to try to find a lot of representations (binary representation, Zeckendorf representation, etc, etc)

Dude max was just hilarious in general in that masters round :O

Yeah, ALL the stuff could be solved using mathcounts level techniques. (Though that's not saying THAT much, since you can prove some very hard theorems using "elementary" techniques. However, the solutions ARE pretty... intuitive.)[/quote][quote="jonathanchou711"]

What did max do to make himself so funny?[/quote]

Max is pretty good at being funny in general :O

A lot of people decided to start a Max Schindler Fan Club on facebook.

Why are all the master rounds topics so well known...

They should at least give us some amazing topics which they discovered in a research project :(

[quote="Yongyi781"][quote="pythag011"]
Dude max was just hilarious in general in that masters round :O
[/quote]

... How could you have known?[/quote]

he went before....max...and was watchin...

because he was there?

is there a broadcast of the masters round, like the countdown round?

Hmm dang strange choice of topic for this year's Masters.
We studied base -2 pretty well at this one MC practice and I thought it was very cool.
Just curious, what kind of clothes did everyone wear for the Masters Round presentation?

Eh, just casual clothing I guess? Or I think everyone just wore their MATHCOUNTS team shirts or something?

Yeah, I agree with CA Math that the topic was... a strange choice of topic at best.

It was horribly well-known, and it wasn't hard at all... I don't think masters round tests problem solving skill that much.

Some people's coaches decided to not let you do anything before all the rounds were over :( and didn't let you do anything fun until the last 12 hours before you leave.

Also they forced you to wear your team shirt at everything. I think they mostly wore either casual clothing or team shirts in masters round.

Hmm, they should make masters rounds that aren't well known.

I don't want to start a new thread for this, so I tried to put it in the one most related.

Can we discuss the master's round problems not only for this year, but for other years too? And does any body have the problem?

hmmmm... sure to TPAM...

Anyways I wore my chapter shirt in... it's no big deal anyways. But the fractions thing was sorta annoying  :mad: ...

And join the Max Schindler fan club if you can (on Facebook)!!!

Last year, everyone had to wear that orange shirt or something...

[quote="mathlete5"]Maximillian Schindler of Missouri won the Masters round.

Bobby Shen won Countdown, with David Yang in 2nd and won the written round.

Go Anya Katsevich!!![/quote]

[quote="mathlete5"]Max Schindler won Masters.[/quote]

What are the point of these posts?

apparently to inform us of what you basically have to be really ignorant if you didn't know.


topology
function
real analysis
real analysis unsolved

In Cantor County the address $h$ of each building is an infinitely long sequence $a_1a_2a_3\dots$ where each $a_i=0$ or $1$. For example, we write $h=0110100111011\dots$ to indicate the address of a building. We will assume that all possible addresses are in use. i.e. each string refers to an actual building.
The Cantor Postal Service measures the distance between two buildings whose addresses are $h_1$ and $h_2$ as follows: Let $h_1=a_1a_2a_3\dots$ and let $h_2=b_1b_2b_3\dots$, and let $D=\{i: a_i\neq b_i\}$. If D is nonempty, then the distance between $h_1$ and $h_2$, written $d(h_1,h_2)$, is $2^{-n}$ where $n$ is the smallest element of $D$. If $D$ is empty, $d(h_1,h_2)=0$.

10. The post office decides to use the digit 2 as well. Each existing building is assigned a new address whose digits are chosen from $\{0,1,2\}$ instead of $\{0,1\}$. As in the old system, a digit need not be used. However, when the post office starts assigning addresses to new buildings, the bureacrats realize, o their shock, that the way in which the post office assigned new addresses to old buildings used up all the new addresses. Show that this is possible by constructing a 1-to-1 correspondence between the old addresses and the new addresses.

Extra question (not part of the original): Is it possible to do this while preserving the topology?

Consider the following algorithm.

1 - Read the leftmost digit of the old address: if it is 0, the leftmost digit of the new address is 0. If it is 1, consider the first two digits: if they are 10, then the first digit of the new address is 1, if they are 11, then the first digit of the new address is 2.

2 - Delete the digit(s) used (0, 10 or 11)

3 - Restart from point 1 with the remaining digits.

This seems to define a 1-1 correspondence preserving topology: indeed if two old addresses coincide on a long initial segment, then the new addresses will coincide on a (possibly smaller) initial segment.

Yes, that's the nice way to do it. I was grading this question at the San Jose site, and none of the thirteen teams there found it. Eight of the teams converted the strings to real numbers and changed base- but all of them missed the nonuniqueness and only got 2 out of 4. The other five teams had nothing.

The grading rubric we were working from didn't even mention the nice solution.

[quote="jmerry"]Yes, that's the nice way to do it.[/quote]

Thank you, jmerry   :)  :) . Let me add a problem inspired by your post. Let us look at the two spaces of addresses as metric spaces. If I'm not wrong, the function in my solution is not only continuous, but also 1/2 Holder continuous.

1 - Is it possible to find a 1-1 correspondence with a better Holder exponent?

2 - If yes, how much better?


find all pairs $ m,n$ of positive integers such that $ m^2$ $ \minus{}$ $ n$ divides $ m$ $ \plus{}$ $ n^2$ and $ n^2$ $ \minus{}$ $ m$ divides $ m^2$ $ \plus{}$ $ n$.


[quote="sharkman"]The vertices of triangle PQR are P(1, 2), Q(-3, 6) and R(4, 8).  A line through Q is parallel to line segment PR and passes through point M(k, 14).  What is the value of k?[/quote]

[hide]Segment $PR$ has the slope of $\frac{8-2}{4-1}=2$. So the line $\|$ to $PR$ and through $Q$ has the equation $2x-y=2(-3)+6=0$.

Since $2x-y=0$ passes through $(7,14)$, $k=7$.[/hide]

The book's answer for k is 1 but you say k = 7.

I played around withthe question further and since the line parallell to PR has the same slope, I did the following:

2/1 = (14 - 6)/(k + 3)

I crossed-multiplied and got k = 1 after all.

I get k=1. I wasted time using lots of approaches, but using slopes the easiest.

Ooops, arithmetic error :blush: $+12 \rightarrow-12$.

[hide]
from points P and R we have a slope of 2

QM has the same slope,

$y-y_{1}= m(x-x_{1})$
$y-6 = 2(x+3)$
$y = 2x+12$

solving for y = 14, $\boxed{x = 1}$
[/hide]


IMO 2008
combinatorics
counting
IMO
IMO Shortlist

Let $ n$ and $ k$ be positive integers with $ k \geq n$ and $ k \minus{} n$ an even number. Let $ 2n$ lamps labelled $ 1$, $ 2$, ..., $ 2n$ be given, each of which can be either [i]on[/i] or [i]off[/i]. Initially all the lamps are off. We consider sequences of steps: at each step one of the lamps is switched (from on to off or from off to on).

Let $ N$ be the number of such sequences consisting of $ k$ steps and resulting in the state where lamps $ 1$ through $ n$ are all on, and lamps $ n \plus{} 1$ through $ 2n$ are all off.

Let $ M$ be number of such sequences consisting of $ k$ steps, resulting in the state where lamps $ 1$ through $ n$ are all on, and lamps $ n \plus{} 1$ through $ 2n$ are all off, but where none of the lamps $ n \plus{} 1$ through $ 2n$ is ever switched on.

Determine $ \frac {N}{M}$.

[i]Author: Bruno Le Floch and Ilia Smilga, France[/i]

Maybe $ 2^{k \minus{} n}$..

at any sequence $ a_1, a_2, \cdots, a_k$ in $ M$

Let $ b_i \equal{} \mid \{ j | a_j \equal{} i, 1 \leq j \leq k \} \mid$

we can change first $ b_i \minus{} 1$ $ i$'s to $ i$ or $ n \plus{} i$ randomly and last $ b_i$-th $ i$ to $ i$ or $ n \plus{} i$ for makes $ n \plus{} i$-th lamp off.

This makes sequences in $ N$ from $ a_1, a_2, \cdots, a_k$

because $ \sum_{i \equal{} 1}^{n} (b_i \minus{} 1) \equal{} k\minus{}n$

the answer is $ 2^{k\minus{}n}$

ex) n = 3, k = 7

in M 1211322
in N 111 $ \rightarrow$ 111, 144, 414, 441 (from 11, 14, 41, 44 $ \rightarrow 2^2$)
      222 $ \rightarrow$ 222, 255, 525, 552 (from 22, 25, 52, 55 $ \rightarrow 2^2$)
      3 $ \rightarrow$ 3 ($ 2^0$)
if we choose 144, 525, 3 $ \rightarrow$ 1544325

$ \Rightarrow 2^2 \times 2^2 \times 2^0 \equal{} 2^4 \equal{} 2^{7 \minus{} 3}$

I am getting 2^((k-n)/2)

Let, P(x,y) be the number of ways we can put y steps in a sequence of length x

So, we put n steps in k length sequence to turn the first n lamps on = P(k,n)
Then we have to hit every lamp twice. So, we can pair up steps. and in each step we have 2n lamps to choose from(for N) and n lamps to choose from(for M). So, we have for N : (2n)^((k-n)/2) choices and for M : n^((k-n)/2) choices.

Now we can put one hit from each pair in the sequence in P((k-n),(k-n)/2) ways and the other hit has just as many choices.

So, N = P(k,n) * (P((k-n),(k-n)/2)^2) * (2n)^((k-n)/2)

and, M = P(k,n) * (P((k-n),(k-n)/2)^2) * (n^((k-n)/2))

Tanvir
Dhaka, Bangladesh

[quote="dblues"][quote="tanvirabs"]So, N = P(k,n) * (P((k-n),(k-n)/2)^2) * (2n)^((k-n)/2)

and, M = P(k,n) * (P((k-n),(k-n)/2)^2) * (n^((k-n)/2))[/quote]
You overcounted.  You haven't accounted for repetitions of lamps chosen. :wink:[/quote]

Yes. Sorry for the mistake. Completely wrong solution.

Tanvir
Dhaka, Bangladesh

[quote="KuMing"][quote="felixx"][quote="KuMing"]Maybe $ 2^{k \minus{} n}$..

at any sequence $ a_1, a_2, \cdots, a_k$ in $ M$

Let $ b_i \equal{} \mid \{ j | a_j \equal{} i, 1 \leq j \leq k \} \mid$

we can change first $ b_i \minus{} 1$ $ i$'s to $ i$ or $ n \plus{} i$ randomly and last $ b_i$-th $ i$ to $ i$ or $ n \plus{} i$ for makes $ n \plus{} i$-th lamp off.

This makes sequences in $ N$ from $ a_1, a_2, \cdots, a_k$

because $ \sum_{i \equal{} 1}^{n} (b_i \minus{} 1) \equal{} k \minus{} n$

the answer is $ 2^{k \minus{} n}$

ex) n = 3, k = 7

in M 1211322
in N 111 $ \rightarrow$ 111, 144, 414, 441 (from 11, 14, 41, 44 $ \rightarrow 2^2$)
      222 $ \rightarrow$ 222, 255, 525, 552 (from 22, 25, 52, 55 $ \rightarrow 2^2$)
      3 $ \rightarrow$ 3 ($ 2^0$)
if we choose 144, 525, 3 $ \rightarrow$ 1544325

$ \Rightarrow 2^2 \times 2^2 \times 2^0 \equal{} 2^4 \equal{} 2^{7 \minus{} 3}$[/quote]

in N, what about sequence 1235555 ? as far as i see haven't counted it...[/quote]

in M 1232222
in N 22222 $ \rightarrow$ 22222, 22255, $ \cdots$ 55552 (from 2222, 2225, $ \cdots$ 5555 $ \rightarrow 2^4$)
if we choose 2555 $ \rightarrow$ 1235555[/quote]
ok, you're right, your solution is very very nice, very intelligent solution:)

If you apply induction on  k-n=2T    k+2-n=2T+2   ( when k=n  solution is 1)  you obtain that whereas N increases 2n(k+1)^2) ( with respect to the induction step) M increases n(k+1)^2  so in each step the ratio N/M duplicates and the answer is 2^(k-n)/2

Note:the formula:  2n(k+1)^2  is obtained from: you have two more steps...the only posibility is to choose any lamp (2n) and turn it on and off. We can perform each operation in one of (k+1) times (suppose that in the induction step you had a valid sequence of steps..in each step you can add these two steps in
_S_S_S_S_......S_S_   since que have k "S" we have k+1 places to put the extra movement...

Hope it is ok and you understand it ( sorry about the presentation it is very messy)

Daniel

Let $ S_N, S_M$ be the sets of sequences with the respective definitions given in the problem ($ |S_N| \equal{} N, |S_M| \equal{} M$). We show a $ 1$ to $ 2^{k\minus{}n}$ correspondence from $ S_M$ to $ S_N$.

Take an arbitrary sequence in $ S_M$. Only the numbers $ 1$ through $ n$ appear and each appears an odd number of times. Given a number $ i$, $ 1 \leq i \leq n$, pick an even number of occurrences of that number in the sequence and replace them with $ n\plus{}i$. If $ i$ appears $ 2m_i\plus{}1$ times, there are
\[ {2m_i\plus{}1 \choose 0} \plus{} {2m_i\plus{}1 \choose 2} \plus{} \ldots \plus{} {2m_i\plus{}1 \choose 2m_i} \equal{} 2^{2m_i}\]
ways to do this. We can determine that $ \sum m_i \equal{} \frac{\sum ( 2m_i \plus{} 1) \minus{} n}{2} \equal{} \frac{k\minus{}n}{2}$. Then the total number of ways is $ \prod 2^{2m_i} \equal{} 2^{2 \sum m_i} \equal{} \boxed{2^{k\minus{}n}}$.

No sequence in $ S_N$ is obtained twice in the way. Note that each element is invariant mod $ n$ in the correspondence. So if two sequences in $ S_M$ gave the same one in $ S_N$, they would be the same mod $ n$ and thus the same sequence. All sequences in $ S_N$ are also obtained; just take each element mod $ n$ again (using residue classes $ 1, 2, \ldots n$) and this gives a sequence in $ S_M$ which generates the one you picked in $ S_N$.

Yes, I have the same solution! Even the same notation: $ S_M,S_N,m_i \dots$ :)

Here is my solution with generating functions

If $ f(x)\equal{}(x\plus{}\frac{x^3}{3!}\plus{}\frac{x^5}{5!}\plus{}\cdots )(1\plus{}\frac{x^2}{2!}\plus{}\frac{x^4}{4!}\plus{}\cdots)\equal{}\frac{\sinh(2x)}{2}$, then $ N\equal{}k! * [x^k](f(x)^n)$

If $ g(x)\equal{}(x\plus{}\frac{x^3}{3!}\plus{}\frac{x^5}{5!}\plus{}\cdots )\equal{}\sinh(x)$, then $ M\equal{}k! * [x^k] (g(x)^n)$

Hence

\[ \frac{N}{M}\equal{}\frac{[x^k] ((\frac{\sinh(2x)}{2})^n)}{[x^k] ((\sinh(x))^n)}\equal{}2^{\minus{}n} \times \frac{[x^k] ((\sinh(2x))^n)}{[x^k] ((\sinh(x))^n)}\equal{}2^{\minus{}n}\times 2^k\equal{}2^{k\minus{}n}
\]

@SplashD: I used the same generating functions but was unable to show your last step (but guessed the answer...). can you explain in more detail?

PS: Hola

basically you see $ sinh(x)$ as a generating function and think of $ sinh(2x)$ as putting $ 2x$ insteead of  $ x$

We will calculate $N$ first. Let $b_1,\ldots,b_{2n}$ be the number of times each lamp was switched, so that $b_1+\cdots+b_{2n}=k$. Since $b_1,\ldots,b_n$'s are all odd, and $b_{n+1},\ldots,b_{2n}$ are even, let $b_i=2a_i+1$ for $1\le i\le n$ and let $b_i=2a_i$ for $n+1\le i \le 2n$, so $a_i\ge 0$. Then $2(a_1+\cdots+a_{2n})+n=k$, so $a_1+\cdots+a_{2n} =\frac{k-n}{2}$. Therefore, $N$ is $k!$ times the coefficient of $X^k$ in
\begin{align*}
    F(X) &= \sum_{k'\ge 0} \sum_{a_1+\cdots+a_{2n}=\frac{k'-n}{2}} \frac{k'!}{(2a_1+1)!\cdots (2a_n+1)! (2a_{n+1})! \cdots (2a_{2n})!} \cdot \frac{X^{k'}}{k'!}  \\
    &= \sum_{k'\ge 0} \sum_{a_1+\cdots +a_{2n} =\frac{k'-n}{2}} \frac{X^{k'}}{(2a_1+1)!\cdots (2a_n+1)! (2a_{n+1})! \cdots (2a_{2n})!} \\
    &=  \sum_{k'\ge 0} \sum_{a_1+\cdots +a_{2n} =\frac{k'-n}{2}} \frac{X^{2a_1+1}\cdots X^{2a_n+1}}{(2a_1+1)!\cdots (2a_n+1)!}  \frac{X^{2a_{n+1}} \cdots X^{2a_{2n}}}{(2a_{n+1})! \cdots (2a_{2n})!} \\
    &= \left( \sum_{X_i \text{ odd}} \frac{X^{X_1+\cdots+X_n}}{X_1!\cdots X_n!} \right) \left(\sum_{y_i \text{ even}} \frac{X^{y_1+\cdots+y_n}}{y_1!\cdots y_n!} \right) \qquad (\text{where } X_i=2a_i+1, y_i=2a_{n+i}) \\
    &= \left(1+\frac{X^2}{2!}+\frac{X^4}{4!} + \cdots \right)^n \left( X+\frac{X^3}{3!}+\frac{X^5}{5!} + \cdots \right)^n \\
    &= \left(\frac{e^X+e^{-X}}{2} \right)^n \left( \frac{e^X-e^{-X}}{2} \right)^n \\
    &= \frac{1}{2^n} \left(\frac{e^{2X}-e^{-2X}}{2}\right)^n.
\end{align*}
For $M$, it's the same as $N$ but we don't need the $y_i$'s, so $M$ is $k!$ times the coefficient of $X^k$ in
\[ \left(X+\frac{X^3}{3!}+\frac{X^5}{5!}+\cdots\right)^n= \left(\frac{e^X-e^{-X}}{2}\right)^n.\]
So the answer is
\[ \frac{1}{2^n} \cdot \frac{\left(\frac{e^{2X}-e^{-2X}}{2}\right)^n [X^k]}{\left(\frac{e^{X}-e^{-X}}{2}\right)^n[X^k]} = \frac{1}{2^n} \cdot \frac{C(2X)^k}{CX^k} = \boxed{2^{k-n}}\]
for some constant $C$ we don't care about.

We formulate a bijection between each sequence of the second type, $M$, and $2^{k - n}$ distinct sequences of the first type, $N$. It would then follow that our answer is $\tfrac{N}{M} = 2^{k - n}$.

Note that in a move sequence, only the number of time each lamp is switched matters, and the order does not. Each $1 \to n$ lamp must be flipped an odd number of time, and each $n+ 1 \to 2n$ lamp must be flipped an even number of times. Suppose that for a sequence of the second type, each lamp $i : 1 \to n$ is flipped $m_i$ times for some odd number $m_i$ with\[m_1 + m_2 + \ldots + m_n = k.\]Suppose for each number $i$ from $1 \to n$, we take an even number of flips $n_i \in [1, m_i]$ performed on lamp $i$ and donate it to lamp $n + i$. We see that $n_i$ can take on values $0, 2, \ldots , m_i - 1$ hence there are a total of\[\binom{m_i}{0} + \binom{m_i}{2} + \ldots + \binom{m_i}{m_i - 1} = 2^{m_i - 1}\]for all $i$ from $1 \to n$. Indeed, multiplying over all such $i$, we find a total of $2^{k - n}$ ways to arrive at sequences of the first form for each given sequence of the second form.

Next, we show that under the previously described process, no two sequences of the first form can be the same. This is clear; elements remain the same modulo $n$ after all operations so if two sequences of the second type give the same sequence of the first type, they must be the same sequence.

We have shown such a bijection exists and we are done. $\blacksquare$

I apologize for what I have done.

Let $S$ denote the set of nonnegative integers $x_1,x_2,\dots,x_{2n}$ for which $x_1+x_2+\cdots+x_{2n}=(k-n)/2$. Let $T$ denote the set of nonnegative integers $x_1,x_2,\dots,x_n$ for which $x_1+x_2+\cdots+x_n=(k-n)/2$. Then
\[N=k!\sum_{(x_1,x_2,\cdots,x_{2n})\in S} \frac{1}{(2x_1+1)!(2x_2+1)!\cdots (2x_n+1)! (2x_{n+1})!\cdots (2x_{2n})!}\]
and
\[M=k!\sum_{(x_1,x_2,\cdots,x_n)\in T} \frac{1}{(2x_1+1)!(2x_2+1)!\cdots (2x_n+1)!}.\]
Let $N/k!=N',M/k!=M'$, then the requisite ratio is $N'/M'$. Now consider the generating functions
\[N(x)=\prod_{i=1}^n \sum_{x_i=0}^\infty \frac{x^{x_i}}{(2x_i+1)!}\cdot \prod_{i=1}^n \sum_{x_i=0}^\infty \frac{x^{x_i}}{(2x_{i+n})!},M(x)=\prod_{i=1}^n \sum_{x_i=0}^\infty \frac{x^{x_i}}{(2x_i+1)!}.\]
Clearly $N'$ is the $(k-n)/2$-th coefficient of $N(x)$ and $M'$ is the $(k-n)/2$-th coefficient of $M(x)$. Then rewrite
\[N(x)=\prod_{i=1}^n \frac{1}{\sqrt{x}}\sum_{x_i=0}^\infty \frac{(\sqrt{x})^{2x_i+1}}{(2x_i+1)!}\cdot \prod_{i=1}^n \sum_{x_i=0}^\infty \frac{(\sqrt{x})^{2x_{i+n}}}{(2x_{i+n})!}=\]
\[\prod_{i=1}^n \frac{1}{2\sqrt{x}}(e^{\sqrt{x}}-e^{-\sqrt{x}})\cdot \prod_{i=1}^n \frac 12(e^{\sqrt{x}}+e^{-\sqrt{x}}) = \frac{1}{2^{2n}\sqrt{x^n}}(e^{\sqrt{x}}-e^{-\sqrt{x}})^n(e^{\sqrt{x}}+e^{-\sqrt{x}})^n=\]
\[\frac{1}{2^{2n}\sqrt{x^n}}(e^{2\sqrt{x}}-e^{-2\sqrt{x}})^n=\prod_{i=1}^n \frac{1}{2\sqrt{x}}\sum_{x_i=0}^\infty \frac{(2\sqrt{x})^{2x_i+1}}{(2x_i+1)!} = \prod_{i=1}^n \sum_{x_i=0}^\infty\frac{2^{2x_i}x^{x_i}}{(2x_i+1)!}.\]
Thus the $(k-n)/2$-th coefficient of $N(x)$ is $2^{k-n}$ times the $(k-n)/2$-th coefficient of $M(x)$, and $N'/M'=2^{k-n}$.

excuse me what

Note $N$ is the coefficient of $x^k$ in the power series
$$k! \left( \frac{x}{1!}+\frac{x^3}{3!}+ \cdots \right)^n \left( \frac{1}{0!} + \frac{x^2}{2!} + \cdots \right)^n = k! \left( \frac{e^x-e^{-x}}{2} \right)^n \left( \frac{e^x+e^{-x}}{2} \right)^n = \frac{1}{4^n} \cdot k! \left( e^{2x}-e^{-2x} \right)^n$$
If we let $f(x)=(e^x-e^{-x})^n$ then this is equal to $\frac{1}{4^n} \cdot \left. \frac{\text{d}^kf(2x)}{\text{d}x^k} \right\vert_{x=0}= f^k(0) \cdot \frac{2^k}{4^n}$ where $f^k$ is the $k$-th derivative of $f$. Similarly, note $M$ is the $x^k$ coefficient of
$$k! \left( \frac{x}{1!}+\frac{x^3}{3!}+ \cdots \right)^n = k!\left( \frac{e^x-e^{-x}}{2} \right)^n = \frac{1}{2^n} \cdot k! \left( e^x-e^{-x} \right)^n$$ which is just $\frac{f^k(0)}{2^n}$. So the answer is just $\frac{N}{M} = \boxed{2^{k-n}}.$

The answer should be $2^{k-n}$. In the following $M$ and $N$ denotes the set of all sequences satisfying the given conditions instead of the number of such sequences.

We will show that we can construct $2^{k-n}$ sequences in $N$ for every sequence in $M$, which will imply the result. Take an arbitrary sequence  in $M$.
We denote by $l_{i}$ the number of times th$i$ appears in this sequence. Obviously $l_{i}$ is odd for $i=1,...,n$ and $\sum_{i=1}^{n} l_{i}=k$. For each $1\leq i\leq n$ we may replace an even number of $i$'s with $n+i$ to obtain a new sequence in $N$. There are $\binom{l_{i}}{0}$ possibilities to replace zero $i'$s,  $\binom{l_{i}}{2}$ possibilities to replace two $i'$ and so on. In total, there are
$$\sum_{k=0}^{\frac{l_{i}-1}{2}}\binom{l_{i}}{2k}=\frac{1}{2}\sum_{k=0}^{l_{i}}\binom{l_{i}}{k}=\frac{1}{2}\cdot 2^{l_{i}}=2^{l_{i}-1}$$
possible choices for each $i$. Thus there are
$$\prod_{i=1}^{n}2^{l_{i}-1}=2^{k-n}$$
possibilities to transform this sequence and obtain a sequence in $N$.

It remains to show that no two different sequences in $M$ can be tranformed into the same sequence and that every sequence in $N$ can actually be obtained
from some sequence in $M$. This becomes clear when considering the 'opposite' transformation:
Take any sequence in $N$ and replace any number $j>n$ in it with $j-n$. In this way, we get the unique sequence in $M$ from which we may generate the original sequence in $N$.

Genfunc bashers scare me.

The answer is $2^{k-n}$. Call sequences described in $N$ boring and those in $M$ fancy. To prove the answer, I will stablish a one to $2^{k-n}$ correspondence between a single fancy sequence and $2^{k-n}$ boring sequences. Observe that we can represent a sequence of steps as a sequence of positive integers, with each representing the lamp toggled in the obvious way. If we have some sequence of positive integers represnting steps that only contains $1$ through $n$, with an odd number of occurrences for each (thus representing a fancy sequence), we can generate a unique boring sequence by replacing some even number of $1$'s with $(n+1)$'s, an even number of $2$'s with $(n+2)$'s, and so on. If we let $a_i$ denote the number of times $i$ appears in our fancy sequence for $1 \leq i \leq n$, the number of ways to replace $i$ with $n+i$ is:
$$\binom{a_i}{0}+\binom{a_i}{2}+\cdots+\binom{a_i}{a_i-1}=2^{a_i-1},$$
where the equality is from a well-known roots of unity filter argument. Hence, multiplying over all $i$ we get the total number of ways we can replace the elements of the old sequence is $2^{n-k}$, so the correspondence is established and we're done. $\blacksquare$

I claim the answer is $2^{k-n}$. We prove this with the following bijection. Take any sequence of flips in $M$ with $x_i$ flips in the $i$-th position. Then, it is well known that there are $2^{x_i-1}$ ways to choose an even number of elements from a set of $x_i$. Thus, if for each $i$ we choose an even number of flip to instead flip at $n+i$, a total of
\[\prod_{i=1}^n 2^{x_i-1} = \frac{2^{\sum x_i}}{2^n}=2^{k-n}\]
sequences are valid.

Now the other direction is obvious because taking the sequence of flips in $N$ mod $n$ clearly gives exactly one sequence in $M$, so all sequences in $N$ can be generated by the described procedure. Thus, we have shown that there are exactly $2^{k-n}$ sequences in $N$ for every one in $M$, so
\[\frac{N}{M}=2^{k-n}\]
$\blacksquare$

$\textbf{Remark}$
This solution is motivated by the following approximations:

N has $(2n)^k$ legal moves, with $\frac{2^{2n}}{2}$ legal positions it could end up at (parity gives $\frac12$).

Similarly, M has $n^k$ legal moves, with $\frac{2^n}{2}$ legal positions it could end up at.

Thus, as $k\to \infty$, the value of $\frac{N}{M}$ becomes
\[\frac{N}{M} = \frac{\frac{(2n)^k}{2^{2n-1}} }{\frac{n^k}{2^{n-1}}} = \frac{2^k}{2^n}\]
at which point we go look for a bijection

I will prove that $\frac{N}{M} = 2^{k-n}$. Let the first condition be called $X$ and the second condition be called $Y$.
Also, define a sequence to have $x$ terms matching with another sequence if there exists exactly $x$ steps for each sequences where the same lamp is switched. For example, the sequences $\{1, 1, 2, 1\}$ and $\{1, 2, 2, 1\}$ have $3$ matching terms.

[color=#3D85C6][b]Lemma: [/b][/color]For odd $m$, $\binom{m}{0}+\binom{m}{2}+\ldots+\binom{m}{m-1} = 2^{m-1}$.

[color=#3D85C6][b]Proof: [/b][/color]A simple induction and the fact that $\binom{m}{k}+\binom{m}{k+1} = \binom{m+1}{k+1}$, or just a simple symmetry.

The mapping $P$ which maps lamps $i$ and $i+n$ or $i-n$ depending on which one is less than in the range $[0, 2n]$. For some sequence of steps $Z$ that satisfies $Y$, let $Z_i$ denote the number of times the lamp $i$ has been switched. I will prove that we can map $2^{k-n}$ sequence of steps that satisfy $X$ to each distinct $Z$. We will call this map $Q$.

Consider the set of sequences $S$ that satisfy $X$ such that for each sequence $s \in S$, $s$ and $Z$ have at least $n$ matching terms that involve all the lamps labelled $1, 2, \ldots n$. We now consider a specific lamp $i \le n$ and notice that $Z_i$ must be odd. Our mapping $P$ maps this lamp to $i+n$. Notice that if we switch any $2k < Z_i$ of these lamps in the sequence with the lamps $i+n$, we end up with a sequence that satisfies $X$. Therefore, for each individual lamp $i$, the total number of ways to change the $Z_i$ terms in the sequence is $$\binom{Z_i}{0}+\binom{Z_i}{2}+\ldots+\binom{Z_i}{Z_i-1} = 2^{Z_i-1}.$$ If we now consider all the lamps, the total number of ways we can switch all these terms in this way is $2^{\left({\sum_{i = 1}^n{Z_i}-n}\right)} = 2^{n-k}$ as desired.

It is clear that this mapping $Q$ is bijective, so $\frac{N}{M} = 2^{k-n}$.

[color=#f00][b]Remarks: [/b][/color]I left out some small details but the reader should be able to figure it out.

[hide = Solution]
The answer is $2^{k - n}$.

We use generating functions. To find $M$, consider the polynomial \[p(x_1, \ldots, x_n) = x_1x_2\cdots x_n(x_1 + x_2 + \cdots + x_n)^k.\] Then $M$ is the sum of the coefficients of the terms of $p$ with an even exponent in each of the $x_i$ (because the expansion of $(x_1 + \cdots + x_n)^k$ contains a term for each possible sequence of $k$ switches not ever using lamps $n + 1$ through $2n$, and a sequence counts iff it has an odd exponent of each of $x_1$, \ldots, $x_n$). By the Roots of Unity Filter, this means \[M = \frac{\sum_{(x_1, \ldots, x_n) \in \{-1, 1\}^n} p(x_1, \ldots, x_n)}{2^n},\] since a term $\prod x_i^{e_i}$ contributes $2^n$ to the sum if all the $e_i$ are even (every contribution is $1$, and there are $2^n$ tuples), and $0$ to the sum otherwise (if $e_i$ is odd, then toggling the sign of $x_i$ gives terms which cancel out). So then using our definition of $p$, we have \[M = \frac{\sum_{(x_1, \ldots, x_n) \in \{-1, 1\}^n} x_1\cdots x_n(x_1 + \cdots + x_n)^k}{2^n}.\] For each $0 \leq m \leq n$, there are $\tbinom{n}{m}$ $(x_1, \ldots, x_n)$ with exactly $m$ terms which are $-1$, and each such term contributes $(-1)^m(n - 2m)^k$ to the sum, so then \[M = \frac{1}{2^n} \sum_{m = 0}^n \binom{n}{m}(-1)^m(n - 2m)^k.\]

Meanwhile, to find $N$, consider the polynomial \[q(x_1, \ldots, x_{2n}) = x_1x_2\cdots x_n(x_1 + x_2 + \cdots + x_{2n})^k.\] Then $N$ is again the sum of the coefficients of the terms of $q$ with an even exponent ineach of the $x_i$ (because the expansion of $(x_1 + \cdots + x_{2n})^k$ contains a term for each possible sequence of $k$ switches, and a sequence counts iff it has an odd exponent of each of $x_1$, \ldots, $x_n$ and an even exponent of $x_{n + 1}$, \ldots, $x_{2n}$). By the same Roots of Unity Filter argument as before, this means \[N = \frac{\sum_{(x_1, \ldots, x_{2n}) \in \{-1, 1\}^{2n}} x_1\cdots x_n(x_1 + \cdots + x_{2n})^k}{2^{2n}}.\] Let $e(n, m)$ be the number of ways to choose $(x_1, \ldots, x_{2n}) \in \{-1, 1\}^{2n}$ such that $m$ of the $x_i$ are $-1$ and $x_1\ldots x_n = 1$ (equivalently, an even number of $x_1$, \ldots, $x_n$ are $-1$), and $o(n, m)$ the number of ways such that $x_1\ldots x_n = -1$ (equivalently, an odd number of $x_1$, \ldots, $x_n$ are $-1$). Then for each $0 \leq m \leq 2n$, if $m$ of the $x_i$ are $-1$, we get a contribution of \[(e(n, m) - o(n, m))\cdot (2n - 2m)^k\] (since there are $e(n, m)$ such terms with $x_1\cdots x_n = 1$, and $o(n, m)$ with $x_1\cdots x_n = -1$, and we always have $x_1 + \cdots + x_{2n} = 2n - 2m$). This means \[N = \frac{1}{2^{2n}} \sum_{m = 0}^{2n} (e(n, m) - o(n, m))(2n - 2m)^k.\]

[color=#0B5394][b]Claim:[/b][/color] For any $0 \leq m \leq 2n$, we have \[e(n, m) - o(n, m) = \begin{cases} 0 & \text{if } m \text{ is odd}, \\ (-1)^\ell\binom{n}{\ell} & \text{if } m = 2\ell.\end{cases}\]

[i]Proof.[/i] For each $0 \leq i \leq n$, let $e_i(n, m)$ and $o_i(n, m)$ be the number of ways to choose $(x_1, \ldots, x_{2n})$ satisfying the given constraints, such that we also have $x_j = x_{n + j}$ for all $1 \leq j \leq i$ (so $e_0$ and $o_0$ are the same as $e$ and $o$). Then we claim that for each $0 \leq i < n$, we have \[e_i(n, m) - o_i(n, m) = e_{i + 1}(n, m) - o_{i + 1}(n, m).\] This is because $e_i(n, m) - e_{i + 1}(n, m)$ counts the number of $(x_1, \ldots, x_{2n})$ satisfying the given constraints for $e$ with $x_j = x_{n + j}$ for all $1 \leq j \leq i$ and $x_{i + 1} \neq x_{n + i + 1}$, and the same is true for $o_i(n, m) - o_{i + 1}(n, m)$. But these counts must be equal, since for any sequence with $x_j = x_{n + j}$ for all $1 \leq j \leq i$ and $x_{i + 1} \neq x_{n + i + 1}$, swapping $x_i$ and $x_{n + i + 1}$ toggles whether the sequence contributes to $e_i(n, m) - e_{i + 1}(n, m)$ or $o_i(n, m) - o_{i + 1}(n, m)$.

So then we have \[e(n, m) - o(n, m) = e_n(n, m) - o_n(n, m).\] If $m$ is odd then these are both $0$, as we cannot have $(x_1, \ldots, x_n) = (x_{n + 1}, \ldots, x_{2n})$ (this would mean an even number of $-1$'s). If $m = 2\ell$, then there are $\binom{n}{\ell}$ solutions with $(x_1, \ldots, x_n) = (x_{n + 1}, \ldots, x_{2n})$ (choose any $\ell$ of the first $n$ to be $-1$'s), and this contributes to $e_n$ if $\ell$ is even and $o_n$ if $\ell$ is odd. So then we have \[e_n(n, m) - o_n(n, m) = (-1)^\ell\binom{n}{\ell},\] which means this is $e(n, m) - o(n, m)$ as well. $\blacksquare$

This means \[N = \frac{1}{2^{2n}} \sum_{\ell = 0}^n (-1)^\ell\binom{n}{\ell} (2n - 4\ell)^k.\] But factoring out $(2n - 4\ell)^k = 2^k(n - 2\ell)^k$, this gives the same sum as in $M$, so \[N = \frac{1}{2^{2n}} \cdot 2^k \cdot 2^nM = 2^{k - n}M.\]
[/hide]

The answer is $2^{k-n}$. The solution is to construct a mapping from the first set of sequences to the second as follows:
Let $M$ be a sequence of second type. Then for $i=1,\dots,n$ take some even number of steps steps where we toggled $i$ and turn them into toggling $i+n$ instead. We get some sequence of second kind $N$ and say that it is a modification of $M$\\

  $\bullet$ It is clear that any sequence of the first kind is a modification of exactly one sequence of second kind.
  $\bullet$ We now count the opposite thing. Suppose that $M$ had $a_1$ toggles for $1$, $\dots$ , $a_n$ toggles for $n$.\\
    Then there are $2^{a_i-1}$ subsets of even size of the set of toggles of $i$ (since a set of odd cardinality has as many even subsets as it has odd subsets). So, there is a total of $\prod{2^{a_i-1}}=2^{k-n}$ ways to generate $N$ from $M$.

Those two arguments establish the answer.

We claim the answer is $2^{k-n}$, and prove via strong induction.

$M(n, k)$ counts the number of sequences where each term is $1, ..., n$ and occurs an odd number of times. $N(n, k)$ counts the number of sequences where each term is $1, ..., 2n$ and $1$ through $n$ occur an odd number of times, $n+1$ through $2n$ an even number. Hence
\begin{align*}
    M(n, k) = \sum_{\substack{a_1 + ... + a_n = k \\ a_i \textrm{ odd}}} {k \choose a_1, ..., a_n}.
\end{align*}
\begin{align*}
    N(n, k) = \sum_{\substack{a_1 + ... + a_{2n} = k \\ a_i \textrm{ odd for } i \le n \\ a_i \textrm{ even for } i > n}} {k \choose a_1, ..., a_{2n}}.
\end{align*}

[b]Claim 1:[/b] $\sum_{i \textrm{ even}} {r \choose i} = \sum_{i \textrm{ odd}} {r \choose i} = 2^{r-1}$.
[i]Proof:[/i] Consider the generating function $G(x) = (1 + x)^r$. $G(1) = E + O = 2^r$, and $G(-1) = E - O = 0$. Hence $E = O = \frac{2^r}{2} = 2^{r-1}$. $\square$ \\

Base case: $n$ = 1. Then $M(1, k) = 1$ since all terms in the sequence must be 1. Furthermore $N(1, k) = \sum_{a_2 \textrm{ even}} {k \choose a_2} = 2^{k-1}$.

Inductive step: Assume $N(n-1, j) = 2^{j-n+1}M(n-1, j)$ for $j \le k$.
\begin{align*}
    M(n, k) &= \sum_{\substack{a_1 \textrm{ odd}}} \left[{k \choose a_1} M(n-1, k-a_1)\right] \\
    N(n, k) &= \sum_{\substack{a_1 + ... + a_{2n} = k \\ a_i \textrm{ odd for } i \le n \\ a_i \textrm{ even for } i > n}} {k \choose a_1} {k-a_1 \choose a_{2n}} {k - a_1 - a_{2n} \choose a_2, ..., a_{2n-1}} \\
    &= \sum_{\substack{a_1 + a_{2n} = \lambda \\ a_1 \textrm{ odd} \\ a_{2n} \textrm{ even}}} \left[{k \choose a_1} {k - a_1 \choose a_{2n}} \sum_{\substack{a_2 + ... + a_{2n-1} = k - \lambda \\ a_i \textrm{ odd for } i \le n \\ a_i \textrm{ even for } i > n}} {k - \lambda \choose a_2, ..., a_{2n-1}}\right] \\
    &= \sum_{\substack{a_1 + a_{2n} = \lambda \\ a_1 \textrm{ odd} \\ a_{2n} \textrm{ even}}} \left[{k \choose \lambda} {k - \lambda \choose a_1} N(n-1, k-\lambda) \right] \\
    &= \sum_{\substack{a_1 + a_{2n} = \lambda \\ a_1 \textrm{ odd} \\ a_{2n} \textrm{ even}}} \left[{k \choose \lambda} {k - \lambda \choose a_1} 2^{k - \lambda - n + 1} M(n-1, k-\lambda) \right] \\
    &= \sum_{\substack{\lambda \textrm{ odd}}} {k \choose \lambda} \sum_{a_1 \textrm{ odd}} \left[ {\lambda \choose a_1} 2^{k - \lambda - n + 1} M(n-1, k-\lambda)\right] \\
    &= \sum_{\substack{\lambda \textrm{ odd}}} \left[{k \choose \lambda} 2^{k - \lambda - n + 1} M(n-1, k-\lambda) \sum_{a_1 \textrm{ odd}} {\lambda \choose a_1}\right] \\
    &= \sum_{\substack{\lambda \textrm{ odd}}} \left[{k \choose \lambda} 2^{k - \lambda - n + 1} M(n-1, k-\lambda) 2^{\lambda - 1}\right] \\
    &= 2^{k - n} \sum_{\substack{\lambda \textrm{ odd}}} \left[{k \choose \lambda} M(n-1, k-\lambda)\right] = 2^{k-n}M(n, k)
\end{align*}
where ${k \choose a_1} {k - a_1 \choose a_{2n}} = {k \choose \lambda} {\lambda \choose a_1}$ because both count the number of ways to choose $a_1$ to be 1 and $a_{2n}$ to be $2n$, in the left by choosing 1 then $2n$ and in the right by choosing those to be either first then choosing those to be 1. Furthermore $2 | k - n \iff 2 | (k-\lambda) - (n-1)$.

We claim that the answer is $2^{k-n}.$\\

Consider a sequence that satisfies the second condition. It must have switched the first $n$ lamps each an odd number of times, and the last $n$ lamps none. Let $a_i$ denote the number of times the $i$th lamp was switched in this sequence. We will construct a set of sequences that satisfies the first condition from this sequence. Suppose that some of the swaps of the $i$th lamp are moved to the $n+i$th lamp, such that the number of swaps of the $i$th lamp remains odd. There are $2^{a_i-1}$ ways to do this (since exactly half of the ways results in the $i$th lamp staying odd), so the number of sequences generated from this is $$\prod_{i=1}^n 2^{a_i-1}=2^{\sum_{i=1}^n a_i-1}=2^{k-n}.$$ Obviously, each of these sequences satisfies the first condition (as we moved an even number to each of the later lamps). For a sequence that satisfies the first condition, the swaps on the later lamps can be moved back to the earlier lamps to form a sequence that satisfies the second condition, so all sequences that satisfies the first condition can be generated in this way, so we are done.

This generating functions solution is absolutely insane.

Let $S$ be the set of all $2n$-tuples $(a_1, a_2, \dots, a_{2n})$ such that $a_1+a_2+\cdots+a_{2n} = k$ with $a_1, a_2, \dots, a_n$ odd and the rest even. Observe that this is the $X^k$ coefficient in the generating function
\begin{align*}
f(X) &= \sum_{(a_1, a_2, \cdots, a_{2n}) \in S} \frac{k!}{a_1a_2\cdots a_{2n}!} \\
&=k! \prod_{i=1}^{n} \left(\sum_{a_i \geq 0 \text { odd}} \frac 1{a_i!}X^{a_i}\right)\prod_{i=n+1}^{2n} \left(\sum_{a_i \geq 0 \text{ even}} \frac 1{a_i!}X^{a_i}\right) \\
&= k! \left(\frac{e^X - e^{-X}}2\right)^n\left(\frac{e^X + e^{-X}}2\right)^n \\
&= \left(\frac{e^{2X} -e^{-2X}}2\right)^n \cdot \frac 1{2^n}.
\end{align*}
 Similarly, the generating function $g(X)$ for $M$ is $\left(\frac{e^X - e^{-X}}2\right)^n$. Thus $f(X) = g(2X)$, so the desired coefficient is that of $X^k$ in $\frac{f(2X)}{f(X)} \cdot \frac 1{2^n} = 2^{k-n}$ because all other terms cancel out.

Suppose $2a_1+1$, $2a_2+2$, $\dots$, $2a_{n}+1$, $2a_{n+1}$, $2a_{n+2}$, $\dots$, $2a_{2n}$ be the number of times we switched the state of lamps $1$, $2$, $\dots$, $2n$ respectively.

Note that for each sequence in $M$, we can construct some amount of sequences in $N$ by taking an even number of moves on lamp $a_i$ and converting it to moves on lamp $a_{i+n}$ for $i=1$, $2$, $\dots$, $n$. Thus, for each sequence in $M$ we can use this method to construct
\[\prod_{i=1}^{n}{\sum_{j=0}^{a_i}{\binom{2a_i-1}{2j}}}=\prod_{i=1}^{n}{2^{2a_1-2}}=2^{k-n}\]
different sequences $N$. Now, to prove that each sequence $N$ can only be obtained from one $M$: note that the sum of number of switches of lamps $i$ and $n+i$ must stay constant using this method. Therefore, only one possible $M$ in which lamp $n+i$ is never switched. We have constructed a $1$ to $2^{k-n}$ correspondence; the answer is $2^{k-n}$.

The answer is $2^{k-n}$. Call a sequence for the $M$ case, $x$, and that for $N$, $y$.
Consider each sequence as a string of length $k$ of integers from $1$ to $2n$ representing the lights switched on those steps. We will prove a claim that immediately finishes.

[b]Claim.[/b] We can map every $x$ to some $y$ such that each $y$ gets mapped to $2^{k-n}$ times.
[b]Proof.[/b] This mapping is changing every integer greater than $n$ to the integer $n$ less than it. It suffices to show that each $y$ gets mapped to $2^{k-n}$ times, and this is easy: for each integer from $1$ to $n$, say WLOG $1$, which occurs $a$ times, there are $2^{a-1}$ ways to change an even number of them to $n+1$. $\blacksquare$


calculus
integration
function
real analysis
calculus computations

Please Help!!!

To compute the Riemann integral of $f: [0,1]\to \mathbb{R}$ given $f(x)=x^k$ where $k\geq 1$ is an integer

1. Let $m\geq 2$ and define $q_m$ = $m^{\frac{-1}{m}}$.
Let $P_m$ be the partition of $[0,1]$ given by $P_m = ( 0<q_m^m<q_m^{m-1}<\ldots<q_m<1)$      Explicitly evaluate $L(f, P_m)$ and $U(f, P_m)$

2. Show that $f$ is integrable on $[0,1]$

3. Show that $\int_{0}^{1} f(x)dx = \frac{1}{k+1}$

Ah, the geometric partition. It's easier to see what's going on if you run this calculation for an interval $[a,b]$ with $0<a<b$, and then extend to intervals with endpoint zero by continuity. The partition you use on $[a,b]$ is $x_k=a\cdot\left(\frac ba\right)^{\frac kn}$. Since the function is increasing, the lower sum is the left-endpoint Riemann sum and the upper sum is the right-endpoint Riemann sum.

There's no substitute for actually doing the calculations here, and you'll appreciate how easy it is compared to the traditional treatment in calculus classes.


[quote="mathematical intelligence"]Let KLM be a inscribed triangle of ABC.(K on AB, L on BC, M on CA)
And put the areas of triangle KLM, AMK, BKL, and CLM S, S1, S2, S3 respectively.
prove that S(S1^-1+S2^-1+S3^-1)>=3.[/quote]

$ \frac{AK}{KB}\equal{}n$, $ \frac{BL}{LC}\equal{}m$,$ \frac{CM}{MA}\equal{}k$
$ S_{ABC}\equal{}S_{0}$

$ \frac{S_{0}}{S_{1}}\equal{}\frac{AB*AC}{AK*AM}\equal{}\frac{(1\plus{}n)(1\plus{}k)}{n}$
$ \frac{S_{0}}{S_{2}}\equal{}\frac{AB*BC}{BK*BL}\equal{}\frac{(1\plus{}n)(1\plus{}m)}{m}$
$ \frac{S_{0}}{S_{3}}\equal{}\frac{BC*AC}{LC*MC}\equal{}\frac{(1\plus{}m)(1\plus{}k)}{k}$

$ S\equal{}S_{0}\minus{}S_{1}\minus{}S_{2}\minus{}S_{3}\equal{}S_{0}(\frac{1\plus{}mnk}{(1\plus{}n)(1\plus{}m)(1\plus{}k)})$   --->

$ S(\frac{1}{S_{1}}\plus{}\frac{1}{S_{2}}\plus{}\frac{1}{S_{3}})\equal{}S_{0}(\frac{1\plus{}mnk}{(1\plus{}n)(1\plus{}m)(1\plus{}k)})(\frac{(1\plus{}n)(1\plus{}k)}{nS_{0}}\plus{}\frac{(1\plus{}n)(1\plus{}m)}{mS_{0}}\plus{}\frac{(1\plus{}m)(1\plus{}k)}{kS_{0}})\equal{}\frac{1\plus{}nmk}{n(1\plus{}m)}\plus{}\frac{1\plus{}nmk}{m(1\plus{}k)}\plus{}\frac{1\plus{}nmk}{k(1\plus{}n)}\equal{}\frac{1\plus{}nmk\plus{}n\plus{}nm}{n(1\plus{}m)}\minus{}1\plus{}\frac{1\plus{}nmk\plus{}m\plus{}mk}{m(1\plus{}k)}\minus{}1\plus{}\frac{1\plus{}nmk\plus{}k\plus{}kn}{k(1\plus{}n)}\minus{}1\equal{}\frac{1\plus{}n}{n(1\plus{}m)}\plus{}\frac{m(1\plus{}k)}{1\plus{}m}\plus{}\frac{1\plus{}m}{m(1\plus{}k)}\plus{}\frac{k(1\plus{}n)}{1\plus{}m}\plus{}\frac{1\plus{}k}{k(1\plus{}n)}\plus{}\frac{n(1\plus{}m)}{1\plus{}n}\minus{}3\geq6\minus{}3\equal{}3$


function
LaTeX
number theory
Diophantine equation
number theory unsolved

Hi everybody,

A=2n where n is an integer composite

k=int(sqrt(A))

s=P(s) where P(s) is the biggest prime < A (example : if A=20 then P(8)= 19)
t=P(t) where P(t) is the biggest prime = or < k (example : if A=60 then k=7 P(4)=7)
S = s# (# is the primorial function)
T = t#
U=S/T

b integer
B=b(A-b) with 1<b<(A/2)

1. Prove that for every n it exist at least one solution such as :

B divide U

2. Prove that :

All the values of B dividing U are odd semi-prime ( a semi-prime if the product of 2 prime) and solutions to Goldbach conjecture (2n=p+q p,q prime)

Example :

n=40
A=80
k=8
s=79
t=7
S=79*73*71*....*3*2
T=7*5*3*2
U= 79*73*71*.....*13*11

B=b(80-b) with 1<b<40

If we use the chinese remainder theorem to prove the first part will it be sufficient?

[quote="ZetaX"]No.[/quote]

Thanx a lot for your helpful answer.
Anyway I still think that there is a way to prove by using smartly the remainder chinese theorem.
It takes time to expand some parts of the equation and a lot of calculations.
Where is going to drive me?
I do not know.

Hi everybody,

Some people told me that it is just a re-statement of Goldbach Conjecture.
I do not think so because the way I presented my problem could lead to solution.
The second point is easy to prove : all the B's dividing U are odd semi-prime and solutions to GC.
The first point could be proved if we consider that :
the proposition "It exist at least one solution" as equivalent to "the diophantine equation b(2n-b) not dividing U has at most n-1 solutions" (we do not take account of the permutations and the way of writing b for example 2*8 is equal to 4*4 that is one solution).
Counting the solutions of any diophantine equation is doable. There are some method to bound the solutions.

Thank you for any help.

It seems that no one can prove the 2 points.
Are they so hard to prove?

You are right.
Hard to read but easy to understand.
Any way someone can re-write it using latex so everybody will be ok.
Sorry for all.

Well, maybe $ 2s\plus{}3T$ is the Grothendieck constant of $ t$, so $ u$¿

[quote="ZetaX"]Well, maybe $ 2s \plus{} 3T$ is the Grothendieck constant of $ t$, so $ u$¿[/quote]

I do not think there is some link between Grothendieck constant and what I proposed above.

But if we start by the point that if p and q are prime and 2k=p+q here is maybe a point to start with :

n=pq
2k=p+q
φ(pq)=(p-1)(q-1)

[b]2k=n-φ(pq)+1[/b]            equation (1)

We can prove that for any k>3 the equation (1) has at least one solution.

Ps : I did not use the variable'names used on the first post.


trigonometry
function
integration
real analysis
real analysis unsolved

Let $ n$ be a positive integer. Prove that, for $ 0<x<\frac{\pi}{n\plus{}1}$,
$ \sin{x}\minus{}\frac{\sin{2x}}{2}\plus{}\cdots\plus{}(\minus{}1)^{n\plus{}1}\frac{\sin{nx}}{n}\minus{}\frac{x}{2}$
is positive if $ n$ is odd and negative if $ n$ is even.

$ f_n(x) \equal{} \sin{x} \minus{} \frac {\sin{2x}}{2} \plus{} \cdots \plus{} ( \minus{} 1)^{n \plus{} 1}\frac {\sin{nx}}{n} \minus{} \frac {x}{2}$.

$ f_n'(x) \equal{} \minus{} \mbox{Re}(\sum_{n \equal{} 1}^{n}z^n) \minus{} \frac12$ with $ z \equal{} e^{i(\pi \plus{} x)}$.
After some simplifications we get
$ f_n'(x) \equal{} \frac {( \minus{} 1)^{n \plus{} 1}}{2}((1 \minus{} \cos(x))\frac {\sin((n \plus{} 1)x)}{\sin(x)} \plus{} \cos((n \plus{} 1)x))$
and $ f_n''(x) \equal{} \frac {( \minus{} 1)^{n}}{2}\frac {(n \plus{} 1)\sin(nx) \plus{} n\sin((n \plus{} 1)x)}{1 \plus{} \cos(x)}$
The formula for $ f_n''$ shows that $ ( \minus{} 1)^n f$ is convex for $ 0 < x < \frac {\pi}{n \plus{} 1}$
$ f_n(0) \equal{} 0$ and $ f_n'(0) \equal{} \frac {( \minus{} 1)^{n \plus{} 1}}{2}$.
We are ready when we can show that $ ( \minus{} 1)^{n \plus{} 1}f_n(\frac {\pi}{n \plus{} 1}) > 0$.

We have to distinct between two different, but very similar cases, namely $ n$ is odd, and $ n$ is even.
Let's restrict to the case $ n$ is even.
We prove $ f_{2n}(\frac {\pi}{2n \plus{} 1}) < 0$.

$ f_{2n}(\frac {\pi}{2n \plus{} 1}) \equal{} \sum_{k \equal{} 1}^{2n} ( \minus{} 1)^{k \plus{} 1}\frac {\sin(\frac {k\pi}{2n \plus{} 1})}{k} \minus{} \frac {\pi}{2(2n \plus{} 1)} \equal{}$

$ \frac {\pi}{2n \plus{} 1}(\sum_{k \equal{} 1}^{n} \frac {\sin(\frac {(2k \minus{} 1)\pi}{2n \plus{} 1})}{\frac {(2k \minus{} 1)\pi}{2n \plus{} 1}} \minus{} \sum_{k \equal{} 1}^{n} \frac {\sin(\frac {2k\pi}{2n \plus{} 1})}{\frac {2k\pi}{2n \plus{} 1}}) \minus{} \frac {\pi}{2(2n \plus{} 1)}$.

The function $ x \mapsto \frac {\sin(x)}{x}$ is descending on $ [0,\pi]$, thus
both sums lay between $ a$ and $ a \plus{} \frac {2\pi}{2n \plus{} 1}$, where $ a \equal{} \int_0^{\pi}\frac {\sin(x)}{x}\,dx$.
Thus $ f_{2n}(\frac {\pi}{2n \plus{} 1}) < \frac {\pi}{2n \plus{} 1}\cdot\frac {2\pi}{2n \plus{} 1} \minus{} \frac {\pi}{2(2n \plus{} 1)} < 0$.


The digits $ 1,2,3,\ldots,9$ are arranged, one per circle, in the triangle shown so that the sum of the numbers in the four circles along each side of the triangle is 17. What is the sum of the numbers in the three circles at the vertices of the triangles?
[asy]draw(Circle((-3,0),.5));
draw(Circle((-1,0),.5));
draw(Circle((1,0),.5));
draw(Circle((3,0),.5));
draw(Circle((2,1),.5));
draw(Circle((1,2),.5));
draw(Circle((0,3),.5));
draw(Circle((-1,2),.5));
draw(Circle((-2,1),.5));[/asy]

Let the numbers in the corner circles be $ a$, $ b$, and $ c$.  If we add up the side sums, we get the sum of all the positive integers from 1 to 9 and the numbers in the corners again, so \[ 3(17)\equal{}(1\plus{}2\plus{}3\plus{}\cdots \plus{}9)\plus{}(a\plus{}b\plus{}c) \Rightarrow a\plus{}b\plus{}c\equal{}\boxed{6}\]


I had a problem that was just a glitch:
[url]pi
[/url]

EDIT: Resolved. The problem doesn't appear in FTW anymore.

[quote="4thgraderstar"]I had a problem that was just a glitch:
[url]pi
[/url][/quote]

I'm afraid that I don't understand what you mean...  This appears to be spam and will be locked as such if there is not a good reason for posting.

I think he wants to do something like this

[url]http://www.artofproblemsolving.com[/url]

With the label saying pi (instead of http://www.artofproblemsolving.com). just putting pi inbetween doesn't work. Is that right?

Something similar to the hide function. Instead of 'click here to reveal hidden content'

[hide="hi"]
hi
[/hide]

It says 'hi'

Hope this clears the question up...

Write it like this (all on one line):

[url=www.artofproblemsolving.com]
pi
[/url]

[url=http://www.artofproblemsolving.com]pi[/url]