AMC
USA(J)MO
USAMO
pigeonhole principle
floor function

[quote="filosofimenos"]Λοιπον παιδια, διαβαζα σημερα ενα προβλημα απο παλια USAMO και σκεφτηκα βασιζομενος σε αυτο μια ασκηση την οποια ομως δεν μπορω να λυσω. Ιδου η ασκηση:

Εστω 60 ατομα. Ο καθενας μισει ακριβως 3 απο τους υπολοιπους(το οτι ο Α μισει τον Β δεν σημαινει πως απαραιτητα και ο Β μισει τον Α). Να βρεθει ποσοι το λιγοτερο "αλληλομισιουνται".

Αν βρειτε λυση γραψτε τη μου παρακαλω.[/quote]

Δεν είμαι σίγουρος ότι καταλαβαίνω τι θέλεις. Φαντάσου το εξής σενάριο:
i. Οι 1, 2...54 μισούν τους 58, 59, 60.
ii. Οι 55, 56, 57 μισούν τους 1, 2, 3.
iii. Οι 58, 59, 60 μισούν τους 55, 56, 57.

Έτσι δεν υπάρχει ζεύγος ανθρώπων που να αλληλομισούνται.

Cheerio,

Durandal 1707

1) Λοιπον, δικιο εχεις, ωρες-ωρες δεν βλεπω μπροστα μου :wallbash_red:

2) Εχει ομως ενδιαφερον ενα αλλο προβλημα σχετικο με αυτο:

[color=red][b]Εστω ν ατομα. Ο καθενας μισει ακριβως κ(με κ<ν, κανενας δεν μπορει να μισει των ευατο του).
Να βρεθουν ολα τα ζευγοι (κ,ν) ωστε να υπαρχουν ακριβως ζ αμοιβαια μιση(ζ≥0).[/b][/color]

Νομιζω οτι αυτο ειναι οντως δυσκολο προβλημα.

[quote="filosofimenos"]2) Εχει ομως ενδιαφερον ενα αλλο προβλημα σχετικο με αυτο:

[color=red][b]Εστω ν ατομα. Ο καθενας μισει ακριβως κ(με κ<ν, κανενας δεν μπορει να μισει των ευατο του).
Να βρεθουν ολα τα ζευγοι (κ,ν) ωστε να υπαρχουν ακριβως ζ αμοιβαια μιση(ζ≥0).[/b][/color][/quote]

Το πόσα αμοιβαία μίση θα υπάρχουν εξαρτάται από το ποιοι θα μισούν ποιούς. Π.χ. στο προηγούμενο σου παράδειγμα, αν ο 1 μισεί τους 2,3,4, ο 2 μισεί τους 1,3,4, ο 3 τους 1,2,4 και ο 4 τους 1,2,3, θα έχεις 4 ανθρώπους να αλληλομισούνται όλοι ανά δύο. Μπορείς να κάνεις την κατασκευή αυτή για όλες τις τετράδες (5-8, 9-12, κ.ο.κ.) και να καταλήξεις σε $ 15\cdot\binom{4}{2}$ αμοιβαία μίση. Με άλλες επιλογές καταλήγεις σε διαφορετικό αριθμό.

Οπότε, τι ακριβώς ζητάς?

Καλύτερο πρόβλημα είναι ίσως το εξής: δεδομένων των $ n$ (συνολικός αριθμός ατόμων) και $ k$ (μίση), να βρεθεί ο ελάχιστος/μέγιστος αριθμός από μίση που είναι αμοιβαία.

Cheerio,

Durandal 1707

Για το δικο μου προβλημα: Αυτο που λεω ειναι
Για πια κ,ν μπορουμε να τοποθετησουμε τα μισοι καταλληλα ωστε να υπαρξουν ζ αλληλομισοι.

Για το δικο σου προβλημα: Εχεις λυση?
Σκεφτομουν οτι ειναι κατα καποιο τροπο αντιστροφο απο το δικο μου, αφου στο δικο μου η σταθερα ειναι το ζ ενω στο δικο σου τα κ,ν.

[quote="filosofimenos"][color=red][b]Εστω ν ατομα. Ο καθενας μισει ακριβως κ(με κ<ν, κανενας δεν μπορει να μισει των ευατο του).
Να βρεθουν ολα τα ζευγοι (κ,ν) ωστε να υπαρχουν ακριβως ζ αμοιβαια μιση(ζ≥0).[/b][/color][/quote]

Κατ' αρχάς δεν υπάρχει το αντίστροφο (αυτό είναι το συμπέρασμα από post του Durandal):

π.χ (κ=2, ν=4)

Α.
ΜΙΣΗ:
1 μισεί 2
1 μισεί 3
2 μισεί 3
2 μισεί 4
3 μισεί 4
3 μισεί 1
4 μισεί 1
4 μισεί 2
ΑΛΛΗΛΟΜΙΣΗ:
1 - 3
2 - 4

Β.
ΜΙΣΗ:
1 μισεί 4
1 μισεί 3
2 μισεί 3
2 μισεί 4
3 μισεί 4
3 μισεί 1
4 μισεί 1
4 μισεί 2
ΑΛΛΗΛΟΜΙΣΗ:
1 - 3
1 - 4
2 - 4

Επίσης, για κ>0 είναι ν>1 άρα ζ >=1 από Dirichlet (Ι).

Μια ιδέα λύσης τώρα για ν>1, κ>=0 (περιέχει 'αλχημείες', απλώς θέλω να μου πείτε τη γνώμη σας):
- οι πιθανοί συνδυασμοί μίσεων είναι κ^ν
- η πιθανότητα να αλληλομισιούνται δύο άτομα είναι 1/(κ^ν) * 1/(κ^ν)
- εκφράζουμε την ίδια πιθανότητα με το ζ ... qed

Για το πρόβλημα του Durandal, είναι n ανά k τα αμοιβαία μίση για κάθε αναδιάταξη του n και με λίγη συνδυαστική βγαίνει (έχω καιρό να κάνω συνδυαστική κια δε θυμάμαι τίποτα για να το υπολογίσω).

Λοιπον προτεινω να πιασουμε ενα-ενα τα προβληματα. Για το δικο μου συμφωνω σε αυτα που λες αλλα για προχωρα το λιγο γιατι δεν βλεπω που θες να καταληξεις...

[b]Edit:[/b] @maniopas λες "Επίσης, για κ>0 είναι ν>1 άρα ζ >=1 από Dirichlet". Δεν το βλεπω σωστο ευκολα κατασκευαζεται αντιπαραδειγμα :wink: .

Δεν έχω διαβάσει όλα τα post πολύ προσεκτίκα γι'αυτο ζητάω συγνώμη αν κάτι δεν κατάλαβα καλά η έχει ήδη απαντηθεί.

[quote="filosofimenos"]Για το δικο μου προβλημα: Αυτο που λεω ειναι
Για πια κ,ν μπορουμε να τοποθετησουμε τα μισοι καταλληλα ωστε να υπαρξουν ζ αλληλομισοι.
[/quote]

Πρέπει σίγουρα να έχουμε 0 <= ζ <= κν/2. (Διαιρώ με το δύο διότι κάθε αμοιβαίο μίσος χρειάζεται δύο μίση για να υπάρξει.)

Έχουμε ακόμη ζ >= κν - ν(ν-1)/2 = ν(2κ + 1 - ν)/2. (Pigeonhole)

Ισχυρίζομαι ότι για κάθε ακέραιο ζ που ικανοποιεί αυτές τις ανισότητες μπορούμε να τοποθετήσουμε τα μίση κατάλληλα ώστε να υπάρχουν ακριβώς ζ αλληλομίση

Hint:
1) Αποδείξτε ότι μπορούμε να έχουμε $ z \equal{} \lfloor kn/2 \rfloor$. (Αυτό είναι ίσως το πιο δύσκολο κομμάτι της απόδειξης)
2) Δείξτε πως μπορείτε να ανατοποθετήσετε τα μίση για να πάτε από ζ σε ζ-1. (Αν ζ >= min(κν - ν(ν-1)/2,0) + 1)

[quote="Demetres"]
Hint:
1) Αποδείξτε ότι μπορούμε να έχουμε $ z \equal{} \lfloor kn/2 \rfloor$. (Αυτό είναι ίσως το πιο δύσκολο κομμάτι της απόδειξης)
2) Δείξτε πως μπορείτε να ανατοποθετήσετε τα μίση για να πάτε από ζ σε ζ-1. (Αν ζ >= min(κν - ν(ν-1)/2,0) + 1)[/quote]

Yup, ακριβώς σε αυτό το maximum αναφερόμουν (γι'αυτό είχα επιλέξει το συγκεκριμένο παράδειγμα στο post μου) :)

Cheerio,

Durandal 1707

[quote="filosofimenos"]Ρε Δημητρη εξηγεις λιγο αυτο"Έχουμε ακόμη ζ >= κν - ν(ν-1)/2 = ν(2κ + 1 - ν)/2. (Pigeonhole) "[/quote]

Έχουμε ν(ν-1)/2 ζευγάρια. Σκέψου κάθε ζευγάρι σαν θέσεις στις οποίες μπορούμε να τοποθετήσουμε τα μίση. Σε κάθε θέση τοποθετούμε το πολύ 2 μίση. Για παράδειγμα στο ζευγάρι 12 μπορούμε να τοποθετήσουμε το μίσος του 1 προς τον 2 και το μίσος του 2 προς τον 1 (αν υπάρχουν) και τίποτα άλλο. Αφού έχουμε κν μίση, θα υπάρχουν τουλάχιστον  κν - ν(ν-1)/2 θέσεις που θα πάρουν από δύο μίση.

To 'πιασα :wink: . Θα δοκιμασω να αποδειξω αυτα που αναφερεις απο αυριο και αν βρω κατι θα το ποσταρω...

Για την ωρα ευχομαι καλη χρονια σε ολους. Τα ξαναλεμε απο 2009...

Να προσθέσω πως σκέφτομαι την άσκηση εγώ. Ίσως βοηθήσει τόσο σε αυτή την άσκηση όσο και σε παρόμοιες.

Οι σχέσεις μίσους που δεν είναι συμμετρικές, ορίζουν ένα κατευθηνόμενο γράφημα (directed graph). Δηλαδή: Έχουμε ένα σύνολο ν κορυφών (vertices) που αντιπροσωπεύουν τα ν άτομα, και ένα σύνολο κατευθηνόμενων ακμών (directed edges) που αντιπροσωπεύουν τα μίση. (Η ακμή μεταξύ των κορυφών 1 και 2 από το 1 στο 2 δηλώνει ότι ο 1 μισεί τον 2 κ.ο.κ.)

Η άσκηση λοιπόν ζητά για κάθε κ,ν,ζ που ικανοποιούν τις συνθήκες που έγραψα σε προηγούμενο post, να κατασκευαστεί κατευθηνόμενο γράφημα ώστε κάθε κορυφή να έχει ακριβώς κ κατευθηνόμενες ακμές από αυτήν την κορυφή σε άλλες κορυφές (out-edges) έτσι ώστε να υπάρχουν ακριβώς ζ ζεύγη που να έχουν ακμές και προς τις δύο κατευθήνσεις.

Και εγω ετσι το ξεκινησα αλλα δεν καταληγω πουθενα οποτe θα δοκιμασω και χωρις graph theory.

Λοιπον παιδες δεν την εχω προσπαθησει αρκετα την ασκηση(πρεπει να γινουν και τα πστκα τα μαθηματα του σχολειου) αλλα εχω αποδειξει για μια ειδικη περιπτωση οτι γινεται ζ=κν/2. Οριστε η αποδειξη:

Θα μελετησουμε την περιπτωση για την οποια το ν ειναι πολλαπλασιο του κ+1. Τοτε, αφου ν=μ(κ+1) χωριζω τα ατομα σε μ ομαδες των κ+1(προφανως δεν υπαρχει ατομο που να βρισκεται σε δυο ομαδες). Ετσι τοποθετουμε τα μιση του καθε ατομου στα υπολοιπα ατομα της ομαδος του και ευκολα βλεπουμε οτι τα αμοιβαια μισοι(αλληλομισοι) ειναι κ(κ+1)/2. Ετσι συνολικα εχουμε  μκ(κ+1)/2 αλληλομισοι αλλα επειδη μ=ν/(κ+1), συνολικα εχουμε νκ/2 μισοι.

[quote="filosofimenos"]Θα μελετησουμε την περιπτωση για την οποια το ν ειναι πολλαπλασιο του κ+1. Τοτε, αφου ν=μ(κ+1) χωριζω τα ατομα σε μ ομαδες των κ+1(προφανως δεν υπαρχει ατομο που να βρισκεται σε δυο ομαδες). Ετσι τοποθετουμε τα μιση του καθε ατομου στα υπολοιπα ατομα της ομαδος του και ευκολα βλεπουμε οτι τα αμοιβαια μισοι(αλληλομισοι) ειναι κ(κ+1)/2. Ετσι συνολικα εχουμε  μκ(κ+1)/2 αλληλομισοι αλλα επειδη μ=ν/(κ+1), συνολικα εχουμε νκ/2 μισοι.[/quote]

Good, γι'αυτόν ακριβώς το λόγο βόλευαν τα αρχικά σου νούμερα :)

Πρόσεξε τώρα ότι ο Dem αναφέρεται σε $ \left\lfloor\frac{kn}{2}\right\rfloor$ μίση και σκέψου τί περισσεύει...

Cheerio,

Durandal 1707

Tι εννοεις "τι περισευει"? :huh:

[quote="filosofimenos"]Tι εννοεις "τι περισευει"? :huh:[/quote]

Εννοώ: σκέψου στους τελευταίους $ r<k\plus{}1$ που περισσεύουν όταν το $ k\plus{}1$ δε διαιρεί το $ n$, πώς μπορούμε να ρυθμίσουμε τα μίση για να πιάσουμε το $ \lfloor nk/2 \rfloor$.

Cheerio,

Durandal 1707

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

Αυτό είναι ένα κλασσικό πρόβλημα θεωρίας γραφημάτων και υπάρχουν πάρα πολλοί τρόποι επίλυσης του.

Μια καλή αρχή θα ήταν να ονομάσεις τις κορυφές 1,2,...,ν και να προσπαθήσεις να βρεις κάποιον τρόπο να τοποθετήσεις τις ακμές ώστε κάθε κορυφή να βρίσκεται σε ακριβώς κ ακμές.

Παιδια επειδη δεν εχω βρει κατι και δεν εχω χρονο να προσπαθησω το προβλημα αλλο εξηγει καποιος την λυση?

Sorry, το είχα ξεχάσει.

Μια πιθανή λύση για $ k \equal{} 2\ell$ άρτιο, είναι να αριθμήσεις τα άτομα $ 1,2,...,n$ με τον $ i$ να μισεί τον $ j$ αν και μόνο αν $ i \minus{} j \in \{\pm 1,\ldots, \pm \ell\} \bmod n$. Η συνθήκη είναι συμμετρική και έτσι παίρνουμε ακριβώς $ \ell n$ αλληλομίση.

Αν παίξεις λίγο με αυτό το παράδειγμα θα βρεις παρόμοιες λύσεις για
- ν άρτιος αλλά κ περιττός
- ν και κ περιττός


[Unparseable or potentially dangerous latex formula. Error 5 : 1279x16]

I get this error when I used more than 2 code \text with a lot of words. In another word, is there anyway I can put sentences in Latex and save it as image? I try to use \text but obviously, Latex doesn't like me.

I strongly discourge the use of \text command inside a LaTeX formula.


MATHCOUNTS
trigonometry
ratio
geometry
trig identities
Law of Sines

In triangle ABC, \[ m\angle{A}=30  \] and \[ m\angle{C}=105  \]. If AC=8 units, what is the length of segment BC?

It said it had to be in simplest radical form.

[color=blue]Moderator kyyuanmathcount's note: MATHCOUNTS supposedly NEVER needs trig.  Please find methods that do not involve trig. for this problem, because, if it was on the workbook, it does NOT need trig., thanks.[/color]

[hide="hint"]Try dividing it into smaller right triangles and use pythagorean theorm or trig to figure it out.[/hide]

[hide="answer"]$4\sqrt{6}$[/hide]

I got [hide]4 sqrt2[/hide] using trig (the law of sines)...

[quote="biffanddoc"][hide="law of sines way"]
$AC=b$
$m\angle B=180-135=45$

$\frac{\sin{45}}{8}=\frac{\sin{30}}{a}$
$8\sin{30}=a\sin{45}$
$4\sqrt{3}=a\frac{\sqrt{2}}{2}$
$\frac{8\sqrt{3}}{\sqrt{2}}=a$
$\frac{2\cdot8\sqrt{3}}{\sqrt{2}}$
$\frac{16\sqrt{2}}{\sqrt{2}}$
$\frac{16\sqrt{6}}{2}$
$8\sqrt{6}$[/hide][/quote]
[hide]
$8\sin{30}\neq4\sqrt{3}.$
ANyways I did the same thing and got $4\sqrt{2}$[/hide]

[quote="felixnguyen"]Thanks. Do we need to know trig for Mathcounts?[/quote]

Nope. :)

[hide="without trig"]Drop an altitude from C down to side AB, and call that point of intersection D. Now C is split into two angles with measures 60 degrees and 45 degrees. This divides triangle ABC into triangle ACD (a 30-60-90) and triangle BCD (a 45-45-90). As the ratio of sides in a 30-60-90 is 1-rt2-2 respectively, side CD is 4. As the ratio of sides in a 45-45-90 is 1-1-rt2, side BC is 4rt2.[/hide]


Find at least one real root of the equation $ 81x^5\minus{}18x^2\minus{}98x\minus{}14\sqrt{2}\equal{}0$.

hello, one solution ist
$ x\equal{}\frac{2}{3}\plus{}\frac{1}{3}\sqrt{2}$.
Sonnhard.

[quote="Dr Sonnhard Graubner"]hello, one solution ist
$ x \equal{} \frac {2}{3} \plus{} \frac {1}{3}\sqrt {2}$.
Sonnhard.[/quote]
Well done!

[quote="Nak"]Find at least one real root of the equation $ 81x^5 \minus{} 18x^2 \minus{} 98x \minus{} 14\sqrt {2} \equal{} 0$.[/quote]

too late  :wink:

$ 81x^5 \minus{} 18x^2 \minus{} 98x \minus{} 14\sqrt {2}$ $ \equal{}(3x\minus{}2\minus{}\sqrt 2)(3x^2\plus{}(2\plus{}\sqrt 2)x\plus{}2\minus{}\sqrt 2)(9x^2\plus{}7\sqrt 2)$

[quote="pco"][quote="Nak"]Find at least one real root of the equation $ 81x^5 \minus{} 18x^2 \minus{} 98x \minus{} 14\sqrt {2} \equal{} 0$.[/quote]

too late  :wink:

$ 81x^5 \minus{} 18x^2 \minus{} 98x \minus{} 14\sqrt {2}$ $ \equal{} (3x \minus{} 2 \minus{} \sqrt 2)(3x^2 \plus{} (2 \plus{} \sqrt 2)x \plus{} 2 \minus{} \sqrt 2)(9x^2 \plus{} 7\sqrt 2)$[/quote]

Nice. Here is my general formula to get fifth degree equation: $ x^5\minus{}pqx^2\minus{}(q\minus{}p^2)^2x\plus{}pq(q\minus{}p^2)$


[quote="aspiringchemlete"]Solve for n:

$ \binom{n}{2}=P_{2}^{n-1}$.[/quote]

Am I missing something here?

[hide]Just use the formulas:
$ \frac{n(n-1)}{2}= (n-1)(n-2)$
$ n = 2n-4 \text{ (Since }n=1 \text{ doesn't work)}$
$ \boxed{n=4}$[/hide]


function
algebra
polynomial
domain
ratio
irrational number
combinatorics unsolved

Find a bijection $ f \, : \, \mathbb{Q} \rightarrow \mathbb{Q} \backslash \{0\}$. Can $ f$ be strictly increasing (that is, $ f(x) < f(y)$ whenever $ x < y$)?

Wrong. [Edit- was a response to shallow's post, now removed. Please don't remove the content of posts that have been replied to.]

An explicit example:
Consider the sequence $ x_0 \equal{} 1, x_1 \equal{} \frac32, x_{n \plus{} 1} \equal{} \frac12\left(x_n \plus{} \frac2{x_n}\right)$; this alternates sides of $ \sqrt {2}$ and converges rapidly to $ \sqrt {2}$, with all $ x_n$ rational.
Define $ f$ piecewise linearly as follows:
$ f(x_n) \equal{} x_n^2 \minus{} 2$
For $ x < x_0 \equal{} 1$, $ f(x) \equal{} x \minus{} 2$
For $ x > x_1 \equal{} \frac32$, $ f(x) \equal{} x \minus{} \frac54$
For $ x_{2k} < x < x_{2k \plus{} 2}$, $ f(x) \equal{} \frac {x_{2k \plus{} 2}^2 \minus{} x_{2k}^2}{x_{2k \plus{} 2} \minus{} x_{2k}}(x \minus{} x_{2k}) \plus{} x_{2k}^2 \minus{} 2 \equal{} \left(x_{2k \plus{} 2} \plus{} x_{2k}\right)x \minus{} x_{2k}x_{2k \plus{} 2} \minus{} 2$
For $ x_{2k \plus{} 1} < x < x_{2k \minus{} 1}$, $ f(x) \equal{} \frac {x_{2k \minus{} 1}^2 \minus{} x_{2k \plus{} 1}^2}{x_{2k \minus{} 1} \minus{} x_{2k \plus{} 1}}(x \minus{} x_{2k \plus{} 1}) \plus{} x_{2k \plus{} 1}^2 \minus{} 2$
$ \equal{} \left(x_{2k \minus{} 1} \plus{} x_{2k \plus{} 1}\right)x \minus{} x_{2k \plus{} 1}x_{2k \minus{} 1} \minus{} 2$
This is monotone increasing, and continuous as a function from $ \mathbb{Q}$ to itself. If you tried to extend it to $ \mathbb{R}$, it would map $ \sqrt {2}$ to zero

[quote="jmerry"]An explicit example:
Consider the sequence $ x_0 \equal{} 1, x_1 \equal{} \frac32, x_{n \plus{} 1} \equal{} \frac12\left(x \plus{} \frac2x\right)$; this alternates sides of $ \sqrt {2}$ and converges rapidly to $ \sqrt {2}$, with all $ x_n$ rational.
[/quote]

Here do you mean $ x_{n\plus{}1} \equal{} \frac12\left(x_n \plus{} \frac{2}{x_n}\right)$ or perhaps $ x_{n\plus{}1} \equal{} \frac12\left(x_n \plus{} \frac{2}{x_{n\minus{}1}}\right)$?

The former. Edited.

The details don't matter that much; all we really need is an irrational number and sequences that tend monotonically to it from each side.

Does this mean that for $ 1 < x < \frac{3}{2}, x \in \mathbb{Q}$, $ f$ maps these values to $ \minus{}1 < f(x) < \frac{11}{4}, f(x) \in \mathbb{Q}$? That doesn't look like a bijection at first sight  :maybe:

Not $ \frac{11}{4}$; $ \frac14$. Aside from that, yes- except that zero isn't the image of anything. We map the rationals greater than $ \sqrt{2}$ to the rationals greater than zero, and the ones less than $ \sqrt{2}$ to the rationals less than zero.

The bijection has to be complicated; this is about as simple as it gets. I can't just use something like $ x^2\minus{}2$, as any nonlinear polynomial misses lots of values. Linear polynomials, on the other hand, hit every rational- but I need to miss something. So we compromise; piecewise linear, with the key points on a higher-degree polynomial curve. Yes, infinitely many pieces are needed.

I think the answer is yes:
[url]http://en.wikipedia.org/wiki/Back-and-forth_method[/url]

[quote="jmerry"]Not $ \frac {11}{4}$; $ \frac14$. Aside from that, yes- except that zero isn't the image of anything. We map the rationals greater than $ \sqrt {2}$ to the rationals greater than zero, and the ones less than $ \sqrt {2}$ to the rationals less than zero.
[/quote]
Yes $ \frac{1}{4}$, my mistake. But still we're mapping a set of size $ \frac{1}{2}$ to a set of size $ \frac{5}{4}$ - is this possible because there's an infinite number of rational numbers in both ranges?

Reading that back-and-forth method now, but there are still some things I don't understand about infinite sets  :maybe:

Bijections of infinite ordered sets (even monotonous) do not necessarily preserve the "size" of sets (like, length of intervals; unlike those for finite sets, which preserve the only possible "size": their cardinality).

[quote="jmerry"]Consider the sequence $ x_0 \equal{} 1, x_1 \equal{} \frac32, x_{n \plus{} 1} \equal{} \frac12\left(x_n \plus{} \frac2{x_n}\right)$; this alternates sides of $ \sqrt {2}$ and converges rapidly to $ \sqrt {2}$, with all $ x_n$ rational.
[/quote]

Just one thing, it doesn't alternate sides of $ \sqrt{2}$ - $ x_2 \equal{} \frac{577}{408}$ is bigger than $ \sqrt{2}$ and so is on the same side as $ x_1$. :maybe:  We have some domains overlapping there!

In fact I used Excel to calculate some values, and the first few $ x_n$ are all bigger than $ \sqrt{2}$, so this function might not work

Actually $ x_2 \equal{} \frac {17}{12}$, but it is still larger than $ \sqrt {2}$.  (The number you gave is $ x_3$.)  But, go re-read post 5 (jmerry's second comment on this thread).

[quote="JBL"]Actually $ x_2 \equal{} \frac {17}{12}$, but it is still larger than $ \sqrt {2}$.[/quote]
Yes, my mistake there.

There's something about sequences that tend monotonically to $ \sqrt {2}$ from each side - in this case it's only the side larger than $ \sqrt {2}$ though. But the domains are overlapping if the function is defined piecewise as jmerry defined

Oh, ack. Yes, my example doesn't work because the sequence behaves the wrong way.

New example: $ x_1\equal{}1, x_2\equal{}2, x_n\equal{}1\plus{}\frac1{x_{n\minus{}1}}\equal{}\frac{F_{n\plus{}1}}{F_n}$ and $ f(x_n)\equal{}x_n^2\minus{}x_n\minus{}1$, continued as a piecewise linear function. Those $ x_n$ alternate sides of the golden ratio $ \frac{\sqrt{5}\plus{}1}{2}$.

Wouldn't

$ f(x) \equal{} \left\{
     \begin{array}{lr}
       x \plus{} 1 &  x \in \mathbb{N}_0\\
       x & \mathrm{ otherwise}
     \end{array}
   \right.$

be an easier bijection?

I don't think that is strictly increasing: $ f(0) \equal{} 1$ and $ f(0.5) \equal{} 0.5$ which violates $ f(x) < f(y)$ if $ x < y$

You're right, it's not strictly increasing. I took the second part of the question to mean "is it possible for any such f to be strictly increasing?".


calculus
integration
function
algebra
rational function
calculus computations

\[ \int {\frac{{xdx}}
{{\left( {x^3  \minus{} 3x \plus{} 2} \right)\sqrt {x^2  \minus{} 4x \plus{} 3} }}}
\]

@b555:I've been through this already....If you think this is my homework , plz don't answer :huh: And to assure you -this isn't my homework. The problems are given to see the different methods of the mathlinkers, though till now , most solutions are similar to mine.

hello, setting $ \sqrt{x^2-4x+3}=t+x$ we get $ x=\frac{3-t^2}{2t+4}$ and ${{ dx=-\frac71}{2}\frac7t^2+4t+3}{(t+2)^2}\,dt$, and after an ugly calculation we get
$ 4\int\frac{(t+3)(t+2)}{t(t+1)^3(t^2-4t-11)}\,dt$ which is a rational function to integrate.
Sonnhard.


abstract algebra
group theory
superior algebra
superior algebra unsolved

[quote="JackSchmidt"][quote="Phidias"]How to prove the central automorphisms of a group are inner automorphisms?[/quote]

It is not true. Take the group to be G = < a,b : a^4=b^3=1, ba=abb >.  The automorphism that takes (a,b) to (aaa,b) is central since on G/Z(G) = S3 it takes (a,b) to (a,b), however the normalizer of <a> in G is just <a> and so the automorphism is not inner.  Of course every abelian group of order at least 3 is also a counterexample, as G/Z(G)=1 in this case, but G is the smallest non-abelian counterexample. Every group of order 16 is a counterexample.[/quote]

Thanks a lot~! Your counterexample is great! Yesterday I found an exercise in a book which called us to prove the proposition above. I have proved that a centual automorphism fixes the commutator subgroup, but I could't go any further. So thank you very much~! The question costed me lots of time...

By the way, how did you find the couterexample? It's so amazing~!


What is the least positive integer that is divisible by 2, 3, 4, 5, 6, 7, and 8?

If we find the LCM it is 8*7*3*5, which equals 840.

The reason we don't include $2$, $4$, and $6$ when we find the LCM is because we already included $3$ and $8$.

$3\cdot 8=24$ and $2$, $4$, $6$ all divide evenly into $24$.


An elevator with a mass of 2500 kg carries four passengers with a combined mass of 260 kg.
a) what is the tension in the supporting cable when the elevator starts from rest and moves upward with costant accleration until reaching a speed of 5.0m/s in 2.0 s.

b) what is the tension in the cable when the elevator starts down with the same load and acceleration of the same maginitude?

help please

(a) We have that $\sum F = \left( m_\textrm{elevator}+m_\textrm{passengers}\right) a$, where $a = \frac{\Delta v}{\Delta t}= 2.5 \, \frac{\textrm m}{\textrm s^{2}}$.
Thus, $F_\textrm{ext}= \left( m_\textrm{elevator}+m_\textrm{passengers}\right) (a+g)$. The tension should also be equal to this.


A new problem:
Let $a,b,c>0$ and $ab+bc+ca=1$.Prove that:
          $(a^2+bc)(b^2+ca)(c^2+ab) \geq \frac{8}{27}$

I got the opposite and I can't understand why...

by AM-GM
$\frac{ab+bc+ca}{3}\geq \sqrt[3]{a^2b^2c^2} \implies a^2b^2c^2 \leq \frac{1}{27}$  (1)

The $LHS$  becomes $2a^2b^2c^2+a^3b^3+b^3c^3+c^3a^3+a^4bc+ab^4c+abc^4$.
Now, by CM-AM, we get

$\sqrt[3]{\frac{a^3b^3+b^3c^3+c^3a^3}{3}}\geq \frac{ab+bc+ca}{3} \implies a^3b^3+b^3c^3+c^3a^3\geq \frac{1}{9}$

and by AM-GM, $a^4bc+ab^4c+abc^4\geq 3a^2b^2c^2$

So $LHS\geq 5a^2b^2c^2+\frac{1}{9}\geq \frac{8}{27} \implies a^2b^2c^2\geq \frac{1}{27}$, but it is false by (1)...

[quote="hydro"]
 $LHS\geq 5a^2b^2c^2+\frac{1}{9}\geq \frac{8}{27} \implies a^2b^2c^2\geq \frac{1}{27}$, but it is false by (1)...[/quote]
hydro!!!!!
$5a^2b^2c^2+\frac{1}{9}\geq \frac{8}{27}$
is not necessary.

[quote="Frey"]
Let $a,b,c>0$ and $ab+bc+ca=1$.Prove that:
          $(a^2+bc)(b^2+ca)(c^2+ab) \geq \frac{8}{27}$[/quote]
$(a^2+bc)(b^2+ca)(c^2+ab) \geq \frac{8}{27}\Leftrightarrow$
$\Leftrightarrow27(a^2+bc)(b^2+ac)(c^2+ab)\geq8(ab+ac+bc)^3.$ The last inequality is obviously true.
How this inequality could be strengthened, not touching LHS?  ;)

[quote="Frey"]This is wrong:
 $5a^2b^2c^2+\frac{1}{9}\geq \frac{8}{27}$
To [b]Argady[/b]:Can you post full Solution of this problem?[/quote]
You just need to homegenize the inequality, then expanding both side, and use Muirhead's - arqady said.

[quote="Frey"]
To [b]Argady[/b]:Can you post full Solution of this problem?[/quote]
$(a^2+bc)(b^2+ca)(c^2+ab) \geq \frac{8}{27}\Leftrightarrow$
$\Leftrightarrow27(a^2+bc)(b^2+ac)(c^2+ab)\geq8(ab+ac+bc)^3\Leftrightarrow$
$\Leftrightarrow9\sum_{cyc}(2a^2b^2c^2+3a^4bc+3a^3b^3)\geq8\sum_{cyc}(a^3b^3+3a^3b^2c+3a^3c^2b+2a^2b^2c^2)\Leftrightarrow$
$\sum_{cyc}(19a^3b^3+27a^4bc-24a^3b^2c-24a^3c^2b+2a^2b^2c^2)\geq0\Leftrightarrow$
$\Leftrightarrow2\sum_{cyc}(a^3b^3-a^3b^2c-a^3c^2b+a^2b^2c^2)+$
$+\sum_{cyc}(17a^3b^3+27a^4bc-22a^3b^2c-22a^3c^2b)\geq0.$ This is true from Muirhead and Schur.

[quote=sqing]Let $a,b,c>0$ and $ab+bc+ca=1.$ Prove that$$(a^2+2bc)(b^2+2ca)(c^2+2ab) \geq 1$$$$(a^2+3bc)(b^2+3ca)(c^2+3ab) \geq \frac{64}{27}$$
[size=50](YZM)[/size][/quote]

The $uvw$ method can definitely kill those problems.

[quote=Frey]A new problem:
Let $a,b,c>0$ and $ab+bc+ca=1$.Prove that:
          $$(a^2+bc)(b^2+ca)(c^2+ab) \geq \frac{8}{27}$$[/quote]
Let $ a,b,c >0$ . [url=https://artofproblemsolving.com/community/c6h195577p1074515]Prove that[/url]
$$ 9(a^2\plus{}bc)(b^2\plus{}ca)(c^2\plus{}ab) \le 8 (a^3 \plus{} b^3 \plus{} c^3)^2$$

[quote=sqing][quote=Frey]A new problem:
Let $a,b,c>0$ and $ab+bc+ca=1$.Prove that:
          $$(a^2+bc)(b^2+ca)(c^2+ab) \geq \frac{8}{27}$$[/quote]
Let $ a,b,c >0$ . [url=https://artofproblemsolving.com/community/c6h195577p1074515Prove that[/url]
$$ 9(a^2\plus{}bc)(b^2\plus{}ca)(c^2\plus{}ab) \le 8 (a^3 \plus{} b^3 \plus{} c^3)^2$$[/quote]

Here's my solution:
It is equivalent to: $\frac{9(a^{2}+bc)(b^{2}+ca)(c^{2}+ab)}{a^{2}b^{2}c^{2}}\leq \frac{8(a^{3}+b^{3}+c^{3})^{2}}{a^{2}b^{2}c^{2}}$
Or $9\left(\frac{a^{2}}{bc}+1\right)\left(\frac{b^{2}}{ca}+1\right)\left(\frac{c^{2}}{ab}+1\right)\leq 8\left(\frac{a^{2}}{bc}+\frac{b^{2}}{ca}+\frac{c^{2}}{ab}\right)^{2}$.
Setting $\frac{a^{2}}{bc}=x$; $\frac{b^{2}}{ca}=y$; $\frac{c^{2}}{ab}=z$. We obtain $xyz=1$ and $x;y;z>0$.
The inequality is equivalent to $9(x+1)(y+1)(z+1)\leq 8(x+y+z)^{2}$ or $8(x^{2}+y^{2}+z^{2})+7(xy+yz+zx)\geq 18+9(x+y+z)$. The term $xy+yz+zx$ is equal to $\frac{1}{x}+\frac{1}{y}+\frac{1}{z}$. Hence, it remains to prove that $\left(8x^{2}+\frac{7}{x}-9x-6\right)+\left(8y^{2}+\frac{7}{y}-9y-6\right)+\left(8z^{2}+\frac{7}{z}-9z-6\right)\geq 0$. The last inequality is obviously true because it's equivalent to $\frac{(x-1)^{2}(8x+7)}{x}+\frac{(y-1)^{2}(8y+7)}{y}+\frac{(z-1)^{2}(8z+7)}{z}\geq 0$ and this is true.
[b][u]End of the solution.[/u][/b]

[quote=Frey]A new problem:
Let $a,b,c>0$ and $ab+bc+ca=1$.Prove that$$(a^2+bc)(b^2+ca)(c^2+ab) \geq \frac{8}{27}$$[/quote]
Let $a,b,c\geq 0$ .Prove that
$$64(a^2+bc)(b^2+ca)(c^2+ab) \leq (a+b+c)^6$$
[size=50](Đặng Trọng Nghĩa)[/size]
Let $\displaystyle a,b,c$ be positive real numbers. Prove that $$\displaystyle \left(a+\frac{bc}{a}\right)\left(b+\frac{ca}{b}\right)\left(c+\frac{ab}{c}\right)-8abc\geq a(b-c)^2+b(c-a)^2+c(a-b)^2.$$
Let $a,b,c>0$ and $ab+bc+ca=3$.[url=https://artofproblemsolving.com/community/c6h2478345p20788282]Prove that[/url]
$$(a+bc)(b+ac)(c+ab)\ge 8$$
$$(a+b)(a+bc)+(b+c)(b+ca)+(c+a)(c+ab)\geq 12$$
[url]https://artofproblemsolving.com/community/c6h2237591p17138075[/url]
[quote=Quantum_fluctuations]
[url]https://artofproblemsolving.com/community/c4h2478164p20786896[/url]
[Hide=A very big failed attempt]

It's a well-known inequality that

$$ (a \enspace+\enspace b \enspace + \enspace c)^2 \enspace\enspace \geq \enspace \enspace 3(ab \enspace + \enspace bc \enspace + \enspace ca)$$

$$ \iff \quad \quad \quad a \enspace+\enspace b \enspace + \enspace c \quad  \geq \quad 3 \quad \quad \quad \quad \quad \quad \quad \quad (1)$$

Therefore, we have the inequalities,

$$a+b \enspace \geq \enspace 3-c \quad ,\quad \quad b+c \enspace \geq \enspace 3-a \quad, \quad \quad a+b \enspace \geq \enspace 3-c$$

And hence,
$$(a+b)(a+bc) \enspace + \enspace  (b+c)(b+ca) \enspace  + \enspace  (c+a)(c+ab) \enspace  \geq \enspace  (3-c)(a+bc) \enspace + \enspace (3-a)(b+ca) \enspace + \enspace (3-b)(c+ab) \enspace + \enspace $$

$$ \iff \quad \quad \quad (a+b)(a+bc) \enspace + \enspace  (b+c)(b+ca) \enspace  + \enspace  (c+a)(c+ab) \enspace \geq \enspace 3(a+b+c) \enspace+\enspace 2(ab+bc+ca) \enspace - \enspace (ab^2+bc^2+ca^2)$$

So, we just need to show that

$$3(a+b+c)  \enspace - \enspace (ab^2+bc^2+ca^2) \quad \geq \quad 6$$

[u]Lemma :[/u]  For positive real number $a$, $b$ and $c$

$$ \frac{4(a+b+c)^3}{27} -abc \enspace \geq \enspace ab^2\enspace+\enspace bc^2\enspace+\enspace ca^2$$

[Hide= Proof]

Since the given inequality is cyclic, we can assume WLOG that $z  = \min \{x,y,z\}$

Let $\{ x,y,z \}$ be a permutation of $\{a,b,c\}$ such that $x\geq y\geq z$. It's clear that $z=c$ and $x=a,y=b$ or $y=a, x=b$ depending on whether $a \geq b$ or $b \geq a$ respectively.

Observe that the expression  $$ab^2+bc^2+ca^2$$ is equivalent to either $$xy^2+yz^2+zx^2$$ or $$yx^2+xz^2+zy^2$$ depending on the relative order of $a$ and $b$.

Now, we  have the following inequalities,

$$ xy \enspace \geq \enspace  xz \enspace  \geq \enspace yz$$

and

$$ x \enspace \geq \enspace  y \enspace \geq z$$

Using rearrangement inequality on the above sequences, we can obtain that

$$x^2y \enspace + \enspace xyz \enspace + \enspace yz^2 \enspace = \enspace x \cdot xy \enspace+\enspace y \cdot xz \enspace +\enspace z \cdot yz \quad \geq \quad   y \cdot xy \enspace + \enspace  x \cdot xz \enspace + \enspace z \cdot yz \enspace = \enspace xy^2 \enspace + \enspace yz^2 \enspace + \enspace zx^2$$

and

$$x^2y\enspace+\enspace xyz \enspace + \enspace yz^2 \enspace = \enspace  x \cdot xy \enspace + \enspace y \cdot xz \enspace + \enspace z \cdot yz \quad \geq \quad    x \cdot xy \enspace + \enspace z \cdot xz\enspace + \enspace y \cdot yz \enspace = \enspace yx^2 \enspace + \enspace xz^2 \enspace + \enspace zy^2$$

Therefore, irrespective of the relative order of $a$ and $b$, we have

$$ x^2y \enspace + \enspace xyz\enspace + \enspace yz^2 \enspace \geq  \enspace ab^2 \enspace + \enspace bc^2 \enspace + \enspace ca^2 \quad \quad \quad  \quad \quad \quad (1)$$

Now, using [b]A.M.-G.M. inequality[/b], we have

$$y \enspace + \enspace \frac{x+z}{2} \enspace + \enspace \frac{x+z}{2} \enspace \geq \enspace 3 \sqrt[3]{  y\left(\frac{x+z}{2}\right)^2}$$

$$ \iff \quad \quad \quad  \frac{4(x+y+z)^3}{27} \quad \geq \quad y(x+z)^2$$

$$ \iff \quad \quad \quad \frac{4(x+y+z)^3}{27} \enspace - \enspace xyz \quad \geq \quad  x^2y\enspace+\enspace xyz\enspace+\enspace yz^2  $$

Also, since $\{ x,y,z \}$ is just a permutation of $\{a,b,c\}$, the last inequality is equivalent to

$$ \iff \quad \quad \quad \frac{4(a+b+c)^3}{27} \enspace - \enspace abc  \quad \geq \quad  x^2y\enspace+\enspace xyz\enspace+\enspace yz^2  \quad \quad \quad \quad \quad \quad (2)$$

Finally, combining the inequalities $(1)$ and $(2)$ proves our lemma.

[/hide]

Applying the above lemma, we have

$$3(a+b+c)  \enspace - \enspace (ab^2+bc^2+ca^2) \quad \geq \quad 3(a+b+c) \enspace - \enspace  \frac{4(a+b+c)^3}{27} \enspace + \enspace abc$$

Now, using the inequality (1)[/quote]

Let  $a,b,c>0.$ Prove that$$(a^2+2bc)(b^2+2ca)(c^2+2ab)\geq (ab+ac+bc)^3$$
[hide=#4][quote=arqady]
$(a^2+bc)(b^2+ca)(c^2+ab) \geq \frac{8}{27}\Leftrightarrow$
$\Leftrightarrow27(a^2+bc)(b^2+ac)(c^2+ab)\geq8(ab+ac+bc)^3.$ The last inequality is obviously true.
[/quote][/hide]
[url=https://artofproblemsolving.com/community/c6h2718981p23650532]here[/url]


function
number theory
number theory theorems

What are some questions that you need the mobius inverse function to solve. I have not found anything real good. Does not have to be olympiad level. Maybe just something above the basics.

It's used in higher mathematics quite often in Algebra and Number Theory, if you ever read:

"A classical introduction to modern number theory" by Rosen and Ireland, it is used throughout.

Thanks. I had asked someone I knew and they recommended a book by Rosen as well. It might be the same one. Thanks again.

One question that I vaguely recall is this.

Let $a_n$ be a sequence of integers, such that $2^n=\sum_{d|n} a_d$. Prove that $n\mid a_n$.
In any case, I solved it using Moebius.

Andrei

Here is the mobius inversion formula : [hide]http://planetmath.org/encyclopedia/MobiusInversionFormula.html[/hide]

How many primitive binary strings are there? Primitve strings can't be broken down into a smaller string repeated many times. For instance, $100101001010010$ is not primitive (it can be broken down into $10010$ 3 times) but $1101$ is.

EDIT: Of length n

[quote="felipeochoa"]How many primitive binary strings are there? Primitve strings can't be broken down into a smaller string repeated many times. For instance, $100101001010010$ is not primitive (it can be broken down into $10010$ 3 times) but $1101$ is.[/quote]

I think you're missing some conditions. There are $\infty$ primitive strings since $11111....110$ is primitive, no matter how many ones it has.

[hide] let $f(n)$ be the amount of primary binary strings of length n and $g(n)$ be the total number of binary strings of length n. Clearly $g(n)=2^n$ On the other hand, every none primitve string can be broken into a primitive string of length $d,$ such that $d \mid n$ and every primitve string of length $d$ can be made into a non-primitive string of length n. From this,
\begin{eqnarray*}g(n) &=& \displaystyle\sum_{d\mid n} f(d)\\ f(n) &=& \sum_{d\mid n} \mu(\frac{n}{d})g(d)\\ f(n) &=& \sum_{d\mid n} \mu(\frac{n}{d})2^d \end{eqnarray*}[/hide]


What single percent discount from the original price is equivalent to
a 40$ \%$ discount on an item already on sale at a 20$ \%$ discount from
the original price?

After the first discount $ 60\% \equal{}0.6$ of the original item is left, and after the second discount, $ 80\% \cdot 0.6\equal{}0.48$ of the original item is left, which is $ 0.52\equal{}\boxed{52\% }$ less.


linear algebra
matrix
function
inequalities
induction
superior algebra
superior algebra solved

Let A in M_2(R), such that detA \geq 0
Proove that
det(A^n+I)+det(A^n-I) \geq (1/2^(n-2))(detA +1)^n

Dan Secleman, Conc. Gheorghe Dumitrescu 2003
-------------------------------------------------------------
Here my solution, if you have a different one i'll take it
thank you.

Consider A as a matrix in M_2(C), A is similar to a triangular superior
with diag(a;a*) where a* is the conjugate of a (A is reals coefficients)
LHS is (a^n+1)(a*^n+1)+(a^n-1)(a*^n-1)=2(|a|^(2n)+1)
RHS is (1/2^(n-2))(|a|+1)^n with |a|=a.a* =detA \geq 0

Lemma If t \geq 0 then 2^(n-1)(t^n+1) \geq (t+1)^n
proof just study the function f(t)=2^(n-1)(t^n+1) - (t+1)^n on R+
min f = f(1)=0

Use the lemma for t=|a|

Mr.Omarjee

For all X,Y in M2(R) we have
det(X+Y)+det(X-Y)=2(det(X)+det(Y)).

So  \sum det(A n \pm I)=2(detA n+1).
The inequality that need proving is
(2 n-1)(x n+1) \geq (x+1) n for all x \geq 0.

There is a more general inequality, a kind of generelization of C.B.S
 \pi {i in 1..n}(a_i n+b_i n) \geq ( \pi a_i+ \pi b_i) n.
If I'm not wrong, this can be proven by the Cauchy induction:
n->2n and n+1->n


probability
algebra
polynomial
quadratics
combinatorics unsolved
combinatorics

Nine houses are built on a circular road. Each house is painted red, white, or blue with probability 1/3 for each color. What is the probability that no two adjacent houses are the same color?

Let's consider the more general case with $n$ houses and $p$ colors.
I assume that the houses are numbered (otherwise, we have to look for colorings which can be deduced from each other with rotation).
Consider the graph where the vertices are the houses, two joined by an edge if and only if they are adjacents on the road (thus the graph is th cyclic one $C_n$).

Since there are clearly $p^n$ ways to assign colors to the vertices, the problem reduces to find the number of proper colorings of $C_n$ with $p$ colors, which is to determine the chromatic polynomial of $C_n$.

Let $P_n$ be the number of proper colorings for $n$ houses and $p$ colors, and $S_n$ be the number of colorings (for $n$ houses and $p$ colors) which are proper except for the houses $1$ and $n$ which form the unique pair of adjacent houses with the same color.

We have $P_1 = p$ and $P_2 = p(p-1)$.
Now, we add the house $n+1$ :

Each proper coloring with $n+1$ houses is obtained from a proper one with $n$ houses (by deleting $n+1$) except perhaps for the colors of $1$ and $n$.
Conversely :
Each of the colorings $P_n$ leads to $p-2$ proper colorings for $n+1$ houses (we may give any color to $n+1$ except the colors of $1$ and $n$, which are different).
Each of the $S_n$ colorings leads to $p-1$ proper colorings (any color for $n+1$ except the common color of $1$ and $n$).
Thus : $P_{n+1} = (p-2)P_n + (p-1)S_n$. (1)

A proper coloring for $n+1$ houses except for $1$ and $n+1$ is only and uniquely obtained from a proper coloring with $n$ houses, by giving $n+1$ the color of $1$.
Thus : $S_{n+1} = P_n$. (2)

From (1) and (2), we deduce that :
\[P_{n+1} = (p-2)P_n + (p-1)P_{n-1}.\]

This is a linear recurrence relation of order $2$, which can be easily solved (the quadratic characteristic equation has roots $-1$ and $p-1$), and using the values of $P_1,P_2$, it leads to :
\[P_n = p(p-1)^{n-1}.\]

Note that it is indeed a polynomial in $p$  :D .

So, the desired probability (for $n$ houses and $p$ colors) is $\dsp \frac  {p(p-1)^{n-1}} {p^n} = ( \frac {p-1} p )^{n-1}$.

Pierre.

Lol? :D

my dear Pierre...
*if you have p colors then for each house there's a 1/p chance it has the same color as the previous, so $\frac{p-1}p$ chance it hasn't. For each of the n-1 other houses means: $\left(\frac{p-1}p\right)^{n-1}$ (which is a little shorter :P)

*You will have noticed my solution is not correct, so since it's got the same result as yours, yours isn't either. We must still require that the n-th house hasn't got the same color as the 1st one. Like if you have 2 colors and an odd amount of houses, there's simply no way at all to make it work. So we still need to include some stuff. :)

I'm not sure about how exactly to do it, we must deduct the chance that 1 and n are the same color, and the other requirements are fulfilled, which looks a little like f(p, n-1)...

Which lead me to this recursion: $f(p, n) =\left(\frac{p-1}p\right)^{n-1} - \frac{f(p, n-1)}{p^{n-1}}$

But I got no clue of an explicit expression for this :) could anyone help me?

But Peter, the fact that your reasoning is not good does not imply that the result is not good either.
If you look at my solution, I take account that the houses $n$ and $1$ have not the same colors.

Pierre.

No I still think you don't. You state it but you didn't deal with it completely.
If you have 2 colors, the probability is simply 0 when n is odd. That's not true for your formula.

I'd wish it were true but $\left(\frac{2-1}{2}\right)^{n-1}\not=0$ for every odd $n-1$...

And yes, since it's an extra requirement compared to my first result, the real amount must be strictly lower than our result $\left(\frac{p-1}{p}\right)^{n-1}$

Ok, I see the error. This is not in the reasoning as you think but, in the computations.
The sequence $(P_n)$ has to be initialized to $P_2 = p(p-1)$ and $P_3 = p(p-1)(p-2)$ since $P_1$ has no sense.

It leads to $P_n = (p-1) \cdot (-1)^n + (p-1)^n$.

And you may check that $P_n = 0$ for $p=2$ and $n$ is odd. :D

Thus, the desired probability is $\frac {(p-1) \cdot (-1)^n + (p-1)^n} {p^n}$.

Pierre.

Nice. I saw you implemented it but I couldn't figure out where it got lost. :)

And it also fits my ugly recursion :cool:


[quote="MysticTerminator"]haha UNC totally pwns OSU

I know this for a fact

since my roommate is from OSU[/quote]
huh
transfer from osu?
huh
dont froshies room with froshies

USC FTW
The message is too small. Please make the message longer before submitting.

well I'm from UNC

anyway is this USC as in trojans or as in gamecocks


geometry
similar triangles
calculus
calculus computations

hey could someone please help me with this question?

A light is at the top of a pole 20 m high. From a point on the ground 8m from the base of the pole a ball is thrown upwards with an inital velocity of 13m/s. At what rate is the shadow of the ball moving aloing the grouind 1 s later.

[hide="solution"]
Let x = distance the tip of the shadow is from the light pole
Let p = height of ball from ground
By similar triangles, we know: $\frac{20-p}{8} = \frac{20}{x} \rightarrow x = \frac{160}{20-p}$
The question asks to find $\frac{dx}{dt} = \frac{160}{(20-p)^2} \frac{dp}{dt}$
Since the ball was thrown up at an initial velocity (13m/s) and falls at g (in m/s/s) we know:
$p = 13t - \frac{g}{2}t^2$, the units of p are meters.
Therefore $\frac{dp}{dt} = 13 - gt \rightarrow @t=1s \frac{dp}{dt} = 13-g$ and $p @t=1 = 13-\frac{g}{2}$
Thus, $\frac{dx}{dt} = \frac{160}{7+\frac{g}{2}} (13-g) = \frac{320(13-g)}{14+g}$
[/hide]
I hope I didn't make a mistake.


Let 1= d1 < d2 < ... dk = n be the divisors of a positive integer n.
Define D = d1d2 + d2d3 + ... + dk-1dk.
(a) Prove that D < n.
(b) Characterize all n such that D divides n.

Isn't this from IMO? Forgot the year (2001 0r 2002)

It is (2002).
Guys, try to solve this yourself if you don't know the problem.


Let $f: \mathbb{R}^{+}\rightarrow \mathbb{R}+$ be an increasing function. For each $u\in\mathbb{R}^{+}$, we denote $g(u)=\inf\{ f(t)+u/t \mid t>0\}$. Prove that:

$(a)$ If $x\leq g(xy)$, then $x\leq 2f(2y)$;

$(b)$ If $x\leq f(y)$, then $x\leq 2g(xy)$.

$(a)$ $x\leq g(xy)\implies x\leq f(t)+\frac{xy}{t}$, for every $t>0$. Letting $t=2y$, we recover that $x/2 \leq f(2y)$, hence the claim.
$(b)$ For this part, we want to show that, $x/2 \leq g(xy)$, or equivalently, $\inf_{t>0}\{f(t)+\frac{xy}{t}\}\geq \frac{x}{2}$. Hence, it suffices to show
$$
f(t)+\frac{xy}{t}\geq \frac{x}{2}, \forall t>0.
$$
If $t\leq y$, the term, $\frac{xy}{t}\geq x \geq \frac{x}{2}$, and since $f(\cdot)$ is non-negative, we are done. If $t>y$, then using the fact that $f(\cdot)$ is increasing, $f(t)\geq f(y)\geq x$, hence we get the same domination. $\square$


Let a system of infinetely many metal balls with centers all the points
$(a,b,c)\in Z^3$. We say that this system is $standard$ when the temperature of each ball is equal with the arithmetic mean of the temperature of the six more neighbour
balls. We suppose that each temperature of each ball is between $0$ and $1$ degree. If the system of the balls is $stantard$ prove that all the metal balls have the same temperature.

It's a rewording of http://www.mathlinks.ro/Forum/viewtopic.php?t=5327 .

  darij

Good. But could you Darij write the beter solution inthis topic with details because there are too many posts in the page you gave me and I get confused. Oh my head :?

[quote="silouan"]Good. But could you Darij write the beter solution in this topic with details because there are too many posts in the page you gave me and I get confused.[/quote]

Please, Silouan, try to understand that we cannot do that. It will take you only 5 minutes to find the correct solution and to try to understand it. And we, moderators, other ML members etc, we just don't have the time to rewrite solutions which have been written on some other place already, do you see? It's the same as asking someone to provide a picture with his solution for a geometry problem - you should draw the picture yourself. Actually, you will learn much more from drawing a diagram yourself than from being lazy and watching diagrams made by others.

Well, could you write me the post in which the solution is correct?For example,write post #1 or #2...

Post #38 gives a solution to your problem.  But I recommend that you read the entire thread, to get the full context.  I think you will learn something.

[quote="enescu"]I hope you will not consider this as spam: I strongly believe that some of us should find the correct balance between keyboard and pencil and paper.[/quote]

What do you mean?

I mean that some posts like " could you please explain", "please draw a picture so I can understand", "I don't follow that step", etc. can be avoided if one takes a piece of paper and a pencil an do some math. I believe that some MLinkers only use the keyboard of their computers, otherwise I cannot understand why they are posting such questions. I can provide enough examples, but maybe this can continue in a separate dedicated thread.
Anyways, I don't mean to offence anybody, it's just an observation. I'll retain myself in the future in making non-mathematical comments.

No, it's fine, I am sure this will make things clear for some people. :)
I second your opinion.

Thanks to Ravi B. I know that mr.Enescu told for me the things who told but it doesn't matter.


inequalities
geometry
circumcircle
inequalities proposed

Prove that in all triangle $ABC$ with area denoted by $S$ we always have
$3abc\ge 4\sqrt{a^{2}+b^{2}+c^{2}}.S$

$R=abc/4S$ so it becomes to prove
\[9R^{2}-a^{2}-c^{2}-b^{2}\ge0\]
\[\iff OH^{2}\ge0\]
where $H-orthocenter \ and \ O-circumcenter$

Yes, It's really easy! You can also prove it by using
$sin^{2}A+sin^{2}B+sin^{2}C \le \frac{9}{4}$

[quote="The soul of rock"]Not sure that it is mine[/quote]
That's a well-known inequality, The soul of rock  :wink:


function
calculus
integration
calculus computations

we can generalize the problem and have this interesting relation

${j\in \mathbb{Z}\land j\geq 0}$
${K\in \mathbb{Q}\land K>0}$
${\left(\sum_{n=0}^{\infty }\frac{(-1)^{n}}{2 n+1}\right)^{2 j+1}=K \sum_{n=0}^{\infty }\frac{(-1)^{n}}{(2 n+1)^{2 j+1}}}$

but what you define as manipulation!? and so, give a hint

oh ! sorry i forgot 'bout this thread completely....   :maybe:

what i meant to say was using basic algebraic identities and manipulation of series only
(such as breaking down of each term into either a "sum of products" or a "product of sums",
and then doing some clever rearrangement of a "selected" number of those broken
down terms), it is possible to show (for the beta function with [b]odd [/b]powers only):

${\boxed{\beta{(2p+1)}}\;=\;\sum_{k=0}^{\infty}\frac{(-1)^{k}}{(2k+1)^{2p+1}}}\;=\;\lambda\left( \;\sum_{k=0}^{\infty}\frac{(-1)^{k}}{2k+1}\;\right)^{2p+1}$

$[ \;\;\;where\;\;\;p>1,\;\;\;p\in\mathbf{N}^{+}\;\;\;\;\;\;and\;\;\;\quad \lambda >1,\;\;\;\lambda\in\mathbf{R}^{+}\;\;\;]$

(which is essentially what yagaron stated above)

this is [u]not [/u]an algebra problem par se, it can be done rather elegantly using
integral calculus and series rearrangements (knopp's textbook shows some techniques)

[quote="misan"](knopp's textbook shows some techniques)[/quote]

Could you give some more precise reference please?


Suppose that $ a;b;c$ be positive integer numbers satisfying $ 0<a^2\plus{}b^2\minus{}abc \leq c$
Prove that $ a^2\plus{}b^2\minus{}abc$ is perfect square

You are right [b] rust[/b]

Also this is problem from PEN Project website.


linear algebra
matrix
geometry
geometric transformation
rotation
superior algebra
superior algebra unsolved

Show that the rule $ \sigma(\theta)\equal{}\begin{bmatrix} \alpha & \alpha^2 \minus{} \alpha \\ 0 & \alpha^2 \end {bmatrix}$, $ \alpha \equal{} e^{i\theta}$, is a representation of $ SO_2$, when a rotation in $ SO_2$ is represented by its angle.

The group $ SO_2$ of rotations of the plane is isomorphic to $ U_1$ that is the unit circle in the complex plane. I can't figure out how $ \sigma(\theta)$ is acquired. Any help will be appreciated.

Can you see how the diagonal matrices $ \begin{bmatrix}\alpha&0\\0&\alpha^2\end{bmatrix}$ work? Take that, and conjugate by $ \begin{bmatrix}1&1\\0&1\end{bmatrix}$.

Alternately, just show that $ \sigma(\theta)\sigma(\phi)\equal{}\sigma(\theta\plus{}\phi)$.

[quote="jmerry"]Can you see how the diagonal matrices $ \begin{bmatrix}\alpha & 0 \\
0 & \alpha^2\end{bmatrix}$ work? Take that, and conjugate by $ \begin{bmatrix}1 & 1 \\
0 & 1\end{bmatrix}$.

Alternately, just show that $ \sigma(\theta)\sigma(\phi) \equal{} \sigma(\theta \plus{} \phi)$.[/quote]

I just started a representation theory, so I can't follow some of your explanation.
Why we need a conjugation to get a representation of SO_2? Is there any geometric meaning?

Thanks.

Well, I haven't seriously done representation theory at all. The only thing you need to know for my explanation is that a representation is a homomorphism to $ GL_n$. If you're given a explicit form, the only thing you need to check is that multiplication works.

What is that conjugation? It's just a change of basis. In the original basis, this representation has that off-diagonal stuff. In the new basis, after a shear, it's diagonal, and obviously a direct sum of two one-dimensional representations.


geometry
3D geometry
algebra
polynomial
calculus

Get the cube root expression on one side and the other terms on the other.  Then multiply out.  It will be ugly but it will work.

Ok! Reality, I have a solution of this equation. But I want get other way from you.

---------------------------------------------------------------
My school site: http://www.chuyenquangtrung.com.vn

[quote="thanhnam2902"]Ok! Reality, I have a solution of this equation. But I want get other way from you.[/quote]

er how's he gonna know if his solution is different from yours unless you post yours? He kinda already posted his solution.. just didn't do it :P

meh I was too lazy to actually expand/solve that, but after plug-and-chugging through my TI-89 (I know, I was bored. you can shun me now XD) the root is actually an integer :ninja:

Do you know of a less bruteforce way (not expanding as much) to get the root?

this problem has been solved with a nice method in another thread.

[url]http://www.artofproblemsolving.com/Forum/viewtopic.php?t=200729[/url]

$ \bullet$ Let $ t\equal{}\sqrt [3]{4x\minus{}4} \Longrightarrow x\equal{}\frac{t^3\plus{}4}{4}$.

$ \bullet$ So we have the equation: $ t^6\minus{}14t^3\minus{}24t\plus{}96\equal{}0$

$ \Longleftrightarrow (t\minus{}2)^2(t^4\plus{}4t^3\plus{}12t^2\plus{}18t\plus{}24)\equal{}0$ $ \Longleftrightarrow$ $ t\equal{}2$ or $ t^4\plus{}4t^3\plus{}12t^2\plus{}18t\plus{}24\equal{}0$

$ \bullet$ $ t\equal{}2 \Longrightarrow x\equal{}3$

$ \bullet$ $ t^4\plus{}4t^3\plus{}12t^2\plus{}18t\plus{}24\equal{}0$ $ \Longleftrightarrow (x^2\plus{}2x)^2\plus{}2(x\plus{}\frac{9}{4})^2\plus{}\frac{111}{8}\equal{}0$, this equation have no root.

End the equation have root is $ x \equal{} 3$.

Assuming that you didn't use derivatives...:

$ 2x^2\minus{}11x\plus{}21\minus{}3\sqrt[3]{4x\minus{}4}\equal{}0$

$ 2x^2\minus{}11x\plus{}21\equal{}3\sqrt[3]{4x\minus{}4}$

$ 8x^6\minus{}132x^5\plus{}974x^4\minus{}4081x^3\plus{}10269x^2\minus{}14553x\plus{}9261\equal{}27(4x\minus{}4)$ *whew!*

$ 8x^6\minus{}132x^5\plus{}974x^4\minus{}4081x^3\plus{}10269x^2\minus{}14553x\plus{}9261\equal{}108x\minus{}108$

$ 8x^6\minus{}132x^5\plus{}974x^4\minus{}4081x^3\plus{}10269x^2\minus{}14445x\plus{}9369\equal{}0$

That's as far as I'm going...Assuming I'm correct, anyone care to factor?  :lol:  :D

[quote="fishythefish"]$ 8x^6 \minus{} 132x^5 \plus{} \textcolor{red}{974}x^4 \minus{} \textcolor{red}{4081}x^3 \plus{} 10269x^2 \minus{} 14553x \plus{} 9261 \equal{} 27(4x \minus{} 4)$ *whew!*[/quote]

Those should be $ 978$ and $ \minus{}4103$, respectively.  In any case, if you really want to know, the final polynomial factors as $ (x \minus{} 3)^2 \left( 8x^4 \minus{} 84x^3 \plus{} 402x^2 \minus{} 935x \plus{} 1041 \right)$.  Now have fun trying to write the last factor as a sum of squares if you insist on avoiding calculus :)

Yes, easy we see the equation: $ 8x^4 \minus{} 84x^3 \plus{} 402x^2 \minus{} 935x \plus{} 1041\equal{}0$, have no root.


algorithm
combinatorics unsolved
combinatorics

Let $ a_1,a_2,\dots ,a_n$ and $ b_1,b_2,\dots ,b_n$ be two distinct collections of $ n$ positive integers where each collection may contain repetitions.If the two collections of integers $ a_i \plus{} a_j(1\leq i\leq j \leq n)$ and  $ b_i \plus{} b_j(1\leq i\leq j \leq n)$ are the same then show that $ n$ is a power of two.
P.S:I'm sure that this is more algebra problem than a combinatoric.(Maybe i must post it in Algebra section :maybe: )

There aren't any examples. We can uniquely reconstruct the original list (up to order) from the list of sums.
An example of the algorithm:
Let the sums be $ 2,3,3,4,4,4,4,5,5,6,6,6,7,7,7,7,8,8,10,10,10$.
$ a_1\equal{}\frac12(2)\equal{}1$.
Sums accounted for so far: $ 2$.
The smallest remaining sum is $ 3$, so $ a_2\equal{}3\minus{}1\equal{}2$.
Sums so far: $ 2,3,4$.
The smallest remaining sum is $ 3$, so $ a_3\equal{}3\minus{}1\equal{}2$.
Sums so far: $ 2,3,3,4,4,4$
The smallest remaining sum is $ 4$, so $ a_4\equal{}4\minus{}1\equal{}3$.
Sums so far: $ 2,3,3,4,4,4,4,5,5,6$
The smallest remaining sum is $ 6$, so $ a_5\equal{}6\minus{}1\equal{}5$.
Sums so far: $ 2,3,3,4,4,4,4,5,5,6,6,7,7,8,10$
The smallest remaining sum is $ 6$, so $ a_6\equal{}6\minus{}1\equal{}5$.
Sums so far: $ 2,3,3,4,4,4,4,5,5,6,6,6,7,7,7,7,8,8,10,10,10$. That's all. The original list was $ 1,2,2,3,5,5$.

Powers of 2 are irrelevant.

Could you explain it in details?
If you have got a counter example please write it.Thank you.

What I'm saying is that there's no exception for powers of 2- this is impossible for all $ n$.

The explanation is there in the example- at each stage, we pick the number that will give the smallest sum not yet accounted for.

It should be the set of sums, not the multiset, and we should have $ i < j$, not $ i \leq j$.  So, for example, every pair of sets with one element and every pair of sets of two elements with the same average are examples.  It's an exercize in Stanley's EC 1 or 2, but I don't know the original source.

Suppose, for example, that the sets are $ \{1, 1, 1, 2, 2\}$ and $ \{1, 1, 2, 2, 2\}$.  As long as each set has the same set of distinct members, and has at least two of each member, the sets of sums will be the same.

If you have $ i<j$, then the same thing applies.

Unless it IS multisets of sums...

I think it is multisets. Otherwise, something like $ (0,1,2,3,5,6,7)$ and $ (0,1,2,4,5,6,7)$ would work.

An example for $ n\equal{}4$: $ (\minus{}2,\minus{}1,0,3)$ and $ (\minus{}3,0,1,2)$.

Sorry, you win -- multisets of sums, but $ i < j$.

Look here, post #6.
http://www.mathlinks.ro/Forum/viewtopic.php?t=150844
The solution from there applies even if some numbers among $ a_1,\ldots,a_n$ or $ b_1,b_2,\ldots,b_n$ are repeated.


How to prove that
$h_a \le m_a$
in any triangle?

What is the shortest distance from a point to a given line? :)

(Or: in any right-angled triangle, the hypotenuse is the longest side.)

:huh:

We know that the perpendicular distance is the shortest.

Let $AD=h_a$.

Then, for any point $P$ on the side $BC$ we have $AP\geq AD$

The equality holds only when $P$ is the same point as $D$


find all functions wich satisfy for all reals $f(x+y+f(xy))=xy+f(x+y)$.
i need just finding that $f$ is injective.

Put $y=-x$ to get $f(f(-x^{2}))=-x^{2}+f(0)$.
This means that for negative $z$, $f(f(z))=z+f(0)$.
Now the injectivity argument is obvious and thus we get that for negative $x$, $f(x)$ is injective.
Now take $x$ negative, very very small, such that $x+f(0)<0$, and $y=0$.
From the original equation we get $f(x+f(0))=f(x)$, and because $f$ is injective on negatives, we get
$x+f(0)=x$, and thus $f(0)=0$.
But we have allready established that $f(f(z))=z+f(0)$, for negative $z$, thus $f(f(z))=z$, for all negative $z$.
Now take $y=-1$ and positive $x$  and plug them in the original equation to get $f(x-1+f(-x))=-x+f(x-1)$.
This means that $f(x-1)=x-1$, for all $x\geq 0$, and thus $f(a)=a$, for all $a\geq-1$. This means that $f(x)=x$, for all positive $x$, and thus $f(x)=x$ for all real $x$.

[quote]Now the injectivity argument is obvious and thus we get that for negative[/quote]
i do not understund this .can u say why.

Ok, so for negative $z$, $f(f(z))=z+f(0)$.
Assume that we have $a,b$ negative, such that $f(a)=f(b)$.
This means that \[ f(f(a))=f(f(b))\Longleftrightarrow a+f(0)=b+f(0)\Longrightarrow a=b,\] therefore $f$ is injective on negatives.

[quote="andyciup"]
Now take $y=-1$ and positive $x$  and plug them in the original equation to get $f(x-1+f(-x))=-x+f(x-1)$.
This means that $f(x-1)=x-1$, for all $x\geq 0$[/quote]
this is what i don't get in your proof... :huh:

Well, because the $x$ i have chosen there is positive, this means $-x$ is negative, and thus
$f(-x)=-x.$
 This means that $f(x-1+f(-x))=f(x-1-x)=f(-1)=-1$.
But $ f(x-1+f(-x))=f(x-1)-x$, thus $f(x-1)-x=-1$, and thus $f(x-1)=x-1$, for all positive $x$.

thanks a lot andyciup for helping and explaning  :)

[quote="andyciup"]Well, because the $x$ i have chosen there is positive, this means $-x$ is negative, and thus
$f(-x)=-x.$
 This means that $f(x-1+f(-x))=f(x-1-x)=f(-1)=-1$.
But $f(x-1+f(-x))=f(x-1)-x$, thus $f(x-1)-x=-1$, and thus $f(x-1)=x-1$, for all positive $x$.[/quote]

Why do you have that $f(-x)=-x$ for positives?

Because $f(x)=x$ for negatives. I proved that in the second post.

i kinda thought you proved that $f(f(x))=x$ for negatives, not $f(x)=x$...
anyway,here is the solution.
$f(x)=x$ for all $x$ or $f(x)=-x$ for all $x$.
i will use your valid conclusions that $f(0)=0$ and $f(f(x))=x$ for negative $x$.
assume that $f(t)=0$ and set $x=t,y=1$ and you get $t=0$.
lets look at the equation. if we take both $x,y$ positive and set $xy=a^{2}$ then we know that $x+y=2a+b$ where $b$ is an arbitrary nonegative number$(AM-GM)$. if we set $x,y$ both negative with $xy=a^{2}$ then $x+y=-2a-b$ where $b$ is an arbitrary nonegative number. if we choose $x\geq 0,y\leq 0$ and $xy=-a^{2}$ we have $x+y=x-\frac{a^{2}}{x}$. since the equation $x-\frac{a^{2}}{x}=r$ always has a positive solution for any real $r$, $x+y$ can take any real value. thus we have our initial equation transformed into a couple of easier ones(atleast to me).
$f(2a+b+f(a^{2}))=a^{2}+f(2a+b)$ $a\geq 0,b\geq 0$ $(1)$
$f(-2a-b+f(a^{2}))=a^{2}+f(-2a-b)$ $a\geq 0,b\geq 0$ $(2)$
$f(b+f(-a^{2}))=-a^{2}+f(b)$ for all $a,b$ $(3)$
set $b=-f(-a^{2})$ to get that $f(-f(-a^{2}))=a^{2}$ so $f$ is surjective.
assume now there exist positive $x,y$ such that $f(x^{2})=-f(y^{2})$. plug $a=x$ and $a=y$ in $(1)$.you get that
$f(2x+b+f(x^{2}))-f(2x+b)=x^{2}$ for any $b>0$
$f(2y+c)-f(2y+c-f(x^{2}))=-y^{2}$ for any $c>0$
since there exist positive $b,c$ such that $2x+b=2y+c-f(x^{2})$ just choose those $b,c$ to get that $x^{2}=-y^{2}$ contradiction.
assume there exist $x,y$ such that $f(-x^{2})=-f(-y^{2})$. plug $a=x$ and $a=y$ in $(3)$ to get
$f(b+f(-x^{2}))-f(b)=-x^{2}$ for any $b$.
$f(c)-f(c-f(-x^{2}))=y^{2}$ for any $c$.
set $c=b+f(-x^{2})$ to get $-x^{2}=y^{2}$ contradiction.
since $f$ is a surjection we know that for every positive $x$ there exists real $y$ such that $f(x^{2})=-f(y)$ and from the past conclusions we have $y=-z^{2}$ for real $z$, $z\not= 0$
now assume that $x>0$ and $f(x^{2})=-f(-z^{2})$. plug $a=x$ in $(1)$ and $a=z$ in $(3)$ to get
$f(2x+b+f(x^{2}))-f(2x+b)=x^{2}$
$f(c)-(f(c-f(x^{2}))=z^{2}$
set $c=2x+b+f(x^{2})$ to get $x^{2}=z^{2}$ or $f(-x^{2})=-f(x^{2})$ and from this we get $f(f(x))=x$ for all $x$ and now $f$ is bijective. since we know that $xy>0$ iff $f(x)f(y)>0$ lets assume that $f(x)>0$ for all $x>0$. then $f(x)<0$ for all $x<0$. put $b=a^{2}$ in $(3)$
you get $f(a^{2}-f(a^{2}))=f(a^{2})-a^{2}$ and now if $f(a^{2})-a^{2}$ is strictly positive or strictly negative you derive easy contradictions in both cases so $f(a^{2})=a^{2}$ and $f(x)=x$ for all $x$.
assume now that $f(x)<0$ for all $x>0$. then $f(x)>0$ for all $x<0$. then put $b=-a^{2}$ in $(3)$ and if  $f(a^{2})+a^{2}\not= 0$ obtain contradictions in the same manner.
so in this case $f(x)=-x$
this is an ill solution...


Here's a cool question i did 1 year back.I didnt get this then.its cool,i know the solution

Person x and y have the following conversation:
x: I forgot how old your three kids are.
y: The product of their ages is 36.
x: I still don't know their ages.
y: The sum of their ages is the same as your house number.
x: I still don't know their ages.
y: The oldest one has red hair.
x: Now I know their ages!

How old are they?

ps-riddler,please dont post away the solution! ;)  :lol:

Oh, I saw something like this in Paul Zeitz's book, although it was a mere introduction of problem solving. (Not the usual X_X Zeitz level.)

Assuming integer ages:
Possibilities are:
1,1,36
1,2,18
1,3,12
1,4,9
1,6,6
2,3,6

The seemingly useless clue tells us that there is one oldest, and that out of possibly many (at least 2, anyways) possible sums of the kids' ages, there must be at least two combinations to get the same sum.
So let's take a look at the sums:
1,1,36 - 38
1,2,18 - 21
1,3,12 - 16
1,4,9 - 14
1,6,6 - 13
2,3,6 - 12
2,2,9 - 13
3,3,4 - 10

Since 13 is the only sum that can be obtained in ways, the ages must be 2,2,9.

YOUR ANSWER IS WRONG (i think)
RAED THE QUEST CAREFULLY.

[hide] Product = $36$ would gives us some pairs of number to guess . Just see the possibility that towersfreak2006 list out :P . After knowing that the sum of pairs is the same as his house number door (which means he knows the sum) , he still cant guess it . This is because the pairs of number which sum up to that particular number must have more than one pair . But then by knowing the oldest one has red hair , we could guess that the other two have no hair (so i would say that the other two are still baby say age 1 or 2 because 3 years old probably already has hair.) So , just make use of towersfreak2006's list you will see that only (2,2,9) satisfy it !  :P [/hide]

I agree with shyong and towersfreak2006, I first thought the last two statements by y were useless  :blush: , but they prove to be useful.

[quote="towersfreak2006"]Since 13 is the only sum that can be obtained in ways, the ages must be 2,2,9.[/quote]
[quote="shyong"]So , just make use of towersfreak2006's list you will see that only (2,2,9) satisfy it ! [/quote]
Shadysaysurspammed, you are absolutely WRONG! I thought posting the problem would make you know the answer.
Shyong and Towersfreak2006 you are both right! :10:

[quote="236factorial"]well, she did say "I think", however she also say she knew the solution  :roll:

bad grammar, I know[/quote]
 :rotfl:  it is a "he" (I know him) :rotfl:  doesnt matter he hasnt specified his gender

[quote="riddler"][quote="236factorial"]well, she did say "I think", however she also say she knew the solution  :roll:

bad grammar, I know[/quote]
 :rotfl:  :rotfl:  :rotfl:  :rotfl:  :rotfl:  :rotfl:  :rotfl:  it is a "he" (I know him) :rotfl:  :rotfl:[/quote]

Shady sounds like a girl name, no wait that's Sandy  :blush:  :rotfl:  :rotfl:

Sorry i said the ans is wrong.its right.i said its  wrong cause the guy said that the remainin things said by y were useless...so i figured he was guessin.

and the person who called me "SHE"!!!!!!!SHADY  REFERS TO EMINEM.SO RESPECT IT.

there was this question posted on this site,i dont know where,it said-find possible solutions if the area and the perimeter of  a triangle are the same.i couldnt find it now.so with all due respect to  :) the person who posted it,could someone please tell me the solution or where it is?

Well, I had to solve this problem when I was 11 in a contest (for my admission in gymnasium  :blush: ). the official answer was 1 6 6 the reasoning being that "The oldest one has red hair (blue eyes_ in contest)  :rotfl: ) " means that there is more than one "oldest", kind of strange no???  :huh:  :?:  oh well... doesn't really matter. BTW no contestant gave the corect answer  :blush: but almost all of us obtained partial marks. the problem is fun but kind of silly.  :blush:  :rotfl: .

[quote="Arne"]The 3 - 4 - 5 triangle and the 5 - 12 - 13 triangle satisfy these conditions.

Use Heron or something.[/quote]

3 - 4 - 5 does not satisfy the conditions:

$6 \neq 12$

do we need integral values? anyway I got a solution,
sides are $4\sqrt{3},4\sqrt{3},2\sqrt{3}$

How did  u  get that riddler?HERONS?i do not know  herons thing.any  simpler way? :(

NILESH, Herons is the same as Hero's formula.

This problem is stolen direct out of ACOPS...
didn't even change the numbers

Those people are right. If you have twins that are older than one child than you don't have an [b]OLDEST[/b] child that elimanates 1,6,6. Therefor it must be the combination 2,2,9 which has an [b]OLDEST[/b] child.

ACOPS=Art and Craft of Problem Solving

It's a well known problem.  I'm pretty sure Zeitz wasn't the original poser of the problem and thus ACOPS wasn't the first place the problem appeared.


[quote="indybar"]For which real numbers $a,b,c$ does
$a^3+b^3+c^3 \geq a^2b+b^2c+c^2a$?[/quote]
$a,b,c \geq 0$?

[quote="shobber"]
$a,b,c \geq 0$?[/quote]

Why?  ;)

a^3+b^3 +b^3>= cubic root(a^3b^3b^3)=ab^2
for a, b >=0

This is the AM-GM inequality

similarly for a,c and b,c and add.

Hope this helps!

Very nice,Socrates. My solution is very simple.Just use $a^3+b^3>=ab(a+b)$

BTW socrates learn $\LaTeX$! (e.g. [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?t=5261]here[/url])

well this is a simple proof with the condition $a,b,c\ge 0$, because only the u can apply AM-GM:

$a^3+b^3+c^3=\frac{a^3+a^3+b^3}3+\frac{b^3+b^3+c^3}3+\frac{c^3+c^3+a^3}3\ge \sqrt[3]{a^3a^3b^3}+\sqrt[3]{b^3b^3c^3}+\sqrt[3]{c^3c^3a^3}= a^2b+b^2c+c^2a\quad_\blacksquare$

this is a not so difficult problem, but notice the method it can be applied on more difficult problems.
have an example:
let $a,b,c\in\mathbb R^+$ and $abc=1$.
prove: $\frac ab+\frac bc+ \frac ca \ge a+b+c$
have fun with this :)

this is from a recent german math contest i think
And is solved by the same way......

Hey,Peeta your problem is very nice. Well it can be proved that if $a,b,c>0$ and$abc<=1$ then we have
 $a/b+b/c+c/a>=a+b+c$.Here is my solution: $a/b+b/c+c/a=a^2c+b^2a+c^2b/abc>=a+b+c $if $ab+bc+ca<=a+b+c$. Otherwise the same inequality gives $a/b+b/c+c/a>=a+b+c$ where we used $abc<=1$.

can u explain that a little more in detail, plz?

[hide="hint"]use a similar method as i (and socrates) did above :) [/hide]

[quote="indybar"]For which real numbers $a,b,c$ does
$a^3+b^3+c^3 \geq a^2b+b^2c+c^2a$?[/quote]
it looks like the problem i posted in the inequality marayhon.


are you allowed to use calculators in amc 10 or 12, and did they change the rules about it recently?

anyone know the score you need to get into aime?
is it always 120 or can it be higher or lower?

im not sure if you were ever allowed to use calculators on the Amc 10/12...you were only allowed on the amc 8....if you were, now its no calculators for any of the tests...

well...its usually around 120 for the amc 10 and 100 for the amc 12....it can be higher or lower, i think, depending on how others scored...hope that helps

[quote="davidyko"]The qualification score is at maximum 120/100, but it can be lowered, depending on the lowest score of the top 1%/5%. (AMC10/12)
You were allowed calculators on the AMC tests until this year, however, from next year on, it's no calculators all the way to IMO!  :wink:[/quote]

Ithink the 1% and 5% will be used more often next year without caculators.

So dont shoot for a goal like of 100. For example, you added up all your points and you have a 97.5, dont guess on like 3 questions hoping you get them right to get 100 and passAMC 12.  Because you never know, if you guess all 3 wrong, your score will go down to 93,and maybethe cutline will be using 5% and be at 94.5 and if you didnt guess tryin to get 100 (which you thought wasa passing) you wouldvne actually passed.

but how do they score the tests?
I though they give you points if you leave it blank, do they subtract if you get it wrong?

6 points for every question right
1.5 points for every question skipped
0 points for every question wrong

Pity it's changed from 2.5 to 1.5. I liked the old scoring system.

They began with the new system last year.

[quote="xxazurewrathxx"][quote="ordinary boy"]

Ithink the 1% and 5% will be used more often next year without caculators.

So dont shoot for a goal like of 100. For example, you added up all your points and you have a 97.5, dont guess on like 3 questions hoping you get them right to get 100 and passAMC 12.  Because you never know, if you guess all 3 wrong, your score will go down to 93,and maybethe cutline will be using 5% and be at 94.5 and if you didnt guess tryin to get 100 (which you thought wasa passing) you wouldvne actually passed.[/quote]

Yeah the calculator rule is fairly new, but calculators never did help me too much on the AMC, especially since I can't program them to save my life. You know, the obvious solution here is to get a 150, problem solved!  :)[/quote]

Thank you! :)  simple and to the point! and yes, that's what I'm shooting for!

yes, i know..
i'm sorry..., but we were taking it for practice, not for real in class...

This year the AMC scoring was different.

[quote="mihail911"][quote="kimmystar94"]i thought u were allowed to use any calculator allowed on the SAT
which is:

no QWERTY keyboard

and that's about it...  :lol:

or theres something i don't know..

OH MY GOD!!
are you serious??
we can't use our life-saving calculators???
because on the AMC 10B 2006, there was a leap year problem and I just couldn't find a good way, so i went to my trusty TI-89 and looked up the date and the day of week!! (yes, I know that's cheating..)[/quote]

 :o  OMG. that's cheatng so badly!!![/quote]
I'm pretty sure that's allowed...

it might be allowed, but it won't help your mathematical ability at all. It's like a certain guy I know who is REALLY GOOD but for some reason likes to always use his calculator for computation. He can't compute stuff very fast, which will be a detriment in the AMC, and less so the AIME and USAMO.

In short, don't use your calculator unless you are multiplying 6, 7, 8 digit numbers. And DON'T LOOK STUFF UP IN IT. what?? You are testing your math skills, not your calculator skills.

Sorry for the rant... :ninja: but I had to say it.

i completely agree...
im not good enough on my TI-89 anyways.. :P

[quote="kimmystar94"]OH MY GOD!!
are you serious??
we can't use our life-saving calculators???
because on the AMC 10B 2006, there was a leap year problem and I just couldn't find a good way, so i went to my trusty TI-89 and looked up the date and the day of week!! (yes, I know that's cheating..)[/quote]

Holy crap actually that's pretty awesome. (yeah don't listen to them)

They're taking off calculators so you can't calculator bash things to death and you have to find the elegant solution. If anything, it'll help people do better on the AIME.

thanks...
but i was running out of time during class...
even my teacher agreed.. he was like, "sure, I don't care"
but now they're banning calcs on the AMC....
thats crap..
I don't care much about the AMC 8, but the AMC 10 I need amazing help with..
my goal this year is AIME, but I don't know if I can do that..
pooey..

[quote="mihail911"][quote="ordinary boy"]well the amc has no real significance compared to the AIME (for colleges) and there has never ever been caculator usage on the AIME for that reason.
so i really dont get why they banned caculators on the amc considering the real math competiton is the AIME and there has never been caculators on there(not that I care about caculators on the AMC but i just dont find it that significant)..because [u][b]if you were one of those people that relied on caculators on the amc, its not like you will  pass AIME[/b][/u][/quote]

im not saying i do, but that was flat out C-O-L-D.... :huuh: but probably true..[/quote]

alright sorry if that was offensive..but comon.

say you have a problem $ x^{2}+\frac{1}{x^{2}}=4$ and it asks to find $ x^{4}+\frac{1}{x^{4}}$, a caculator way would be to graph that and find the values.  Then plug that into the other equation.  But on the AIME (those problems are not that easy) but you will have no way of doing the problem.

That was an example..if you really want a reason why maybe this problem..

http://www.artofproblemsolving.com/Forum/viewtopic.php?p=382596#p382596

will tell..it was a number 24 on amc 12. with a caculator it would take me like 30 seconds because i can find like sin 75 (as a deicmla expression instead having to write it as sum of square roots, making computation harder)

[quote="ordinary boy"]well the amc has no real significance compared to the AIME (for colleges) and there has never ever been caculator usage on the AIME for that reason.
so i really dont get why they banned caculators on the amc considering the real math competiton is the AIME and there has never been caculators on there(not that I care about caculators on the AMC but i just dont find it that significant)..because if you were one of those people that relied on caculators on the amc, its not like you will  pass AIME[/quote]
Uh... Do you really think the reason there's never been calculators on AIME is because colleges care about AIME?
Also, I'm quite sure that plenty of people who rely on calcs for AMC pass AIME, because AMC is a lot more about speed, and some people can do hard problems but struggle doing problems fast.

[quote="Klebian"]
Uh... Do you really think the reason there's never been calculators on AIME is because colleges care about AIME?
Also, I'm quite sure that plenty of people who rely on calcs for AMC pass AIME, because AMC is a lot more about speed, and some people can do hard problems but struggle doing problems fast.[/quote]

No when did I say that.  I said colleges care about AIME more than AMC.  Then I said theres never been caculators on AIME becuase it is more important and tests your math skills than compared to the amc.  Im not making a direct correlation.

Yes, okay but guess what, if you can pass AIME, im pretty sure you can pass AMC.  Those people who rely on caculators on AMC can also pass amc without caculators.  I wasnt talking about those people.  I was talking about those who only pass amcs without caculators......way to misinterpret everything i said.

Now reading what i wrote, i would interpret myself as you did..my bad..


probability
geometry
geometric transformation
rotation
perimeter
integration
calculus

Let P and Q be points be two points randomly chosen on the sides of a square with side 2. What is the probability that PQ<1?

[hide="Geometric probability"]Let $ P$ be a random point in the square $ ABCD$.
We can assume, WLOG (by rotations and mirrors), that $ P$ is in side $ AB$, nearest to $ A$.
Let's consider $ x$ the distance $ AP$, which will be a random value between $ 0$ and $ 1$ (otherwise $ B$ would be nearest, contradiction).
We'll paint in red the points $ Q$ with $ PQ<1$:
- We'll paint a length of $ 1$ from $ P$ going to $ B$.
- We'll paint all the length from $ P$ to $ A$, that is $ x$, and (in order to complete the distance $ 1$) a length of $ \sqrt{1-x^{2}}$ from $ A$ going to $ D$.
So, we'll have to find the mean value of the total length painted in red ($ 1+x+\sqrt{1-x^{2}}$, with $ 0<x<1$), and divide it by the total perimeter of the square ($ 8$), to compute the desired probability.
That is $ P(PQ<1)=\frac{\frac{\int_{0}^{1}{(1+x+\sqrt{1-x^{2}})dx}}{1-0}}{8}=\frac{1+\frac{1}{2}+\frac{\pi}{4}}{8}=\frac{6+\pi}{32}$ (approx $ 28.56\%$).
(You can compute the integral as the sum of the areas of a rectangle, a triangle and a quarter of a circle)[/hide]


abstract algebra
vector
linear algebra
group theory
superior algebra
superior algebra unsolved

Is it possible to deduce the famous linear algebra formula: \[\dim \ V = \dim \ Ker(\varphi)+\dim \ Im(\varphi)\] with isomorphism theorems. The exercice was proposed in a text where the concept 'monoid' was not even defined. Since the additive group is infinite, I did not found it possible to use $|G: Ker(\varphi)|=|Im(\varphi)|$ to answer the question.

Has someone else an idea (without using the notion 'monoid')?
(I did not learn about modules yet, only the usual stuff untill isomorphism theorem)

[hide="what I tried"]
I tried to construct a monoid $M$ of all subspaces of an n-dimensional vectorspace (up to isomorphisms) over a field $F$ with the operation $+$ on it. Then this is indeed a monoid with neutral element $\mathcal{O}$, the nullspace and $\sum \mathcal{F}_{i}= M$. Then, if I have some homomorphism $\eta$ from $M \to Im(\eta)$ which is surjective, then I indeed have that $M/Ker(\eta) \cong Im(\eta)$ and since $M = \mathcal{O}\oplus \mathcal{F}_{1}\oplus \mathcal{F}_{2}\oplus ... \oplus \mathcal{F}_{n}$, it follows that $| M / Ker(\eta) | = |(\mathcal{O}\oplus \mathcal{F}_{1}\oplus \mathcal{F}_{2}\oplus ... \oplus \mathcal{F}_{n})/Ker(\eta)|=n-\dim \ Ker(\eta)$ $= \dim Im( \eta )$.

Corrections are welcome. This answer feels a bit sloppy :>
[/hide]

[quote="jmerry"]To make sense of dimension, we need the notion of a basis. If we're using a basis, it's all very straightforward.

Here's how I would do it:
The image of $\varphi$ is a vector space, so it has a basis $y_{1},\cdots,y_{m}$. For each $m$, find $x_{m}\in V$ so that $\varphi(x_{m})=y_{m}$. This choice is arbitrary, and cannot be made canonically. This choice gives us a linear map $\theta$ from the image of $\varphi$ to $V$ which is a 1-sided inverse of $\varphi$.

Let $W$ be the subspace of $V$ spanned by the $x_{i}$ (the image of $\theta$). We can show that $V=\text{Ker}(\varphi)\oplus W$, from which the dimension formula follows immediately.[/quote]

mmm, I don't see where you used the (group-theoretical) isomorphism theorem or how you reduced an infinite additive group to something finite 'like a dimension'.

thanks in advance, yannick

this can't be derived from group/monoid isomorphisms ... we have vector spaces, so we need vector space isomorphisms.

use the following facts:

1. $\dim(U \oplus W) = \dim(U)+\dim(W)$

2. every subspace $U$ of $V$ is a direct summand of $V$, say $V = U \oplus W$, and $W \cong V/U$.

3. every linear map $f : V \to W$ induces an isomorphism $V/Ker(f) \cong Im(f)$.

[quote="jmerry"]Dimension doesn't make sense in purely group-theoretic terms. The additive group of $\mathbb{R}$ is isomorphic to the additive group of $\mathbb{R}^{n}$ for any finite $n$. You can't prove any such dimension formula in general with only group theory, because you can't even define the terms of the statement.[/quote]

ok, my mistake. I was relying on [url=http://www.amazon.com/Abstract-Algebra-David-S-Dummit/dp/0471433349]Dummit & Foote,[/url] third edition (page 97, under Corrollary 17)

thanks guys


trigonometry
calculus
integration
function
calculus computations

Prove that $ \tan x$ is increasing on $ \Big]\minus{}\frac\pi2,\frac\pi2\Big[$

Compute the values for $ a$ such that the following integral converges: $ \int_1^\infty\frac x{(x\minus{}1)^a}\,dx.$

With first problem, note that $ (\tan x)' \equal{} 1/\cos^2 x > 0\forall x\in ( \minus{} \frac { \pi}{2},\frac {\pi}{2})$. :D

hi Ilek.
in seccond try to calculate this integral if you cant and is difficult for you then do substitution $ x\minus{}1\equal{}y$ nd integral will be
$ \int_{0}^{\plus{}oo}y^{\minus{}a}dy$
maybe now this integral has more simple face (try to calculate it)
consider two case :
when $ a\equal{}1$
and another when $ a$ is not equal to $ 1$
do hyou know how to integrate like this function?


here are some fun problems...
1) solve:
3^log2(x) -12x^log16(9) = log3((1/3)^3^3)
note loga(b) means log base a of b

2) simplify:
[(1/sqrt(x-1)-sqrt(x+1))/(1/sqrt(x+1)-1/sqrt(x-1))] / sqrt(x+1)/((x-1)sqrt(x+1) - (x+1)sqrt(x-1)) - (1-x^2)

Please $\LaTeX$ your expressions.  They are very ugly in plaintext.  There's an entire section of the site dedicated to it, and it's really not that difficult to learn.

[size=59][quote="DiscreetFourierTransform"]1)
$3^{\log_{2}x}-12x^{\log_{16}9}= log_{3}((\frac{1}{3})^{3})^{3})$
Is this the right expression?
[/quote][/size]
I think it shud be
$3^{\log_{2}x}-12x^{\log_{16}9}= \log_{3}((\frac{1}{3})^{3^{3}})$
[hide]Then right side simpyfies to -27, and for the right side use $a^{\log_{b}c}=c^{\log_{b}a}$[/hide]

-3 is how it should b however i itended delta's to b the correct form

[quote="DiscreetFourierTransform"]1)
$3^{\log_{2}x}-12x^{\log_{16}9}= log_{3}((\frac{1}{3})^{3})^{3})$

Is this the right expression?

I'll assume it is.
The RHS simplifies to $\log_{3}\frac{1}{27}$ which further simplifies to $-3$.

Thus, we have $3^{\log_{2}x}-12x^{\log_{16}9}=-3$
Doh. I'm stuck.[/quote]

That can be a bit more simplified:
$3^{\log_{2}x}-12x^{\log_{4}3}=-3$

Can that $3^{\log_{2}x}$ become $3^{\log_{4}x^{2}}$? If so, we can combine exponents, I think... Not too sure about this log stuff, we haven't gotten to it yet.


inequalities
quadratics
inequalities solved

the lhs is S = xyz(x+y+z).
But :
S  \leq ( (x+y+z)/3 ) 2 (x+y+z)  from AM/GM
= 3( (x+y+z)/3 ) 4
 \leq  3( (x 2  + y 2  + z 2 )/3 ) 2  from the inequality between arithmetic and quadratic means
= 1/3.

Note that equality occurs iff x = y = z = 1/ \sqrt 3.

Pierre.


algebra
polynomial
number theory unsolved
number theory

By fermat's theorm,
$ k^{p-1} \equiv 1 \bmod {p} \ for\ k < p $. therefore, summing all such eqns. and denoting LHS of your eqn by $S$ we've $ S \equiv -1 \bmod{p} $
Also , by Wilson's theorm,
$ (p-1)! \equiv -1 \bmod{p} $.
Thus we have ,
$ S \equiv (p-1)! \bmod  {p} $
therefore, $ (\ (p-1)! -\ S) \ =\ integer\ \times p \\
\\ \Rightarrow (\ p! -\ pS )\ = integer\ \times p^2 $
therefore, $ (\ p^2 + p! -\ pS )\ = integer\ \times p^2 $

Now if your statement is true, multiplying it by p , we get my statement which is clearly true as I have shown. Therefore, your result is established

[quote="Rushil"]
Now if your statement is true, multiplying it by p , we get my statement which is clearly true as I have shown. Therefore, your result is established[/quote]
It's not that easy  ;)

[tex]ap\equiv bp \mod p^2 \not\Rightarrow a\equiv b \mod p^2[/tex]

I know that and I though about it. But isn't it true that if you arrive at something from the question and prove it , then the question is true

Oh yeah , I think I get it now, my statement may not be true in this case

 :?:  :help:  :ewpu:  :fool:  :stretcher:

Am i right till proving
$ pS \equiv p^2 + p!  \ (\ \mod{p^2})\ $

[quote="Rushil"]Do you think you can get the original question from my result[/quote]

No . $ab\equiv bc \mod d$ can only become $a \equiv c \mod d$ if gcd(b,d)=1

Consider the polynomial:$P(x)=\displaystyle \frac{x^{p-1}-1-(x-1)...(x-(p-1))}{p}$
Note that $degP=p-2 \tex{and} P(x)\in \mathbb{Z}(x)$
Note also that $p|1^{k}+...+(p-1)^{k},0\le k\le p-2$,hence $p|P(0)+...+P(p-1) \tex{qed}$


Στα μαθηματα προετημασιας για τον Seemous μας εδωσαν καποιες ασκησεις να λυσουμε, μια απο αυτες ειναι η παρακατω:

Να δειξετε οτι για καθε θετικη ακολουθια $ (a_n)$ ισχυει:

$ \sum_{n \equal{} 1}^{\infty}{\sqrt [n]{a_1a_2...a_n}} < e\sum_{n \equal{} 1}^{\infty}{a_n}$

Εχω δοκιμασει ανισοτητες ΑΜ-ΓΜ, Jensen, Holder, Επαγωγη και εχω προσπαθισει αρχικα να την αποδειξω για πεπερασμενο πληθος ορων με μια απο τις σειρες που συγκλινουν στο e αντι του e στο δεξι μελος και μετα να παρω ορια στο απειρο, αλλα τιποτα δεν δουλευει... βοηθηστε με γιατι μου φαινεται οτι ειναι ευκολη και οτι απλα δεν παει το μυαλο μου και θα τρελαθω σε λιγο...

Η ανισότητα είναι γνωστή ως Carleman's Inequality, και την θεωρώ αρκετά δύσκολη. Νομίζω συνήθως αποδεικνύεται χρησιμοποιώντας την Hardy Inequality.

Βγαίνει όμως και με ΑΜ-ΓΜ. Ας υποθέσουμε πως έχουμε βρει θετικούς αριθμούς
x_11
x_12,x_22
x_13,x_23,x_33
.
.
.

ώστε το άθροισμα κάθε στήλης να είναι το πολύ e, και το γινόμενο της ν-ιοστής σειράς να είναι τουλάχιστον (1/ν)^ν. Τότε χρησιμοποιώντας ΑΜ-ΓΜ σε όλες τις σειρές (τα x_ij θα είναι οι συντελεστές των a_i.) και προσθέτωντας βγαίνει η ανισότητα. Το πρόβλημα είναι να βρεις τέτοια x_ij. Για να είναι όμως ισχυρή η ανισότητα, θα πρέπει όλες οι ΑΜ-ΓΜ να είναι ισότητες. Αν το κοιτάξεις λίγο, θα πρέπει να πάρεις x_22/x_12 = x_23/x_13 = ..., και x_33/x_23 = x_34/x_24 = ... κτλ. Αυτό βοηθάει κάπως για να βρεις τα x_ij αλλά... [size=59]καλές πράξεις.[/size]

Όντως έτσι έχουν τα πράγματα .See here  http://www.mathlinks.ro/viewtopic.php?search_id=239346162&t=5016  and here

http://en.wikipedia.org/wiki/Carleman's_inequality

Thanx παιδια, να υποθεσω οτι αφου ειναι γνωστη ανισοτητα μπορει και να χρησημοποιηθει σε καποιο διαγωνισμο χωρις αποδειξη?


MATHCOUNTS
geometry
trapezoid
geometric transformation
reflection
function
calculus

Hello! This competition is open to everyone entering 8th grade or below. If you feel this competition will be too easy for you, please don't enter. :D (I mean that in the nicest way possible.)

[b] Format: [/b]
There will be 2 rounds of 25 questions each. There is no multiple choice.
It is basically one test split into 2 sections, meaning the difficulty level is strictly increasing. (The easiest problem of the second round is about the same as the hardest problem of the first round.)
The first round will be about Chapter-level MathCounts and the second round will be about State-level (maybe slightly harder) MathCounts.

There may be a Countdown Round for the top 3-5 people. If there is, they will be difficult questions, with no time limit.

[b] Rules: [/b]
No Cheating! (Duh): no asking other people, no searching through past competitions, etc.

[color=red][b] NO CALCULATORS. [/b][/color]  :P

[b] Scoring: [/b]
The first 10 questions are worth 3 points, next 10 are 4 points, etc. for a total of 250 points.

If you provide a correct answer, you will get full credit. If you provide an incorrect answer, you will get 0 points. A solution (albeit incorrect) can be awarded partial credit.

It's up to you whether to include solutions. You may choose to include solutions to only the problems you are unsure about.

[b] Time Frame: [/b]
I will most likely post the First Round on September 12.
The Second Round will begin September 19.
The First Round is due September 26.
The Second Round is due October 10.

You may sign up at anytime and turn in your answers as long as the round has not ended.

[size=134][color=green][b] Please give your thoughts, comments, suggestions. [/b][/color][/size]

[quote="SplashD"]how many are the last 5 questions worth?

whatever, i'll sign up.[/quote]
There are 50 questions. :P

ill be in

how much is "full credit" for a correct answer?

[quote="akalra1"]how much is "full credit" for a correct answer?[/quote]
3,4,5,...,7 points depending on the question.

[b][u]Participants:[/u][/b]
SplashD
ragnarok23
bpms
akalra1

I'd like to get at least 10 people before posting the first round. :D

[quote="nutz_for2.718281828"]hihihihihihihihi

I'minI'minI'minI'minI'minI'minI'minI'min

(Hi, I'm in)[/quote]

god nutz

So it's to our advantage to write a solution to all 25 problems?

Sorry,i cannot participate to the second round  :oops: .
1)too many stuff that i don't understand yet
2)kinda busy  :(

Btw you should start posting the results for the first round.
I got an [hide]$82$, i have done everything i knew about  :no: [/hide]

[quote="funcia"][quote]
You can't use that argument because most the problems from mathcounts nats aren't allowed to be posted in the mathcounts forum since they're too hard. if everything is the level that you expect, everyone would at everything right and there's no fun in that
[/quote]

But I hardly know how to start...at least it will help me learn but I don't even know all those terms...? I guess it'll help in the long run to be exposed to these problems.

Does anyone know of a good definition or tutorial site other than mathwords.com that I can use for problems 17 & 21? B/c I hardly have a clue what they are asking...[/quote]
I don't know any sites but I can try to explain it:
The incircle of the triangle (17) is inscribed in the triangle, and is tangent to all three sides. If you look at the three angle bisectors of the triangle, their intersection point will be the center of the incircle.
The circumcircle is circumscribed about the triangle (each point of the triangle touches the circle.) The center of the circumcircle is the intersection point of the triangle's three perpendicular bisectors.
An isosceles trapezoid is a trapezoid with legs of equal length. Its incircle is tangent to all four of its sides.
Hope this helps!

I think if lotrgreengrapes7926 doesn't reply to you within a day or two PM them but you can start the problems on the first page now.

[quote="easyas3.14159..."]An isosceles trapezoid is a trapezoid with legs of equal length. Its incircle is tangent to all four of its sides.[/quote] I don't think the incircle has to touch all 4 sides. :maybe:

Welcome to AoPS pianist. Just solve the problems on the first post and PM me your answers.

Just a reminder, second(last round) due tomorrow!

OK, since no one has sent me anything in about 2 weeks, I think this competition is dead. :stretcher:
SplashD :first: 224 points
Yeah, that's the only official placing, because I don't have the PMs anymore. :blush:
You can post your score here if you would like, and discuss the problems.

r u doing another competition like this anytime soon?
-jorian

I just found this forum...are we taking a test? :|

jhredsox, probably not. It was too much work and no one really answered the questions. Maybe over the summer when people are bored. :D

hairymonkey, it was a competition, but not running anymore.

A suggestion is that you should have 5 questions with 5 rounds, then its faster to do them. :D


[quote="ark_xm"]If a quadrilateral is inscribed in a circle, is it [b]always[/b] a cyclic quadrilateral?

Thanks  :)[/quote]

The definition certainly says so..

[url]http://en.wikipedia.org/wiki/Cyclic_quadrilateral[/url]

"In geometry, a cyclic quadrilateral is a quadrilateral whose vertices all lie on a single circle." Which means the same as being inscribed in a circle.


function
limit
real analysis
real analysis unsolved

[quote="Svejk"]Let $ f: (0,\infty) \to (0,\infty)$ differentiable two times such that $ f''(x)\plus{}f'(x)\geq f^2(x)$ for all $ x>0$ .
Prove that $ \exists \lim_{x\to\infty} f(x)$ and is finite.Find $ \lim_{x\to\infty }f(x)$[/quote]
http://www.artofproblemsolving.com/Forum/viewtopic.php?f=67&t=284502&p=1537035&hilit=differentiable+function#p1537035


[quote="4everwise"]If $b>1$, $\sin x>0$, $\cos x>0$, and $\log_b \sin x = a$, then $\log_b \cos x$ equals
$\text{(A)} \ 2\log_b(1-b^{a/2}) ~~\text{(B)} \ \sqrt{1-a^2} ~~\text{(C)} \ b^{a^2} ~~\text{(D)} \ \frac 12 \log_b(1-b^{2a}) ~~\text{(E)} \ \text{none of these}$[/quote]
[hide]From the definition of logarithms, $b^a=\sin x$.
Since $\sin x,\cos x>0$, $\cos x = \sqrt{1-\sin^2x}=\sqrt{1-b^{2a}}$.
Take logarithms of the above equation, \[ \log_b\cos x=\log_b\sqrt{1-b^{2a}}, \] \[ \log_b\cos x=\frac{1}{2} \log_b(1-b^{2a}), \] and the correct answer is D.[/hide]

[hide]
Since $\cos x = \sqrt{1 - \sin^2 x}$, we can rewrite as
$\log_b \sqrt{1 - \sin^2x} = \frac12 \log_b (1 - \sin^2 x)$
$\log_b \sin x = a \implies \sin x = b^a$
$\frac12 \log_b (1 - b^{2a}) \implies \boxed D$
[/hide]


Point A is located at (5,5) on the Cartesian Plane.  Point B is also in the plane and has integer coordinates.  If 0 < AB </= 4, at how many points could B be located?

Answer: [hide]48[/hide]

There is a method traditionally used in some Russian villages to see which of the young women in the village are to be married the next year.  Three blades of grass are folded in half and held in a such a away that the six ends of the blades are visible but the rest of the blades are hidden.  A young woman ties the ends together in pairs at random such that there are three knots and each end si tied to exactly one other end.  If, on release, a three-blade loop is formed, the woman will be married the next year.  What is the probability of getting a three-blade loop?  Express your answer a as a common fraction?

Answer: [hide]8/15[/hide]

[quote="mathcrazed"][hide="Hints"]Number 1: Draw the circle of radius 4 with center $ (5,5)$.

Easy to see the answer then.

Number 2: This is merely interpretation.  What's the probability that each end of one blade of grass will be tied to a different one?[/hide][/quote]

mathcrazed -

So for number 1, after I draw the circle of radius 4 with center (5,5), do I just try to find all of the lattice points in the circle's interior or circumference?  (Am I supposed to graph this on graph paper and then count the lattice points?)

For number 2, I don't understand the question.  Could you explain a little more, please?

Thanks so much.

OK. Read: 3 blades of grass. You fold them.  You have two ends for each blade correct? Now, if both ends of the same blade are tied together, then there will be no three-blade loop.  So you want each end tied to a different blade.

[quote="alanchou"]Actually, in mathcounts, graph paper is forbidden

For #1, you find the number of lattice points in both the circumference and the interior[/quote]

How would you find the number of lattice points without graph paper?

All points on a circle satisfy an equation... $ (x\minus{}h)^2\plus{}(y\minus{}k)^2\equal{}r^2$
If the LHS>RHS, then the point is outside of the circle.  If the point satisfies that equation, it lies on the circumference.  If LHS<RHS, it lies within the circle. There's also a way that automatically tells you how to do it, but I forgot.


IMO 1998 Shortlist.
Hint : use Chebyshef's inequality ! ;-)

Solme solutions can be found on http://www.mathlinks.ro

OK but it posted it here so that people who want to become better in proving inequalities can learn new techniques here ... I don't think that it will help to look at the solution without trying to prove it yourself ...
A bit, maybe, but not much !

Yes you're right. Sorry! You all should try and solve(I'm sure you can) and them maybe look at the solutions on mathlinks(if you don't find them first)

Nobody wants to try this ? Otherwise, I'll post the solution myself ...

I think this lemma works (again!): sum (a_i^2/x_i) >= (sum a_i)^2/sum x_i. We amplify the first fraction by x, the second one by y and the third by z and we get sum (x^4/(x+xy+xz+1)) >= 3/4 (this is what we must prove). We use the lemma by considering a_1=x^2, a_2=y^2 and a_3=z^2.

After all the calculations, if we prove the following we're done:
(x^2+y^2+z^2)^2/(x+y+z+2xy+2yz+2zx+3) >= 3/4. We just reverse it and we get the summation of 3 easy-to-prove ineqs.


how did all of u do?
i could just manage 30 odd questions in the given time
too bad performance for me :(

Yeah Me too. 35 odd...... I did maths fully, that took most of my time. I did phy and chem super fast and did whichever ones which I thought I could do..... And in the end just randomnly shaded cause there's no negative marking. :P

But bah, who cares... I don't really give a d.amn to what happens in the NSO...

However the questions were very decent and much higher std to what I expected, especially considering that first round was 9th Std level maths.... This was pretty close to AIEEE level, I must say. :D

I loved the very first question. Easy but still nice.

Let g(x) be a function from [-1,1]... The equilateral triangle with 2 of its vertices as (0,0) and (x,g(x)) has its area as $ \frac {\sqrt{3}}{4}$. Solve for G(x).

everyone my advice is dont listen to nething that anit says, it seems he expected rank more than 5000 in FTSE but he ended up getting 125 or sth Wth :wow:  :P   :rotfl:

[quote="anitsahu"]i dont expect anything better than a 700+ rank :D[/quote]

You can't get that rank my boy. Only the top 500 write NSO.  :rotfl:  :rotfl:

[quote="anitsahu"]i dont expect anything better than a 700+ rank :D[/quote]

Semma muthuva?  :rotfl:  Athukku than ivalo scene poda koodadhu nu sollarardhu  :P   :rotfl:

for your info madness
miracles happen only once :mad:
shreyas
for your info
even school toppers appear in the schools where no one in a class is in top 500 :D

can't say about class 12
but i gave class 10 and am expecting for at least 40 maybe 45
questions were not so tough for 10
if anybody except me from 10 has also given please give your expected marks so i can understand whether i have done well or not

I had time only for 40 odd and the rest I guessed all of them meaning I managed to attempt all the 50.

It was too long the paper and some ruddy idiotic calculations without any help like logs or values,etc. :o

as shreyas said, the standard of the paper was better than the 1st round, but only in a more-rigorous-solving kind of way. i had time only for around 40 too. guessed all the rest as 'C' :D

i did abt 35 questions and the other question i made some logical guesses...

[quote="anitsahu"]hey chemrock and hash_include
u r great   :roll:
how come did u manage to do 40 odd questions in that hour i dont understand
u really need a standing ovation :omighty:[/quote]

i finally got the answer to the question:

chennai : srini :: bubhaneshwar: ???

think the answer is pretty obvious :D :P[/hide]

[quote="anitsahu"]hey hash_include
i m not from bhubaneshwar
i m from rourkela :D  :P[/quote]
hash wasn't talking about u :P  :rotfl:  :rotfl:

[quote="pardesi"][quote="anitsahu"]hey hash_include
i m not from bhubaneshwar
i m from rourkela :D  :P[/quote]
hash wasn't talking about u[/quote]

actually he was...
he was about to say. Chennai: Srini :: Bhub :: Anit

Change it to rourkela now. :D

[quote="Cyber-Shreyas"]
actually he was...
he was about to say. Chennai: Srini :: Bhub :: Anit

Change it to rourkela now. :D[/quote]
chumma jujubi :rotfl:  :rotfl:

[quote="anitsahu"]hey chemrock and hash_include
u r great   :roll:
how come did u manage to do 40 odd questions in that hour i dont understand
u really need a standing ovation :omighty:[/quote]
Actually the examiner fool gave us the paper 5 minutes early and gave the OMR 10 minutes late. :rotfl:
So I finished chem in about 10-12 minutes and then maths in about 30-35 mins. and the rest for physics. :D

sorry abt that fellows :D

but pardesi, why am i not able to edit my post??!  :maybe:

[quote="hash_include"]sorry abt that fellows

but pardesi, why am i not able to edit my post??! [/quote]

Chumma Jujubi  :rotfl:  :rotfl:

[hide]After some days you wont be able to. YOu have to request our honorable moderator.  :o I find that stupid. [/hide]

[quote="Cyber-Shreyas"]After some days you wont be able to. YOu have to request our honorable moderator.  :o I find that stupid. [/quote]
mariyathe... :D

[quote="VARUNARASU"][quote="Cyber-shreyas"]
our honorable moderator
[/quote]
even i find that stupid. :)[/quote]
he never found that part stupid  :huh:  :huh:  :huh: :bruce:

[quote="Cyber-Shreyas"] YOu have to request our honorable moderator. :o I find that stupid.[/quote]

Please stop misquoting and misinterpreting :huh:  :huh: ....
i am not out here doing social service :ninja:   :weightlift:

he found the mod stupid? That's a gr8 discovery winning him the next yrs greatest discoverer prize fer finding the ob  :P   :rotfl:

I meant that, I find the idea of me requesting someone else to edit my own posts idiotic. Sorry for all the confusion. I wonder what the others found stupid.

 :rotfl:  :rotfl:  :rotfl:

i know you did. i was just pulling pardesi's leg :P


The computers in a computer room are in a network such that every computer is connected by a cable to exactly three others. The computers can exchange data directly or indirectly (via other computers). Let $ k$ be the smallest number of computers that need to be removed so that two of the remaining computers can no longer exchange data or there is only one computer left. Let $ l$ be the smallest number of cables that need to be removed so that some two of the remaining computers can no longer exchange data.

Show that $ k\equal{}l$

I $ Highly$ doubt this is correct but :
 let this be a graph and the cables are edges and computers are points. if each computer is connected to three others and if you want two points out of the network then $ k \equal{} l$ because if  $ k < l$ then  1 unwanted  point is still connected to the graph and if $ k > l$ then one of the wanted points is out of the network.

[quote="Poincare"]if  $ k < l$ then  1 unwanted  point is still connected to the graph and if $ k > l$ then one of the wanted points is out of the network.[/quote]

Don't really understand this. Please explain in more detail.