IMO Shortlist
combinatorics
graph theory
invariant

[quote="who"]A house has an even number of lamps distributed among its rooms in such a way that there are at least three lamps in every room. Each lamp shares a switch with exactly one other lamp, not necessarily from the same room. Each change in the switch shared by two lamps changes their states simultaneously. Prove that for every initial state of the lamps there exists a sequence of changes in some of the switches at the end of which each room contains lamps which are on as well as lamps which are off.[/quote]

Let's prove that given an initial configuration with at least one room $ r_{1}$ having all lamps in the same position, we can reduce the number of such rooms by one.

Switch a lamp in $ r_{1}$. If that lamp is connected to another one in $ r_{1}$, we're done (because there are at least three lamps here). Otherwise, we've affected another room $ r_{2}$. If $ r_{2}$ now has lamps in both states, we're finished. Otherwise, we've just turned it into a monochromatic room. Choose a lamp in it, different from the one just switched, and switch it. We keep doing this, each time choosing a lamp different from the ones already switched, until we first reach a room we've been in before: $ r_{m} \equal{} r_{n}$ for some $ m > n$.

Before making the last move, the room $ r_{n}$ had been left with one room on and two off, or vice-versa. Our last move affects one of the two lamps in $ r_{n}$ which share the same state, so $ r_{m} \equal{} r_{n}$ will have lamps of both states, as will all rooms we've been through, including $ r_{1}$. We have thus reduced the number of rooms which have all lamsp in the same position.

Let's call rooms which have all bulbs in the same state [i]boring[/i] and all other rooms [i]interesting[/i]. Two lamps are called [i]friends[/i] if they share the same switch, and two lamps are called [i]neighbors[/i] if they are in the same room (note that two lamps can be both friends and neighbors). A room containing two lamps which are friends is called [i]narcissist[/i] and all other rooms are called [i]generous[/i].

Let there be a total of $n$ rooms in the house. We induct on $n.$ The base case $n=1$ is trivial: note that there must be at least four lamps (since there are an even number of lamps in the house). If one of them is in a different state than the others, we're done. Otherwise, pick two friends and change their states.

Now, suppose our assertion holds true for $j$ rooms. We need to show that if we add another room in the house, we shall still be able to find a sequence of change of states which leads to all the rooms being interesting. Label the rooms $\{R_1, R_2, \cdots , R_j, R_{j+1}\}.$

[b]Claim:[/b] There exists a sequence of change of states which leads to all the rooms $R_1, R_2, \cdots , R_j$ being interesting.
[i]Proof:[/i] By our inductive hypothesis, if there weren't any new room $R_{j+1},$ there would exist such a sequence of change of states. Now, if no lamp in $R_{j+1}$ were friends with a lamp in one of the other rooms, adding this new room wouldn't affect this sequence at all. What we do when adding the new room disturbs this state of sequence is mimicking the friendship between two lamps. Consider two lamps $L_1$ and $L_2$ which were friends in the original configuration of $j$ rooms but aren't friends anymore after another room has been added. We can still impose some rules upon ourselves to make $L_1$ and $L_2$ look like friends. That is, we vow that whenever we change the state of $L_1,$ we shall also change the state of $L_2.$ This keeps the sequence of change of states undisturbed. $\blacksquare$

So suppose all the rooms $R_1, R_2, \cdots , R_j$ are interesting. If $R_{j+1}$ is interesting as well, we're done. So let $R_{j+1}$ be boring. If $R_{j+1}$ were narcissist as well, we'd be done because changing the state of two of its lamps would keep the lamps in the other rooms unaffected and make $R_{j+1}$ interesting.

Let's choose a lamp in $R_{j+1},$ which makes $R_{j+1}$ interesting. Changing its state affects the state of a lamp in another room. If that room is still interesting, we're done. Suppose that room is boring. If it were narcissist, we'd be done because then we could change the state of two of the lamps in it without affecting any of the others. Then, choose another lamp in that room and change its state. Note that that makes that room interesting again. Keep doing this operation until we reach another lamp in the room $R_{j+1}$ again. That makes two of the lamps in $R_{j+1}$ in a different state from the others, so $R_{j+1}$ is interesting and so are all of the other rooms. Hence, we're done. $\blacksquare$

We represent a lamp which is on by $1$ and the one off by $0$.Call a room [i]unattained[/i] if its lamps are either all on or all off, and [i]attained[/i] otherwise.Call two rooms $P$ and $Q$ [i]connected [/i]if there exists a pair of lamps among them which have a common switch.

If two unattained rooms are connected then we change the state of a pair of lamps connected among them.This decreases the number of unattained rooms.If no two unattained rooms are connected among themselves then each of them are only connected to attained rooms.If there exists an attained room which is connected to one of the unattained rooms and has  atleast two on and two off lamps then change the state of a pair of lamps between that attained room and the corresponding unattained room.Again this decreases the number of unattained rooms.In fact we cannot decrease the number of unattained rooms by this process only when every unattained room is connected to an attained room and the state of the connected lamp of the attained room is the only lamp of that state in the attained room.This also means that the two rooms share a switch only among one pair of lamps.
(Let us call this kind of connected rooms [i]poorly-connected[/i])

In this case,change of state between a pair of connected lamps between two rooms makes the attained room unattained and vice versa.If the newly obtained unattained room is connected to an unattained room we can reduce the number of unattained rooms by previous paragraph.Otherwise the originally attained room was connected to another attained room poorly.Going like this we see that this generates new poorly connected attained rooms to avoid the decrease of unattained rooms.Since the number of attained rooms is not infinite there must an attained or unattained room connected not poorly to an attained room.Contradiction! This means that this situation cannot arise.

Finally that we have described a method of decreasing the number of unattained rooms,we can induct on the same,the base case being trivial.

Beautiful problem! :)

I am short on time so will provide a sketch for now.

[hide=sol] Call a room [i]fixed[/i] if all lamps in it have the same state, [i]almost fixed[/i] if all but one lamp have the same state and [i]mixed[/i] if not all lamps have the same state and the room is not almost fixed. Suppose that after performing several such moves we have reached the configuration with a minimal number $m \ge 1$ of [i]fixed[/i] rooms. If a lamp is connected by a switch to another lamp in a fixed room then we can apply the switch, decreasing the number of fixed rooms, which is not possible.

If a lamp from a fixed room is connected by a switch to a lamp in a mixed room then we can apply this switch. Therefore, we can assume due to minimality of the number of fixed rooms that any lamp in such a room can only be connected by a switch to a lamp in an almost fixed room.

Starting with a fixed room $R_1$, pick any lamp of this room which has not been chosen already, and apply its switch. This changes $R_1$ to an almost fixed room and the adjoining lamps room $R_2$ fixed. Apply the same operation for $R_2$ to get a room $R_3$ and proceed likewise. Due to finiteness of the number of rooms, we eventually end up in a cycle $R_1, R_2, \dots, R_k, R_{k+1}, \dots, R_{\ell}, R_k$. Note that before the last operation was performed, the rooms $R_{\ell}$ and $R_k$ were fixed, so after performing this move, they both are almost fixed since the lamp of $R_k$ which was toggled was not used previously. Evidently, we have decreased the number of fixed rooms by $1$ contradicting the minimality of $m \ge 1$. Therefore, we can attain a configuration where no room is fixed. $\square$

[/hide]

Can we solve this using induction on the number of switches??

This post is unfortunately left out inadvertently :D

[hide = solution]

There are only a finite number of ways to flip the lamps, thus there exists some series of steps after which we obtain a configuration  with minimal number of rooms containing only on or off lamps. We'll show that this is impossible as long as $N$ is not zero. We will say a lamp being the only one on or off in a room is minor and the other lamps in that room are major.

Take a room $A$ with lamps all on or off, each of its lamps must be connected to a lamp in a room where that lamp is minor(it's easy to see otherwise we can always switch to reduce the number). But now if we consider all these rooms connected with $A$, the major lamps in them must again be connected to a minor lamp or else we can switch those two lamps and keep switching until we toggle a lamp in $A$ while not increasing $N$.Each time we would see more rooms but it can't happen indefinitely since we have a finite number of rooms so we get a contradiction and $N = 0$. [/hide]

Solution from [i]Twitch Solves ISL[/i]:

First, we interpret the problem in a graph-theoretic language: [list] [*]We interpret the problem as a graph $G$ with rooms corresponding to vertices and switches with edges (which may include self-loops). [*]The only condition is that the minimal degree is at least $3$ (where self-loops contribute $2$ to the degree). [*]The edges come in two colors, which we call [i]aligned[/i] (switches between lamps of the same state) or [i]clashing[/i] (switches between lamps of different states). [*]We wish to [i]label[/i] the endpoints of each edge with $0$'s and $1$'s (corresponding to ``off'' and ``on'') such that [list] 	[*]aligned edges have $00$ or $11$ on their endpoint; 	[*]clashing edges have $01$ or $10$ on their endpoint; 	[*]every vertex has both $0$'s and $1$'s written 	(we call such edges [i]happy[/i]). [/list] [/list] For simplicity, we assume (WLOG) the graph $G$ is connected. We will also assume $|V(G)| > 2$ (the case $|V(G)|=2$ is easy). We describe an algorithm to do so: it takes place in several steps. [list] 	[*][b]Step 1.[/b] 	Let $T$ be a spanning tree of $G$, 	and root the tree $T$ by taking any non-leaf $v_0$. 	Start by assigning all edges of $v_0$ in $T$ 	in such a way that $v_0$ is happy.
Then starting from $v_0$ and following 	the pattern, label all edges of $T$ 	such that all vertices of $v_0$ become happy 	except for the leaves 	(which will only have one label).
[*][b]Step 2.[/b] Let $H$ be the set of leaves of $T$, 	considered also an induced subgraph of $T$. 	Every vertex of $H$ has at least one label. 	If we take a spanning forest of $H$, 	then we can proceed similarly as in Step 1 	until there is at most one vertex in 	each connected component of $H$ which is not happy.
[*][b]Step 3.[/b] 	Consider the set $S$ of remaining unhappy vertices; 	the set $S$ is an independent set, by construction. 	Because the minimal degree is $3$, 	they each have at least one more edge. 	So they can be made happy. [/list] We then label any remaining edges of $G$ arbitrarily; since all vertices are happy already it doesn't matter how.
A cartoon of the process is given below.
[asy] size(9cm); draw(box((-4,-1), (4,1)), blue+dashed); label("$H$", (4,1), dir(90), blue);
pair v0 = (0,4); pair w1 = (-3,2); pair w2 = (-1.5,2); pair w3 = ( 1,2); pair w4 = ( 3,2);
draw(v0--w1); draw(v0--w2); draw(v0--w3, lightgrey); draw(v0--w4);
pair x1 = (-3,0); pair x2 = (-1.5,0); pair x3 = (-0.5,0); pair x4 = (2,0); pair x5 = (3,0);
draw(w1--x1, lightgrey); draw(w2--x2); draw(w3--x3, lightgrey); draw(w3--x4); draw(w4--x5, lightgrey);
dot(v0); dot(w1); dot(w2); dot(w3); dot(w4); draw(x1..(-1,-0.5)..x3, blue); draw(x3..(1,-0.5)..x4, paleblue); draw(x2..(0,-0.8)..x5, blue);
dot(x1, blue); dot(x2, blue); dot(x3, blue); dot(x4, blue); dot(x5, blue);
draw(box(x4+(-0.2,-0.2), x4+(0.2,0.2)), red); draw(box(x5+(-0.2,-0.2), x5+(0.2,0.2)), red);
defaultpen(fontsize(8pt)); void main(string s1, string s2, pair X, pair Y, pair t1, pair t2) { 	label(s1, 0.85*X+0.15*Y, t1*dir(Y-X)); 	label(s2, 0.85*Y+0.15*X, t2*dir(Y-X)); }
main("0", "0", v0, w1, dir(-90), dir(-90)); main("1", "1", v0, w2, dir(10), dir(120)); main("0", "1", v0, w3, dir(-10), dir(-120)); main("0", "0", v0, w4, dir(90), dir(90));
main("1", "0", w1, x1, dir(90), dir(90)); main("0", "0", w2, x2, dir(90), dir(90)); main("0", "1", w3, x3, dir(90), dir(90)); main("1", "1", w3, x4, dir(90), dir(90)); main("1", "0", w4, x5, dir(90), dir(90));
label("1", x1, dir(-15)*2.5, blue); label("1", x3, dir(195)*2.5, blue); label("0", x3, dir(-15)*2.5, blue); label("1", x4, dir(195)*2.5, blue); label("1", x2, dir(-15)*2.5, blue); label("0", x5, dir(195)*2.5, blue); [/asy]
The edges used in Step 1 and the tree $T$ itself are black; the labeling is done from top to bottom. The spanning forest of $H$ and its vertices are drawn in blue; the labeling is done from left to right. The vertices of $S$ are colored red and one more edge is used for each of them (not shown). Clashing edges are drawn in a lighter color than aligned edges.

Wow this was such a cool problem! And I also used graphs!

Consider a graph $G$ where the rooms are the vertices. Let each edge denote a switch connecting a lamp at one room to a lamp at a different room (we allow loops and multiple edges between two vertices). Define a [i]cycle[/i] in $G$ in the usual way (but here we also consider cycles with only one vertex or only two vertices).
Call a vertex $V$ [i]just-fixed[/i] if all but one lamp in $V$ are in the same state, [i]broken[/i] if all lamps in $V$ are the same state, and [i]normal-fixed[/i] otherwise. Further a vertex is called [i]fixed[/i] if it is just-fixed or normal-fixed. Our goal is to get all the vertices to be fixed.

[b]Claim:[/b] Let $C$ be any cycle in $G$. Then all the vertices in $C$ can be fixed.

[b]Proof:[/b]
[b]i)[/b][i]If the cycle is a loop:[/i] Then two lamps $L_1,L_2$ in one vertex (say $V$) share a switch. If $L_1,L_2$ are in different states initially, then they can never be in the same states by any sequence of switches. Otherwise if $L_1,L_2$ are in the same state, then if at any time, $V$ is broken, then we simply change the states of both $L_1,L_2$ and $V$ will be normal-fixed.

[b]ii)[/b][i]If the cycle is not a loop:[/i] Denote the cycle $C$ by $V_1-V_2-\dots-V_{k}-V_1$, where $k\geq 2$. Let the edge/switch between vertices $V_i$ and $V_{i+1}$ be denoted by $e_i$ (here $V_{k+1}=V_1$). Now perform the following algorithm (call it [b]ALGORITHM[/b]) repeatedly- "Choose the smallest index $j$ such that $V_j$ is broken. Change the switch $e_j$." If we can stop before reaching $V_k$ then all the vertices will have been fixed. Otherwise suppose we reach $V_k$ and it is broken. Then change $e_k$. Now note that $V_k$ is just-fixed. If $V_1$ becomes broken, then run ALGORITHM again as long as we do not reach $V_{k-1}$. If we stop before that, then done. If $V_{k-1}$ is broken, change $e_{k-1}$. Since $e_k$ and $e_{k-1}$ operate on different lamps in $V_k$, so changing $e_{k-1}$ makes $V_k$ normal-fixed and we can finally stop ALGORITHM. Hence all vertices in $C$ have been fixed. $\square$

Now consider all connected sub-graphs in $G$. Since for each $V\in G$, $\deg(V)\geq 3$, we know that none of the sub-graphs is a [i]tree[/i] (connected graph with no cycles), since it is well-known that a tree must have at least two vertices with degree 1. Now just consider any broken vertex $A_1$ and a path $A_1-A_2-\dots-A_m-C$ where $C$ denotes a cycle $-V_1-\dots-V_{k}-V_1$. Again let $f_i$ denote a switch/edge between $A_i$ and $A_{i+1}$. Now run ALGORITHM (replace $V$ with $A$ and $e$ with $f$) on the vertices $A_1,A_2,\dots,A_m$. If we stop before reaching $A_m$, we are done. If $A_m$ needs to be fixed, then change the switch between $A_m$ and $V_1$. Now our [b]Claim[/b] will take care of the cycle $C$. Thus all vertices can be fixed. $\blacksquare$

The idea is  to push forward, making the rooms that satisfy the condition more and more. It is made via a dumb greedy actions. We take a room which is not ok, flip a lamp, then another room could be spoiled, we again try to recover that room, the other one gets damaged, and so on till, we hope, there is no room spoiled. What follows is just a routine argument.

Consider a configuration that maximizes the number of rooms satisfying the condition. We claim all the rooms are ok, that's, they have two lamps of different states. Assume, on the contrary, $ R_0$ is a room with all the lamps having the same state. Take a lamp $ \ell_0$ in $ R_0$ and change its state. It's matched with another lamp $ \ell_1$. If $ \ell_1$ is also in $ R_0$ we are done since $ R_0$ is already ok, because there is another lamp in it with different state. Suppose $ \ell_1$ is in some other room $ R_1\neq R_0$. If changing the state of $ \ell_1$ doesn't spoil the things in $ R_1$ we are done, otherwise we take a lamp $ \ell'_1\neq \ell_1$ in $ R_1$ and flip its state, thus $ R_1$ is still ok. It also affects the state of the lamp $ \ell_2$ that is matched with $ \ell'_1$ mounted in a room $ R_2$.
Proceeding with this process leads to two possible outcomes. Either we reach a room $ R_n$ which is not spoiled after the lamp $ \ell_n$ in it is flipped, or we reach a room $ R_n$ which coincides with some previous room $ R_m, m<n$. In the latter case, the room $ R_n$ is already ok since $ \ell_m,\ell_m'$ in $ R_m$ are in different states and we enter again $ R_m$ in another lamp different from $ \ell_m, \ell'_m$. Thus, in all cases, we increase the number of rooms that are ok,  contradiction.

[b]Comment.[/b] I think, the graph theory approach makes things worse, instead of helping, see also [url=https://dgrozev.wordpress.com/2020/08/20/when-graphs-make-things-worse-imo-2005-shortlist-c1/]my remarks here[/url]. The right approach, in my humble opinion, is to imagine the picture as disjoint subsets of points (each subset being a room, each point - a lamp) and some full matching between the points. The problem is easier than it appears in the first glance.

Solved with [b]Th3Numb3rThr33[/b].

Interpret the problem as follows: each room is a vertex of degree at least three in a (not necessarily simple) graph, and each pair of lamps represents an edge between two (not necessarily distinct rooms.) The goal is to color the edges with two colors such that each vertex has edges of both colors.

Call a vertex [i]monochromatic[/i] if all its edges are the same color. Assume for contradiction the goal is not possible, and take a configuration with the smallest number of monochromatic vertices. Let \(v_1\) be one such monochromatic vertex, and select an edge \(v_1\sim v_2\). If we flip the color of this edge, then \(v_2\) must become monochromatic by minimality.

From here, select an edge \(v_2\sim v_3\) in the same way, and construct such a sequence \(v_1\to v_2\to\cdots\). But this sequence can not have any cycles: if for example, \(v_k\to v_1\) appears in the sequence, then toggling the color of \(v_k\sim v_1\) makes \(v_1\) monochromatic again, which is absurd since \(\deg v_1\ge3\) and all edges incident to \(v_1\) besides \(v_1\sim v_2\) are the same color. Thus the sequence continues forever, contradiction.

We call a room bad if all the lights in the room are the same state and good otherwise. Let $s(L)$ denote the state of lamp $L$ (on or off). Suppose that some room is bad, and let the lamps in the bad room be $L_1, L_2, L_3$. WLOG let all of them be on. If 2 lamps in the room are connected, we can just switch them and make them good. So assume no 2 are connected in the same room. Let $L_1$ be connected to $L_4$ and let $L_5,L_6$ be the other lamps in the same room as $L_4$. If $s(L_4)=s(L_5)$ or $s(L_4)=s(L_6)$, then switching $L_1$ would make both rooms good. So assume that $s(L_4) \neq s(L_{5,6})$. If $L_2$ shares a switch with either $L_5$ or $L_6$, switching $L_2$ would make both rooms good. So assume $L_1,L_2,L_3$ all share switches with lamps from different rooms. Let $L_2$ share a switch with $L_7$ (same room as $L_8, L_9$) and $L_3$ share a switch with $L_{10}$ (same room as $L_{11}, L_{12}$). Now switch any one of $L_1, L_2, L_3$  WLOG $L_2$. Now the first room has become good whereas the room containing $L_7, L_8, L_9$ is bad. Suppose $L_8$ is connected to any of $L_5, L_6, L_{11}, L_{12}$. Then turning $L_8$ would make all rooms good. Hence we need to introduce a new room which becomes bad upon switching $L_8$. Say, $L_8$ is connected to $L_{13}$ in room $L_{13}, L_{14}, L_{15}$. By the same logic, $L_{14}, L_{15}$ cannot be connected to any of the previous rooms, and this process can only continue finitely since there are a finite number of rooms. Hence at some point we must reach a  bad room where one of the lamps is connected to one of the equal lamps in a good room. So we can always reduce the number of bad rooms by $1$.

Basically the same argument as 123, but I think its a bit easier to understand.

FTSOC suppose that there exists some configuration for which it is impossible to get each room to have at least one off and one on lamp. Suppose that there are $n$ such rooms, which we will denote as good rooms(and the other type as bad rooms). We show that we can get this number of bad rooms down from $n$ to $n-1$ rooms, and thus, down to $0$ rooms at the end.

Suppose there is a bad room $v_1$. Notice that because this room has at least $3$ lamps within it, for $v_1$ to be bad, it must have no pair of lamps within it which are linked by a switch and all of the corresponding lamps which are linked by a switch to each of the lamps within $v_1$ must be in rooms which are one step away from becoming bad by that lamp. In other words, the lamp which each of the lamps in $v_1$ is linked to by a switch must be a switch in its room which, if it changes its state, that room would become bad.

Pick an arbitrary lamp in $v_1$ and change its state along with the corresponding lamp (which is in another room). Then we have to repeat the same process on the room in which the corresponding lamp is in. Notice that we can never go back to previous lamps, because if we did, then it would not be to a lamp which "saves" the lamp from being bad by one step, so it would result in all lamps being good. Therefore, we must have an infinite number of lamps, a contradiction.

Oops, it seem like the graph representation was a lot clearer than this one.

suppose we can not do that . Suppose we have k rooms each has at least 3 lamps and number of lamps is 2n than number of switchs is n . And we interpret problem to graph theoritic language. we have bipartite graph one component is lamps in the houses and other component is switchs , consider lamps and switches as vertices.it is clear that degree of each lamp is 1 and deg of each switch is 2.let if switch is on we color it`s edges to blue otherwise to red.suppose we can do that condition for $k_{1}$ rooms ( $k_{1}$ less than k )

[quote=who]A house has an even number of lamps distributed among its rooms in such a way that there are at least three lamps in every room. Each lamp shares a switch with exactly one other lamp, not necessarily from the same room. Each change in the switch shared by two lamps changes their states simultaneously. Prove that for every initial state of the lamps there exists a sequence of changes in some of the switches at the end of which each room contains lamps which are on as well as lamps which are off.

[i]Proposed by Australia[/i][/quote]

[hide=Solution][hide=Terminology]Label all the rooms as $r_1,r_2,........,r_n$
A room is said to be $"\text{bad}"$ if it doesn't satisfy the condition and $"\text{good}"$ otherwise.
A $"\text{circuit}"$ is formed between two cells if they are connected.
An off bulb is represented by $0$ and $1$ in all other cases.
[/hide]
[hide=Monovaiant]Re-lable $r_i$ s.t $r_1$ is bad.
$\;\;\; \bullet$ Start from $r_1$ and swap the sides of the circuit.If another bad room is formed then WLOG it is $r_2$ and again swap sides of the circuit.
$\;\;\; \bullet$ The process is finite:-once we return back to $r_1$ after finitely many steps,the number of "bad" pairs have now been decreased,whence it is a Monovaiant which keeps decreasing.$\blacksquare$
 [/hide][/hide]

ISL marabot solve

Define connected as shares a switch with.

Suppose there are some number of rooms where each of its lamps are of the same state. We will show that if this number is greater than $0$, we can always decrease it. This solves the problem.

Let $r_1$ be one of these rooms. Switch a lamp in $r_1$. If this lamp is connected with another lamp in $r_1$, then we are done.

If this lamp is connected with a lamp in $r_2$, then if $r_2$ has lamps with all the same state prior to the switch, then we are also done.

For this to not be possible, we need $r_2$ to have all lamps with the same state after the switch.

Now we are at the same position as the beginning with $r_2$ swapped with $r_1$. Now we switch a lamp in $r_2$, which is connected to another lamp in $r_3$.

Repeat this process until we reach a room we've been in before. Call that room $r_n$ can call the room we reach before it $r_m$.

Prior to the last switch, $r_n$ had two lights on and the other off, or vice versa. WLOG it's two lights on and the other off.

Note that the off light is already connected to some room not equal to $r_m$, so one of the on lights is switched.

So $r_n$ won't have all it's lamps with the same state.

Thus, we have decreased that number.

Let a room be [i]boring[/i] if it only contains lights of the same state. Suppose our initial configuration has at least one boring room. We claim that we can reduce the number of boring rooms by one, which through repeated application will prove the problem.

Notice that if we change a lamp in a boring room, the number of boring rooms cannot increase, and must decrease unless the room with the other changed lamp becomes boring. Start with a boring room, then do the following procedure repeatedly: change a light from the last created boring room (the initial boring room if this is first change). This procedure ends when a change doesn't create a boring room, which decreases the number of boring rooms by one, so it suffices to prove this procedure always ends.

Suppose that a room went boring two times in this procedure. Consider the first time this happens. Notice that after the first time the room went boring, two changes were made to the light, and it is boring again. This means that the two changes were done to the same light. However, this also means two changes were done to the light it's linked to, so the corresponding room has been boring twice, contradiction.

Therefore, we will eventually run out of rooms, forcing the procedure to stop and finishing the problem.

[b][i]Claim:[/i][/b] If there are any number of rooms, each with at least $3$ lamps, and some pairs of lamps are connected but no lamp is connected to two other lamps, then it is possible to switch the lamps such that each room has at two lamps in different states.

Proof:
Note that this problem is equivalent to each pair of connected lamps being always the same or always opposite of each other. Say that two lamps are "directly connected" if they are always the same and "oppositely connected" if they are always opposite of each other.

We will use induction on the number of rooms. In the base case, there is 1 room. This is clearly possible since there are at least 3 lamps, so one can simply find two lamps not connected to each other and switch them so one is on and the other is off.

Assume there are multiple rooms. Let $A$ be a room.

Case 1: $A$ has two lamps connected to each other or a lamp not connected to anything
Proof for this case: Let $a$ be a lamp not connected to any lamp outside of $A$. Let $b$ be a lamp in $A$ that isn't connected to $a$. By the inductive hypothesis, it is possible to switch all the lamps not in $A$ such that each room has a lamp that is on and a lamp that is off. Note that $a$ can't be affected by this. If $b$ is affected by this, switch $a$ such that it is the opposite of $b$. If $b$ is not affected by this, then switch both $a$ and $b$ such that they are the opposite of each other. So, $A$ will have two opposite lamps.

Case 2: Every lamp in $A$ is connected to a lamp in another room
Proof for this case: Let $a$ and $b$ be two lamps in $A$. Let them be connected to $a'$ and $b'$, respectively, which are in other rooms.

Case 2a: When $a$ and $b$ are opposite, $a'$ and $b'$ are the same: By the inductive hypothesis, in the case with all the rooms except for $A$ where $a'$ and $b'$ are directly connected, it is possible to switch the lights such that each room has a light on and a light off. So, it is possible to switch all the lamps not in $A$ so that each room has a lamp on and a lamp off and $a'$ and $b'$ are the same as each other. Then, $a$ and $b$ will be different from each other, so $A$ will have two opposite lamps.

Case 2b: When $a$ and $b$ are opposite, $a'$ and $b'$ are opposite: Using similar logic to case 2a, but making $a'$ and $b'$ oppositely connected instead, this case works.

Thus, the claim is true, which is enough to prove the problem statement.

Really chunky solution, but whatever.

We will first define a term. Let a [i]free lamp[/i] be a lamp that can be whatever we want it to be, without breaking the other lamp with the same switch. A room with a free lamp always satisfies the required condition.

Note that if a room contains two lamps connected by the same switch, the two lamps are essentially one free lamp, which clearly makes the problem easier. Therefore, in the below proof, we will assume that there is no room with two lamps controlled by one switch.

We now use strong induction on the number of rooms. The case with one room is trivial. Let the number of rooms be $n$.

First, we create a graph, where each node is a room and two nodes are connected if and only if there is a switch that controls a lamp in each room. We see that each node must be connected to at least two other nodes, as if that is not the case, the room has to be completely connected to another room. If that other room has more lamps, it provides more free lamps, then clearly works by strong induction with $2$ rooms and $n-2$ rooms. If the other room has the same number of lamps, this still clearly woks by strong induction with $2$ rooms and $n-2$ rooms.

Now, this means that the number of connections in the graph must be at least $\frac{2n}{2}=n$, which means that there must exist a loop of nodes. Let the nodes in this loop in order be $a_1,a_2,\dots,a_k$, where $k\le n$. We can let $a_1$ provide a free lamp to $a_2$, $a_2$ provide a free lamp to $a_3$, etc, until $a_k$ provides a free lamp to $a_1$. Then, each of these rooms still has at least one lamp left, so it can provide free lamps to everything connected to the loop(or not if $k=n$, in that case we're just done). QED.

Edit2: I just realized that I didn't explain the last sentence clearly enough/correctly enough. The loop nodes give free lamps to anything connected to it besides the loop itself, and a room with a free lamp can reach another room with a free lamp, etc. This clearly continues to the entire connected region because of the argument we used with the leading out of the loop. Remember that if the graph is disconnected, it is taken care of by strong induction.

Is this right? I bolded the parts which are most likely to have errors.

Suppose that we have a graph where each room represents a node, and two nodes are connected if there exist two lamps from those rooms which share a switch. Then, call a pair of rooms [i]good[/i] if they are in the same component.

Assume that in every room there exists a lamp which shares a switch with a lamp not in that room (we can do this because we could just delete the room otherwise). Now, suppose that we have a room which contains two lamps which share a switch. Then, regardless of the states of the other lamps in that room, we will always be able to have this room contain lamps which are on, as well as lamps which are off. This means that the states of the other lamps are "free", which means that the lamps they are connected to are also "free". [b]Inductively, it follows that the whole component will be able to satisfy the condition in the problem.[/b] Then, we can simply delete the whole component. This allows us to assume that every switch connects two lamps from different rooms.

Next, suppose there exists two rooms such that there are two switches which connect four different lamps, two from each room. It's easy to show (by simply taking cases) that the rest of the lamps in these rooms are "free". [b]Similar to the first process, we can apply this logic inductively and so we may assume that there do not exist two rooms such that there are two switches which connect four different lamps (i.e. for any two lamps in a room, each one shares a switch with lamps from different rooms).[/b]

Finally, assume there are at least three rooms in the house (the other cases being trivial). Then let three of them be rooms $1$, $2$, and $3$. Then there must exist two lamps from room $1$ such that one connects to room $2$ and the other connects to room $3$. [b]Again, notice that all of the other lamps in these three rooms are "free". Thus we may assume that no three rooms satisfying the condition stated exist, by induction. [/b]

Now we have exhausted all cases, so we are done. $\blacksquare$

Call a room boring if all the lamp states are the same. Call it interesting if there is exactly one lamp that is different from all the rest. We prove that if there is a positive number of boring rooms there is a way to decrease this number by one.

Pick any room that is boring then switch the state of one of them to make it interesting. If we're not done, some other room was just made boring. Then in that boring room, we switch the state of some lamp to make it interesting. Eventually following this algorithm, we're either done, or we have to go back to a room we have already entered.

In this case, consider the first time we revisit a room, $r$. Every room that was operated on is now interesting, except for the one we just entered. Before entering, the room was interesting so there is exactly one lamp to make it boring. When we first entered this room we operated on the very same lamp, so that means we have visited the room before $r$, call it $s$ previously, unless the room entering sequence goes $r\to s\to r.$

This is a contradiction with the fact that we operate on a different lamp than one that was just changed, so we're done.

Call a room bad if all of its lamps are in the same state, and good otherwise. We will find an algorithm that always decreases the number of bad rooms, as long as there is at least 1 bad room.

Take a bad room, and call it room 1. Change one of its lamps. If this change did not make a previously good room bad, then we have already succeded in reducing the number of bad rooms. If this does make another room, say room 2, bad, we then flip a lamp in room 2 that wasn't connected to the one we just flipped. If this lamp is connected to a lamp in room 1, then this will make room 2 good while not making room 1 bad, so we are done in this case. Otherwise, this lamp is linked to another room, which we call room 3. If we keep doing this, eventually we will return to an already visited room, and have successfully decreased the number of bad rooms, so we are done.

i think i may have misunderstood the problem

There are $2n$ vertices. Call a bad room a room in which the lamps are either all on or all off. We proceed by induction on $n$ with the base case trivial.

Assume the statement for $n=k$. Let graph $G$ have $2k+2$ vertices and let the rooms be $A_1,\ldots,A_r$. Assume there exists $1\leq i<j\leq r$ such that there exists an edge $vu$ between $A_i$ and $A_j$ (otherwise it is trivial). Now apply the induction hypothesis on all the vertices except $v$ and $u$ with rooms being $A_1,\ldots,A_{i-1},A_{i+1},\ldots,A_{j-1},A_{j+1},\ldots,A_r,A_i\cup A_j\setminus\{v,u\}$. At most one room is bad, and it is among $A_i$ and $A_j$. Then just change the state of $v$ and $u$ so that we remove the bad room, completing the induction step. $\square$

EDIT: fakesolve  :blush:
the assumption that at most one of $A_i$ and $A_j$ is bad is incorrect

Hopefully this works?

Let edges be lamps (on or off), and let nodes be rooms. We wish for all of the nodes to have at least one of each colored edge attached to it.\\

For each connected component of the graph:\\

Pick some edge and remove it, leaving the graph still connected (since the degree of each node is greater than or equal to 3, such edge must exist; otherwise the graph is a bamboo).\\

From one of the endpoints of that edge as the root, construct the DFS tree, with its edges alternating on/off based on distance from the root.\\

Place back the removed edge in off. Now, the root node has both on/off edges and is good. Also, all non-leaf nodes are good since they have edges going in them and out of them in the DFS tree, so they must be of opposite color. Now, all leaf nodes either have 1 or 2 free edges left (1 if and only if they are matched with the removed edge at the start).\\

Pick either that node with free degree 1, or any random node. Color any of its edges its missing color if it exists, or any random color if not. Go to the other end of the edge just colored, and repeat. If at any point we return to a leaf node we already fixed, go to another unfixed leaf node.\\

Thus, we can fix any leaf node we consider; we thus can fix all nodes.

[quote]Each lamp shares a switch with exactly one other lamp[/quote]
When translating the problem into graph theory, vertices are lamps. An edge is a switch incident to the two vertices the switch controls. Is the graph described in the problem any graph or is it the graph with $|E|=\frac{1}{2}|V|$ and $\frac{1}{2}|V|$ connected components?

I read a few monovariant sols from above and it seems like the graph is the latter.

Call a room bad if it does not satisfy the condition. We describe an algorithm that reduces the number of bad rooms by 1. Start at a bad room. If two lamps in that room share a switch, we are done. Otherwise, flip a switch and go the room that is connected to the switch. If this room went from good to bad, then repeat. Eventually, we must reach a room we have visited before. Consider the first repeated room. But the only switch that could be changed to make that room bad again is the switch that was changed originally, and this is only possible if the room that was visited immediately before was the same both times. This is impossible, as we assumed this was the first repeated room, and we are done.

Call the process of [i]fixing[/i] a room the process of making it not monochromatic. Suppose for the sake of contradiction that every room has at least one unfixed room. Take the first unfixed room, and flick on an arbitrary light in there. If It turns on a light in the same room, done. Otherwise, a light elsewhere turns on. If that light keeps the room fixed, then also done. Otherwise, the process of turning on this light will make another unfixed room. Now fix this room. Repeat until we visit a room we have visited before. The only way to unfix this room again is to turn off/on the light that fixed it in the first place. But this was already on our switch list that we made while fixing rooms, contradiction.

Hence we have achieved a contradiction, and we are done.

I think this one is more accessible, probably even to a student who just needs to reinterpret the problem and after that it's just logic.
Let the rooms be vertices, each with degree at least 3 where each edge represents a lamp sharing a connection with some lamp in another room (vertex). The problem is reduced to saying that we need a configuration such that each of the edges incident to any vertex are not all the same color. Indeed, if we switch some v_1<->v_2 it must still not work, so v_2 must become [i]monochromatic[/i]. Then the sequence v_1-v_2-...v_k must never be a loop, otherwise after v_k becomes monochromatic switch v_k with v_1, since v_1 has 2 of the first color and 1 of the second color but switching that edge's color changes it from first to second color, v_1 is now not monochromatic, so we're done! And finally, note that this sequence cannot be infinite since it must EVENTUALLY cycle. $\blacksquare$

Fairly boring problem.

Suppose that there exists some set of rooms $S$ that don't satisfy the condition. We will prescribe an operation that strictly decreases $|S|$, more or less in the most obvious way possible. Say some room $R \in S$.

If there exists two lamps in $R$ connected to each other, we are done immediately. Else, this means that flipping a lamp in $R$ causes some other room $R_1$ to not work; now, perform the same operation on $R_1$, and so on. This gives us a path $R, R_1, R_2, \dots, R_n$. If $R_n$ does not connect to any more rooms, then it must have a self-loop, thus we can finish. Else, $R_n = R_i$ must cycle eventually, but then $R_i$ necessarily also has to work (because the originally toggled lamp was still toggled.) Thus done.

Take simple graph $G(V,E)$ where two rooms are connected iff they share a connected bulb

Use induction on $n$. If there is a room with degree $4+$ or a loop we are done.

Assume the graph is $3$-regular
Now select the edges of a spanning tree and select any non-selected edge.
This creates a single cycle with branch-like extensions that connect all of the points of the graph.
Selecting bulbs along selected edges provides a solution.

[hide=Comment]
Algorithmically clearing the graph to $3$-regular also works, but induction is much easier to explain formally
[/hide]

Rewrite

We show that if there are a nonzero amount of rooms with all lamps of the same state, we can decrease the amount of such rooms. Call such rooms dull and lamps that share a switch connected. Suppose we couldn't decrease the number of dull rooms.

Suppose $r_1$ is a dull room. If two connected lamps were both in $r_1$ then we can just switch both those lamps and thus decrease the amount of dull rooms. Therefore, no two connected lamps can be both in $r_1$. Now, there must exist a room that has a lamp connected to one in $r_1$. Randomly choose such a room and call it $r_2$. If we switch a lamp connecting $r_1$ and $r_2$, we see that $r_1$ isn't dull anymore, and thus $r_2$ must become dull so that the number of dull rooms is preserved. In particular, $r_2$ cannot be dull before the switch. Now, we can choose another room $r_3$ sharing a switch with $r_2$, and get that it must be dull after the switch, and similarly we choose rooms $r_4, r_5, \ldots, $ in the same manner. Each room $r_i$ cannot dull prior to the switch of the lamp shared with $r_{i - 1}$. However, at some point some $r_n$ repeats (since there are a finite number of rooms), but $r_n$ is dull due to having been switched earlier, which is a contradiction because it can't be dull after the switch.

We say that a room is good if there exist both lamps that are on as well as lamps that are off; conversely, say that a room is bad if all lamps are either on or off. Note that it suffices to devise an algorithm that will strictly decrease the number of bad rooms upon running it, as applying our algorithm sufficiently many times would then result in a configuration with no bad rooms at all.

Our algorithm is as follows. Suppose that there exists some bad room $R_1$. If there exists a pair of lamps in $R_1$ that share a switch, then we can simply toggle the states of those two lamps; since $R_1$ has at least three lamps as given, it would then become a good room, so we are finished in this case.

Otherwise, consider some lamp in $R_1$ that shares a switch $s_1$ with a lamp in another room, which we call $R_2$. Toggle this switch; clearly, $R_1$ becomes a good room. If $R_2$ remains good or becomes good, then we are again finished. Otherwise, $R_2$ has been made into a bad room.

We then repeat the same considerations above on $R_2$, considering whether there exists a pair of lamps in $R_2$ sharing a switch; if so, we are done and terminate. If not, we flip the switch $s_2$ of some lamp in $R_2$ that is shared with a lamp in another room, say $R_3$ while guaranteeing that $s_1\neq s_2$, as each room has at least three lamps. If $R_3$ is good, we are again finished and terminate; otherwise, we repeat the same process on $R_3$.

We then repeat this process indefinitely many times until termination; it then suffices to prove that such a termination must happen. Indeed, if there exists some room $R_n$ containing a pair of lamps sharing a switch, then we terminate. Otherwise, by finiteness, we must come across some room $R_n$ that we have processed previously, so that there exists some $k<n-1$ satisfying $R_k=R_n$.

Before flipping the common switch $s_{n-1}$ connecting rooms $R_{n-1}$ and $R_n$, we note that flipping the switch $s_k$ between $R_k$ and $R_{k+1}$ has made $R_k=R_n$ to be already good. Since each lamp shares a switch with exactly one other lamp and $k<n$, we must have $s_k\neq s_{n-1}$, implying that flipping switch $s_{n-1}$ does not undo $s_k$. Since room $R_n$ has at least two lamps, it will remain good, thus terminating our algorithm.

One can check that running our algorithm will make each $R_i$ good, for all $i\in\{1,2,\cdots,n\}$. Since $R_1$ was originally bad, this algorithm must then decrease the number of bad rooms. $\blacksquare$

- Jörg


LaTeX
algebra
polynomial
linear equation

Solve for x

2x+ [u]xsquared +1[/u] = 3x+ [u] 2 [/u]
        ____ x-1  __________    _        x-1

Does that equal 6xsquared - 5x + 1

Please use $\LaTeX$ (at the moment I can't even understand the question), use proper topic-naming, but most important: don't post everything here in Superior Algebra!
This subforum is for that nonelementary Algebra stuff after school level that is not that much (but sometimes it is indeed) usefull for olympiads, e.g. rings, fields, groups, ... (well it's hard to describe what essentially belongs here, but simple calculating with polynomials or linear-equation-solving does not).

i don't understand it either. what do the blanks mean in the second equation?

[hide][quote]Does that equal 6xsquared - 5x + 1[/quote]

how does an equation equal an expression? :huh: i think u mean

$2x+\frac{x^2+1}{x-1}=3x+\frac{2}{x-1}$

in that case u multiply by $x-1$ and simplify to get $x=1$[/hide]


LaTeX geometry calculus limit integration Asymptote ratio

Hey guys,

I hope I'm putting this on the right forum... It's not a junk question so I don't think it belongs in Games and Fun Factory. Anyway, I'm planning to launch a new math contest here late this year and want to have a good logo. Unfortunately, I'm not good with my KSEG, and I don't have enough enough to buy geometer's sketchpad. Moreover, my computer is slow now so I can't install LaTeX program I used to have either.

So, can anyone make me a logo with complex geometry figure(s) and bit of algebraic symbols? I don't care what are they as long as things related to calculus are not involved (no calculus in the actual competition so I don't want to have it on the logo either; those include $ \lim$ and $ \int$, etc).

Thanks!

If anyone can, please post reply here and see if you can make one as well. It has to be [b]original[/b] (not copied off from Google).

I don't know much Asymptote but you can generate a Golden Ratio picture which would make a pretty good logo (with some other things added of course). Just an idea  :) .


complex analysis
complex analysis unsolved

I have another problem that I couldn't solve.

Let $ f(z)=g(az)$ for $ a\neq0$. Prove that then is $ Res\limits_{z=\frac {z_0} a} f(z) = \frac 1 a Res\limits_{z=z_0} g(z)$.

Thanks.

at point $ z = \frac{z_{0}}{a}$  we can write  Laurent  series
$ f(z) = +....+\frac{a_{-1}}{z-z_{0}/a}+....$ where $ a_{-1}$ is  residue.
on the other hand:
$ g(az) = f(z) =  +....+\frac{a_{-1}}{z-z_{0}/a}+....$ if denote $ az =y$
  then :
$ g(y) =+....+\frac{a_{-1}}{y/a-z_{0}/a}+.... = +....+\frac{a*a_{-1}}{y-z_{0}}+....$ and since residue at point $ y=z_{0}$ of  $ g(y)$ will be equal to  $ a*a_{-1}$ thus we obtain :

$ Res\limits_{z=\frac {z_0} a} f(z) = \frac 1 a Res\limits_{y=z_0} g(y)$


Is there any way I could type LaTeX code on a PDF form? I would like to type something like $ \langle x, y | x^2\equal{}y^3\equal{}1, xy\equal{}yx \rangle$. I tried creating an image and pasting it on, but then it gets all fuzzy, and unreadable.

I use WinEdt, but I also have TeXnicCenter


function
trigonometry
analytic geometry
conics
hyperbola
inequalities
geometry

I thought it might be fun if a creative proof contest was started. Someone can post a well known theorem and others can submit their proofs of it. Wikipedia and mathworld won't be of much help since its based on creativity. Feel free to post a theorem and make sure any proofs are well-typed and easy to read. I might as well post the first theorem:

Fermat's Little Theorem

Does "creative" imply "proofs that are not widely known"?  Original proofs of FLT are difficult to come by.  There is a well-known and rather creative counting proof; does that count?

How about... prove that $ a\plus{}\frac{1}{a}\geq2$, given that $ a>0$? :P

[hide="Example"] Let $ f(a) \equal{} a \plus{} \frac{1}{a}$.  Because $ f(a) \equal{} f \left( \frac{1}{a} \right)$, we can assume WLOG that $ a \le 1$.

Let $ S \equal{} \{ s \le 1 : s \plus{} \frac{1}{s} \le 2 \}$.  Let $ m$ be the infimum of $ S$.  Then

$ \left( m \plus{} \frac{1}{m} \right)^2 \equal{} m^2 \plus{} \frac{1}{m^2} \plus{} 2 \le 4 \implies$
$ m^2 \in S$.

On the other hand, $ m^2 \le m$ with equality when $ m \equal{} 1$.  Hence $ S \equal{} \{ 1 \}$. [/hide]

[hide="must... avoid... AM-GM"]By Cauchy-Schwarz, we have $ (a\plus{}\frac{1}{a})(\frac{1}{a}\plus{}a)\geq(1\plus{}1)^2 \Rightarrow (a\plus{}\frac{1}{a})^2\geq4 \Rightarrow a\plus{}\frac{1}{a} \geq 2$. Equality is met when $ \frac{1}{\frac{1}{a}}\equal{}\frac{\frac{1}{a}}{a} \Rightarrow a^4\equal{}1 \Rightarrow a\equal{}1$[/hide]

Well, Cauchy on $ x, y$ and $ y, x$ just gives you AM-GM.

[hide="Another"] This is equivalent to proving that the [url=http://en.wikipedia.org/wiki/Hyperbolic_function]hyperbolic cosine[/url] $ \cosh t \equal{} \frac {e^t \plus{} e^{ \minus{} t}}{2}$ is greater than or equal to $ 1$.  But since $ \cosh t$ parameterizes the $ x$-coordinate of the hyperbola $ x^2 \minus{} y^2 \equal{} 1$, this is obvious.  (This is a slightly different use of the trivial inequality than the standard one.)

In less geometric terms, $ \left( a \plus{} \frac{1}{a} \right)^2 \minus{} \left( a \minus{} \frac{1}{a} \right)^2 \equal{} 4$. [/hide]
I'm not sure if I would call what I'm doing truly "creative": I'm merely applying fairly standard techniques (contradiction, bijection to a different kind of problem) to inequalities, an area where those techniques are encountered less often.  Inequalities are a good place for arguments like this since there are many ways to prove an inequality that isn't tight for most values of the variables involved.

On the other hand, here's an inequality that, as far as I can tell, owes its entire existence to Cauchy-Schwarz:  prove that for any sequence $ a_k$ and positive integer $ n$,

$ (a_1^2 \plus{} 4a_2^2 \plus{} 9a_3^2 \plus{} ... \plus{} n^2 a_n^2) \ge \frac {6}{\pi^2} \left( a_1 \plus{} a_2 \plus{} ... \plus{} a_n \right)^2$.

[quote="t0rajir0u"]Well, Cauchy on $ x, y$ and $ y, x$ just gives you AM-GM.[/quote]
Shh! And I mean explicitly using it. :P
[quote="t0rajir0u"][hide="Another"]This is equivalent to proving that the [url=http://en.wikipedia.org/wiki/Hyperbolic_function]hyperbolic cosine[/url] $ \cosh t \equal{} \frac {e^t \plus{} e^{ \minus{} t}}{2}$ is greater than or equal to $ 1$.  But since $ \cosh t$ parameterizes the $ x$-coordinate of the hyperbola $ x^2 \minus{} y^2 \equal{} 1$, this is obvious.  (This is a slightly different use of the [b]trivial inequality[/b] than the standard one.) [/hide][/quote]
Ooh!
[hide="Yet another"]$ a\plus{}\frac{1}{a}\geq2 \iff a^2\plus{}1\geq2a$ since $ a>0$. Since $ a^2\plus{}1\geq2a \iff a^2\minus{}2a\plus{}1\geq0 \iff (a\minus{}1)^2\geq0$ is true, the original inequality is true.[/hide]

That's the standard proof of AM-GM in two variables.  (Note that the inequality we're trying to prove is equivalent to AM-GM in two variables since $ a \plus{} b \ge 2 \sqrt{ab} \Leftrightarrow \frac{a}{ \sqrt{ab} } \plus{} \frac{b}{ \sqrt{ab} } \ge 2$.)

I don't know if any of you have seen this but:

1. Find a closed form solution for the $ n^{th}$ term of the Fibonacci Sequence.

2. $ a,b\in\mathbb{Z^\plus{}}$, show that if $ 4ab\minus{}1$ divides $ (4a^2\minus{}1)^2$, then $ a\equal{}b$. (IMO)

[quote="JZambrano201"]1. Find a closed form solution for the $ n^{th}$ term of the Fibonacci Sequence.[/quote]
I have given a few proofs of [url=http://mathworld.wolfram.com/BinetsFibonacciNumberFormula.html]Binet's formula[/url] on my blog and [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?t=178530&search_id=2069231291]this thread[/url].  I consider none of them particularly creative - the matrix method is an immediate consequence of the technique of matrix diagonalization and the generating functions method is equally standard.  The solution by vector spaces similarly is more about very general concepts than whatever "creativity" means.

The second problem has several solutions in the Olympiad thread where it was first posted.


arithmetic sequence
algebra unsolved
algebra

if the fourth power of the commen difference of an arithmetic progression is added to the product of any four consecutive terms of it prove that the resulting sum is the square of an integer

I don't think your statement is true.  Suppose $ \{a_{n}\}\equal{}n\times .01$.  Then $ d\equal{}.01$.  Let's choose the first four terms for simplicity.  Then $ a_{1}a_{2}a_{3}a_{4}\equal{}.00000024$ and $ d^{4}\equal{}.00000001$.  Clearly, their sum is not the square of an integer.

If the progression is a progression of integer numbers... We can explicit this square.

$ a(a \plus{} b)(a \plus{} 2b)(a \plus{} 3b) \plus{} b^4 \equal{} (a^2 \plus{} 3ab \plus{} b^2)^2$

Open to verify it.

jrav if the commen difference is 0.1 then the nth. term is is n-1 times the commen difference + the first term
feliz i'm sorry i forgot to mention that the progression has terms which are integers

First of all, the common difference is not 0.1, it's 0.01.  Second, I know what the terms of the sequence are and clearly your problem doesn't work.  As you said, the terms must be integers.


calculus
trigonometry
AMC
USA(J)MO
USAMO
AMC 10
\/closed

Hello, I am unsure as to what difficulty level the courses on the AoPs course list are. For although they superficially appear exteremely easy I am not sure if they have some latent difficult matiriel that I would enjoy. What level of course would you suggest as the supremum (math joke...bad I know) for these classes? Like what is the class that if you have taken this or any above it you will probably no longer benefit from the AoPs courses.

Mathstud.

I don't think you can really compare them to other classes like that -- for example, we have plenty of students who have taken AP Calculus who struggle with, say, our Intermediate Trig class.  The standard curriculum is so completely different than ours that there's not a mapping like this that works.  Take the diagnostic tests that are in the Online Classes section; these will give you some guidance.

If you can give me an idea of how you did (or might do) and your goals, then I might be able to recommend some classes for you.

For example, if you are aiming for a ~140-150 on the AMC 10, the AMC 10 problem series class would probably be helpful.

If you were aiming for a decent USAMO score and maybe MOP qualification, WOOT would probably be right. I'm going to take WOOT this year. But I hear it's a really tough class.

Hope that helps!  :)


be careful, in the article, it said:"Pi is an infinite decimal whose numbers never repeat in a pattern." This is implying that Pi is known to be normal, which I have not yet heard of.

Yea but it's from BBC isn't that fairly reliable?

[quote="Myself"]It also says that Pi is a ratio. :?[/quote]

Do you disagree? I mean, usually pi is defined as the [b]ratio[/b] of the circumference of a circle to its diameter. :harhar:

Yeah, the source is reliable, I would say.  There are a bunch of articles from other sources as well: http://news.google.com/news?hl=en&hs=zEi&lr=&client=firefox-a&rls=org.mozilla:en-US:official&tab=wn&ie=ISO-8859-1&ncl=http://weblog.physorg.com/news2285.html.

And I don't think by any means that "Pi is an infinite decimal whose numbers never repeat in a pattern" implies that they are saying pi is normal.  This is a BBC article meant for the general public and not a mathematical journal entry.

But who cares about reciting pi?  Don't you only need 39 digits to calculate the cirumference of the universe within the width of some sort of atom...

Maybe you need it to measure more than one universe!

I heard about this yesterday...my computer cant load the article but anyway isnt this girl 59 years old and didnt it take her 8 hours to write.

Do a search for pi recitation...you're computer should be able to load one of the results...at least I would hope :? And it's a guy but you got the 59 right :)  He recited it...he did not write it.

Wow. that guy recited 80, 000 digits. wow :o

how do they retain all this information at 59 and anyway i was wondering if this person gets paid for breaking the record?

[quote="stupidkid"]Man people need to find better things to do.  This is crazy.
http://news.bbc.co.uk/2/hi/asia-pacific/4644103.stm[/quote]

Wow. Thats all I can say. All I know of $\pi$ is 3.1415926535. Not very much. But then I think why someone would memorize pi to such a large place.

Probably because they have nothing better to do and they are bored.

Memorizing that many digits of pi is really unnessasary...

I think it's a waste of time...I've memorized 30 something...I can't count: :rotfl:

3.1415926535897932384626433832795028...

Please tell me any errors...PM me or something...

That person has NO life...

I bet he does something like memorizes one digit every minute or something...  :P

One time on Discovery Channel they showed a person who had memorized like 50,000 digits of pi.
He was autistic and had a photographic memory.
He memorized the 50,000 digits in like one week.

[quote="jhollenbeck"]and...why did he memorize 83,000 digits of pi??he must have been really bored.[/quote]
he is bored and has nothing better to do with his life so i guess he wants to waste it on pi. :)

wow... 8 hrs to recite it...
i can't even remember the words i said 8 hours ago

I tried memorizing some in 6th grade.

My teacher exempted me from all homework because he didn't believe that I had 80 digits or whatever it was in 5 days worth.

3.14159265359979323846264338327950288419716939937510582097494459230781640628899 - unsure about last few digits. It's very hazy.

3.141592653589793238462643383279502884197169399375105820...
54 digits, white_horse_king, there were some mistakes in yours, but seriously, who really cares...


Calculating $ \frac{1}{4\cdot7}\plus{}\frac{1}{7\cdot 11}\plus{}\cdots \plus{}\frac{1}{n(n\plus{}1)}$ is simple:

$ \sum \frac{1}{n(n\plus{}3)}\equal{}\sum \frac{A}{n}\plus{}\frac{B}{n\plus{}3}$

From where we find $ A$ and $ B$ and solve the problem. With three terms in the denominator it is a little more time-consuming to find $ A$ , $ B$ , and $ C$:

$ \frac{1}{5\cdot11\cdot17}\plus{}\frac{1}{11\cdot17\cdot23}\plus{}\cdots$

$ \sum \frac{1}{(n\minus{}6)n(n\plus{}6)}\equal{}\sum \frac{A}{n\minus{}6}\plus{}\frac{B}{n}\plus{}\frac{C}{n\plus{}6}$

But with four or more terms in the denominator it is much more time-consuming. Is there any easier method for calculating this without Calculus?

What would be the general term for an expression in the form of:

$ \frac{1}{n(n\plus{}k)(n\plus{}2k)...}$

if this is much harder without calculus, how would we go with four or five terms in the denominator?

You could do $ \frac1{(n\minus{}6)n(n\plus{}6)}\equal{}\frac{A}{(n\minus{}6)n}\plus{}\frac{B}{(n(n\plus{}6)}$, instead. So, for four or more terms, it is still easy. :D

[quote="triplebig"]How would you do it for four then?[/quote]

It doesn't matter. Because if a+6=n, n(n-6)=a(a+6).

I'll put an example so you guys could illustrate what you mean if possible...

$ \frac{1}{2\cdot5\cdot8\cdot 11}\plus{}\frac{1}{5\cdot8\cdot11\cdot14}\plus{}\cdots\plus{}\frac{1}{(n\plus{}1)(n\plus{}4)(n\plus{}7)(n\plus{}10)}$

$ \sum_{k\equal{}1}^n \frac{1}{(n\plus{}1)(n\plus{}4)(n\plus{}7)(n\plus{}10)}\equal{}\sum \frac{A}{(n\plus{}1)(n\plus{}4)}\plus{}\frac{B}{(n\plus{}7)(n\plus{}10)}$

$ \equal{}\sum \frac{An^2\plus{}17An\plus{}70A\plus{}Bn^2\plus{}5Bn\plus{}4B}{(n\plus{}1)(n\plus{}4)(n\plus{}7)(n\plus{}10)}$

Which leads to disaster. Could anybody solve this example?

[quote="triplebig"]I'll put an example so you guys could illustrate what you mean if possible...

$ \frac {1}{2\cdot5\cdot8\cdot 11} \plus{} \frac {1}{5\cdot8\cdot11\cdot14} \plus{} \cdots \plus{} \frac {1}{(n \plus{} 1)(n \plus{} 4)(n \plus{} 7)(n \plus{} 10)}$

$ \sum_{k \equal{} 1}^n \frac {1}{(n \plus{} 1)(n \plus{} 4)(n \plus{} 7)(n \plus{} 10)} \equal{} \sum \frac {A}{(n \plus{} 1)(n \plus{} 4)} \plus{} \frac {B}{(n \plus{} 7)(n \plus{} 10)}$

$ \equal{} \sum \frac {An^2 \plus{} 17An \plus{} 70A \plus{} Bn^2 \plus{} 5Bn \plus{} 4B}{(n \plus{} 1)(n \plus{} 4)(n \plus{} 7)(n \plus{} 10)}$

Which leads to disaster. Could anybody solve this example?[/quote]

Let be $ \frac {A}{(n\plus{}1)(n\plus{}4)(n\plus{}7)}\plus{}\frac {B}{(n\plus{}4)(n\plus{}7)(n\plus{}10)}$.

Let's say you break it up as $ \frac{A}{n\plus{}1}\plus{}\frac{B}{n\plus{}4}\plus{}\frac{C}{n\plus{}7}\plus{}\frac{D}{n\plus{}10}\equal{}\frac{1}{(n\plus{}1)(n\plus{}4)(n\plus{}7)(n\plus{}10)}$

Clearing denominators,

$ A(n\plus{}4)(n\plus{}7)(n\plus{}10)\plus{}B(n\plus{}1)(n\plus{}7)(n\plus{}10)\plus{}C(n\plus{}1)(n\plus{}4)(n\plus{}10)\plus{}D(n\plus{}1)(n\plus{}4)(n\plus{}7)\equal{}1$

Now, plug in $ n\equal{}\minus{}1,\minus{}4,\minus{}7,\minus{}10$ to get the values that you need, since all but one term will cancel in each case.

Look up method of partial fraction decomposition for more information.

[quote="triplebig"]Giving us

$ \frac {1}{9} \cdot \sum_{k \equal{} 1}^n \frac {1}{(n \plus{} 4)(n \plus{} 7)}\left(\frac {1}{n \plus{} 1} \minus{} \frac {1}{n \plus{} 10}\right)$

Do I do the same thing for $ \frac {1}{(n \plus{} 4)(n \plus{} 7)}$ , distribute, and do it again for each of the terms?

What I have so far is

$ \frac {1}{27}\cdot \sum \left(\frac {1}{n \plus{} 4} \minus{} \frac {1}{n \plus{} 7}\right)\cdot\left(\frac {1}{n \plus{} 1} \minus{} \frac {1}{n \plus{} 10}\right)$

What comes next?[/quote]

Huhh...triplebig, we can let $ A \equal{} \frac {1}{6}, B \equal{} \minus{} \frac {1}{6}$.


I'm getting [hide]5.

We know that 6 is impossible, because there are fifteen games, becoming 15 wins and 15 losses, but we can't split 15 into 6 parts.

Suppose the teams are A,B,C,D,E,F
A beats B,C,D
B beats C,D,E
C beats D,E,F
D loses to everyone
E beats A,D,F
F beats A,B,D

Q.E.D. 5 teams is the maximum, though I may have misinterpreted the question...[/hide]

I agree.

We know that since 15 games are held, there must be 15 games won. If 6 teams have the same record, that means each team won 15/6, which is not an integer number of games. If 5 teams have the same record then each of the 5 teams will have won 15/3=5 and the last one will have won 0.

5's the right answer.
At state, I was afraid, because everyone else on my team got 3 for the answer.

[quote="314.math"]In a six-team softball league, each team played each other team exactly once during the season.  No game ended in a tie.  At the end of the season, $ n$ teams had the same best record.  What is the maximum possible value of $ n$?

Thanks in advance![/quote]
You don't actually need brute force to solve this problem. There are 6(5)/2=15 games (therefore wins) being played in all. Obviously, all 6 teams can't all have the same record, but 5 teams can have the same best record because each wins 3 games and the other team has no wins. So the maximum value of n is 5.

What's an easy way to test $5$? It would take me while to think, oh, each team must win 3, except for one team..which loses all games..


geometry
3D geometry
octahedron
symmetry
tetrahedron
function

Australian Mathematics Competition(Senior Section)2005
Question 28

[img]http://img.photobucket.com/albums/v250/kennylcc/07080501.jpg[/img]

A regular octahedron has eight triangular faces and all sides the same length. A portion of a regular octahedron of volume $120cm^3$ consists of that part of it which is closer to the top vertex than to any other one.In the diagram,the outside part of this volume is shown shaede,and it extends down to the centre of the octahedron. What is the volume,in cubic centimetres, of this unusually shaped portion?

This is a short answer question.

This question also came out in the Intermediate Paper (Q29).

[quote]that part of it which is closer to the top vertex than to any other one.[/quote]

Then the rest of the octahedron can be divided up into the parts which are closest to their nearest vertice. Since there are 5 more similar vertices (as the polyhedron is regular), by symmetry, there should be 5 more such portions. So the answer is simply $\frac {120}{6} cm^3 = 20 cm^3$. The way the question is worded made me confused at first.

What other questions came out for the last 5 in the Senior paper?

Ya,the words and language in this question is quite weird..
I got this Q right ^^

Senior Paper Qs :

26. Cutting a L-shaped cake.

27. $ff(x)=6x+2005$ , Find the integer $t$,satisfying $f(t)=6t+2005$

28.(above)

29.$x+y+z=5$
     $x^2 + y^2 + z^2=15$
     $xyz=z^2$
    Find the value of 1/x + 1/y + 1/z

30.Sum of four squres (posted in this forum before)

[quote]I got this Q right ^^ [/quote]

Nice to hear that. I also got it right. 27 and 29 look interesting, I have no idea how to approach Q30.  :(

Hm actually i thought this qs was 15 :oops:.
Well about how you said you can cut it up into 5 such portions; when you draw the correspondant region for each of the 4 corner sides (the ones not at the top); those are in fact twice the area of the regions for the top ones. To see this, chop it up into different tetrahedrons and then 'join' them. So you can in fact chop up the octahedron into 8 of those areas. So the area of the top one is
 120/8=15.

Your solution sounds right.
But,do any 1 have a real "proof" for it?

Hmm... on second thoughts... anyway, the best we can do is wait for Australia to publicize the solution if no one has a proof.  :)

Didn't know the thread had been moved here... I also got 5 for 29... but I made use of the instructions, i.e. that the answer must be an integer.

[quote="kennylcc"]The answer for 27. is 401
Its can b done by "f"-ing the both side of the given equation.

The answer for 29 is 5
You can get xyz = 1 and xy+yz+xz = 5 by "making" a cubic function with roots x,y,z.[/quote]

for Q27, I do it like "f" -ing both side so i get

$ff(t)=f(6t+2005)$ . But since $ff(x)=6x+2005$ , we have $ff(t)=6t+2005$

Hence $ff(t)=6t+2005=f(6t+2005)$ . Lets assumme $6t+2005=p$ then we have $f(p)=p$ . So $ff(p)=p=6p+2005 \Leftrightarrow p=-401$ . Since $p=6t+2005$ . We will have $t=-401$ . Well , i do get a $401$ using your method but theres a negative sign . What could have been going wrong ? :?


Cars A and B travel the same distance.  Car A travels half the [i]distance[/i] at $ u$ miles per hour and half at $ v$ miles per hour.  Car B travels half the [i]time[/i] at $ u$ miles per hour and half at $ v$ miles per hour.  The average speed of Car A is $ x$ miles per hour and that of Car B is $ y$ miles per hour.  Prove that $ x\leq y$.

[hide]
If the cars travel a distance $ d$ then;
Car $ A$ travel for $ t_1$ hours at $ \frac {d}{2u}$ and $ t_2$ hours at $ \frac {d}{2v}$
$ \Rightarrow x \equal{} \frac {d}{t_1 \plus{} t_2} \equal{} \frac {2}{\frac {1}{u} \plus{} \frac {1}{v}}$

Car $ B$ travels for $ \frac{d}{y}$ hours in total; so the first half of the journey is $ d_1 \equal{} u\cdot \frac {d}{2y}$ and the second half of the journey is $ d_2 \equal{} v \cdot \frac {d}{2y}$.
$ \Rightarrow d_1 \plus{} d_2 \equal{} d \equal{} \frac {d(u \plus{} v)}{2y} \Rightarrow y \equal{} \frac {u \plus{} v}{2}$

Now by the AM-HM inequality

$ \frac {u \plus{} v}{2} \ge \frac {2}{\frac {1}{u} \plus{} \frac {1}{v}} \Rightarrow y \ge x \qquad Q.E.D$
With equality when $ u\equal{}v$ [/hide]


[quote="mna851"]I'm currently a tenth grade trying to qualify for the USAMO.  I have a couple of old AIME's, that I purchased.  Sometimes I can't make it through the solution the first 2-3 times of a #14 or #15.  Do you think I'm missing out in preparation if I try the solution and then just skip it, and focus on the other questions?[/quote]

Nope, you're not. From what it looks like, you don't really need to be worried about the #14's and #15's of AIMEs right now. First make sure you can understand up to #12 or so, and go from there. By the time you're often getting 10's on AIMEs, maybe you should study the #14's and #15's. But by then you can probably understand the solutions more easily.

Thanks.  I can understand up to twelve usually, and I'm not getting 10's often... yet, right now its like 7-8.

[quote="JesusFreak197"]If you practice until you're at the point where you can generally solve at least 7 correctly in the first hour as I can (also in 10th), then you're just fine. Even lower than that should have no problem, especially because you then have two more hours to do more problems, and 7 is even sometimes high enough to qualify. :roll:[/quote]

Well, if you practice until you're at the point where you can generally solve at least 16 correctly in the first minute (I can do it in the first second, also in 10th), then you should be fine. But seriously, what does this have to do with the question?

In any case, the key to improving (in my opinion) is to concentrate work on those problems which you felt like you could have gotten but didn't. Maybe you had the right idea but discarded it. Maybe you noticed some interesting things but didn't quite make that key insight. Gradually, if you look at the solutions, you can probably learn what kinds of things work and what kinds of things don't.

Hmm, Jesusfreak, I usually only solve non or close to that or so the first hour, because I spend the first hour or so, going through all the problems and deciding which ones are approachable, and work on them a bit, until I'm satisfied I can get the answer later.

Ehh, I wouldn't say that.  It's possible 7-8 might be good enough but theres also a decent chance it could be higher or it could be a difficult AIME where I can't get 7-8.  I'm working towards 9-10.

As I said, in the first hour. Given that on most AIME's where it's not too difficult to do that the floor will probably be 8 or 9, if not higher (although that would mean extremely easy), and any where the floor is 7 or lower, you most likely won't be able to do that well that quickly, but if you can solve that many in the first hour, you have two hours left to work on harder problems.

Yea, I guess.  But its still cutting it close hoping to squeeze out that extra difficult question or two in two hours.

[quote="JesusFreak197"][quote="probability1.01"]But seriously, what does this have to do with the question? [/quote]

It means he doesn't even need to read #14/15 if he doesn't want to, because he can do well enough to qualify for USAMO, his stated goal, already.[/quote]

Okay your goal on AIME should always be doing the best you can, not just qualifying for USAMO. You never know the floor value this year was a 9 and nobody expected that before. So say you solved first 8 in the first hour and checked them over a few times and not even bothering read the rest and like sleep for the remainder of the time, you won't make USAMO. And #14 and #15 are not always that inapproachable, like on this year's AIME 1 #15 was easier than #13 and #14, probably was equally hard as the #11 on the same test.

Always try to solve as many as you can.

I heard that the AAST people were taught to do 8 problems on the AIME and check them over a gazillion times, and so last year they had a big drop in USAMO quals ;).

I don't really see how it benefits you to do AIME problems fast. As long as you're not taking like 20+ minutes on each easy problem (which I doubt you are), it's better just to go slowly and check your work thoroughly. Along the lines of the previous post, you should make sure you can do as many problems as possible. Not only does that give you something to fall back on in case of stupid mistakes or a bad day, but it also improves your chances next year. And sometimes those extra problems you can do are not necessarily #8 and #9. A lot of later problems look scary but are actually approachable once you try. For example, in addition to what beta said, 2004 AIME I #14 was a lot easier than #13 and #15.

Should I aim to understand any 12 out of the 15 questions or the first 12?

Any 12 that you can understand, I would say. I've had times when I can get a #15 much more quickly than an earlier problem, such as 2003 AIME II.


Find the sum of reciprocals of the positive divisors of $360$.

[quote="Elemennop"]Isn't it just sum of divisors divided by number of divisors?[/quote]

that would give you 48 and three quarters, which sounds way way off, considering there's only 24 factors.

the first method is correct.

basically, you look at the formula for the sum of the divisors, and recriprocate every term within parentheses.

Oh, i was wrong, it's sum of divisors divided by the n, which is 360 in this case.

[quote="Treething"][hide="answer"]
i believe that 360 is equal to $2^{3}$ times $3^{2}$ times $5^{1}$
based off that assumption:

$\frac11+\frac12+\frac14+\frac18 = \frac{15}{8}$

$\frac{15}{8}(\frac11+\frac13+\frac19) = \frac{65}{24}$

$\frac{65}{24}(\frac11+\frac15) = \boxed{\frac{13}{4}}$
[/hide]

i'm guessing that's correct[/quote]

How are you sure that that's correct ?

isn't any trick here? what about huge number like 23324?

Generally if $n=\prod_{1\leqslant i\leqslant k}p_{i}^{\alpha_{i}}$ and $p_{i}$ are different, then sum of divisors of $n$ is $\prod_{1\leqslant i\leqslant k}\frac{p_{i}^{\alpha_{i}+1}-1}{p_{i}-1}$, so sum of their reciprocals is $\prod_{1\leqslant i\leqslant k}\frac{p_{i}-p_{i}^{-\alpha_{i}}}{p_{i}-1}$. For $n=23324$ we can easily calculate this product (it is $\frac{1800}{833}$), because $n=2^{2}\cdot 7^{3}\cdot 17$.


invariant
linear algebra
matrix
vector
linear algebra unsolved

What are the 2-dimensional subspaces of $\mathbb{C}^{3}$ that are invariant under multiplication by the matrix \[A= \begin{pmatrix}\lambda & 1 & 0 \\ 0 & \lambda & 1 \\ 0 & 0 & \lambda \end{pmatrix}\] i.e. subspaces $V$ where $A(V) \subseteq V$.

Hello,

are you familiar with Jordan decomposition?  (It might help)

Well anyway, here we go:

suppose $W$ is a 2 dimensional invariant subspace
It is described by this equation :
$W=\{x|v^{t}x=0\}$ with $v\neq 0$

Now if the space is invariant, than that means

$v^{t}x=0 \Longrightarrow v^{t}(A x)=(v^{t}A) x=0$

Now this is equivalent with saying there is some $r$ such that

$v^{t}A =r v^{t}$

or, when transposing, there is an $r$ such that
$A^{t}v= r v$

so $v$ must be an eigenvector of $A^{t}$, thus it must be a multiple

of $\left(\begin{matrix}0\\0\\1\end{matrix}\right)$

So we can conclude that there is only one 2 dimensional invariant subspace :µ

$\{\left(\begin{matrix}p\\q\\0\end{matrix}\right)|p,q\in \mathbb{C}\}$

May I know how you arrived at that description of W?

What did you not understand, the final step or the calculation of $v$?

At the beginning where you say W is described by that equation.

I have the following argument but I am not sure whether it is correct:

First observe that $V = \{ (a,b,0): a,b, \in \mathbb{C}\}$ is a 2-dimensional $A$-invariant subspace.
Let $W$ be a 2-dimensional $A$-invariant subspace. Take $v=(a,b,c)^{T}\in W, v \neq 0$. Then $v, Av, A^{2}v \in W$. Note that $Av = \lambda v+(b,c,0)^{T}$ and $A^{2}v = \lambda^{2}v+(2\lambda b+c, 2\lambda c, 0)^{T}$. Thus $(b,c,0)^{T}, (2\lambda b+c, 2\lambda c, 0)^{T}\in W$. These two vectors together with $v$ will be linearly dependent so the matrix formed by putting these three vectors as columns has determinant 0, which will imply that $c=0$. Thus $W = V$.


Your source for news for the Florida Association of Mu Alpha Theta!

I've got a contest archive running too!

when are you guys going to get state combined jan regional scores up?

[quote="bpms"]What's the difficulty of the mu alpha theta test compared to the aime?[/quote]
hahahaha
dude mu alpha theta isn't hard at all
not even close to aime
take a look at the tests on the website

[quote="bpms"]What's the difficulty of the mu alpha theta test compared to the aime?[/quote]

 :rotfl:  :rotfl:  :rotfl:

sorry, but thats hilarious.

so, geometry individual, january regional, from this weekend:

#1: how many diagnols does a regular octagon have?


Four integers are marked on a circle. On each step we simultaneously replace each number by the difference between this number and next number on the circle in a given direction (that is, the numbers $a$, $b$, $c$, $d$ are replaced by $a-b$, $b-c$, $c-d$, $d-a$). Is it possible after $1996$ such steps to have numbers $a$, $b$, $c$ and $d$ such that the numbers $|bc-ad|$, $|ac-bd|$ and $|ab-cd|$ are primes?

No, it's not.

Iterating, we consequently get $ (a\minus{}b,b\minus{}c,c\minus{}d,d\minus{}a)$, $ (a\minus{}2b\plus{}c,b\minus{}2c\plus{}d,c\minus{}2d\plus{}a,d\minus{}2a\plus{}b)$, $ (a\minus{}3b\plus{}3c\minus{}d,b\minus{}3c\plus{}3d\minus{}a,c\minus{}3d\plus{}3a\minus{}b,d\minus{}3a\plus{}3b\minus{}c)$, $ (2a\minus{}4b\plus{}6c\minus{}4d,2b\minus{}4c\plus{}6d\minus{}4a,2c\minus{}4d\plus{}6a\minus{}4b,2d\minus{}4a\plus{}6b\minus{}4c)$, ... and we note that the fourth step has only even numbers. Since every next step conserves the factor $ 2$, $ |BC\minus{}AD|,|AC\minus{}BD|, |AB\minus{}CD|$ are all multiples of $ 4$ and thus not prime.

from the first step $ a \plus{} b \plus{} c \plus{} d \equal{} 0$ that we can factorize and obtain that $ |(bc \minus{} ad)(ac \minus{} bd)(ab \minus{} cd)| \equal{} ((a \plus{} b)(b \plus{} c)(c \plus{} a))^2$, contradiction.

[quote=Pythagorasauras]What is the contradiction?[/quote]

If we suppose that they are all prime we conclude that each of them should be a perfect square. Contradiction.
Also if at least two of them are equal we still get contradiction.


Notice that for each term the coefficient of the parenthesized part and the denominator cancel out.

$ 2(1 \minus{} \frac {1}{2}) \plus{} 3(1 \minus{} \frac {1}{3}) \plus{} 4(1 \minus{} \frac {1}{4}) \plus{} \ldots \plus{} 10(1 \minus{} \frac {1}{10}) \equal{} 1 \plus{} 2 \plus{} 3 \plus{} 4 \plus{} 5 \plus{} 6 \plus{} 7 \plus{} 8 \plus{} 9 \equal{} \frac {9(10)}{2} \equal{} \frac {90}{2} \equal{} \boxed{45}$


calculus
integration
trigonometry
Support
vector
analytic geometry
geometry

Compute: $ \int_0^{\pi}\frac{(R\minus{}r\cos\theta)(2\pi r\sin\theta)}{(R^2\plus{}r^2\minus{}2Rr\cos\theta)^{3/2}}\,d\theta$

(a) under the assumption that $ R>r>0,$ and

(b) under the assumption that $ r>R>0.$

$ \frac{4 \pi  r}{R^2}$ for the a and zero for the b.

But I see no physical interest on it.

If you put the question and how to arrive at this, it would have interest.

In this form just seem someones homework.

That should be $ \frac{4\pi r^2}{R^2}.$

Not homework. In my History of Math class today, I was talking about Isaac Newton. Part of the point: the distance from the earth to the moon is about $ 60$ times the radius of the earth. The acceleration of an apple falling from a tree is about $ 60^2$ times the acceleration needed to keep the moon in its orbit around the earth. So far, that seems to support the inverse square law - but why would it be reasonable, from the apple's point of view, to pretend that the mass of the earth was $ 4000$ miles away from the apple?

Now can you see where that might have come from? (Of course, with some 19th century tools like the divergence theorem, we can make this much easier.)

By the way, how do you solve the differential equation
$ Z''|Z|^3\equal{}\minus{}Z$ (representing an object with neligible mass orbiting another object with infinite mass at the origin)

I've tried looking for solutions, but its always something confusing involving lots of vectors.

In electrostatics, you pretty much have to assume that the inverse-square law is true because otherwise, the photon would have mass and light would not travel at the speed of light.

Answering 0714446459923: this isn't easy. I tried doing it myself from scratch today, without looking anything up, and there are many places to make missteps. But I think I have it under control.

The first thing to do is to look at the quantity $ L \equal{} Z\times Z'$ (That's the 3-dimensional vector cross product). Then

$ L' \equal{} (Z\times Z')' \equal{} Z'\times Z' \plus{} Z\times Z'' \equal{} 0 \plus{} Z\times\left(\frac { \minus{} Z}{|Z|^3}\right) \equal{} 0$

Hence $ L$ is constant - constant in both magnitude and direction. The constant direction means that the motion takes place in a plane. We will immediately seize upon that and drop the 3-dimensional notation. From now on, we will say that the motion takes place in a plane, and we will use polar coordinates in that plane. As for the constant magnitude, this is the conservation of angular momentum and the source of Kepler's "equal area in equal time" law of planetary motion.

[One aside: of course I talked about the Newton-Leibniz calculus priority controversy. As near as I can determine, Newton probably had the basic structures of calculus a few years before Leibniz, Leibniz probably came to his conclusions entirely independently of Newton, Leibniz published first, and Newton was reluctant to publish at all, and if neither of them had done it, someone else would have done the same, before 1700. The vehemence and persistence of the controversy did no one any good, and probably particularly harmed English mathematics in the 18th century. And in what follows, I will use both Newtonian dots and Leibnizian differentials, sometimes in the same line, without apologizing to anyone.]

In polar coordinates, consider a local frame of reference with orthogonal unit vectors $ \hat{e}_r$ pointing in the outward radial direction and $ \hat{e}_{\theta}$ perpendicular to that pointing in the counterclockwise direction. If we change $ r,$ neither of these vectors change, but if we change $ \theta$ they both do. Drawing pictures of what happens, it shouldn't be too hard to convince yourself that $ \frac {d}{dt}\hat{e}_r \equal{} \dot{\theta}\hat{e}_{\theta}$ and $ \frac {d}{dt}\hat{e}_{\theta} \equal{} \minus{} \dot{\theta}\hat{e}_r.$

We write $ Z \equal{} r\hat{e}_r.$ The differential equation can be written as $ \ddot{Z} \equal{} \minus{} \frac {K}{r^2}\hat{e}_r.$

(Note: I went ahead and put in a constant $ K$ where 0714446459923 had $ 1.$ I needed to do some dimensional analysis at one point to track down some mistakes I was making, and I needed $ K$ to carry the appropriate units of measurement. $ K \equal{} GM,$ more or less.)

$ \dot{Z} \equal{} \dot{r}\hat{e}_r \plus{} r\dot{\theta}\hat{e}_{\theta}$

$ \ddot{Z} \equal{} \ddot{r}\hat{e}_r \plus{} 2\dot{r}\dot{\theta}\hat{e}_{\theta} \plus{} r\ddot{\theta}\hat{e}_{\theta} \minus{} r(\dot{\theta})^2\hat{e}_r.$

Equate the components. For the $ \hat{e}_{\theta}$ component, we find that

$ 2\dot{r}\dot{\theta} \plus{} r\ddot{\theta} \equal{} 0$

$ 2r\dot{r}\dot{\theta} \plus{} r^2\ddot{\theta} \equal{} 0$

$ \frac {d}{dt}(r^2\dot{\theta}) \equal{} 0,$ so $ r^2\dot{\theta} \equal{} L$ is constant.

We've seen that already; that's the conservation of angular momentum repeated. And we'll find it useful to write $ \dot{\theta} \equal{} \frac {L}{r^2}.$

Equating the $ \hat{e}_r$ components, we get

$ \ddot{r} \minus{} r(\dot{\theta})^2 \equal{} \minus{} \frac {K}{r^2}$

$ \ddot{r} \minus{} \frac {L^2}{r^3} \equal{} \minus{} \frac {K}{r^2}$

[color=green][To be continued.][/color]

This is why integral tables are very useful.

Our next step is to give up on expressing $ r$ as a function of $ t.$ Instead, we will concentrate on finding $ r$ as a function of $ \theta.$ In other words, we will try to find only the path of the orbiting planet, separating that from the question of when the planet will be at what location in the orbit. Once we've done that, we will be able to determine the time from the angular momentum idea (Kepler's equal area in equal time).

We'll write $ \dot{r} \equal{} \frac {dr}{dt}$ and $ r' \equal{} \frac {dr}{d\theta}.$

$ \dot{r} \equal{} \frac {dr}{dt} \equal{} \frac {dr}{d\theta}\,\frac {d\theta}{dt} \equal{} r'\dot{\theta} \equal{} r'\,\frac {L}{r^2}.$

$ \ddot{r} \equal{} \frac {dr'}{d\theta}\,\frac {d\theta}{dt}\,\frac {L}{r^2} \minus{} r'\,\frac {2L}{r^3}\,\frac {dr}{d\theta}\,\frac {d\theta}{dt} \equal{} \frac {L^2}{r^4}\,r'' \minus{} \frac {2L^2}{r^5}(r')^2$

So our differential equation is now

$ \frac {L^2}{r^4}\,r'' \minus{} \frac {2L^2}{r^5}(r')^2 \minus{} \frac {L^2}{r^3} \equal{} \minus{} \frac {K}{r^2}$

Multiply by $ \frac {r^2}{L^2}$ but leave a common denominator of $ r^4$ on the left. (This particular arrangement was achieved by trial and error.)

$ \frac {r^2r'' \minus{} 2r(r')^2}{r^4} \equal{} \frac {1}{r} \minus{} \frac {K}{L^2}$

$ \left(\frac {r'}{r^2}\right)' \equal{} \frac {1}{r} \minus{} \frac {K}{L^2}.$

And now the final adjustment. Let $ s \equal{} \frac1r.$ Note that $ s' \equal{} \frac { \minus{} r'}{r^2}$ so that $ s'' \equal{} \minus{} \left(\frac {r'}{r^2}\right)'.$ We have

$ \minus{} s'' \equal{} s \minus{} \frac {K}{L^2}$

$ s'' \plus{} s \equal{} \frac {K}{L^2}.$

This is now a very familiar differential equation - the equation of simple harmonic motion, offset by a constant. We can write the solution in amplitude-phase form as

$ s \equal{} \frac {K}{L^2}(1 \plus{} e\cos(\theta \minus{} \delta))$ where the amplitude $ e$ and the phase $ \delta$ will be determined by the initial conditions. Take reciprocals to get that
\[ \boxed{r \equal{} \frac {L^2}{K}\,\frac {1}{1 \plus{} e\cos(\theta \minus{} \delta)}}
\]
Thus the path of planetary motion is a conic section. $ e \equal{} 0$ is a circle, $ 0 < e < 1$ is an ellipse with the center at one focus, $ e \equal{} 1$ is a parabola with the center at the focus, and $ e > 1$ is a hyperbola with the center at one focus. All are possible solutions; which one applies depends on initial conditions.

A further computation, assuming the path is an ellipse:

In the boxed formula above, choose your axes so that $ \delta\equal{}0.$ The minimum value of $ r$ is then $ \frac{L^2}{K}\,\frac1{1\minus{}e}$ and the maximum value of $ r$ is $ \frac{L^2}{K}\,\frac1{1\plus{}e}.$ These are the ends of the major axis. Add these $ r$ values to get that the length of the major axis is $ \frac{L^2}{K}\,\frac{2}{1\minus{}e^2}.$ (I am assuming that $ e<1.$)

To find the minor axis, we must find the maximum value of $ y\equal{}r\sin\theta\equal{}\frac{L^2}{K}\,\frac{\sin\theta}{1\plus{}e\cos\theta}.$ This is a fairly routine optimization problem, and we get that the length of the minor axis is $ \frac{L^2}{K}\,\frac{2}{\sqrt{1\minus{}e^2}}.$

The area of an ellipse is $ \pi$ times the product of half the major axis and half the minor axis. In other words, the area is $ \frac{L^4}{K^2}\,\frac{\pi}{(1\minus{}e^2)^{3/2}}.$

The rate at which the planet sweeps out area is given by $ \frac{1}{2}\,r^2\dot{\theta}.$ But we know that this is constant, and equals $ \frac{L}{2}.$ Hence, if $ T$ is the orbital period,

$ \frac12LT\equal{}\frac{L^4}{K^2}\,\frac{\pi}{(1\minus{}e^2)^{3/2}}.$

$ T\equal{}\frac{2\pi L^3}{K^2(1\minus{}e^2)^{3/2}}.$

This is proportional (with a constant of proportionality that depends on $ K$) to the $ 3/2$ power of the length of the major axis - which is another of Kepler's laws.

The crowning achievement of Newton's [i]Philosophae naturalis principia mathematica[/i] was his demonstration (in different language than what I've done here) that Kepler's laws of planetary motion could be derived from the assumption of Newton's laws of motion and universal gravitation with an inverse square law.

I believe the Spivak "Calculus" book goes through some sort of derivation, and my vector calc book derives Kepler's Laws.


$1-\frac{1}{2}+\frac{1}{3}-\frac{1}{4}+........+\frac{1}{2005}-\frac{1}{2006}=\frac{1}{1004}+\frac{1}{1005}+.......+\frac{1}{2006}$

Then, genralize it!

Oooopsie, i don't think this is pre-olympiad, i miss clicked on it  :mad: .However does anybody have a proof?

i believe that problem is called [b]the catalan's identity[/b]. there was similar problem proposed on the forum (just different numbers)
i have no time now, but in the evening if this problem remains unsolved and/or if you don't find that problem in previous topics, i'll try to do it.


geometry
perimeter
calculus
trigonometry
integration
analytic geometry
probability

A semicircle has $O$ as its diameter midpoint and radius $1$.

Two points $P_1$ and $P_2$ are randomly and independently picked on the perimeter of the semicircle, including its diameter. Let $\triangle$ denote the area of triangle $OP_1P_2$.

What is the expected value of $\triangle$?

this seems to need calculus,

Clearly the first point is independent of the second one, so we say that $P_1$ is fixed. The other point can be anywhere on the circle with uniform distribution in terms of arc length or angle. Since the circle is symmetric, consider only one half of the circle that is divided by diameter $OP_1$. The area of the triangle is:

$\[ \frac{1}{2}*\sin\theta$

by the sine area formula where $0\le \theta \le \pi$.

Then the expected value is just the average of the areas. We can easily do that using integrals.

$\frac{1}{b-a}\int_{a}^bf(x) \, dx$

$\frac{1}{2\pi}\int_0^\pi \sin x \, dx$

$\frac{-\cos\pi+\cos 0}{2\pi}=\frac{1}{\pi}$

nice i didnt even think about using calculus...i was trying to use "basic" geometry and such (didnt work).  :)

The answer changes depending on how the points are randomly selected.

Method 1:  Select a random $x$-coordinate, then pick one of the two viable $y$-coordinates.

Method 2:  Place the center of the circle at the origin of a polar coordinate system, and select a random $\theta$.  (Altheman's solution)

You can clearly see that these two methods give different distributions and hence a different answer.

Altheman: You forgot that the points can lie on the diameter.

[quote="t0rajir0u"]The answer changes depending on how the points are randomly selected.[/quote]

Although it should have been specified, selecting a point "randomly" on a curve usually means you choose by arclength -- the point has a probability $p$ of landing on any arc which is $p$ of the total arclength.


Siv bought 12 dozen tapes at $ \$24$ per dozen. There were 18 damaged tapes in the box which Siv could not sell. Siv sold the remaining tapes at 3 for $ \$8$. What was her percent profit? Express your answer as a decimal, rounded to the nearest tenth.

Siv payed $ 24 \times 12 \equal{} 288$ dollars. 18 were damaged, so Siv could only sell 126, and so she made $ 126 \div 3 \times 8 \equal{} 336$. The percent profit was:

$ \frac {336 \minus{} 288}{288} \approx \boxed{16}$ percent.

the question asked for the nearest tenth, so our answer would be 16.7


nintey nine girls and one boy are in a mathematics class.  how many girls have to leave the room so the the percentage of girls becomes 98%?

[hide]50 girls have to leave. Obviously, you can't have a part of a girl, and so the ways to make 98% girls are 98/100 (not possible), and 49/50. After that you can't divide both by the same #, because 49 and 50 are relatively prime. So you have to get rid of 50 people. The 1/50 (1) would be the boy, and the 49/50 (49) would be the girls.  :)

I feel sorry for that guy.  :) [/hide]

[hide]
50 girls because 49/50=98%.
[/hide]

proportions! :-)
[hide]
So you set up the ratio of g:b where g= the number of girls and b=the number of boys
Then you have 98:2 or 49:1. <-(hint: there's the answer). Here's the proportion.

$\frac{g}{b} = \frac{49}{1}$

$g = 49b$

There we go. There will be 49 girls, but we didnt answer the question yet.
99-49 = [b]50 girls. There's your answer.[/b][/hide][/b]

[hide][color=indigo]one boy has to equal 2%, so that means there would have to be 50 people total. [/color][color=green]50[/color] [color=indigo]girls have to leave.[/color][/hide]


algebra
polynomial
induction
superior algebra
superior algebra unsolved

[quote="ficsur"]Let $ k \subset K$ be an algebraic field extension such that both fields are inside the field of complex numbers. If every nonconstant polynomial from $ k[X]$ has a root in $ K$, prove that $ K$ is algebraically closed.[/quote]

Every element of $ K$ is algebraic in $ k$. Consider a polynomial $ p$ in $ K[X]$, then it's a polynomial in $ k(a_1 \dots a_n)[X]$ where $ a_1 \dots a_n$ are the coefficients of $ p$ and $ k \subseteq k(a_1 \dots a_n)$ is algebraic. If $ \alpha$ is a root of $ p$ then $ k(a_1 \dots a_n) \subseteq k(a_1 \dots a_n)(\alpha)$ is an algebraic extension and so $ k \subseteq k(a_1 \dots a_n, \alpha)$ is algebraic and there exist a polynomial in $ k[X]$ that have $ \alpha$ as a root.

So how does this make $ K$ algebraically closed?

He just showed that every element algebraic over $ K$ is algebraic over $ k$ and so contained in $ K$.  (This last deduction is just a little bit of induction using the given in the second sentence.)

Sorry, but I still don't get it. Can you be a bit more elaborate?

If every element algebraic over $ K$ is in $ K$, then that means given any polynomial with coefficients in $ K$, say $ P(X)$, all its roots (which are algebraic over $ K$) are in $ K$. This is the definition of $ K$ being algebraically closed.

I understand that $ \alpha$ is algebraic over $ k$. That is fairly easy. But that does not mean that $ \alpha$ is in $ K$. It only means that the minimal polynomial of $ \alpha$ has a root in $ K$. That is $ k(\beta) \subset K$ where $ k(\beta)$ is isomorphic to $ k(\alpha)$. That does not mean that $ k(\beta) \subset K$.  :(

It also follows that all polynomials in $ k[x]$ split in $ K$. If we have a polynomial $ p \in k[x]$, then it has a root $ \alpha \in K$, so we can factor it as $ (x\minus{}\alpha)q(x)$ in $ K[x]$. Using a similar argument, we can show that $ q(x)$ has a root in $ K$ and then continue.

calc rulz: What "similar argument"¿

Like ficsur, I don't see any concise and working argument, just some standard facts about algebraic extensions. This problem was posted before (but I cannot find it) and it wasn't completely trivial.


Có bạn nào biết cách gõ latex trên forum này không?Mình quen gõ trên http://www.diendantoanhoc.net rùi,bây giờ thấy lạ quá :lol:

Trịnh Lưu Ly_Triệu Gia Yến :blush:

Trên ddth em dùng

[code][text] công thức[/tex][/code]
thì trên mathlinks em dùng

[code]$công thức$[/code]

Chúc vui vẻ trên trang. :D

[quote="Jumong4958"]anh ơi, thế gõ chỉ số dưới ( ví dụ dãy số un) thì gõ thế nào để nó ra chỉ số n ???[/quote]
Về code thì ở đâu cũng giống nhau hết. Nếu bạn chưa rõ hết công thức thì có thể vào đây http://www.codecogs.com/latex/eqneditor.php gõ rồi copy code sang ML, đặt vào giữa 2 ký tự $

Bây giờ cách gõ $\LaTeX$ bên diendantoanhoc.net và artofproblemsolving.com là như nhau, đều kẹp bởi
[code]$công thức$[/code]

[quote=thanhnam2902]Lúc đầu tôi cũng gặp khó khăn trong việc gõ công thức. Đây là những kinh nghiệm của tôi về gõ công thức Toán trên http://www.mathlink.ro. Xin chia sẻ cho các bạn. Nếu có gì sai sót mong bạn thông cảm.[/quote]

Anh từng học ở thầy Phạm Văn Quý trường chuyên à anh ?