search
superior algebra
superior algebra unsolved

If G is a finite set closed under an associative operation such that ax=ay forces x=y and ua=wa forces u=w, for every a,x,y,u,w $ \in$ G, prove that G is a group.

Can you please tell me if the following steps sufficiently answer this problem, thanks.

Given the finite set is closed under an associative operation, I just need to prove that a unique identity and inverse exist.

1) For the identity,

        x=ex=ey=y such that x=y  (left identity exists)
        u=ue=we=w=ua=wa  such that ue = ua  and e=a (right identity exists)
        therfore  e=ea=ae=a  (unqiue identity exists)

 2) For the inverse,

     $ ax\equal{}ay$
	$ a^{\minus{}1}(ax) \equal{} a^{\minus{}1}(ay)$  implies left inverse exists ($ a^{\minus{}1}$).
	$ (a^{\minus{}1}a)x \equal{} (a^{\minus{}1}a)y$
	$ ex \equal{} ey$
	$ x \equal{} y$
Also,
	$ ua \equal{} wa$
	$ (ua)(a^{\minus{}1}) \equal{} (wa)(a^{\minus{}1})$  implies right inverse exists ($ a^{\minus{}1}$).
	$ ue \equal{} we$
	$ u \equal{} w$

	therefore $ a^{\minus{}1}$ exists where $ aa^{\minus{}1} \equal{} e$
  $ e\equal{}aa^{\minus{}1}\equal{}a^{\minus{}1}a$  (unique inverse)

Therefore it is a group.

That goes wrong in the very first line. Your equations don't prove anything; you need quantifiers for them to be meaningful.
In particular, this is not true without the finiteness assumption. You haven't used that assumption, so your proof must be wrong.

Thanks for the feedback.  This is my first class in abstract algebra.

Could you please explain or give me an example of what you mean by the finiteness assumption.
Thanks.

The integers under multiplication satisfy all of the conditions except that they are not finite, but the integers are not a group under multiplication. It is important that G is a finite set. You have not used the given information that G is finite in your proof, so it cannot be correct.
[quote]
x=ex=ey=y such that x=y (left identity exists) [/quote]
What are x, e, y? Are they general elements in G or do they have certain properties? How do you know there are x and e in the set so that x=ex? It looks like you simply stated some definition or property related to the identity but did not show that there actually exist elements in the set that satisfy the criteria.

Similarly, you introduce $ a^{\minus{}1}$ without defining it or showing that an element with the properties you want $ a^{\minus{}1}$ to have actually exists in G.

Start with a general element of G and examine its powers.

Actually, I would start by looking at the list of elements $ ax$ for some arbitrary fixed $ x$ as $ a$ runs through the group. That's the most direct way to find the identity, and it leads to the other parts as well.
[Edit: missing letter added. I hate my keyboard.]

Oh thanks, I definitely see that yours is faster than my way. :)

Thanks for the reply.  After some further research, I think the following proof may work better.  I found some material to help with the identity, but not the inverse...

For the identity:
Fix $ a \in G$,  since G is finite, the subset $ {a, a^{2}, a^{3},...}$ is also finite.     Let n be the largest positive integer such that $ a, a^{2},...a^{n}$ are distinct elements.   So $ a, a^{2},...a^{n}$ are distinct but $ a^{n\plus{}1} \equal{} a^{i}$ for some $ 1\leq i \leq n$.   We claim that i = 1.   If $ i \geq 2$, then from $ a^{n\plus{}1} \equal{} a^{i}$ by cancellation we would have $ a^{n} \equal{} a^{i\minus{}1}$, which would contradict the choice of n.   Define an element e in G by setting $ e \equal{} a^{n}$.   We claim that e acts as a left identity for G.  Let $ x \in G$.   Then $ a^{n\plus{}1}x \equal{} ax$, so by canceling a on the left we have $ ex \equal{} a^{n}x \equal{} x$.

For the inverse?...
For each element x of G, there exists an element $ x^{\minus{}1}$ of G such that:
$ e \equal{} xx^{\minus{}1} \equal{} a^{n}xx^{\minus{}1} \equal{} a^{n} \equal{} ea^{n} \equal{} x^{\minus{}1}xa^{n} \equal{} x^{\minus{}1}x$
Is this sufficient for the inverse?

[quote="smurf"]For each element x of G, there exists an element $ x^{ \minus{} 1}$ of G[/quote]
This is exactly what you're trying to prove, though.  Use the fact that the mapping $ x \mapsto ax$ is a bijection, so it must map to the identity.
See my discussion [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?search_id=1964693067&t=213504]here[/url].

Thank you very much for the direction, I think I'm starting to understand.  Could you explain how the solution method would change if the problem were changed slightly to the following:

Suppose that G is a set closed under an associative operation such that:
1.  given $ a, y \in G$, there is an $ x \in G$ such that ax = y, and
2.  given $ a, w \in G$, there is a $ u \in G$ such that ua = w.
Show that G is a group.


In $ \triangle ABC$, pick a point $ P$ such that \[ \angle APB\equal{}\angle BPC\equal{}\angle CPA\equal{}120^{\circ}\]
Show that \[ PA\plus{}PB\plus{}PC<AB\plus{}BC\]

[hide="Solution"]

P is Fermat's point, so the distance to vertexes of triangle are the least (their sum) for point P.

$ AP\plus{}BP\plus{}CP<BA\plus{}BB\plus{}BC\equal{}BA\plus{}BC$
[/hide]

[quote="m4467"]In $ \triangle ABC$, pick a point $ P$ such that
\[ \angle APB \equal{} \angle BPC \equal{} \angle CPA \equal{} 120^{\circ}\]
Show that
\[ PA \plus{} PB \plus{} PC < AB \plus{} BC\]
[/quote]

Be carefull m4467 this inequality is not always true ,there are triangle where the Torricelli point or fermat as bugi said is exterior to ABC , then this inequality could not be truly


Terry needs at least four square feet of floor space per bird in his chicken coop. Terry plans to build a 30-foot by 20-foot chicken coop. What is the maximum number of chickens he can house?

total area of chicken coop is 20*30, so 600.

Terry needs 4 square feet of space per bird.

so there can be 600/4=150 birds in Terry's house.

answer : 150 birds

Or you could do it the faster way. The square root of 4 is 2.

(30/2) * (20/2)

Thus, 15 * 10 = 150


real analysis
function
integration
trigonometry
calculus
real analysis unsolved

Evaluate, as a function of $x,$

$\int_{-\infty}^{\infty}\frac{\sin\pi(x-y)}{\pi(x-y)}\cdot\frac{\sin\pi y}{\pi y}\,dy$

[Note: the integral does converge absolutely, since the integrand is $O(y^{-2})$ as $|y|\to\infty.$ But if you try to certain things, such as differentiating under the integral sign, you're going to be on very shaky ground.]

This might be an idea. The integral equals $\frac{\sin \pi x}{\pi x}$, $x\neq 0$.

The convolution product of two functions $f$ and $g$ is defined by:

$f*g(x)=\int_{-\infty}^{\infty}f(y)g(x-y)dy$.

Then we have the formula:

$\int_{-\infty}^{\infty}F(u)G(u)e^{iux}du=\int_{-\infty}^{\infty}g(y)f(x-y)dy$, where

$F(u)=\frac{1}{\sqrt{2\pi}}\int_{-\infty}^{\infty}f(t)e^{-iut}dt$ is the Fourier transform of $f$.

The Fourier transform of $\frac{\sin(ax)}{x}$ is given by $\sqrt{\pi/2}$ is $|u|<|a|$ and 0 otherwise, thus we get that

${I=\int_{-\pi}^{\pi}(\frac{1}{\pi}\sqrt{\pi/2}})^{2}e^{iux}du=\frac{\sin \pi x}{\pi x}$.

If $x=0$ of course the integral equals 1.

I hope I made no computational mistakes.

That is correct. (And the function is defined at zero as well, with the value 1, which makes it smooth.)

I was inspired to post this because of [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?t=149767]this topic.[/url] I actually set this up to be friendly to a Fourier transform notation with $e^{-2\pi i\xi x}$ rather then the $e^{-iux}$ that didilica is using. By switching to a definition of the Fourier transform  with differently placed $2\pi,$ didi has to do a little more work than I would have done. But only a little more, and it is essentially the same argument as I would have used.

The commutative Banach algebra $L^{1}(\mathbb{R})$ with convolution as multiplication has no nonzero idempotents. (This includes having no identity.) Of course, in this problem we have just exhibited a convolution idempotent - but it's not in $L^{1}.$


I guess you mean math enthusiasts. yes, it is. Please don't make new topics like this, you could post your questions in the Questions, Suggestions, & Announcements forum (though it is for more serious questions).


[quote="tjhance"]Do you mean:

$f(f(f(f(f(f(a))))))$
or
$(f(a))^{6}$?[/quote]

The first.

$a^{2}=2\cos 15^\circ\Longrightarrow f(a)=1+2\cos 30^\circ.$

Hmm...

The problem might be written wrong.

Don't work on the problem until I fix it.

[hide="hint"]i think the problem becomes easier when you use the binomial theorem..
miyomiyo: nice problem by the way :D [/hide]

[quote="kunny"]Right! 1,4, 6, 4, 1 isn't it? :D[/quote]yes!  :wink:  but i do not see a nice way to find $f^{6}(a)$..  :maybe:

So I can't see how to possibly go about this without [i]any[/i] brute forcing. However:

[hide]
Notice the apparent significance of $1+\sqrt{3}$, as there are multiple occurrences of $4+2\sqrt{3}=(1+\sqrt{3})^{2}$.

This raises our suspicions, and we realize:
$208+120\sqrt{3}=(1+\sqrt{3})^{6}$

So let's go ahead and let $\alpha = 1+\sqrt{3}$

The expression now becomes:
$\sqrt[8]{1+4\sqrt{\alpha}+6 \alpha+4 \alpha \sqrt{\alpha}+\alpha^{2}}= \sqrt[8]{(1+\sqrt{\alpha})^{4}}=\sqrt{1+\sqrt{\alpha}}=\sqrt{1+\sqrt{1+\sqrt{3}}}$

$f^{6}(a)=63$
[/hide]

By the way, nice problem  :)

[quote="The Zuton Force"]Quick extension:

Find the remainder when $f^{2007}(a)$ is divided by $1000$.[/quote]

Hmm... how would you do that?  I know that it's just $f^{2004}(3)$, but how do you apply ETF with the subtractions?

Well for starters...

[hide]$f^{5}(a) = 8 \equiv 0 \; \pmod{8}$
$f(0)=-1$, $f(-1) = 0$[/hide]

You can think along those lines...


Ok guys I seriously need some help here. I can work with LaTeX but I am not a pro at all. There is this geometry package Geomplex (by Dirk Laurie) [url]http://econpapers.repec.org/software/codoctave/c031004.htm[/url] available on the web and it seems to be really good. However, I do not quite see how I can install and use it. He gives some instructions like "Place geomplex.sty somewhere in your TeX path" etc (I don't even know what it is and whether I have one - by the way, what IS a .sty file??) and he also says stuff about Octave (which I don't know, what is it) etc. His gplexdoc.tex - file start with

\documentclass[11pt]{article}
\usepackage{a4wide,palatcm,verbatim,curves,geomplex}

and I don't know what to do with those packages, don't think my pc *knows* them, so I am kind of stuck... Could someone PLEASE explain to me, step by step, what I should do in order to use this geometry package?

What installation of LaTeX are you using?  Are you using MikTeX on a Windows PC?

A .sty file is a package that gets loaded with the \usepackage command.  Generally, they live on your PC somewhere in the texmf folder.  (That's what you "TeX path" is; on a PC running MikTeX, it's usually the C:\texmf folder.)

Assuming you're running MikTeX using Windows:

1. Make a folder C:\texmf\tex\generic\geomplex, and put the geomplex.sty file in that folder.

2. Start up the MikTeX Options program (in Windows XP, click on the Start menu in the lower-left of the screen, then go "All Programs" -> "MikTeX" -> "MikTex Options"

3. Click the button that says "Refresh Now"

And it (hopefully) should be working.

Thanks! I'll see whether it works.

So I don't need to worry about the Octave stuff etc?

No, it doesn't work.

This is the "Read Me":

[i]Geomplex: geometry package for Octave/LaTeX

Quick Start:  Type  make  and read the file  geomplex.dvi.

Installation:  You will be able to use the package in the directory into
which you unzipped the package.  For a more permanent installation (for
your own use only):

  1. Place geomplex.sty somewhere in your TeX path.  The usual way is to
     make the directory ~/tex for all your personal TeX styles and
        export $TEXINPUT=$HOME/tex:

  2. Put the .m files somewhere in your Octave load path. The usual way
     is to make the directory ~/octave for all your personal Octave
     utilities and put in your ~/.octaverc file this line:
        LOADPATH=['.:/$HOME/octave//:' LOADPATH]
     Put all the m-files in their own subdirectory of ~/octave.

If you can become root, you can install it for everybody.

  1. Find out where TeX is (perhaps /usr/share/texmf).  Create the directory
     /usr/share/texmf/tex/latex/geomplex and put geomplex.sty there.
     Then run texhash.

  2. Find out where Octave is (perhaps /usr/share/octave).  Create the
     directory /usr/share/octave/site/m/geomplex and put the m-files there.

This software is made available under the GNU Public Licence (GPL).
A copy of the licence is included with your Octave distribution.

Dirk Laurie  (dlaurie@na-net.ornl.gov)[/i]

Now, palatcm.sty and curves.sty cannot be found and I do not understand what to do with all those m-files. More help - please?

I've never heard of Octave, so I can't help you there.

The other .sty files you should be able to install in the same way.

From http://www.octave.org/
[quote]GNU Octave is a high-level language, primarily intended for numerical computations. It provides a convenient command line interface for solving linear and nonlinear problems numerically, and for performing other numerical experiments using a language that is mostly compatible with Matlab. It may also be used as a batch-oriented language.[/quote] From what I can see Geomplex allows you to produce LaTeX drawings using the command line in Octave. Unless you are experienced with Octave (or Matlab) then this is not likely to be the best way for you to produce such diagrams.

Assuming you are not able to pay for commercial software such as Mathematica, Matlab etc which will output LaTeX code, then you should ask in this forum for recommendations as to what free software users like. Some possibilities are:
[list][*][url=http://tug.org/PSTricks/main.cgi/]PSTricks[/url]
[*][url=http://tpx.sourceforge.net/]TpX[/url]
[*][url=http://www.matf.bg.ac.yu/~janicic/gclc/]GCLC/WinGCLC[/url]
[*][url=http://www.mit.edu/~ibaran/kseg.html]KSEG[/url] (outputs ps files)
[*][url=http://jpicedt.sourceforge.net/]jPicEdt[/url][/list]etc etc

Other users' recommendations are the most valuable but please make it clear
[list][*]which operating system you are using
[*]your level of experience
[*]what sort of diagrams you want to produce
[*]how you want to use those diagrams[/list]

I'll start off the list with a program I used to use and like (though I haven't tried it in XP): [url=http://mars.netanya.ac.il/~samy/tkpaint.html]Tkpaint[/url]. It works in Windows, is easy to use, can do geometrical shapes and produces eps files for inclusion in LaTeX.

I'll be fascinated to see other people's recommendations.

I strongly recommend [url=http://www.tug.org/metapost.html]MetaPost[/url].  Granted, it is somewhat difficult to learn (it is a programming language rather than a point-and-click drawing program), but the quality of the output is spectacular.  Click on the link that says "[url=http://tex.loria.fr/prod-graph/zoonekynd/metapost/metapost.html]MétaPost exemples[/url]".  (Don't worry -- the page that it links to is not in French.)

We are using MetaPost for all of the diagrams in our new textbooks.

[quote="Arne"]Ok, let's see - I am using a computer with Windows XP on it, and I am doing geometry on quite a high level (actually I am coach for IMO teams and I need to write training texts on geometry, but I want to include clear diagrams to make it easier for them. So basically I need diagrams in all my texts and problem proposals. I had to study geometry without diagrams myself while training for IMO a few years ago and that was not always easy. The diagrams are quite complicated sometimes) Could I use MetaPost? Do you recommend something else? Etcetera. Let's say that I am very experienced with typing in LaTeX but that I do not really know how the whole LaTeX thing works (ask me what a .sty file is and I won't really be able to give you a satisfactory answer)[/quote]

For your purposes, I will recommend WinGLC (the link given above by stevem). The program can give you a latex code picture or a bmp file output. See the attachment to see what this program can do for you

Octave appears to be sort of an open-source mathematical programming language. If you wait till october, your university will probably allow you to download MathLab for free, a more user-friendly (but expensive) version of it, which is extremely powerful to make complicated numerical computations.

At least that's what the guys at our departement told me about this :)

Wow, this is really cool stuff, I discovered it today and look what I can do with it already! I wrote up my solution for IMO 2004 problem 5 and made a nice diagram for the problem, so that you can see how easy it is to use the program.

So, here is the attachment:

(I know the margins etc aren't perfect since I did everything rather quickly, but that's not a problem, right? :))

Did you have to include any separate files for this, or did you do this by typing things in your TeX file only? It always bores me that I have to keep images in the same folder to compile my tex-files, so if this could be typed straight into the tex-file, I'd be very interested. :)

"Although GCLC was initially built as a tool for converting formal descriptions of geometric constructions into LaTeX form..."

Don't know. At this moment I am using some separate program to draw and view (!) the pictures/diagrams I make, and then in the LaTeX file I simply type

\input{bulgaria2002.pic}

and then the diagram is there. So, I guess no, but it's extremely easy to work with, and in the WinGCLC program you basically need to select the option "File/Export to/LaTeX". I am not an expert on this kind of things, you know :) Anyway, you need to put the file gclc.sty somewhere in your TeX path.

By the way, I have a stupid question. In the example the author gives, you just need to type "cmark_rt S_b", for example, and then the "name" $S_b$ appears on the diagram. However, if I type the same thing in my files, I get $S_{}\_b$ and not $S_b$. How come, does anyone know? What am I doing wrong?

Oh, I see now. When I export the file to LaTeX, the names do appear correctly in the diagram! That's really neat!

i tried running the GCLC program using the \usepackage{gclc} command in the preamble of the $LaTeX$ document. But it says "gclc.sty not found" I have the above file. Where do I have to put it???

thanks a lot!!!
just a conformation: You can add GCLC files only as separate objects rather than as normal .eps files are added to a Latex Document?!?!

What do you mean?

I just create the diagram using WinGCLC, then I select the option "export to LaTeX" and then I type \input{...}. Done.

I believe the document you posted above isn't working!

If you mean imo20045.dvi then save it first before opening it, rather than just opening it. It should work fine then.

Can you please include the code for the above document imo200405.dvi files. I twill be immensely useful!!

[quote="Arne"]Create the folder .../texmf/tex/latex/gclc and put gclc.sty in there :)

(That's how I did it :))[/quote]
another way, just put gclc.sty in the same folder where you make your tex file. Thats what i did if i was lazy to put the .sty in the correct path :).

[quote="Arne"]Rushil, do you mean the commands I used to create the diagram? :)[/quote]

I think he means everything, from scratch :)

Here is the LaTeX file. For some reason the .gcl file was not accepted on the forum.

So, I am just posting it here, sorry:

number XSIZE 140
number YSIZE 100
dim XSIZE YSIZE

number Xlb 5
number Ylb 5
number Xrt 135
number Yrt 95
area Xlb Ylb Xrt Yrt
point P1 Xlb Ylb
point P2 Xrt Ylb
point P3 Xrt Yrt
point P4 Xlb Yrt
drawdashsegment P1 P2
drawdashsegment P2 P3
drawdashsegment P3 P4
drawdashsegment P4 P1
point O 70 50
point J 70 80

circle G O J

point B 46 68
drawpoint B
cmark_lt B

point D 94 68
drawpoint D
cmark_rt D

point O' 70.6 52
point O" 69.0 52
line z' O O'
line z" O O"
intersec2 A J' G z'
intersec2 J" C G z"
drawpoint A
drawpoint C
cmark_lt A
cmark_rb C

drawsegment A B
drawsegment A D
drawsegment B D
drawsegment B C
drawsegment C D

bis l A D C
intersec2 D E l G
line p D E
line d B D
sim B' p B
line s D B'
med t A C
intersec P s t
drawpoint P
cmark_lb P
drawsegment A P
drawsegment B P
drawsegment C P
drawsegment D P

line l_{AB} A B
line l_{BC} B C
line l_{CD} C D
line l_{DA} D A
perp a P l_{AB}
perp b P l_{BC}
perp c P l_{CD}
perp d P l_{DA}
intersec A' a l_{AB}
intersec B' b l_{BC}
intersec C' c l_{CD}
intersec D' d l_{DA}
drawpoint A'
drawpoint B'
drawpoint C'
drawpoint D'
cmark_lt A'
cmark_lb B'
cmark_rb C'
cmark_rt D'
drawdashsegment P A'
drawdashsegment P B'
drawdashsegment P C'
drawdashsegment P D'
drawsegment A' B'
drawsegment B' C'
drawsegment C' D'
drawsegment D' A'
midpoint M B P
midpoint N D P
drawsegment M N
drawpoint M
cmark_rt M
drawpoint N
cmark_rb N
line a M N
drawline a

Thanks, Arne!!! please tell us the language of your page http://www.q-e-d.be Do you have an english version??

That is Dutch. :)

And no, I am sorry but we don't have an English version. It is an IMO training page for Belgian students...


topology
advanced fields
advanced fields unsolved

Possibly a dumb question, but I'm not getting this

Suppose $ X$ is a set and $ A\subset X$ is non empty
Is $ \mathcal{T}\equal{}\{\phi,A,X\}$ a Topology over $ X$?

Now, an open set $ S\in\mathcal{T}$ has the property that for any member $ x\in S$, there exists a neighbourhood $ V$ such that $ x\in V\subset S$. How is this true in the case above?

Also, is the property $ x\in V\subset S$ or should it be $ x\in V\subseteq S$?

[quote="shreyas_patankar"]Is $ \mathcal{T} \equal{} \{\phi,A,X\}$ a Topology over $ X$?[/quote]
yes (trivial)
[quote]Now, an open set $ S\in\mathcal{T}$ has the property that for any member $ x\in S$, there exists a neighbourhood $ V$ such that $ x\in V\subset S$. How is this true in the case above?[/quote]
why do you doubt it? anyway, put $ V \equal{} S$ ...
 [quote]Also, is the property $ x\in V\subset S$ or should it be $ x\in V\subseteq S$?[/quote]
yes, but many authors are lazy and write subsets as $ \subset$.

Ok thanks

My problem was that I was not sure if we had to use only proper subsets or that $ V\equal{}S$ was allowed


function
linear algebra
combinatorics
IMO Shortlist
Ramsey Theory

Suppose that every integer has been given one of the colours red, blue, green or yellow. Let $x$ and $y$ be odd integers so that $|x| \neq |y|$. Show that there are two integers of the same colour whose difference has one of the following values: $x,y,x+y$ or $x-y$.

Please post your solutions. This is just a solution template to write up your solutions in a nice way and formatted in LaTeX. But maybe your solution is so well written that this is not required finally. For more information and instructions regarding the ISL/ILL problems please look here: [url=http://www.mathlinks.ro/Forum/viewtopic.php?t=15623]introduction for the IMO ShortList/LongList project[/url] and regarding[url=http://www.mathlinks.ro/Forum/viewtopic.php?t=15623]solutions[/url]  :)

Let's assume $x,y>0$ (clearly, we can do this, since if what we want to prove doesn't hold, then it doesn't hold if we replace $x$ with $-x$ and/or $y$ with $-y$). Let's work with non-negative integers only.

The negation of what we want to prove states that there is a set $S\subset \mathbb N$ s.t. $S,S+x,S+y,S+x+y$ are mutually disjoint, and their union is $\mathbb N$. This means that, working with formal power series, $1+t+t^2+\ldots=\left(\sum_{s\in S}t^s\right)(1+t^x)(1+t^y)$. Assume now that $y<x$. We have $\frac{1+t+t^2+\ldots}{1+t^y}=(1+t+\ldots+t^{y-1})+(t^{2y}+t^{2y+1}+\ldots+t^{3y-1})+\ldots=\mathcal E$.

When we divide $\mathcal E$ by $1+t^x$ we have to get a series whose only coefficients are $0$ and $1$, and this will yield the contradiction: our series contains $1+t+\ldots+t^{y-1}$, because $y<x$. There must be a $k$ s.t. $x\in(2ky,(2k+1)y-1)$ (the interval is open because the endpoints are even, but $x$ is odd). However, there is an $\alpha\in\overline{0,y-1}$ s.t. $x+\alpha=(2k+1)y$, and this means that if our power series has no negative terms (to get rid of $t^{(2k+1)y}$, which does not appear in $\mathcal E$), when multiplied by $1+t^x$ contains $t^{(2k+1)y}$, but $\mathcal E$ doesn't have this term, so we have a contradiction.

[b]OFFICIAL SOLUTION[/b]

Suppose that there exist a colouring function $f: \mathbb{Z} \rightarrow \{R,B,G,Y\}$ with the property that for any integer $a$

\[
f\{a,a+x,a+y,a+x+y\} = \{R,B,G,Y\}.
\]
In particular, colouring the integer lattice by the rule

\[
g: \mathbb{Z} \times \mathbb{Z} \rightarrow \{R,B,G,Y\}, g(i,j) = f(ix+jy),
\]
we obtain that the vertices of any unit square have all four different colours.

[i]Claim 1[/i]: If there exists a column $i \times \mathbb{Z}$ such that $g | i \times \mathbb{Z}$ is not periodical with period 2, then there exists a row $\mathbb{Z} \times j$ such that $g | \mathbb{Z} \times j$ is not periodical with period 2.

[i]Proof[/i]: If $g | i \times \mathbb{Z}$ is not periodical, then we can find the configuration $\begin{matrix} Y \\ B \\ R \end{matrix}$; using the adjacent unit squares, we get $\begin{matrix} RYR \\ GBG \\ YRY \end{matrix}$ and also $\begin{matrix} YRYRY \\ BGBGB \\ RYRYR \end{matrix}$ and so on. Thus we obtain three periodical lines. $\Box$

[i]Claim 2[/i]: If for one integer $i,g_i = g | \mathbb{Z} \times i$ is periodical with period 2, then for every $j \in \mathbb{Z}, g_j  = g | \mathbb{Z} \times j$ has period 2. The values of $g_i$ are the values $g_j$ if $i \equiv j \pmod{2}$ and the other values if $i \not \equiv j \pmod{2}$.

[i]Proof[/i]: Applying the square rule to the line $\ldots RBRBRB \ldots$ we get $\begin{matrix} \ldots YGYGY \ldots \\ \ldots RBRBR \ldots \end{matrix}$ and next $\begin{matrix} \ldots RBRBR \ldots \\ \ldots YGYGY \ldots \\ \ldots RBRBR \ldots \end{matrix}$ or $\begin{matrix} \ldots BRBRB \ldots \\ \ldots YGYGY \ldots \\ \ldots RBRBR \ldots \end{matrix}$
A similar argument holds for the rows below the line $\mathbb{Z} \times i$. $\Box$
Changing between the 'rows' and 'columns' we have similar claims. So we can suppose that the rows are periodical with period 2 and $g(0,0)= R, g(1,0)=B$. Therefore $g(y,0) = B$ ($y$ is odd). The row $\mathbb{Z} \times \{x\}$ is odd too; hence $ g(\mathbb{Z} \times \{x\}) = \{Y,G\ $. From $g(y,0) = f(xy) = g(0,x)$ we get a contradiction.

[i]Remark[/i]: The same result is true for $x = 2^k(2p+1), 2^k (2q+1)$; just take $g(i,y) = f(\frac{ix+jy}{2^k})$.

[hide]
$x, y$ can be taken such that they are coprime (divide by gcd) and congruent $\pmod{4}$ (flip one of their signs if not). Let $y = x + 4k$. Define $f(b, c)$ (from $\mathbb{Z}^2$ to $\{1, 2, 3, 4\}$) to the color of $xb + 4kc$, and define $g(b, c)$ to be the set of two colors $\{f(b, c), f(b + 1, c)\}$. It is easier to work first with $g$.

Suppose that a consistent function $f$ exists. Then, $f(b, c)$ is not equal to $f(b + 1, c), f(b, c + 1), f(b + 1, c + 1)$, or $f(b + 2, c + 1)$. So no two of $f(b, c), f(b + 1, c), f(b + 1, c + 1), f(b + 2, c + 1)$ are equal. Thus $g(b, c) = g(b + 1,c + 1)^c$ (complement in $\{1, 2, 3, 4\}$). In particular

$g(b, c) = g(b + 2, c + 2)$  (1)

by applying that twice.

Going back to the definition of $f$, $f(b + 4k, c - x) = f(b, c)$, so the same identity holds for $g$ in place of $f$.

$g(b, c) = g(b + 4k, c - x)$ (2)

From (1) and (2) we can find that

$g(b + 8k - 2x, c) = g(b, c)$

and

$g(b, c + 4k + x) = g(b, c)$,

so $g$ is periodic in both $b$ and $c$! From here for any $\alpha, \beta, \gamma$, we have

$g(b + 4k\alpha + (8k-2x)\beta, c - x\alpha + (4k + x)\gamma) = g(b, c)$

In particular $g(b, c + 1) = g(b, c)$ since $x$ and $4k + x$ are coprime. But that yields a contradiction because $f(b, c) \not\in g(b, c+1)$.
[/hide]

Hopefully this is different form the above:

As everyone else did, note that the set $\{a, a+x, a+y, a+x+y\}$ must have 4 distinct colors. Assume $\gcd{x, y} = 1$, or just only work with multiples of the $\gcd$. Let the "colors" have values assigned to them, let's say $\{-3, -1, 1, 3\}$ for fun (it doesn't matter). Let $c_i$ be the color number assigned to the number $i$.

Firstly assign color numbers to $c_0, c_1, \ldots, c_{x+y-1}$. Since $\{a, a+x, a+y, a+x+y\}$ is 4 distinct colors, the $c_i$ satisfy a recurrence: $c_{x+y+i}+c_{x+i}+c_{y+i}+c_i = -3-1+1+3 = 0$. The characteristic polynomial of this recurrence is $Z^{x+y}+Z^x+Z^y+1 = (Z^x+1)(Z^y+1)$. Since I let $\gcd(x, y) = 1$, and both are odd, the polynomial has a double root at $-1$ and single roots at roots of unity. Therefore, the characteristic polynomial is of the form $(Cn + D) \cdot (-1)^n + \sum_{\text {roots of unity  } \omega_i} C_i \cdot \omega_i^n$. Since the $\omega$ terms are bounded, but the linear term isn't, the magnitude of terms can grow arbitrarily large, so they will no longer lie in the set $\{-3, -1, 1, 3\}$, contradiction. $_\blacksquare$

[b]Edit:[/b] Blah yeah, see below. $C = 0$ is possible. Hmmm, I can't see how to patch this.

[quote="mathocean97"]$(Cn + D) \cdot (-1)^n + \sum_{\text {roots of unity  } \omega_i} C_i \cdot \omega_i^n$. Since the $\omega$ terms are bounded, but the linear term isn't, the magnitude of terms can grow arbitrarily large, so they will no longer lie in the set $\{-3, -1, 1, 3\}$, contradiction. $_\blacksquare$[/quote]
We could have $C=0$ though, if $c_0+\cdots+c_{x+y-1}t^{x+y-1}$ is always divisible by $1+t$ no matter what we choose for the $c_i$ (for instance, if $c_0 = \cdots = c_{x+y-1}$, since $x+y-1$ is odd).
---
Also, let's fix grobber's solution:
[quote="grobber"]Let's assume $x,y>0$ (clearly, we can do this, since if what we want to prove doesn't hold, then it doesn't hold if we replace $x$ with $-x$ and/or $y$ with $-y$). Let's work with non-negative integers only.

The negation of what we want to prove states that there is a set $S\subset \mathbb N$ s.t. $S,S+x,S+y,S+x+y$ are mutually disjoint, and their union is $\mathbb N$.[/quote]
This is not quite true, but almost true. Let $R$ be the set of red integers, so $R,R+x,R+y,R+x+y$ are pairwise disjoint (if $R+x,R+y$ intersect, then so do $R,R+x-y$, etc.), and also cover the integers (exactly one of $n,n-x,n-y,n-x-y$ is red for each integer $n$; actually this gives us pairwise disjoint-ness too). Note that we don't necessarily know that $R+x$ (for instance) is monochromatic, but it is true that such $R$'s existence would allow a construction with $R+x,R+y,R+x+y$ all blue, yellow, and green, respectively.

Following [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2444807#p2444807]this post[/url], $R$ is purely periodic with some period $\ell>0$. If $f$ denotes the indicator function of $R$, then $f(n)+f(n-x)+f(n-y)+f(n-x-y)=1$ for $n=0,1,\ldots,\ell-1$, so
\[ P(t)=\sum_{k=0}^{\ell-1}f(k)t^k\implies P(t)(1+t^x)(1+t^y)\equiv 1+t+\cdots+t^{\ell-1}\pmod{t^\ell-1}. \]Now $4P(1)=\ell$, so $\ell = 2^r s$ for some $r\ge2$ and odd $s$. If $\gcd((t^{2^r}-1)/(t^2-1),(1+t^x)(1+t^y)) = 1$ (as polynomials), then $\frac{t^{2^r}-1}{t^2-1}\mid P(t)$ (in $\mathbb{Z}[t]$), so $2^{r-1}\mid P(1) = \ell/4 = 2^{r-2} s$, contradiction. Since $1+t^{2^u}$ is irreducible for $u=1,2,\ldots,r-1$, we have some $1+t^{2^u}\mid (1+t^x)(1+t^y)$, which is absurd, since $\gcd(1+t^{2^u},1+t^z) = 1$ for any odd $z$.

I'd like to propose a solution based on a different idea- an application of discrete fourier transform (DFT).
Let $f(n)$ be the indicator function of, for example, the red integers. Suppose on the contrary:
\[ f(n) + f(n-x) + f(n-y) + f(n-x-y) =1 \,, \forall n\in \mathbb{Z} \]
As mentioned in the above post, $f$ is periodic. We can establish that without using [url=http://terrytao.wordpress.com/2007/05/25/open-question-effective-skolem-mahler-lech-theorem]Skolem-Mahler-Lech theorem[/url]. Let us take some integer $T,\, T>x+y$ and consider the following $(x+y)$-tuples: $\left(f(kT+1), f(kT+2),\cdots, f(kT+x+y) \right)\,, k=0,1,\ldots$. Obviously, there are two of them, for $k=k_1$ and $k=k_2$ that coincide, which yields $f$ is periodic with period $\ell=(k_2-k_1)T$.

We proceed by considering the discrete fourier transform $\hat{f}$ of $f$.
\[\hat{f}(n):= \frac{1}{\ell}\sum_{k=0}^{\ell-1} f(k)\cdot e^{\frac{-2\pi i n\cdot k}{\ell}}\,\,\,\,\,\,\,\,\text{(1)} \]
The inverse Fourier formula holds:
\[f(n)= \sum_{k=0}^{\ell-1} \hat{f}(k)\cdot e^{\frac{2\pi i n \cdot k}{\ell}} \,\,\,\,\,\,\, \text{(2)}\]

For given $f,g$ , complex valued, periodic with period $\ell$, let us define its inner product as:
\[\langle f,g \rangle_{L^2} = \frac{1}{\ell}\sum_{k=0}^{\ell-1} f(k)\cdot \overline{g(k)}\]
and on the Fourier side as:
\[\langle f,g \rangle_{\hat{L}^2} = \sum_{k=0}^{\ell-1} f(k)\cdot \overline{g(k)}\]

Then the following properties take place:
\[\langle f,g\rangle_{L^2} = \langle \hat{f}, \hat{g}\rangle_{\hat{L}^2} \]
(Parseval identity)
\[\|f\|_{L^2}= \|\hat{f}\|_{\hat{L}^2} \]
(Plancherel identity)
In our case, since $f(\cdot),f(\cdot-x), f(\cdot-y), f(\cdot-x-y)$ are orthogonal with the same $L^2$ norm, we obtain:
\[ \|f\|_{L^2}^{2}=\frac{1}{4} \,\,\,\,\,\,\, \text{(3)} \]
Hence, $\hat{f}(0) = \frac{1}{\ell} \sum f(k) =\frac{1}{4}$. Furthermore, for a given $a\in \mathbb{Z}$, we have: $\widehat{f(n-a)} = \hat{f}(n)\cdot e^{-\frac{2\pi i n a}{\ell}}$. Hence:
\[ \hat{f}(n) (1+\omega_n^x)(1+\omega_n^y) = \hat{1}= \delta(n) \,\,\,\,\,\,\text{(4)} \]
where $\omega_n=e^{-\frac{2\pi i n}{\ell}},\,  \delta(n)=1$ for $n=0$ and $\delta(n)=0$ if $ n\neq 0$
Denote:
\[ A=\{n\in \mathbb{Z}\mid 0\leq n\leq \ell-1, \omega_n^x=-1 \text{ or }\omega_n^y=-1 \} \]
Thus, using (4), we have $ \hat{f}(n)=0, \, n\not\in (A\cup \{0\})$. Now, applying (2), for $n=xy $ and  $n=2xy$, we get:
\[ f(xy) = \hat{f}(0) + \sum_{n\in A} \hat{f}(n)\cdot \omega_n^{x\cdot y} = \frac{1}{4} - \sum_{n\in A} \hat{f}(n) \]
because of $\hat{f}(0)=\frac{1}{4}$ and $\omega_n^{xy} = -1$ when $n\in A$. Here we use the fact $x,y$ are both odd. In the same way:
\[ f(2xy) = \frac{1}{4} + \sum_{n\in A} \hat{f}(n) \]
It means that $f(xy)+f(2xy)=\frac{1}{2}$ which is imposible since $f(n)\in \{0,1\}$.

[hide="Copy-Pasta Facebook"]so if you look at the 4-tuple
(s, s + b, s + a, s + a + b)
where we assume WLOG a > b
then it's easy to see this tuple must be rainbow

now look at the 4-tuple
(s + a, s + a + b, s + 2a, s + 2a + b)
the first two coordinates of this tuple are the last two coordinates of the previous one
so (s + 2a, s + 2a + b) must be colored with some permutation of the (distinct) colors assigned to (s, s + b)
continuing this way, we see that (s + ab, s + ab + b) must be colored with some permutation of the (distinct) colors assigned to (s + a, s + a + b)

now we do the same thing for b-shifts
look at (s, s + b, s + a, s + a + b)
and (s + b, s + 2b, s + a + b, s + a + 2b)
again we have some overlap, which tells us (s + 2b, s + a + 2b) must be colored with some permutation of the (distinct) colors assigned to (s, s + a)
once more, continuing this forces (s + ab, s + ab + a) to be colored with some permutation of the (distinct) colors assigned to (s + b, s + a + b)

thus s + ab must be colored the same as s + a + b
which means s + ab + a must be colored the same as s + b
and s + ab + b must be colored the same as s + a
and finally that s + ab + a + b must be colored the same as s

thus shifts by each of the following 4 values preserves color:
ab + a + b
ab + a - b
ab - a + b
ab - a - b

in particular, shifts of 2a and 2b preserve color
since a, b are odd and coprime, some linear combination of them equals 1 whence shifts by 2 must preserve color
yet this means numbers are colored by parity, which can't be since (a + b) is even
and a forbidden difference[/hide]

[quote=hyperbolictangent]so if you look at the 4-tuple
(s, s + b, s + a, s + a + b)
where we assume WLOG a > b
then it's easy to see this tuple must be rainbow

now look at the 4-tuple
(s + a, s + a + b, s + 2a, s + 2a + b)
the first two coordinates of this tuple are the last two coordinates of the previous one
so (s + 2a, s + 2a + b) must be colored with some permutation of the (distinct) colors assigned to (s, s + b)
continuing this way, we see that (s + ab, s + ab + b) must be colored with some permutation of the (distinct) colors assigned to (s + a, s + a + b)

now we do the same thing for b-shifts
look at (s, s + b, s + a, s + a + b)
and (s + b, s + 2b, s + a + b, s + a + 2b)
again we have some overlap, which tells us (s + 2b, s + a + 2b) must be colored with some permutation of the (distinct) colors assigned to (s, s + a)
once more, continuing this forces (s + ab, s + ab + a) to be colored with some permutation of the (distinct) colors assigned to (s + b, s + a + b)

thus s + ab must be colored the same as s + a + b
which means s + ab + a must be colored the same as s + b
and s + ab + b must be colored the same as s + a
and finally that s + ab + a + b must be colored the same as s [/quote]

Why is $s+ab$ the same as $s+a+b$ though?

[quote=dgrozev]
In our case, since $f(\cdot),f(\cdot-x), f(\cdot-y), f(\cdot-x-y)$ are orthogonal with the same $L^2$ norm, we obtain:
\[ \|f\|_{L^2}^{2}=\frac{1}{4} \,\,\,\,\,\,\, \text{(3)} \]
Hence, $\hat{f}(0) = \frac{1}{\ell} \sum f(k) =\frac{1}{4}$.
[/quote]

Hi bro. Sorry that I can't understand how you obtain $\[ \|f\|_{L^2}^{2}=\frac{1}{4}$. Could you write it in detail? Thank you so much!

Update: I think this part is not necessary...

Assume on the contrary that there exists a coloring such that for each integer $s$, $s$, $s+x$, $s+y$, and $s+x+y$ are all different colors. Let $C_s(a,b)$ denote the color of $s+ax+by$. Then, $C_s(a,b)$, $C_s(a,b+1)$, $C_s(a+1,b)$, and $C_s(a+1,b+1)$ are all distinct. We also know that $C_s(a+1,b)$, $C_s(a+1,b+1)$, $C_s(a+2,b)$, and $C_s(a+2,b+1)$ are all distinct. Therefore, \[\{C_s(a,b),C_s(a,b+1)\}=\{C_s(a+2,b),C_s(a+2,b+1)\}\] and similarly,
\[\{C_s(a,b),C_s(a+1,b)\}=\{C_s(a,b+2),C_s(a+1,b+2)\}\]
Suppose $C_s(a,b)\neq C_s(a,b+2)$ for some $a,b$. Then, $C_s(a,b)$, $C_s(a,b+1)$, $C_s(a,b+2)$ are all distinct. Since $C_s(a+1,b+1)$ cannot be any of those colors, so its color is fixed, fixing the colors of $C_s(a+1,b)$, which happens to equal $C_s(a,b+2)$ and $C_s(a+1,b+2)=C_s(a,b)$. In particular, $C_s(a+1,b)\neq C_s(a+1,b+2)$, which means that $C_s(a+1,b)$, $C_s(a+1,b+1)$, $C_s(a+1,b+2)$ are all distinct, so we can apply the same operation. Note that in this way we get that $C_s(a,b)=C_s(a+1,b+2)=C_s(a+2,b)$. Thus, colors are periodic either by $2x$ or $2y$. Let the minimum period be $k$ with $4\nmid k$, but then there is more of one color, clearly false by  considering the grid globally (since each $2\times 2$ square has equal parts of each color). We are done.

Here's a completely elementary combinatorial solution. Assign the colors labels of $1, 2, 3, 4$, and let $C(x)$ be the color of $x$.

We will look at an infinite table where the entry in the $a$th row and $b$th column is equal to the color of $ax+by$. In particular, any $2 \times 2$ subgrid of this table must have four distinct values.

[b][color=#f00]Claim.[/b][/color] Suppose some row $a$ in this table is not periodic with period $2$. Then row $a+2$ must be identical to row $a$.

[i]Proof.[/i] Actually, I claim that we can describe the contents of row $a$ explicitly. Because no two consecutive entries in a row may be identical, there must exist three consecutive distinct entries in row $a$, say $1, 2, 3$ at positions $b-1, b, b+1$. It follows that the entry at $(a+1, b)$ is fixed (in this case, at $4$), and because no two entries in row $a+1$ can be identical that $(a, b+2)$ contains $4$. Repeating this process, it necessitates that row $a$ consists of all four colors cycled with period $4$. As row $a+1$ also contains four colors cycled with period $4$ shifted by $2$ from row $a$, it follows that rows $a$ and $a+2$ are identical. $\blacksquare$

This implies that either all the rows are periodic with modulo $2$ or all the columns are periodic with modulo $2$; assume the former. But the entry at $(a_1, b_1)$ must be identical to the entry at $(a_1-y, b_1+x)$, but this is impossible because $b_1+x$ and $b_1$ are opposite parity.


USAMTS
AMC
USA(J)MO
USAMO
calculus
AMC 10
number theory

How can I tell whether I actually know enough math to answer a question? That is- suppose a problem doesn't use any words or symbols I'm unfamiliar with but I cannot seem to form a method to solve it with.

This is also something I want to know for the USAMTS, which I assume contains more advanced math than what I would see on the AMC 10 or Mathcounts. Actually, does it?

I want to know if I can determine when to spend a few more hours on a problem and when to research or go back to the books to learn more first...

Here's one hint that has served me well. Be confident that if there's some result you don't know that would help solve a problem, you have the ability to eventually rediscover that result, or at least the part essential to solving the problem. If not that, then you'll find another approach more suited to the math you do know. Then plunge in. This philosophy is best used on Olympiads, which have longer time limits; on tests like the AMC, do the same thing except save those problems for last. If you think a problem is impossible because you don't know enough, you really won't get anywhere.

For instance, back when doing last year's USAMO #4, I had no idea it could be cited as well-known that turning a connected graph into a tree was always possible; I didn't even know the term tree existed. I still used that in my proof; I just had to sit on the problem for hours.

Some exceptions to this are Fermat's Last Theorem, Bertrand's Postulate, and Dirichlet's Theorem, which have proofs that can't be rediscovered on a timed test.

[quote="randomdragoon"]I'm pretty sure Fermat's Last Theorem would be useless in almost any testing circumstance  :P[/quote]

OBJECTION! One of the short-answer contests last year used it :P I think it was PuMaC?

[quote="randomdragoon"]I'm pretty sure Fermat's Last Theorem would be useless in almost any testing circumstance  :P[/quote]
What? I've definitely used it on some number theory problems I've done from past olympiads.

[quote="Hamster1800"][quote="randomdragoon"]"The problems can all be solved using pre-calculus methods"

hmm?[/quote]

Citing Fermat's Last Theorem and proving it are very different difficulty.[/quote]

Like Euler's Formula? It is pretty common in pre-calc but most proof's I've seen involve calculus.

[quote="Hamster1800"][quote="randomdragoon"]"The problems can all be solved using pre-calculus methods"

hmm?[/quote]

Citing Fermat's Last Theorem and proving it are very different difficulty.[/quote]

A person who doesn't know calculus can cite a lot of theorems from calculus too but that doesn't mean a problem should require it.

Easy to say, but I think a lot of contests on the Olympiad level disagree with you. I won't get into more details because we've derailed this topic. Someone besides me should respond to the original query.

Always try a question. Stop if you are just staring at the problem without testing any approaches.

Ok, back on topic: I have sat through USAMO competitions where I have gotten a solution literally in the last half-hour. So, don't automatically assume that if you don't find an answer now, or and hour from now you won't find an answer after working on it for another couple hours, because you just might.


geometry
geometric transformation
reflection
analytic geometry

Thetis, who is currently at the point $ (1,\minus{}2)$, needs to take Achilles to the river Styx(represented by the line $ y\equal{}x\plus{}1$) to give him his morning bath. She must then take him to the point $ (2,1)$, where he will be trained as a warrior. Find the shortest distance that Thetis can travel.

[quote="greentreeroad"]hint:
[hide]reflect (2,1) in line y=x+1, the shortest distance is from (1,-2) to the reflected point (why? :D [hide]because the length of segment between two points is the shortest distance between them, and the path from (1,-2) to a point on line y=x+1 then to the reflection point equals the length of path you might take in the problem[/hide][/hide][/quote]
Well there's one of my problems, I don't know how to reflect a point over such line D:

Let's make a substitution to shift our coordinate system. Let $ z \equal{} x \plus{} 1$.

Now, our $ (z,y)$ coordinates are $ (2, \minus{} 2)$ for Thetis' current location, the river Styx is $ y \equal{} z$, and the destination point is $ (3,1)$.

The suggestion was to reflect the destination point across Styx. Do you know how to reflect across the line $ y \equal{} z$?  :wink:

[hide="Answer to the above"]Switch the $ y$ and $ z$ coordinates[/hide]


For every positive integer m, does there exist a positive integer n such that the sum of the digits of n is m and the sum of the digits of n^2 is m^2?

I noticed that 1...1 (m 1's) satisfies the criteria (by elemenrary-school long multiplication), but is that considered a valid *proof* (ie acceptable on an olympiad)? How would I prove it rigorously? Would writing n^2 as (Sum[1..m-1] 10^k)^2 and considering integer partitions of the exponents be valid?

Did you try m 1's for m :ge: 10?  I think you will be in for a surprise.

could you have m for any number and m followed by x zeroes for n?

It seems to me that it's a funny question since n=1 works. Perhaps they asked if there are infinitely many or something like that?

[quote="Fierytycoon"]Ravi:

Whoops, guess I was wrong. However, in any case, say that it did indeed work. Would working everything out using long-multiplication in a not-so-rigorous sort of fashion as I mentioned above be viable for an olympiad?[/quote]

Well the questions asks does there exist, if you find one and prove that it works then thats rigourous enough.. in this case, you don't want to write 11...11 as the sum of powers of 10, you write it as (10^m-1)/9. Square that and its easy to see what the answer looks like..

ComplexZeta, yes, I think the problem needs a "For every positive integer m," added to the beginning.

Fiery, I don't really know what the standards are for Olympiad grading.  My guess is that they are looking for rigorous proofs.  I think your presentation would fall short.  It's okay to say "m 1's", but then you would have to say (and, even better, prove) what the square of such a number looks like.

By the way, Fiery, I think you can fix up your example by adding some 0's.  Consider the sum of 102i for i from 0 to m - 1.  To prove that it works, you can use the fact that binary representation of numbers is unique.  But you do need a proof...

How did you ever come up with something like 10^(2^i)?

What messed up your original example were carries.  So I looked for a way to avoid carries.  For the exponents of 10, I was looking for a sequence of numbers ai such that no number is represented by the form ai + aj in more than 2 (or even 9) different ways.  I thought of ai = 2i because I knew binary representation was unique.

The idea is to do the same thing that you were trying to do with the 1111...11 but with enough extra spaces so that you don't carry over and mess up the digital sum.

[quote="Fierytycoon"]Eh, yeah, sorry, it should be "for every m". The original problem had m=1999, and I forgot to change the wording for the generalization.

[quote] in this case, you don't want to write 11...11 as the sum of powers of 10, you write it as (10^m-1)/9. Square that and its easy to see what the answer looks like..[/quote]

Emm...not so easy for me. :( Maybe I am missing something...[/quote]

OK this is unrelated to the problem now but its (10^2m - 2x10^m +1)/81, which is 99999....800000...001 divided by 9 twice, which is 111...10888..89 divided by 9.. which is 1234... blah blah you can work it out like that..

Ok, thanks for the help guys. So we don't even need to use base 2; since numbers in any base b are uniquely represented, we can use any base, right?


Prove that the necessary and sufficient condition for which all of $ a,\ b,\ c$ are positive real numbers is $ a\plus{}b\plus{}c>0,\ ab\plus{}bc\plus{}ca>0,\ abc>0.$

For three variables it can be done in many ways.

[color=red]I would be interested in a purely algebraic solution for $ n$ variables, where the fact that all fundamental symmetric expressions (from $ \sum x, \sum xy, \ldots$ to $ \prod x$) are positive implies the variables being positive.[/color]

[color=blue](Analytically, this is easily done by considering the table of variation for the polynomial whose roots are the variables, and the coefficients the fundamental symmetric expressions (by Viete).)[/color]

EDIT. [color=red]Drats, it was too simple! For the $ k^{\textrm{th}}$ fundamental symmetric expression being $ a_k > 0$, and the polynomial whose roots are the variables being $ P(x) \equal{} x^n \minus{} a_1x^{n \minus{} 1} \plus{} \cdots \plus{} ( \minus{} 1)^na_n$, calculating in $ x < 0$ yields $ P(x) < 0$ for $ n$ odd, and $ P(x) > 0$ for $ n$ even, hence always $ P(x) \neq 0$, therefore all roots are positive.[/color]

For some odd reason, this question reminds me of Descartes' Rule of Signs...  :huh:

[quote="mavropnevma"]For three variables it can be done in many ways. [/quote]

Can you show your solution?

Let $ p,q,r$ be $ a\plus{}b\plus{}c,ab\plus{}ac\plus{}bc,abc$ respectively.

$ x^3\minus{}px^2\plus{}qx\minus{}r\equal{}0$, which has roots $ a,b,c$. If x is non-negative, then it cannot be a root ( since L.H.S. $ \le \minus{}r$), so $ a,b,c > 0$.

If one or three of the variables is negative then the third inequality is obviously false. If two of them, b and c, are negative, we can let $ a \equal{} x$, $ b \equal{} \minus{} y$, $ c \equal{} \minus{} z$, where $ x$,$ y$ and $ z$ are positive. Then the first two inequalities are
$ x > y \plus{} z$
$ yz > x(y \plus{} z)$
But these two would imply $ yz > (y \plus{} z)^2\equal{}y^2\plus{}2yz\plus{}z^2$, a contradiction.


superior algebra
superior algebra solved

Hello

suppose $R$ is a noncommutative ring with identity

suppose $1-a b$ is a unit (thus invertible)

prove that $1- b a$ is also a unit

I can't find it  :|

Let c(1-ab)=1, then from
(1-ab)a = a(1-ba), multiply both sides by c,
a = ca(1-ba) multiply both sides by b,
ba = bca(1-ba)
0 = bca(1-ba) - ba
1 = bca(1-ba) + (1-ba)
1 = (bca+1)(1-ba)
Using the same way we get (1-ba)(bca+1) = 1 too.

nice  :D
how did you do it?
just playing around, or did you know which inverse to work towards to?

tried to mess around and thought a(1-ba)=(1-ab)a is  of some importance  :D


i could not understand the official soln of this problem. can any one help?? (specially u gold medalist KUBUS?? :D )

What exactly do you not understand? I don't feel like explaining everything in detail, but basically, it's all about data structure which I call an "interval tree" = a binary tree, whose nodes represent some number intervals, two children of each node representing two parts (halves) of the interval represented by that node. If you store some additional information in the nodes (besides the boundaries of the intervals themselves), you can do interesting things in an interesting time (O(log N)) ... it is useful for computing (and storing so you can retrieve them efficiently) sums, maximums of numbers in given intervals. With a little of thought, you can figure out how. With a little more of thought, you will figure out how to solve the MOUntain problem ... but I wouldn't really dare to implement it. (That's why I've got a 76;-)

well, say the size of the rail is: 100. and u r given: I 3 3. then???

[What i am wondering is what will be the memory size??]

again say after I 3 3 i am giving u I 3 4. in that case u have to modify two nodes right?? this is where i am puzzled :(

Concerning memory size: you can either do this dynamically (start with an interval, say, 1..100 and on an incoming query with boundaries not matching current intervals, divide the intervals that the new querry falls into) or statically - read the input all at once and then you will know what are the smallest possible intervals (memory = O(reconfig.queries)), so you can construct the tree just as you do a heap and it will be balanced.

I don't exactly know what you mean by I 3 3, because it needs 3 parameters, but anyway, what you do strongly depends on how exactly you do your solution. I think that the model solution describes one way to do it quite well.

The number of nodes you have to modify is at least log N, even if you reconfigure a single point of the track. You then have to modify nodes representing the intervals which contain this point, that is, all its predecessors in the tree...

hmm.. now i am 100% clear! Thanks kubus!

Just out of curiosity, did you go to the IOI last year mahbub? (i know kubus did as per your post above)

well snow, most probably u missed "IOI result" topic. if u had read that u would be clear.

anyway, i was selected from our country for IOI 2005. But for the VISA reason we could not go. we did not get VISA in due time (they agreed when it was all over  :mad: )

but i participated at online version of IOI and there i scored 399 which would have managed me silver :) .

Mahbub


For what n can one place the integers 1 to n on a circle so  that the sum of any two successive integers in the circle is divisible  by the next one in clockwise order

Answer: $n=3$.

If walking clockwise if we meet odd,even,even we have that even divides odd+even=odd contradiction!
So, there must not be even,even.
but before every even number we must have two numbers which are both even or both odd. But we cannot have even,even so we must have odd,odd.
Now, before every even number there must be two odd numbers
Then
$|oddnumberslessthanN|\geq 2|evennumberslessthanN|$
which is possible only when n=3.


Prove that for any positive integer $ n>5$, the set $ A\equal{}\{ n,2n\plus{}1,3n\plus{}2,4n\plus{}3,6n\plus{}1 \}$ contains at least one compound number.

Go to High School Basic.

mod 5 all of them and the result follows.


trigonometry
function
vector
calculus
derivative
analytic geometry
calculus computations

Obtain the equation of the plane which is tangent to the surface $ z \equal{} 3x^2y \sin \left(\frac{\pi x}{2}\right)$ at the point $ x \equal{} y \equal{} 1$.

Take East to be in the direction $ (1,0,0)$ and North to be $ (0,1,0)$. In which direction will a marble roll if placed at the surface at $ x \equal{} 1, y \equal{} \frac{1}{2}$?

Ok, for the equation of the plane I think the first thing we need to do is set up the function $ f(x,y,z) \equal{} 3x^2y \sin \left(\frac{\pi x}{2}\right) \minus{} z \equal{} 0$. I'm told that $ \nabla f$ gives the normal to the surface at a point if $ f(x,y,z) \equal{} c$ where $ c$ is constant. Why is this so - isn't $ \nabla f$ the direction of the greatest rate of change of the surface?

It's true that $ \nabla f$ is the direction of the fastest change of $ f$. Also, the rate of change in any direction $ u$ (unit vector) is $ \nabla f\cdot u$. On the surface that you're interested in the function $ f$ does not change at all - it stays equal to $ c$. Therefore the directional derivatives of $ f$ in the directions along the surface are all zero. Which means those directions are perpendicular to $ \nabla f$.

I see, but I think the marble should roll along the direction where the change in the surface is the greatest - shouldn't that be in the direction of $ \nabla f$? I think I'm getting something conceptually wrong here  :maybe:

I think you are mixing up two related, but different functions.

1) One of them, which you did not name [a mistake!], is $ g(x,y)\equal{} 3x^2y \sin \left(\frac{\pi x}{2}\right)$. This is a function of two variables. The surface is described by the equation $ z\equal{}g(x,y)$.

2) The other one you called f: $ f(x,y,z)\equal{}g(x,y)\minus{}z\equal{}3x^2y \sin \left(\frac{\pi x}{2}\right)\minus{}z$. This is a function of three variables. The surface is also described by the equation $ f(x,y,z)\equal{}0$.

Both functions are useful. The gradient of $ f$ is a normal vector for the surface, which you need to find the tangent plane. The gradient of $ g$ is a vector in 2 dimensions (in xy-plane). This is the direction of the greatest increase of $ g(x,y)$ -- which is the $ z$-coordinate (height) of the surface. Under the force of gravity the marble will roll so that its $ z$-coordinate [b]decreases[/b] as fast as possible. The vector $ \minus{}\nabla g$ describes that direction, at least partially (in terms of x and y). If you also needed the third component of marble's direction, it's $ \minus{}|\nabla g(x,y)|$. But from the way the question is phrased, I see that a two-dimensional answer is expected (even in geographical terms such as "North-East".)


abstract algebra
Ring Theory
superior algebra
superior algebra unsolved

Let $R$ be a noetherian local ring. Prove that if there exists a nonzero, finitely generated, injective $R$-module, then $R$ is artinian.

First, let's make some notations and some simplifications:

Let $\frak m$ be the maximal ideal of $R$. Also, denote the non-zero, finitely generated, injective module by $M$. Given an element $x\in R,\ \mbox{Ann}(x)$ is its annihilator, i.e. the set $\{y\in R\ |\ yx=0\}$. Similarly, we can define the annihilator $\mbox{Ann}(m)$ of an element $m\in M$. If $x\in R$, then $(x)$ denotes the ideal of $R$ generated by $x$.

Consider the set $\frak a$ of elements in $R$ which are nilpotent and annihilate every element of $M$. Clearly, $\frak a$ is an ideal of $R$, and nothing changes if we replace $R$ with $R/\frak a$. This is because on the one hand, $M$ can be naturally considered to be an $R/\frak a$-module, with all its properties intact (non-triviality, finite generation, and injectivity), and on the other hand, all prime ideals of $R$ contain $\frak a$, so the conclusion we want to reach (namely that $R$ has precisely one prime ideal: Artinian rings = Noetherian rings of dimension zero) is not affected by passing to $R/\frak a$. Now, instead of writing $R/\frak a$, I'll keep $R$ and I'll simply make the additional assumption that $(*)$ there are no non-zero nilpotent elements of $R$ which annihilate all of $M$.

One observation that will be used repeatedly: there is an $R$-module homomorphism from $(x)$ into $M$ sending $x$ onto $m\in M$ iff $\mbox{Ann}(x)\le\mbox{Ann}(m)$. Whenever this happens, by injectivity, the homomorphism can be extended to $R\to M$. If $1\mapsto n$, then $x\mapsto xn=m$, so $m\in xM$.

Now for the actual proof:

Assume there is a non-zero-divisor $x\in\frak m$. Then for any $m\in M$ we can find a homomorphism $(x)\to M$ with $x\mapsto m$. By the remarks made above, $m\in xM$.Since $m$ was arbitrary, this says that $M=xM$. $x$ belongs to the radical of $R$ and $M$ is finitely generated, so Nakayama's Lemma gives $M=0$, contradiction. Hence, all elements of $\frak m$ are zero-divisors.

Assume now that the conclusion we want to reach is false, i.e. assume $\frak m$ is not the only prime ideal. Equivalently, assume not all elements in $\frak m$ are nilpotent.

The set of zero-divisors is the union of the finitely many prime ideals belonging to $(0)$ in $R$ (the radicals of the members of a primary decomposition of $(0)$, that is), so by teh above, $\frak m$ must coincide with one of these prime ideals. Since the mentioned prime ideals are precisely the prime annihilators of elements of $R$, we can find $x\in R$ with $\mbox{Ann}(x)=\frak m$. If $x$ happens to be invertible, we're done: the annihilator of an invertible element is $(0)$, so $\frak m=(0)$, contradicting our assumption. Otherwise, $x$ is nilpotent. By $(*)$, it does not annihilate $M$, so we can find $xm\ne 0$ for some $m\in M$. The annihilator of $xm$ is $\frak m$, so if $a$ is any non-zero element of $R$, then there is a homomorphism $(a)\to M,\ a\mapsto xm$. In turn, this implies $xm\in aM$. Now take $a\in\frak m$ to be non-nilpotent (there is one such element, by assumption), and repeat the procedure for $a^{n},\ n\ge 1$. We get $xm\in\bigcap_{n\ge 1}a^{n}M=\{0\}$ (this last equality is a particular case of a result of Krull, I believe), contradicting $xm\ne 0$.


Let n be an positive integer.Find all $ \ f: R \to R$ such that:
$ \ f(x\minus{}f(y))\equal{}f(x\plus{}y^n)\plus{}f(f(y)\plus{}y^n)\plus{}2004$

The idea is almost same as
http://www.mathlinks.ro/viewtopic.php?t=242519

Let $ a\equal{}f(0)$, we will get
$ f(x)\equal{}f(x\plus{}f(y)\plus{}y^n\minus{}a)$

1) $ n>1$
$ f(y)\equal{}a\minus{}y^n$ is not a solution.  Let $ p\ne0$ be a period of $ f$ and $ m$ any integer. We see
$ f(y\plus{}mp)\plus{}(y\plus{}mp)^n\minus{}a$ and $ f(y)\plus{}y^n\minus{}a$ are all periods.
Hence, $ (y\plus{}mp)^n\minus{}y^n$ is also a period.
If $ n$ is even, $ (y\plus{}mp)^n\minus{}y^n$ can take any real value.
If $ n$ is odd, $ (y\plus{}2p)^n\plus{}y^n\minus{}2(y\plus{}p)^n$ is a period which can take any real value.
In either case, $ f$ is constant.
$ f(x)\equal{}\minus{}2004$.

2) $ n\equal{}1$.
This case has many solutions. Two continuous solutions are $ f(x)\equal{}\minus{}2004$ and $ f(x)\equal{}\minus{}2004\minus{}x$.
A discountinuous solution could be
$ f(x)\equal{}\minus{}2004\minus{}x$ when $ x$ is rational, $ f(x)\equal{}r\minus{}x$ when $ x$ is irrational, where $ r$ is arbitrary rational number.


Sorry for reviving an old thread but togehter is wrong in the second part.
Willpost the solution completely for the case $ z \ne 1$ tomorrow.

[quote="Rushil"]Solve for integers $ x,y,z$:
\[ \{\begin{array}{ccc} x + y & = & 1 - z \\
x^3 + y^3 & = & 1 - z^3 . \end{array}
\]
[/quote]
$ z \neq 1$: $ x+y = 1-z, x^3 + y^3 = (x+y)(x^2-xy+y^2) = (1-z)(x^2-xy+y^2) = (1-z)(1^2 + z + z^2) \iff$
$ (x+y)^2 - 3xy = 1 + z + z^2$. Since $ z = x+y+1$ :
$ xy = 1 + x+y$. Now let $ xy = 1 + x + y = n \in \mathbb{Z}$:
Then $ x,y$ are roots in $ p(t) = (t-x)(t-y) = t^2 - (n-1)t + n = 0 \iff$
$ t = \frac{n-1 \pm \sqrt{n^2-6n+1}}{2}$. Hence we will require that $ n^2 - 6n + 1$ is a square. So there exists $ k \in \mathbb{N}_0$ so that:
$ n^2-6n+1 = k^2 \iff$
$ (n-3)^2 - 8 = k^2 \iff$
$ (n-3-k)(n-3+k) = 8$. From here on it is easy.. ;)

The result of Mathias_DK is false
The result of Together is correct.

My solution:
$ \{\begin{array}{ccc} x + y & = & 1 - z----> (1) \\
x^3 + y^3 & = & 1 - z^2----> (2) . \end{array}$      are the given equations.
In equation $ (2)$, we have $ (1-z)(x^2 -xy+y^2 +x + y - 2) = 0$
So either $ 1-z=0$or $ x^2-xy +y^2+x+y-2 = 0$.

If $ 1-z=0$, the solutions for $ (x,y,z)$are $ (t,-t,1)$ for any integer $ t$.

Case 2:$ x^2-xy +y^2+x+y-2 = 0$which implies that   $ [ (x+1) - (y+1)] ^2  +  (x+1)^2 + (y+1)^2 = 6$ and since $ 6$ can be expressed as a sum of three squares only as $ 1+1+4$, we can take cases and solve for $ x,y,z$.

Thus the required solutions $ (x,y,z)$ are $ ( t,-t,1)$, $ t$-  any integer, $ (1,0,0), (-2,0,3), (-3,-2,6), (0,-2,3), (0,1,0) , (-2,-3,6)$

Hi Agr_94_Math,
is it a joke ?
$ x^3\plus{}y^3\equal{}1\minus{}z^2$, are you sure ?

I don't see any mistake in Together's solution. I will try to explain:

\begin{align*}x^3+y^3&=1-z^3\\\Leftrightarrow
(x+y)(x^2-xy+y^2)&=(1-z)(1+z+z^2)\\\Leftrightarrow
(x+y)((x+y)^2-3xy)&=(1-z)(1+z+z^2).\end{align*}Substitute $ x+y=1-z$ to this equation: $ (1-z)((1-z)^2-3xy)=(1-z)(1+z+z^2)\quad(3)$.

(i) $ z=1$. From equation (1) we have $ x+y=1-1=0$. So $ x=-y$. We get a solution $ (x,-x,0)$ for any real number $ x$.

(ii) $ z\ne1$. From equation (3) we have $ (1-z)^2-3xy=1+z+z^2\Leftrightarrow 1-2z+z^2-3xy=1+z+z^2\Leftrightarrow z=-xy$. Substitute this to equation (1), $ x+y=1+xy\Leftrightarrow xy-x-y+1=0\Leftrightarrow(x-1)(y-1)=0$. So $ x=1$ or $ y=1$. We get other solutions $ (1,y,-y),(x,1,-x)$ for any real numbers $ x,y$.

very nice
from the first equation we get $ x + y + z = 1$ or $ (x + y + z)^3 = 1$

from the second we get $ x^3 + y^3 + z^3 = 1$

now applying $ (x + y + z)^3 - x^3 - y^3 - z^3 = 3(x + y)(y + z)(z + x)$

we'll get the result easily  :wink:

And the general problem

$ \{\begin{array}{ccc} x + y & = & a - z \\
x^3 + y^3 & = & a^3 - z^3 . \end{array}$

Will be done follow

The question as posted is incorrect.

The [b]official question paper[/b] of INMO 2000 says the actual question is :

Solve for $x$, $y$ and $z$: $x+y=1-z$ and $x^3+y^3=1-z^2$

I request the moderator to correct the error.I am attaching the official solutions.Please refer to that to find out what the real question was.

sayantan,you have missed a solution. :D  :lol:
check it :wink:

Sorry for reviving this very old thread, but sayantan's solution has its first case incorrect.
$z=1$ implies that $x+y=1-z=0$
Hence the solution family which holds for this is $x$ = $-y$, i.e. $(m, -m, 1)$ is a solution for all integers $m$.

For case z=*1 find the value of xy the combine it with the first equation ,solve quadratic eqation for x or y and get your result

[quote=Night_Witch123][hide=Night_Witch124's solution]$$(x+y)(x^2-xy+y^2)=1-z^2$$
[b]Case 1:[/b] $1-z=0$ $\implies$ $\boxed{(x,y,z) \equiv (k,-k,1)}$ for all $k \in \mathbb{Z}$
[b]Case 2:[/b] $$\begin{cases} x^2-xy+y^2=1+z \\\ x+y=1-z \end{cases} \implies x^2+2xy+y^2=1+z^2-2z \implies \boxed{y=\frac{z(z-3)}{3x}} \implies 3x^2+(3z-3)x+z^2-3z=0$$
The discriminant of this quadratic taken with respect to $x$ should be positive which is only true for $z=[0,6]$ and also $x$ is an integer, hence only $z=0,3,6$ work
$$\implies (x,y,z) \equiv \boxed{(k,-l,1),(0,1,0),(1,0,0),(0,-2,3),(-2,0,3),(-2,-3,6),(-3,-2,6)}$$[/hide][/quote]

A small typo here, in the last line, it must be $(k,-k,1)$ and not $(k,-l,1)$

Anyways, here's [hide=my solution][quote=Rushil]Solve for integers $x,y,z$: \[ \{ \begin{array}{ccc} x + y &=& 1 - z \\ x^3 + y^3 &=& 1 - z^2 . \end{array}  \][/quote]

Substituting $z=1-x-y$ in the second equation,
$x^3+y^3=1-(1-x-y)^2$
So, either $x=-y$, which gives $(k,-k,1)$ as a solution,
Or, $x^2-xy+y^2+x+y-2=0$
Multiplying by 2, and rearranging,
$x^2-2xy+y^2+x^2+2x+1+y^2+2y+1=6$
$(x-y)^2+(x+1)^2+(y+1)^2=6$
Now it's easy as $x,y$ are integers and RHS is sum of squares. So, just some value checking

Observe that since $x^3 + y^3 = (x+y)(x^2+y^2-xy)$, and $x^2 + y^2 - xy$ is $\ge 0$, $1-z, 1-z^2$ must have the same sign and so $z \ge -1$

Now, consider the cases when $z \le 1$

If $z = -1$, it means $x+y = 2, x^3 + y^3 = 0$. But this means $x^2 + y^2 - xy = 0$, which is not possible except when $x = y = 0$, which is not a solution

If $z = 0$, it means $x+y=1, x^3 + y^3 = 1$, which means $x^2 + y^2 - xy = 1 \implies (x-y)^2 + xy = 1$, which has only the solutions $(0,1,0)$ and $(1,0,0)$

If $z = 1$, it means $x+y = 0$, $x^3 + y^3 = 0$, which has the solutions $(k,-k,1)$ for all integers $k$

Now consider the case when one of the variables is 0, WLOG let $x = 0$, this means $y = 1-z, y^3 = 1-z^2$, if $y = 0$, then the solution is $(0,0,1)$ which has already been included. So, if $y \neq 0$, $y^2 = 1+z$. Solving, we see that this means $z(z-3) = 0$, since $z = 0$ has already been considered, we see that for $z = 3$, $(0,-2,3),(-2,0,3)$ work

Now henceforth, assume $z > 1$ and $xy \neq 0$. Observe that $x^2 + y^2 - xy = 1+z$ and so $(x+y)^2 - 3xy = 1+z \implies (1-z)^2 - 3xy = z+1 \implies 3xy = z(z-3)$ and so we see that $3 | z$. Also, since $xy \neq 0$, we see that $z = 3$ is not a solution. So, $z > 3$ and so $xy > 0$ which means both $x,y$ are both negative. So now, replace $x,y$ with $-x, -y$

This means $x+y = z-1, x^3 + y^3 = z^2 - 1$ and $3xy = z(z-3)$

Observe that $z^2 - 1 = x^3 + y^3 \ge x^2y + y^2x = xy(x+y) = \frac{z(z-3)(z-1)}{3}$ which means $z^2 - 6z - 3 \le 0 \implies (z+1)(z-7) + 4 \le 0$, which means that for $z \ge 7$, this inequality does not hold. So, since $3 | z$, the only possibility is that $z = 6$

This means $x + y = -5, x^3 + y^3 = -35 \implies x^2 + y^2 - xy = 7 \implies (x-y)^2 + xy = 7$. So, $x-y \le 2$.

$x = y$ has no integer solutions

$x = y+1$ means $y(y+1) = 6 \implies y = -3, 2$ but $(2,3)$ doesn't work, so the only possiblity is $(x,y) = (-2,-3),(-3,-2)$

$x = y+2$ means $y(y+2) = 3$ which means $y = -3,1$, neither of which has solutions.

So, finally, the solutions are: $(k,-k,1), (-2,-3,6), (-3,-2,6), (0,0,1), (0,1,0), (0,-2,3), (-2,0,3)$

here is mine solution for it :-
also we finish off our problem with a trivial case of $x+y$=0 , and $x^3+y^3=0$ , implying $z=1$ , gives $(x,y) \in {m,-m}$ , where $m$ is an integer


i think that the only way to ensure that a string of terms is a perfect square is showing that the string contains each term d_n an even number of times.

[quote="mdk"]Let D = {d_1, d_2,... d_10} be a set of 10 distinct positive integers. Show that any sequence of 2006 integers from D contains a block of one or more consecutive terms whose product is the square of a positive integer.[/quote]
By the way, 2006 is way to much all you need is 1024. See prove below.

Let $ (a_{n})$ be the sequence obtained by these integers.

Consider the integers
$ n_{1}=a_{1}$
$ n_{2}=a_{1}a_{2}$
$ n_{3}=a_{1}a_{2}a_{3}$
....
$ n_{1024}=a_{1}...a_{1024}$

Now, $ n_{i}= d_{1}^{k_{1}}d_{2}^{k_{2}}...d_{10}^{k_{10}}$ can be expressed uniquely for non-negative integers $ k_{i}$.

Look at the parity of each of the exponents. Each one can be even or odd. There are $ 2^{10}=1024$ such possibilities. If one of $ n_{i}$ has all $ k_{i}$ even then $ n_{i}$ is a perfect square and the proof is complete. Otherwise there are $ 1023$ different parity exponents and by pigeonhole two $ n_{i}$ and $ n_{j}$ have the same one. WLOG with $ i<j$ and then $ n_{j}/n_{i}$ is a perfect square because now all exponents are even. And so $ a_{1}a_{2}...a_{j}/a_{1}a_{2}...a_{i}= a_{i+1}...a_{j}$ is a block of integers that is a perfect square.

I wanna thank Phelpodo for teaching me this trick. It like the 3rd time I used it. :)

[quote="JBL"][quote="sylow_theory"]By the way, 2006 is way to much all you need is 1024.[/quote]

Bonus question: is 1024 minimal?  (That is, for 1023, does there exist a counterexample?)[/quote]

I think maybe mdk was asking that maybe 2006 will mean there is a block whose product is a perfect cube.  :maybe:  But I dont know how to show something like that. Pigeonhole seems to be weak here.

No, mdk was asking exactly what mdk meant to ask.  (2006 because the year this problem was written happened to be an integer larger than 1024.)

For my question, pigeonhole isn't going to be effective.  You might consider smaller examples to see if you can give a general construction of a counterexample.  (I suspect, although I do not know for sure, that one exists.)

Here is the counterexample for 1023.

Suppose that $ d_{1}= 2, d_{2}= 3, d_{3}= 5$, etc. until $ d_{10}= 29$. This is for simplicity; it is sufficient that no two numbers are divisible by the same prime an odd number of times, and that none of the numbers are squares.

Let $ f(n) = k$ where $ n = 2^{k}\cdot m$ for an odd integer $ m$. Now if our 1023 term sequence is $ a_{1}, a_{2}, a_{3}\ldots a_{1023}$, let $ a_{n}= d_{f(n)+1}$.

This makes the first few terms of $ \{a_{i}\}$ the following:
$ 2, 3, 2, 5, 2, 3, 2, 7, 2, 3, 2, 5, \ldots$
in such a way that it resembles the inchmarks on a ruler. If you let the length of the sequence be $ 2^{n}-1$ (where $ n = 10$ here), then the fact that no product of consecutive terms is a perfect square is a simple induction on $ n$.

EDIT: As a further query, the condition I gave for the 10 $ d_{i}$ is not necessary. Just consider each of the numbers I gave multiplied by $ 31$. This fails the condition I gave but still gives the required counterexample. What are the necessary and sufficient conditions?

Nice work.  A sufficient condition is that, if $ d_{1}, \ldots, d_{n}$ are integers then $ a_{1}^{d_{1}}\cdot a_{2}^{d_{2}}\cdot\cdots\cdot a_{n}^{d_{n}}= 1 \implies d_{1}= d_{2}= \ldots = d_{n}= 0$.  (This is a sort of linear independence condition.)  It's probably necessary, too.


I'm running asymptote through the command-line thing, and it can do things like draw lines perfectly, but the label command doesn't seem to work. The error message I get seems to be telling me to put something into config.asy, but it doesn't really make sense... Can anybody help?

Have a look at Problem 3 in [url=http://www.artofproblemsolving.com/Wiki/index.php/Asymptote:_Help]Asymptote Help[/url]


calculus
integration
binomial coefficients
algebra proposed
algebra

Prove that $ \sum_{k \equal{} 1}^{n}\frac {\left( \minus{} 1\right)^{k \minus{} 1}}{k}\cdot \binom{n}{k}\sum_{j \equal{} 1}^{k}\frac {H_{j}}{j} \equal{} \sum_{k \equal{} 1}^{n}\frac {1}{k^{3}}$ for all $ n\in\mathbb{N}$, where $ H_{j} \equal{} \frac {1}{1} \plus{} \frac {1}{2} \plus{} ... \plus{} \frac {1}{j}$ for every $ j\in\mathbb{N}$.

[quote="N.T.TUAN"]Prove that $\sum_{k = 1}^{n}\frac {\left( - 1\right)^{k - 1}}{k}\cdot \binom{n}{k}\sum_{j = 1}^{k}\frac {H_{j}}{j} = \sum_{k = 1}^{n}\frac {1}{k^{3}}$ for all $n\in\mathbb{N}$, where $H_{j} = \frac {1}{1} + \frac {1}{2} + ... + \frac {1}{j}$ for every $j\in\mathbb{N}$.[/quote]

Not the hardest combinatorial identity I have seen, but nice exercise. There are 4 solutions published in AMM (1999 (vol. 106) no. 6 pp. 588-590) - one using integrals, one by binomial inversion, one using finite difference and one through a [url=http://www.mathlinks.ro/viewtopic.php?t=255493]generalization[/url] which was proven using integrals).

Here is mine:

First, some trivia about binomial coefficients:

[color=green][b](1)[/b][/color] $\binom{a}{b} = \binom{a - 1}{b - 1} + \binom{a - 1}{b}$ for all integers $a$ and $b$;

[color=green][b](2)[/b][/color] $\frac {1}{k + 1}\binom{i - 1}{k} = \frac {1}{i}\binom{i}{k + 1}$ for all integers $i\neq0$ and $k\neq - 1$;

[color=green][b](3)[/b][/color] $\binom{n}{k} = \sum_{i = 1}^{n}\binom{i - 1}{k - 1}$ for all $n\in\mathbb{N}$ and $k\in\left\{ 1,2,...,n\right\}$.

[hide=Proofs of these trivia]
In fact, [color=green][b](1)[/b][/color] is the recurrence relation of the binomial coefficients. The equality [color=green][b](2)[/b][/color] follows from

$\frac {1}{k + 1}\binom{i - 1}{k} = \frac {1}{k + 1} \cdot \frac {\left( i - 1\right)\left( i - 2\right) \cdots \left(i - k\right)}{k!} = \frac {\left( i - 1\right)\left( i - 2\right) \cdots \left(i - k\right)}{\left(k+1\right) \cdot k!}$
$= \frac {\left( i - 1\right)\left( i - 2\right) \cdots \left(i - k\right)}{\left(k+1\right)!} = \frac{1}{i} \cdot \frac {i\left( i - 1\right)\left( i - 2\right) \cdots \left(i - k\right)}{\left(k+1\right)!} = \frac {1}{i}\binom{i}{k + 1}$

(at least in the case when $k \geq 0$; but the remaining cases are easily checked by hand). Finally, the equality [color=green][b](3)[/b][/color] holds because every $i\in\left\{1,2,...,n\right\}$ satisfies $\binom{i}{k} = \binom{i - 1}{k - 1} + \binom{i - 1}{k}$ (by [color=green][b](1)[/b][/color]) and thus $\binom{i - 1}{k - 1} = \binom{i}{k} - \binom{i - 1}{k}$, so that

$\sum_{i = 1}^{n}\binom{i - 1}{k - 1} = \sum_{i = 1}^{n}\left( \binom{i}{k} - \binom{i - 1}{k}\right)$
$= \sum_{i = 1}^{n}\binom{i}{k} - \sum_{i = 1}^{n}\binom{i - 1}{k}$
$= \sum_{i = 1}^{n}\binom{i}{k} - \sum_{i = 0}^{n - 1}\binom{i}{k}$ (here we substituted $i$ for $i - 1$ in the second sum)
$= \binom{n}{k} - \binom{0}{k} = \binom{n}{k}$ (since $\binom{0}{k} = 0$ because of $k > 0$).
[/hide]

Besides, for every integer $i > 0$, we have

[color=green][b](4)[/b][/color] $\sum_{k = 1}^{i}\left( - 1\right) ^{k} \binom{i}{k}\sum_{j = 1}^{k}\frac {H_{j}}{j} = - \frac {1}{i^{2}}$

since

$\sum_{k = 1}^{i}\left( - 1\right) ^{k}\binom{i}{k}\sum_{j = 1}^{k}\frac {H_{j}}{j} = \sum_{k = 1}^{i}\left( - 1\right) ^{k}\left( \binom{i - 1}{k - 1} + \binom{i - 1}{k}\right) \sum_{j = 1}^{k}\frac {H_{j}}{j}$
(since $\binom{i}{k} = \binom{i - 1}{k - 1} + \binom{i - 1}{k}$ by [color=green][b](1)[/b][/color])
$= \sum_{k = 1}^{i}\left( - 1\right) ^{k}\binom{i - 1}{k - 1}\sum_{j = 1}^{k} \frac {H_{j}}{j} + \sum_{k = 1}^{i}\left( - 1\right) ^{k}\binom{i - 1}{k}\sum_{j = 1}^{k}\frac {H_{j}}{j}$
$= \sum_{k = 0}^{i - 1}\left( - 1\right) ^{k + 1}\binom{i - 1}{k}\sum_{j = 1}^{k + 1}\frac {H_{j}}{j} + \sum_{k = 1}^{i}\left( - 1\right)^{k}\binom{i - 1}{k}\sum_{j = 1}^{k}\frac {H_{j}}{j}$
(here we substituted $k$ for $k - 1$ in the first sum)
$= \sum_{k = 0}^{i}\left( - 1\right) ^{k + 1}\binom{i - 1}{k}\sum_{j = 1}^{k + 1}\frac {H_{j}}{j} + \sum_{k = 1}^{i}\left( - 1\right) ^{k}\binom{i - 1}{k}\sum_{j = 1}^{k}\frac {H_{j}}{j}$
(here, we replaced the $\sum_{k = 0}^{i - 1}$ sign by a $\sum_{k = 0}^{i}$, since the summand for $k = i$ is zero because of $\binom{i - 1}{k} = 0$ for $k = i$)
$= \sum_{k = 0}^{i}\left( - 1\right) ^{k + 1}\binom{i - 1}{k}\sum_{j = 1}^{k + 1} \frac {H_{j}}{j} + \sum_{k = 0}^{i}\left( - 1\right) ^{k}\binom{i - 1}{k} \sum_{j = 1}^{k}\frac {H_{j}}{j}$
(here, we replaced the $\sum_{k = 1}^{i}$ sign by a $\sum_{k = 0}^{i}$, since the summand for $k = 0$ is zero because of $\sum_{j = 1}^{k}\frac {H_{j}}{j} = 0$ for $k = 0$)
$= \sum_{k = 0}^{i}\left( \left( - 1\right) ^{k + 1}\binom{i - 1}{k}\sum_{j = 1}^{k + 1}\frac {H_{j}}{j} + \underbrace{\left( - 1\right) ^{k}}_{ = - \left( - 1\right) ^{k + 1}}\binom{i - 1}{k}\sum_{j = 1}^{k}\frac {H_{j}}{j}\right)$
$= \sum_{k = 0}^{i}\left( - 1\right) ^{k + 1}\binom{i - 1}{k}\left( \sum_{j = 1}^{k + 1}\frac {H_{j}}{j} - \sum_{j = 1}^{k}\frac {H_{j}}{j}\right)$
$= \sum_{k = 0}^{i}\left( - 1\right) ^{k + 1}\binom{i - 1}{k}\frac {H_{k + 1}}{k + 1} = \sum_{k = 0}^{i}\left( - 1\right) ^{k + 1}\frac {1}{k + 1}\binom{i - 1}{k}H_{k + 1}$
$= \sum_{k = 0}^{i}\left( - 1\right) ^{k + 1}\frac {1}{i}\binom{i}{k + 1}H_{k + 1}$
(since $\frac {1}{k + 1}\binom{i - 1}{k} = \frac {1}{i}\binom{i}{k + 1}$ by [color=green][b](2)[/b][/color])
$= \frac {1}{i}\sum_{k = 0}^{i}\left( - 1\right) ^{k + 1}\binom{i}{k + 1} H_{k + 1} = \frac {1}{i}\sum_{k = 0}^{i}\left( - 1\right) ^{k + 1}\left(\binom{i - 1}{k} + \binom{i - 1}{k + 1}\right) H_{k + 1}$
(since [color=green][b](1)[/b][/color] yields $\binom{i}{k + 1} = \binom{i - 1}{\left( k + 1\right) - 1} + \binom{i - 1}{k + 1} = \binom{i - 1}{k} + \binom{i - 1}{k + 1}$)
$= \frac {1}{i}\left( \sum_{k = 0}^{i}\left( - 1\right) ^{k + 1}\binom{i - 1}{k}H_{k + 1} + \sum_{k = 0}^{i}\left( - 1\right) ^{k + 1}\binom{i - 1}{k + 1}H_{k + 1}\right)$
$= \frac {1}{i}\left( \sum_{k = 0}^{i}\left( - 1\right) ^{k + 1}\binom{i - 1}{k}H_{k + 1} + \sum_{k = 1}^{i + 1}\left( - 1\right) ^{k}\binom{i - 1}{k}H_{k}\right)$
(here we substituted $k$ for $k + 1$ in the second sum)
$= \frac {1}{i}\left( \sum_{k = 0}^{i}\left( - 1\right) ^{k + 1}\binom{i - 1}{k}H_{k + 1} + \sum_{k = 0}^{i - 1}\left( - 1\right) ^{k}\binom{i - 1}{k}H_{k}\right)$
(here, we replaced the $\sum_{k = 1}^{i + 1}$ sign by a $\sum_{k = 0}^{i - 1}$, since the summands for $k\geq i$ are zero because of $\binom{i - 1}{k} = 0$ for $k\geq i$, and the summand for $k = 0$ is zero because of $H_{0} = 0$)
$= \frac {1}{i}\left( \sum_{k = 0}^{i - 1}\left( - 1\right) ^{k + 1}\binom{i - 1}{k}H_{k + 1} + \sum_{k = 0}^{i - 1}\left( - 1\right) ^{k}\binom{i - 1}{k}H_{k}\right)$
(here, we replaced the $\sum_{k = 0}^{i}$ sign by a $\sum_{k = 0}^{i - 1}$, since the summand for $k = i$ is zero because of $\binom{i - 1}{k} = 0$ for $k = i$)
$= \frac {1}{i}\sum_{k = 0}^{i - 1}\left( \left( - 1\right) ^{k + 1}\binom{i - 1}{k}H_{k + 1} + \underbrace{\left( - 1\right) ^{k}}_{ = - \left( - 1\right) ^{k + 1}}\binom{i - 1}{k}H_{k}\right)$
$= \frac {1}{i}\sum_{k = 0}^{i - 1}\left( - 1\right) ^{k + 1}\binom{i - 1}{k}\left(H_{k + 1} - H_{k}\right) = \frac {1}{i}\sum_{k = 0}^{i - 1}\left( - 1\right)^{k + 1}\binom{i - 1}{k}\frac {1}{k + 1}$
(since $H_{k + 1} - H_{k} = \left( \frac {1}{1} + \frac {1}{2} + ... + \frac {1}{k + 1}\right) - \left( \frac {1}{1} + \frac {1}{2} + ... + \frac {1}{k}\right) = \frac {1}{k + 1}$)
$= \frac {1}{i}\sum_{k = 0}^{i - 1}\left( - 1\right) ^{k + 1}\frac {1}{i}\binom{i}{k + 1}$
(since $\binom{i - 1}{k}\frac {1}{k + 1} = \frac {1}{i}\binom{i}{k + 1}$ by [color=green][b](2)[/b][/color])
$= \frac {1}{i^{2}}\sum_{k = 0}^{i - 1}\left( - 1\right) ^{k + 1}\binom{i}{k + 1}$
$= \frac {1}{i^{2}}\sum_{k = 1}^{i}\left( - 1\right) ^{k}\binom{i}{k}$ (here we substituted $k$ for $k + 1$)
$= \frac {1}{i^{2}}\left( \underbrace{\sum_{k = 0}^{i}\left( - 1\right)^{k}\binom{i}{k}}_{\substack{ = \left( 1 + \left( - 1\right) \right)^{i}\text{ by the} \\
\text{binomial formula}}} - \underbrace{\left( - 1\right)^{0}}_{ = 1}\underbrace{\binom{i}{0}}_{ = 1}\right)$
$= \frac {1}{i^{2}}\left( \left( 1 + \left( - 1\right) \right) ^{i} - 1\right) = \frac {1}{i^{2}}\left( 0^{i} - 1\right) = \frac {1}{i^{2}}\left( - 1\right)$ (since $0^{i} = 0$, since $i > 0$)
$= - \frac {1}{i^{2}}$.

Now, [color=green][b](3)[/b][/color] yields

$\sum_{k = 1}^{n}\frac {\left( - 1\right) ^{k - 1}}{k}\cdot\binom{n}{k}\sum_{j = 1}^{k}\frac {H_{j}}{j}$
$= \sum_{k = 1}^{n}\frac {\left( - 1\right) ^{k - 1}}{k}\cdot\sum_{i = 1}^{n}\binom{i - 1}{k - 1}\sum_{j = 1}^{k}\frac {H_{j}}{j}$
$= \sum_{i = 1}^{n}\sum_{k = 1}^{n}\frac {\left( - 1\right) ^{k - 1}}{k}\binom{i - 1}{k - 1}\sum_{j = 1}^{k}\frac {H_{j}}{j}$
$= \sum_{i = 1}^{n}\sum_{k = 1}^{n}\left( - 1\right) ^{k - 1}\cdot\frac {1}{k}\binom{i - 1}{k - 1}\sum_{j = 1}^{k}\frac {H_{j}}{j}$
$= \sum_{i = 1}^{n}\sum_{k = 1}^{n}\left( - 1\right) ^{k - 1}\cdot\frac {1}{i}\binom{i}{k}\sum_{j = 1}^{k}\frac {H_{j}}{j}$
(since $\frac {1}{k}\binom{i - 1}{k - 1} = \frac {1}{i}\binom{i}{k}$ follows from [color=green][b](2)[/b][/color] if we substitute $k - 1$ for $k$)
$= \sum_{i = 1}^{n}\frac {1}{i}\sum_{k = 1}^{n}\left( - 1\right) ^{k - 1}\binom{i}{k}\sum_{j = 1}^{k}\frac {H_{j}}{j}$
$= \sum_{i = 1}^{n}\frac {1}{i}\sum_{k = 1}^{i}\underbrace{\left( - 1\right)^{k - 1}}_{ = - \left( - 1\right) ^{k}}\binom{i}{k}\sum_{j = 1}^{k}\frac {H_{j}}{j}$
(here, we replaced the $\sum_{k = 1}^{n}$ sign by a $\sum_{k = 1}^{i},$ since all summands for $k > i$ are zero because $\binom{i}{k} = 0$ for $k > i$)
$= \sum_{i = 1}^{n}\frac { - 1}{i}\sum_{k = 1}^{i}\left( - 1\right) ^{k}\binom{i}{k}\sum_{j = 1}^{k}\frac {H_{j}}{j} = \sum_{i = 1}^{n}\frac { - 1}{i}\left( - \frac {1}{i^{2}}\right)$ (by [color=green][b](4)[/b][/color])
$= \sum_{i = 1}^{n}\frac {1}{i^{3}}$,

qed.

  darij

$ A_n: \equal{}\sum_{k\equal{}0}^n (\minus{}1)^k \frac{1}{k\plus{}1} \binom{n}{k} \sum_{1 \leq i \leq j \leq k\plus{}1} \frac{1}{ij}$
$ \frac{1}{n\plus{}1} \sum_{k\equal{}0}^n (\minus{}1)^k \binom{n\plus{}1}{k\plus{}1} \sum_{1 \leq i \leq j \leq k\plus{}1} \frac{1}{ij}$
$ \equal{}\frac{1}{n\plus{}1} \left( (\frac{1}{1\cdot 1}) \binom{n\plus{}1}{1} \minus{} (\frac{1}{1\cdot 1}\plus{}\frac{1}{1\cdot 2}\plus{}\frac{1}{2\cdot 2}) \binom{n\plus{}1}{2}\plus{}\cdots \right)$
$ \equal{}\frac{1}{n\plus{}1} \left( (\frac{1}{1 \cdot 1})(\binom{n\plus{}1}{1}\minus{}\binom{n\plus{}1}{2}\plus{}\cdots)\plus{}(\frac{1}{1 \cdot 2}\plus{}\frac{1}{2\cdot 2})(\minus{}\binom{n\plus{}1}{2}\plus{}\cdots)\plus{}\cdots \right)$
$ \equal{}\frac{1}{n\plus{}1} \left( \frac{1}{1}H_1 \binom{n}{0} \minus{} \frac{1}{2}H_2 \binom{n}{1} \plus{} \cdots \right)\equal{}\frac{1}{(n\plus{}1)^2} \left( H_1 \binom{n\plus{}1}{1} \minus{} H_2 \binom{n\plus{}1}{2}\plus{}\cdots \right)$
$ \equal{}\frac{1}{(n\plus{}1)^2} \left( \frac{1}{1}(\binom{n\plus{}1}{1}\minus{}\binom{n\plus{}1}{2}\plus{}\cdots)\plus{}\frac{1}{2}(\minus{}\binom{n\plus{}1}{2}\plus{}\cdots)\plus{}\cdots \right)$
$ \equal{}\frac{1}{(n\plus{}1)^2} \left( \frac{1}{1}\binom{n}{0} \minus{} \frac{1}{2}\binom{n}{1} \plus{} \cdots \right)\equal{}\frac{1}{(n\plus{}1)^3} \left( \frac{n\plus{}1}{1}\minus{}\frac{n\plus{}1}{2}\plus{}\cdots \right)\equal{}\frac{1}{(n\plus{}1)^3}$.

Thus $ (LHS)\equal{}\sum_{k\equal{}0}^{n\minus{}1}A_k \equal{} \sum_{k\equal{}0}^{n\minus{}1} \frac{1}{(n\plus{}1)^3}\equal{}(RHS)$.


trigonometry
analytic geometry
ratio
advanced fields
advanced fields unsolved

Hello, let $ P(u,v) \equal{} (e^{v}\cos e^{u}, e^{v}\sin e^{u}, e^{u})\qquad u,v\in\mathbf R$

How can I find principal curvatures and asymptotic lines without too many computation?

Since g=0 (or N if you like :) ) I just found that the v-coordinate lines are asymptotic but no more :(

Mathematica computations showed that also e=L=0 so also the u=const coordinate lines are asymptotic... but still no idea for the principal curvatures. All I know is they have opposit sign (gaussian curvature is < 0)

edit:

since e=g=F=0 I can easily write the curvature lines differential equation which is

$ G\dot v^{2}\equal{} E\dot u^{2}$

So the principal curvatures become $ \frac{2f\dot u\dot v}{2E\dot u^{2}}\equal{}\frac{f\dot v}{E\dot u}$
The curvature lines are regular so I can suppose $ \dot u,\dot v\neq 0$

I also know that $ \frac{\dot v}{\dot u}\equal{}\pm\sqrt{\frac{E}{G}}$ so it is

$ \kappa_{1,2}\equal{}\pm\sqrt{\frac{G}{E}}\frac{f}{E}\equal{}\pm\frac{f}{\sqrt{EG}}$

it is the same also if we use $ \dot u/\dot v$, the curvature line is regular so at least one of these ratio must be possible.

what do you think?


Nice problem.

[hide]I wrote a diagram in my mind with four horizontal bars, each for the four criteria with the telephone at the bottom bar, then the car, then house, then marriage. First fill up 70 from the left of the bottom most bar. Draw a dotted line upwards into the "car" bar. that would be at 70 (maybe labels will help keep it organized.) then from the dotted bar on to the right fill up 75. When you reach the right end of the bar just keep going from the left end. (kinda like base 100; probably there's a way smarter way to do this with mods but I still don't know mods ) Write dotted line upward until you get to the "house" bar then repeat the steps until you reach the "marriage" bar. The bar should be filled from 15 to the right end (100). What that tells us is that there is a way to arrange them so that all of them have one criteria unfulfilled. (Also the number of people that don't have one of the four things in order from largest to smallest is 30, 25, 20, and 15 which adds up to a 100) Thus the answer is 0[/hide]

Please let me get this right please!

ah, try again

edit: mods are covered in the early chapters of aops v1

Um well I'm not sure about all the bit you wrote at the start Tare, that doesn't seem to be any sort of proof, however the bit you wrote in brackets is very almost correct. Try adding up those numbers again :)

Agh! I knew it! I was trying to solve for four numbers multiple of 5 which is in a pattern which adds up to 100 and I couldn't get an answer! I kept going round and round and round...try it, it's quite intriguing :)

Anyways 15+20+25+30 is [b]90[/b] so the answer is 10.

[quote="Syntax Error"]in a small town or 100 men, 85 are married, 70 have a telephone, 75 own a car, and 80 own their own home.  on this basis, what is the smallest possible number of men who are married, have their own telephone, own their own car, and own their own home?[/quote]
100-85=15 single men
100-70=30 men without phones
100-75=25 men without cars
100-80=20 men without homes (they can be found under the bridge... jk)
Since we want to minimize the number of men who do not fit into any of those groups, let no man occur in two of the groups. Thus 100-15-30-25-20=10 men are not in any of the groups, and must own a car, phone, home, and wife, or at least have a wife.


geometry
geometric transformation
reflection
symmetry
circumcircle
geometry proposed

$ABC$ is an acute-angled triangle and $A_{1}, B_{1}, C_{1}$

are points on $AA^{'}, BB^{'}, CC^{'}$ ( the altitudes of

tringle $ABC$ ) and  $A_{1}, B_{1}, C_{1}$ are distinct from

$H$ ( the orthocenter of $ABC$ ) . Also:

$S_{ABC_{1}}+S_{BCA_{1}}+S_{CAB_{1}}= S_{ABC}$

Prove that $A_{1}, B_{1}, C_{1}$, $H$ are on a circle.

Let $A_{1}$, $B_{1}$ and $C_{1}$ be the reflections of $H$ with respect to the sides, then you get a counter-example.

sorry but What do you mean by a counter example :huh:

I think it is true and it is nice problem but need to assume $A_{1},B_{1},C_{1},\in$ segment $AA',BB',CC'$!

Oh yes, that's right gemath, it's really simple
For the solution, Assume that the circle passing through points $A_{1}, B_{1}, H$ intersects  $CC^{'}$ at $C^{'}_{1}$ , now can anyone prove that $C^{'}_{1}= C_{1}$ ?

assume that (by symmetry) $A_{1},B_{1},C_{1}$ are on segments $AH,HB',CH$ respectively. we have : $HB_{1}.b=HC_{1}.c+HA_{1}.a$.so : $HB_{1}.sinB=HC_{1}.sinC+HA_{1}.sinA$.now assume that the circumcircle of $HB_{1}C_{1}$ intersects $AA'$ at $A'_{1}$.by Ptolemi : $HB_{1}.A'_{1}C_{1}=HC_{1}.A'_{1}B_{1}+HA'_{1}.B_{1}C_{1}$and so :$HB_{1}.sinB=HC_{1}.sinC+HA'_{1}.sinA$ and so : $A'_{1}=A_{1}$ . so we are done.


inequalities
real analysis
real analysis solved

Let a(n) be a decreasing set which converges to 0.
We define $b(n)= \sum_{i=1}^n{(a(i)-a(i+1))/a(i)} $.
Find whether b(n) has a limit;

Maybe the question is whether the sequence is convergent or not? It obviously has a limit (finite or not), because it's increasing. And there's no reason for it to be convergent, since you can take $a_{n+1}$ as small compared to $a_n$ as you want, in order to make $1-\frac{a_{n+1}}{a_n}$ as close to $1$ as you want.

It think that it's possible to show that b(n) is always divergent.If I'm wrong you can just give me an counterexample.

Oh, but I didn't say it could be convergent. I said it could be divergent, and then forgot to check whether it could be convergent.

Finishing the problem...

We have $b_{m-1}-b_{n-1}=\sum_{i=n}^{m-1} \frac{a_i-a_{i+1}}{a_i} \le \sum_{i=n}^{m-1} \frac{a_i-a_{i+1}}{a_n} = \frac{a_n-a_m}{a_n}$ for $m>n$.
Now choose $n_1, n_2, \dots, n_k, \dots$ so that $\frac{a(n_{k+1})}{a(n_k)} < \frac12$. By the above inequality, $b(n_{k+1}-1)-b(n_k-1) > \frac12$ and the series diverges.


Let $ M$ be a point inside $ \triangle ABC$ . Prove that: $ \frac{MA}{BC}\plus{}\frac{MB}{CA}\plus{}\frac{MC}{AB}\ \ge\ \sqrt{3}$ .


I have read in many places that a+bi is purely real if b=0 and purely imaginary if a=0. It seems very logical.

But then, what about zero? For that number, both a and b are 0, and thus, is it the case that zero is both purely real and purely imaginary? Or is it neither?

It is both. See [url]http://mathforum.org/library/drmath/view/65170.html[/url]

EDIT:0 isn't positive or negative because the trichotomy axiom says the reals consist of 3 disjoint sets: the positive reals, 0, and the negative reals. But the axioms do say it is part of the reals, as the reals contain an additive identity, so I think it should at least be real. As to whether it's a pure imaginary or not, I think it depends on how we define pure imaginary, but if we define it as the product of a real number and i, then 0 would count.

Neither. 0 wouldn't be purely imaginary or purely real because it doesn't fit into both descriptions. Its just like the question, "Is 0 positive or negative?". Its neither because it doesnt fit into both desctriptions.

EDIT: Beaten.

I interpret the definition of "pure imaginary" as a number that can be written as $ ai$ where $ a$ is real.

The definition of real is, well,... real? And 0 is real.

IDK... I might say 0 is both

Is there such thing?

The theorems I can think of that hold for purely real and / or purely imaginary numbers also hold for $ 0$, so I don't see the harm in letting $ 0$ be both.


Does anyone know why
[code]\text{Wow^{Ok}}[/code]
 gives this weird output $\text{Wow^{Ok}}$ ?

You can do...

[code]\text{Wow}^{\text{Ok}}[/code]
$\text{Wow}^{\text{Ok}}$

...or...

[code]\text{Wow}^{Ok}[/code]
$\text{Wow}^{Ok}$

I don't know why the way you did it makes it repeat 4 times. :huh:

It's bad code. I tested it outside the forum, and got an error which prevented typesetting completely.
The forum is generally pretty forgiving of bad code- it tries to interpret it rather than rejecting it completely. In this case, I would have expected an "Unparseable" error.

In a document text mode differs from math mode. You don't need any dollar signs in text mode and, to get the effect you want, just type Wow\textsuperscript{OK}. ^ is meant for math mode.

On the forum, text is handled by the forum itself and LaTeX is only required for math mode. It is good practice not to use LaTeX for text on the forum.


$ ABCD$ is rectangle and $ (O)$ is a internal circle tangent to the opposite sides $ AB,CD$  . The tangent lines  form $ D$ and $ C$ to $ (O)$ different from $ CD$ touch $ (O)$ in $ M,N$ and meet at $ P$. Show that the triangle $ PAB$ and the quadrilateral $ PMON$ have same areas.

Let the circle touch $ DC$ at $ S$ and $ AB$ at $ T$. Let $ DS\equal{}DM\equal{}a, CS\equal{}CN\equal{}b$ and $ PM\equal{}PN\equal{}c$ (common tangents).

Let the inradius $ OS\equal{}OM\equal{}ON \equal{} r$.

The quadrilateral $ OMPN$ is made up of two triangles: $ OMP$ and $ ONP$, each with area $ \frac{1}{2}\cdot rc$, and so has an area of $ rc$.

Let the side $ DA$ meet the line through $ P$ parallel to $ DC$ at $ E$ and the side $ CB$ meet the same line at $ F$.

Then $ (DAP) \plus{} (CBP) \equal{} \frac{1}{2}(2r)EP \plus{} \frac{1}{2}(2r)PF \equal{} (a\plus{}b)r$.

The area of DAPC is

$ (DAP)\plus{}(CBP)\plus{}(PCD)$

$ \equal{}  (a\plus{}b)r\plus{}(PCD)$

$ \equal{} (a\plus{}b)r \plus{} rs$

$ \equal{}(a\plus{}b)r \plus{}(a\plus{}b\plus{}c)r$

$ \equal{} 2r(a\plus{}b) \plus{}rc$

$ \equal{}(ABCD) \plus{} (APB)$,

where $ s$ is the semiperimeter, $ a\plus{}b\plus{}c$.

Therefore $ (APB) \equal{} (OMPN) \equal{} rc$

thanks Andrewtom! your solution is similar to mine, very nice!  :)


Let a, b, c be real numbers satisifying a+b+c=2 and abc=4.
(1) Find the minimum of max{a, b, c}.
(2) Find the minimum of |a|+|b|+|c|.

Let $a\leq b\leq c.$ Then $a+b=2-c$ and $ab=\frac{4}{c}.$
Hence, $a$ and $b$ is roots of equation $z^2+(c-2)z+\frac{4}{c}=0.$
Hence, $(c-2)^2-\frac{16}{c}\geq0\Leftrightarrow\frac{(c^2+4)(c-4)}{c}\geq0.$
Hence, $c\geq4$ or $c<0.$
If $c<0$ then $ab<0$ and or $a>0$ or $b>0.$ Contradiction($c=max\{a,b,c\}$).
Thence, $c\geq4.$
Hence, $minmax\{a,b,c\}=4.$
Since $c\geq4$ then $a+b<0$ and $ab>0.$
Hence $a<0,b<0.$
Thence, $|a|+|b|+|c|=-a-b+c=c-2+c=2c-2\geq2\cdot4-2=6.$
Hence, $min(|a|+|b|+|c|)=6.$    $(a=-1,b=-1,c=4)$  :)


calculus
derivative
trigonometry
parameterization
calculus computations

[quote="breez"]If $f(x) = \sin x$ and $\sin(90^{\circ}-x) = \cos x$

If $f' = \cos x$, then shouldn't $f'(90^{\circ}-x) = f'\sin(90^{\circ}-x) = \cos(90^{\circ}-x) = \sin x$?

However, as we all know, derivative of $\cos x =-\sin x$.

Why is the above unreasonable?[/quote]
You forgot to use the Chain Rule (from $90^\circ-x$).  :wink:
It would actually be \[(\sin(90^{\circ}-x))'=\cos(90^{\circ}-x)(-1)=-\sin x.\]

[quote="breez"]I think I thought getting derivatives was like identities. Is it true you cannot simply plug in functional parameters into the derivative like I did above?

So unlike identities, the derivative identities don't generalize to variable parameters due to the chain rule.[/quote]

Yeah, whenever you plug something in, you have to account for the fact that whatever you plug in does not change at the same rate as your original variable. So that's why you need the chain rule.


linear algebra
matrix
algebra
system of equations

This is a problem I made up for my school math team to practice on, but I wanted to post it here to make sure I didn't mess it up. It's also a variant on a AoPS Vol. 2 problem.

Find all values of $ a$ such that the following system of equations cannot be solved for a unique answer $ (x,y,z)$:

$ ax \plus{} 3y \plus{} 4z \equal{} 13$
$ 2x \plus{} y \plus{} z \equal{} 3$
$ 4x \plus{} 3y \plus{} az \equal{} 7$

I would say a=4 because then the first and third equations are the same. I can't think of any other values at the moment.  :wink:

[quote="7h3.D3m0n.117"]How are the first and third equations almost the same? One equals 13 and the other equals 7. This does, however, let us know that $ x > z$ (although I have no idea how that helps).[/quote]

Notice there is an ax at the front of equation 1.
And an az in the rightish-middlish of equation 3.

[hide="hint"]Determinants come in here.[/hide]

[hide="Answer"]$ a \equal{} 4 , 8$[/hide]
[hide="Solution(solving method)"]Indeed, the way to solve this one is to first put all of the coefficients into a matrix:
$ \left(\begin{array}{ccc}a & 3 & 4 \\
2 & 1 & 2 \\
4 & 3 & a\end{array}\right) \left(\begin{array}{c}x \\
y \\
z\end{array}\right) \equal{} \left(\begin{array}{c}13 \\
3 \\
7\end{array}\right)$
If we label the coefficient matrix $ A$, the variable matrix $ X$, and the constant matrix $ B$, then $ X \equal{} A^{ \minus{} 1}B$ If matrix $ A$ is not invertible, then there is no unique solution to the system (this also means that the constant values don't matter in determining whether or not there are solutions to the system). If the determinant of $ A$ is 0, then $ A$ is not invertible.
Solving the determinant for 0:
$ a(a \minus{} 6) \minus{} 3(2a \minus{} 8) \plus{} 4(6 \minus{} 4) \equal{} 0$
$ a^2 \minus{} 6a \minus{} 6a \plus{} 24 \plus{} 8 \equal{} 0$
$ a^2 \minus{} 12a \plus{} 32 \equal{} 0$
$ (a \minus{} 4)(a \minus{} 8) \equal{} 0$

[size=150]$ a \equal{} 4 , 8$[/size][/hide]

[quote="gauss202"][quote="Temperal"]The real way to do this is Gaussian elimination.[/quote]

Gaussian elimination would work, but it is overkill for this question.

[quote="Lulze"]

[hide="Solution(solving method)"]Indeed, the way to solve this one is to first put all of the coefficients into a matrix:
$ \left(\begin{array}{ccc}a & 3 & 4 \\
2 & 1 & 2 \\
4 & 3 & a\end{array}\right) \left(\begin{array}{c}x \\
y \\
z\end{array}\right) \equal{} \left(\begin{array}{c}13 \\
3 \\
7\end{array}\right)$
If we label the coefficient matrix $ A$, the variable matrix $ X$, and the constant matrix $ B$, then $ X \equal{} A^{ \minus{} 1}B$ If matrix $ A$ is not invertible, then there is no unique solution to the system (this also means that the constant values don't matter in determining whether or not there are solutions to the system). If the determinant of $ A$ is 0, then $ A$ is not invertible.
Solving the determinant for 0:
$ a(a \minus{} 6) \minus{} 3(2a \minus{} 8) \plus{} 4(6 \minus{} 4) \equal{} 0$
$ a^2 \minus{} 6a \minus{} 24 \plus{} 8 \equal{} 0$
$ a^2 \minus{} 12a \plus{} 32 \equal{} 0$
$ (a \minus{} 4)(a \minus{} 8) \equal{} 0$

[size=150]$ a \equal{} 4 , 8$[/size][/hide][/quote]

Your solution method is correct, but the numbers you have don't agree with the original numbers in the problem. Also, one of the steps in your algebra doesn't agree with the surrounding lines of algebra.[/quote]
You're right, I'm sorry! I mistyped the problem, and copied that solution over from my work in my notebook. Unfortunately, I can't edit the main post anymore. The second equation should be $ 2x \plus{} y \plus{} 2z \equal{} 3$, NOT what is there ($ 2x \plus{} y \plus{} z \equal{} 3$). Also, I fixed the mistakes in the algebra of my solution, too. (Forgive me, I've been bogged down with school work lately and as a result am a bit tired.  :wink: )

You should be careful when you set the determinant equal to zero. It is possible that one of those values of $ a$ would lead to an inconsistent system.

The question is not very clear, I think it means only one solution. I'm not sure if you would call 'no solution' a unique answer.

The question says that there isn't one unique answer.  This can mean either that the solution is not unique or that there isn't one (as written).

Okay, I just wasn't clear on the meaning of answer in this context.

are you just using cramer's rule and making the D = 0?


advanced fields
advanced fields unsolved

Given a sequence of open sets $(A_{n})$ in a compact space, is it possible that $\bigcap_{n=1}^{k} A_{n} \neq \emptyset$ for all k?

Definitely. Just take the intervals $A_n = (0,1/2^n)$.