vacant catastrophe @vacantcatastrophe - Tumblr Blog

Dividing d-Dimensional Space with Hyperplanes

We consider the problem of dividing $ \mathbb{R}^d $ into as many regions as possible, using $ n $ $ d-1 $ dimensional hyperplanes. We denote the maximum number of regions achievable by $ P^d(n) $. We’ll go up to dimension 3 because that’s where it gets interesting.

Dimension $ 1 $ is simply a line with $ n $ points along it. All configurations of points are equally good, and we get that the line is divided into \[ P^1(n) = n + 1 \] segments.

Dimension $ 2 $ is the plane, $ \mathbb{R}^2 $, divided by $ n $ lines. One can easily work out that $P^2(1) = 2, P^2(2) = 4 $ and $ P^2(3) = 7 $. To find the general formula we consider the problem of adding an $n^{th} $ line to $ n-1$ lines. The goal is to divide the $n^{th} $ line into as many segments as possible (with the other lines) because each segment corresponds to an old region being split into $2 $. Of course each pair of lines can cross at most once (and will cross exactly once so long as our lines are in general position) so the $n^{th} $ line is divided into $ n $ segments (note this is the dimension 1 problem). Thus \[P^2(n) = n + P^2(n-1) = P^1(n-1) + P^2(n-1). \]

Dimension $3 $ is $ \mathbb{R}^3 $, divided by $n $ planes. We see that $ P^3(1) = 2, P^3(2) = 4 $ and $ P^3(3) = 8 $. Again, to work out the general formula we consider the problem of adding an $n^{th} $ plane to $n-1$ planes. Maximizing the number of regions added is now equivalent to maximizing the number of regions the new plane is divided into by the lines of intersection of it with the previous planes. But this is exactly $ P^2(n-1) $. Thus we have \[ P^3(n) = P^2(n-1) + P^3(n-1). \]

#geometry

•18+ Adults Only

Watch Anya Live on Cam

Anya is live and ready to show you everything. Watch her strip, dance, and perform exclusive shows just for you. Interact in real-time and make your fantasies come true.

✓ Live Streaming✓ Interactive Chat✓ Private Shows✓ HD Quality

Anya is LIVE right now

FREE

Free to watch • No registration required • HD streaming

#reading list

Generating Functions Are the Chillest Part I

Question: Given any set $A= \{a_1,...,a_n \} $ of integers such that no two subsets have equal sum, what is the maximum possible value of $ \sum_{i=1}^n \frac{1}{a_i} $?

Answer: 2. Actually, it’s strictly less than 2.

Proof.

The brilliant part is the first step, encapsulating our assumption on $ A$ in a generating function. Let $0 < x < 1$ and note that:

\[ \prod_{i=1}^n (1 + x^{a_i}) < \sum_{n=0}^\infty x^n = \frac{1}{1-x}. \]

Thus taking logarithms and dividing by $ x$ (because both are monotonic and respects the inequality) we see:

\[ -\sum_{i=1}^n \sum_{n=1}^\infty \frac{(-1)^n x^{a_i n-1}}{n} = \sum_{i=1}^n \frac{\log(1+x^{a_i})}{x} < - \frac{\log(1-x)}{x} = \sum_{i=1}^\infty \frac{x^{n-1}}{n} .\]

Now, this looks ugly, but we integrate both sides, because the integral of the right hand side is actually something nice. Well, provided you put the integral inside the sum first, but this is legal thanks to the MCT. We find:

\[- \sum_{i=1}^n \sum_{n=1}^\infty \int_0^1 \frac{(-1)^n x^{a_i n}}{nx} dx < \sum_{i=1}^\infty \int_0^1 \frac{x^{n-1}}{n} dx ,\]

and so (changing $ x^{a_i} = y$ and $a_i x^{a_i-1} dx = dy$):

\[- \sum_{i=1}^n \sum_{n=0}^\infty \int_0^1 \frac{(-1)^n y^{ n} }{n y a_i} dy < \sum_{i=1}^\infty \frac{1}{n^2} = \frac{ \pi^2}{6},\]

\[- \sum_{i=1}^n \frac{1}{a_i} \left(\sum_{n=0}^\infty \frac{1 }{(2n)^2} - \sum_{n=0}^\infty \frac{1 }{(2n+1)^2} \right) < \frac{\pi^2}{6} ,\]

\[- \sum_{i=1}^n \frac{1}{a_i} \left(\frac{\pi^2}{24} - \frac{\pi^2}{8} \right) < \frac{\pi^2}{6} ,\]

\[ \sum_{i=1}^n \frac{1}{a_i} < 2 . \blacksquare \]

#generating functions #fav

Calculating the Divisor of a Line

Let our elliptic curve $C$be defined by $y^2 = x^3 + cx +d$. We calculate the divisors $(y-ax-b)$and $(x-c)$in terms of the intersection points which we will label $P, Q, R$(so that $\ominus R = P \oplus Q$).

There are a couple of ways we could approach this, possibly the shortest route would be found by computing the order of $y-ax -b$at $\mathcal{O} = [0 : 1 : 0]$to be $-3$, then using that a principal divisor has degree zero, and that each of the three intersection points, $P, Q, R$have order at least $1$so that overall $(y - ax -b) = 1 (P) + 1 (Q) + 1 (R) - 3 ( \mathcal{O})$.

Computing the order at infinity is quick if we use that one of the coordinate functions must be a uniformizer there. We consider our curve in projective space and then map to the affine patch containing $\mathcal{O} = [0 : 1 : 0]$. There $C$is defined by $Z = X^3+cXZ + dZ^3$, our line becomes $1 = aX + bZ$and $\mathcal{O} = (0,0)$(using the transformation $X = x/y, Z = z/y$). Then we know one of $X$or $Z$is a uniformizer, and it is just a matter of determining which has the lower order. We have $Ord_\mathcal{O}(Z) \geq \min\{ 3 Ord_\mathcal{O}(X), Ord_\mathcal{O}(X) + Ord_\mathcal{O}(Z), 3 Ord_\mathcal{O}(Z) \} $ with equality if the minimum is unique. If we assume that the minimum is not unique then $Ord_\mathcal{O}(Z) \neq 0$implies $Ord_\mathcal{O}(Z) < 3 Ord_\mathcal{O}(Z)$so the minimum must be $3 Ord_\mathcal{O}(X) = Ord_\mathcal{O}(X) + Ord_\mathcal{O}(Z)$. But then $2 Ord_\mathcal{O}(X) = Ord_\mathcal{O}(Z) \geq 3 Ord_\mathcal{O}(X) $, a contradiction because $Ord_\mathcal{O}(X) \neq 0$. Thus the minimum is unique and to avoid a contradiction must be $3 Ord_\mathcal{O}(X)$. Thus $X$is the uniformizer and $Z$order $3$. Back in projective coordinates this implies $Ord_\mathcal{O}(x/y) = 1$and $Ord_\mathcal{O}(z/y) = 3$and so in our original affine patch ($z=1$) $Ord_\mathcal{O}(y) = -3$and $Ord_\mathcal{O}(x) = 1$and $Ord_\mathcal{O}(y - ax -b) = \min\{ -3, 1\} = -3$.

Okay, that was slightly longer than the author expected once written down. And there is more to follow (readers are advised to proceed at their own risk).

Let $P = (\alpha, \beta)$be an intersection point of $y = ax + b$and $C$.

\textbf{Case 1 $\beta \neq 0$:} We first show that $x - \alpha$is a uniformizer. To see this expand $y^2 = x^3 + cx + d = C_0 + C_1(x- \alpha) + C_2(x - \alpha)^2 + C_3(x - \alpha)^3$. Then evaluating at $(\alpha, \beta)$we see $\beta^2 = C_0$, and so can rearrange $(y - \beta)(y + \beta) = y^2 - \beta^2 = C_1 (x - \alpha) + C_2 (x-\alpha)^2 + C_3(x - \alpha)^3$. Because $\beta \neq 0$, \(y + \beta \( is a unit and we have

$$(y - \beta) = \frac{C_1 (x - \alpha) + C_2 (x-\alpha)^2 + C_3(x - \alpha)^3}{(y + \beta) }.$$

Clearly the right hand side is contained in $\langle x - \alpha \rangle$. Thus the maximal ideal of $\mathcal{O}_{C,P}$, a priory generated by $\langle y - \beta, x - \alpha \rangle$may in fact be written $\langle x - \alpha \rangle$, implying $(x - \alpha)$is a uniformizer.

Given this we can compute:

$$ (y - ax -b) (-y -ax -b) $$

$$ = -y^2 +a^2x^2 + 2abx + b^2 $$

$$ = a^2 x^2 + 2 a b x + b^2 - c x - d - x^3 $$

$$ = (b^2 - d + 2 a b \alpha - c \alpha + a^2 \alpha^2 - \alpha^3) + (2 a b - c + 2 a^2 \alpha - 3 \alpha^2) (x - \alpha) $$

$$ \hspace{8cm} + (a^2 - 3 \alpha) (x - \alpha)^2 - (x - \alpha)^3 $$

$$ = (x - \alpha)\left[(2 a b - c + 2 a^2 \alpha - 3 \alpha^2) + (a^2 - 3 \alpha) (x - \alpha)- (x - \alpha)^2 \right].$$

Where we have used in the last line that $b^2 - d + 2 a b \alpha - c \alpha + a^2 \alpha^2 - \alpha^3 = (a\alpha + b)^2 - \alpha^3 - c \alpha^2 - d = \beta^2 - \beta^2 = 0$. Note that $-y - a x - b$is a unit (using our assumption $\beta \neq 0$). Suppose that $y = ax + b$is not tangent to $C$, in this case the reader can confirm (by taking a derivative) that $2 a b - c + 2 a^2 \alpha - 3 \alpha^2 \neq 0$must hold. Thus:

$$u(x,y) : = \frac{\left[ (2 a b - c + 2 a^2 \alpha - 3 \alpha^2) + (a^2 - 3 \alpha) (x - \alpha)- (x - \alpha)^2 \right]}{(-y -ax -b) }$$

is a unit in $\mathcal{O}_{C, P}$. And we have $(y - ax -b ) = u(x,y) (x - \alpha)$, giving us $ord_P(y - ax - b) = 1$as expected.

Alternatively, if we allow $y = ax + b$to be tangent, we see $2 a b - c + 2 a^2 \alpha - 3 \alpha^2 = 0$and so

$$(y - ax -b ) = (x- \alpha)^2 \frac{\left[ (a^2 - 3 \alpha) - (x - \alpha) \right]}{(-y -ax -b) }.$$

If $a^2 \neq 3 \alpha $ we have that $ord_P(y-ax-b) = ord_P((x-\alpha)^2) = 2$, else $ord_P(y-ax-b) = ord_P((x-\alpha)^3) = 3$. In the first case we know (because $deg(Div(y-ax-b)) = 0$) that $y-ax-b$meets $C$at two distinct points, $P, R = \ominus(P \oplus P)$, while in the second case all three of our intersection points are in fact the same point, $P$.

\textbf{Case 2 $\beta = 0$:} We claim that $y$is a uniformizer, and $x - \alpha$has order $2$. Since $\alpha^3 + c \alpha + d = 0$our taylor expansion loses its constant term: $y^2 = C_1 (x-\alpha) + C_2 (x - \alpha)^2 + C_3 (x - \alpha)^3 = (x-\alpha) \left[ C_1 + C_2 (x - \alpha) + C_3 (x - \alpha)^2 \right]$. Note $C_1 \neq 0$else our cubic is singular - thus the $C_1 + C_2 (x - \alpha) + C_3 (x - \alpha)^2$factor is a unit, so that:

$$(x - \alpha) = y^2 / (C_1 + C_2 (x - \alpha) + C_3 (x - \alpha)^2). $$

Since the maximal idea of $\mathcal{O}_{C,P}$was generated by $\langle y, x- \alpha \rangle$, and we have just seen $x - \alpha \in \langle y \rangle$, we have that $y$is in fact a uniformizer, while $2 \cdot ord_{P} (y) = ord_{P} (x- \alpha) + 0$implies the order of $x - \alpha$is $2$.

Given this, we write $y - ax - b = y - a(x - \alpha)$(using that $\alpha a + b = 0$). Thus $ord_{P}(y - ax - b) = \min \{ ord_{P}(y), ord_{P}(x-\alpha)\} = 1$(using that the minimum is achieved when the two orders are distinct).

Thus we have found that for an intersection point $P$, $ord_{P}(y - ax - b) = 1, 2, $ or $3$depending on if $y = ax + b$is tangent to $C$at $P$. Noting that a principal divisor has degree zero, and $\mathcal{O}$the only possible pole, we see then that $(y - ax - b) = 1 (P) + 1 (Q) + 1 (R) - 3 (\mathcal{O})$, where $P, Q, R$may in fact be the same point in some cases (in which case $(y - ax - b) = 2 (P) + 1 (R) - 3 (\mathcal{O})$or $3 (P) - 3 (\mathcal{O})$).

\textbf{Vertical line case: $x - r_x$}. Yes dear reader, believe it or not, we have still not even answered the whole question. Luckily in this case much of our previous work applies. Here we are supposing our third intersection point $Q = (r_x, r_y)$, and to begin with we will assume $r_y \neq 0$. Then the derivations from Case 1 above apply and we have that $x - r_x$is a uniformizer, thus $Ord_R(x-r_x) = 1$. By the same argument $\ominus R = (r_x, -r_y)$has identical uniformizer $x-r_x$, so $Ord_{\ominus R}(x-r_x) = 1$. Because these are the only two intersection points, and $\mathcal{O}$the only possible pole, we have $(x - r_x) = 1 (Q) + 1 (\ominus Q) - 2 (\mathcal{O})$.

If we assume $r_y = 0$, then the derivations of case $2$apply and we have $ord_R(x-r_x) = 2$. Note also that $R = \ominus R$, and so there is only one intersection point and we have $(x - r_x) = 2 ( R ) - 2 (\mathcal{O})$.

#mathematics #elliptic #curve #divisor #algebraic geometry

Zeroing a board

Suppose you have an nxm board of integers, the entries may be positive or negative. You can modify the board by adding or subtracting 1 from any pair of adjacent squares (horizontally or vertically - no diagonals). That is, if I add 1 to the upper left hand corner, 0x0, I must add 1 to either 1x0 or 0x1 as well. Is it possible to zero the baord?

Image the board coloured as a checkerboard, roughly half the squares black and half white. We will show that the boad can be zero'd iff and only if the sum of black squares equals the sum of white squares. Note first that each operation either adds 1 to both the black-square-sum and the white-square-sum, or subtracts 1 from both. Thus reaching all zeros is only possible if both sums start out equal. The condition is sufficient as well. To see this note that addition and subtraction opertations can be chained so that +1 (or -1) can be added to any pair of black/white squares, or chained so that +1 is applied to one black (white) square, and -1 to another black (white) square. That these operations can be used to develop a zeroing algorithm is left as an exercise for the reader :)

#checkerboard #board

•18+ Adults Only

Watch Anya Live on Cam

Anya is live and ready to show you everything. Watch her strip, dance, and perform exclusive shows just for you. Interact in real-time and make your fantasies come true.

✓ Live Streaming✓ Interactive Chat✓ Private Shows✓ HD Quality

Anya is LIVE right now

FREE

Free to watch • No registration required • HD streaming

Sums of Combinations

We all know:

\[ \sum_{k=0}^n {n \choose k} = 2^n \] as the right side counts all subsets of an $ n $-element set and the left adds up the number of subsets of size $k=1$ to $k=n$. But why does

\[ \sum_{k=0}^n k {n \choose k} = n 2^{n-1} \] hold? This can be seen by a similar argument: the right side counts the number of ways of choosing a single element of the $n$-element set, call it $ x$, and then choosing a subset not containing $x $. The left meanwhile adds up, for each $k \in \{ 0...n \} $, the number of choices of subset of that size, times the number of choices for $x $, if $x $ were then taken and removed from the subset. In either case the end result is the same.

#babies

We count the number of subsets of an $n$ element set with cardinality divisible by prime $p$.

For each $0 \leq kp \leq n$, we add the number of subsets of that size to our total:

\[ \sum\limits_{k=0}^{kp \leq n} {n \choose kp} \overset{*}{=} \sum\limits_{j=0}^n {n \choose j} \left[ \frac{1}{p} \sum\limits_{m=0}^{p-1} e^{(2\pi i) j m / p } \right] \] \[ =\frac{1}{p} \sum\limits_{m=0}^{p-1} \sum\limits_{j=0}^n \left[ {n \choose j} e^{(2\pi i) j m / p } \right] =\frac{1}{p} \sum\limits_{m=0}^{p-1} (1 + e^{(2 \pi i) m / p})^n \] \[ =\frac{1}{p} \sum\limits_{m=0}^{p-1} (e^{-(\pi i) m /p} + e^{(\pi i) m / p})^n(e^{(\pi i) m n / p}) \] \[= \frac{1}{p} \sum\limits_{m=0}^{p-1} (2 \cos(\pi m / p))^n(e^{(\pi i) m n / p}) \] \[= \frac{1}{p} \left[ \sum\limits_{m=1}^{(p-1)/2 } 2^{n+1} \cos^n(\pi m / p) \cos(\pi m n / p) \right] + \frac{2^n}{p} \]

$* \frac{1}{p} \sum\limits_{m=0}^{p-1} e^{(2\pi i) j m / p } = 1 $ if $ p \mid j$ and 0 otherwise. For the suspicious reader: this is because $p \mid j \rightarrow j m / p \in \mathbb{Z}$ and $2 j m /p$ even so that each $e^{(2\pi i) j m / p } = 1$. Meanwhile if $p \nmid j$ then $e^{(2\pi i) j / p } \neq 1$ and we may sum the geometric series $ \sum_{m=0}^{p-1} (e^{(2\pi i) j / p})^m = (e^{(2\pi i) j } -1)/(e^{(2\pi i) j / p } -1) = 0 $.

#counting

1985 Putnam, A2

Let $T$ be an acute triangle. Inscribe a pair $R, S$ of rectangles in $T$ as shown:

Let $ A(X) $ denote the area of polygon $ X $. Find the maximum value, or show that no maximum exists, of $ \frac{A(R)+A(S)}{A(T)} $, where $ T $ ranges over all triangles and $ R, S $ over all rectangles as above.

We solve by a series of reductions. First I claim a right triangle, eg:

is sufficient. To see this note that any other triangle (such as the first triangle above) could be split down its vertical, then if the two halves to do not have identical ratios it would be better to throw away the side with the smaller ratio entirely - leaving us with a right triangle. Secondly, I claim the right triangle might as well be isosceles. If it were not, say the vertical arm was some factor $ \alpha $ longer than the base arm, then there exists an isosceles triangle with the height of the triangle and heights of the rectangles scaled down equally. Note that this isosceles triangle will then have the same ratio (because all areas have been scaled by the same amount) as the first one. Thus it is sufficient to consider only isosceles right triangles in our quest for the greatest ratio. Now given that our triangle is so symmetrical we are free to reflect it along its diagonal and create a square:

We are interested in the white area to total area ratio (minimizing it will maximize the non-white to total ratio). Before we begin, note that the white rectangles are in fact white squares since the diagonal of an isosceles triangle runs at a 45 degree angle.

First we will solve a simpler case, a $1 \times 1$ square with only 2 white squares contained within:

In this case there is only one free parameter to choose (ie. the height of the lower white square determines everything else). Lets call this $ c $, then the white area is $ c^2 + (c-1)^2 $ and we are interested in minimizing the ratio of this over the size of the whole square, 1. After a moment of calculus we see this occurs at $ c = 1/2 $. At this point the white area is $ (1/2)^2 + (1/2)^2 = 1/2 $. So the largest possible ratio of non-white area to total is then $ 1/2 $, in this case.

Now we put this solution back into the larger picture. Note that the upper two white squares live in a square (call it $B$ ) within our outer square - and of course we'll want to maximize the non-white space within $ B $ as doing so has no effect on the remaining white square. The only parameter it remains to pick then is the ratio of larger outer square that $ B $ takes up. So let the base of $ B $ be $ x $. Then the total white area is the area from $ B $ plus that of the 3rd white square: $ x^2/2 + (1-x)^2 $, and again after some calc we see this is minimized at $ x = 2/3$. So Then white has area $ (2/3)^2/2 + (1/3)^2 = 1/3 $ leaving us a maximal area (ratio) of $2/3$. $ \blacksquare $

#geometry #Putnam #triangle #A2

1985 Putnam, A1

Determine, with proof, the number of ordered triples $ (A_1, A_2, A_3) $ of sets which have the properties: (i) $A_1 \cup A_2 \cup A_3 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} $, and (ii) $ A_1 \cap A_2 \cap A_3 = \emptyset $. Express the answer in the form $2^a 3^b 5^c 7^d $, where $ a, b, c, $ and $ d $ are nonnegative integers.

Note that we are allowed pair-wise non-empty intersections, just no elements shared by all three. So we count.

First we choose the non-overlapping sections of $ A_1$ and $ A_2 $ (note that this then determines the non-overlapping section of $ A_3 $, and then choose the overlap between all pairs:

For each possible $ A_1 $: count all possible $A_2 \cap A_1^c $: and, given that, each possible $ A_2 \cap A_1 $, and each possible $ A_3 \cap A_1 $ and finally, every possible $ A_3 \cap A_2 $, given the previous choices. This looks like: $ \sum_{k=0}^{10} {10 \choose k} [ \sum_{j=0}^{10-k} {10 - k \choose j} [ \sum_{i=0}^k { k \choose i} [ \sum_{l=0}^{k-i} {k-i \choose l} [ \sum_{m=0}^j { j \choose m } ]]]] $ $ = \sum_{k=0}^{10} {10 \choose k} [ \sum_{j=0}^{10-k} {10 - k \choose j} [ 2^{k-j} [ 2^j ]] $ $ = \sum_{k=0}^{10} {10 \choose k} [ 3^{10}] = 2^{10} 3^{10} $.

By the way, no there is apparently no known closed form expression for the number of ways to sort $ n $ labelled things into $m $ labelled buckets. Luckily there were only 3 buckets here.

#babies

Quadratic residues

We let $ N = p_1 ... p_n $ where the $ p_i $ are distinct odd primes. We will prove that there are $ \frac{1}{2^n}\Pi_{i=1}^n (p_i + 1) $ distinct quadratic residues mod $ N $.

Lemma: $ \alpha $ is a quadratic residue mod $ N $ iff $ \alpha $ is a quadratic residue mod $ p_i $ for all $ i $ in $ 1,..., n $. Proof: $ \Rightarrow $ if $ \alpha \equiv x^2 \pmod{N} $ then $ \alpha \equiv x^2 \pmod{p_i} $ just because $ p_i \vert N$.

$ \Leftarrow $ suppose $ \exists x_i $ for all $ i $ s.t. $ \alpha \equiv x_i^2 \pmod{p_i} $. Then, by the CRT, there exists unique ( mod $ N $ ) $ y $ s.t. $ y \equiv x_i \pmod{p_i} $ for all $ i $. But then $ y^2 \equiv x_i^2 \equiv \alpha \pmod{p_i} $ for all $ i $, and so $ y^2 \equiv \alpha \pmod{N} $ as well (again by CRT). And so $ \alpha $ a quadratic residue in $ \mathbb{Z}/N\mathbb{Z} $.

Now we count. By the above, and since each $ x \in \mathbb{Z}/N\mathbb{Z} $ corresponds to precisely one set of modulos by the $ p_i $ (ie. $ \{ x \pmod{p_1}$, through to $x \pmod{p_n} \} $) by CRT, the number of distinct quadratic residues mod $ N $ is exactly the number of elements in $\{ (\alpha_1, ..., \alpha_n) | \alpha_i = x_i^2 \pmod{p_i} \} $. Since the number of quadratic residues in $ \mathbb{Z}/p_i\mathbb{Z} = (p_i + 1)/2$ this gives us $ \Pi_{i=1}^n \frac{p_i + 1}{2} = \frac{1}{2^n}\Pi_{i=1}^n (p_i + 1) $ in total.

#quadratic residue #number theory #prime #combinatorics

•18+ Adults Only

Watch Anya Live on Cam

Anya is live and ready to show you everything. Watch her strip, dance, and perform exclusive shows just for you. Interact in real-time and make your fantasies come true.

✓ Live Streaming✓ Interactive Chat✓ Private Shows✓ HD Quality

Anya is LIVE right now

FREE

Free to watch • No registration required • HD streaming

Exercise 6.1

Six musicians gathered at a music festival. At each concert some musicians played in the concerts while the others listened, as part of the audience. What is the least number of concerts needed to be scheduled in order that each musician may listen, as part of the audience, to every other musician.

Full disclosure: I still don't know what TT means by the 'point-scoring' hint he gives. I guess in a way you could call what I'm about to do scoring, but it's not as creative as I feel like point scoring usually is. So we are going to convert this problem into another shape - bear with me. Each concert selects a group of musicians as listeners. Note that each musician then sees every musician not in that group on the stage. Thus for a musician $ m $ to have seen every other on stage, they need to be in a set of groups $ G_m $ such that for every other musician, $ m' $ there is some $ g \in G_m $ s.t. $ m' \notin g $. Or equivalently, the intersection of groups containing $ m $ must only contain $ m $.

First a simpler case: one can quickly check that 3 musicians require 3 groups. Next we check that 4 musicians require 4 groups. First, a group of size 1 would reduce us to the 3 musician and 3 group case (giving us a total of 4 groups again), while using a group of size 3 would require the 3 musicians contained within to again be split with 3 groups (so 4 groups total). Meanwhile using only groups of size 2, and less than 4 groups would give us ( 4 musicians ) ( # average groups per musician ) = ( # groups ) ( 2 musicians per group ) < 8 $ \rightarrow $ # average groups per musician $ < 2 $, so there must be some musician with only 1 group, and then that group must be of size 1. A contradiction. So 6 musicians would require at least 4 concerts, and indeed it turns out this is sufficient. Given musicians labelled $ a $ through $ f $ we can use groups $ (a, b, f) $, $ (b, c, d) $, $ (d, e, f) $, $ ( a, c, e ) $. The reader can check the intersections work as desired. $ \blacksquare $

#TT #musicians #exercise 6.1

Taylor 1989, Q5

Suppose on some certain island there are 13 grey, 15 brown, and 17 crimson chameleons. If two chameleons of different colour meet, they both change to the third colour. This is the only time they change colour. Is it possible for all chameleons to eventually be the same colour?

So TT completely works out a solution in a personal perspective, but since my thoughts were at least superficially different I thought I'd add them here. I focus on the three deltas between colour-amounts ( # grey - # brown, # brown - # crimson, # crimson - #grey ). In the case of all chameleons a single colour the deltas would be (some permutation of) 0, 45 and 45. Now consider what our colour-changing operation does to the delta's. One colour will gain 2 chameleons, and another loses a chameleon - if that second colour had more chameleons to begin with the delta decreases by 3, and otherwise increases (by 3). The same applies to the other colour to lose a chameleon (and so the delta between that colour and the one to gain 2 chameleons is also $ \pm 3 $ ). Finally, since both lose exactly 1, the delta between chameleon-losing colours is unchanged. So delta's can only change by 3, if anything. But what do they start off as? 2, 2 and 4. Certainly there is no $ n \in \mathbb{Z} $ s.t. $ 2 + 3n = 0 $ ( or $ 4 + 3n = 0 $, or 45 for that matter. Thus no chameleon colour can ever completely obliterate the competition. $ \blacksquare $

#chameleon #taylor #1989 #tt

Find all solutions: $ x^p + y^q = y^r + z^p = z^q + x^r $.

Where $ x, y, z \in \mathbb{R}^+ $ and $ p, q, r \in \mathbb{Z}^+ $. Spent 2 weeks on this. Then discovered there was a missing "= 2", as in it's actually find all solutions to $ x^p + y^q = y^r + z^p = z^q + x^r = 2$. As in $ x = y = z = 1 $ (with whatever $ p, q, r $ you like) are the only solutions. As in the proof is just $ x > 1 \rightarrow y < 1 \rightarrow z > 1 \rightarrow x < 1 $. :C

#typos make me cry

IMO 1986 Question 5

Find all (if any) functions $ f $ taking the non-negative reals such that (a) $ f(y)f(xf(y)) = f(x + y) $ for all non-negative $ x, y $

(b) $ f(2) = 0 $

We know immediately $ f $'s behaviour outside of $ [0, 2) $: let $ y = 2 $ then (a) says $ f(2 + x) = f(2) f(x f(2)) = 0 \cdot f(x \cdot 0) = 0 $. ie. $ f $ is the zero function above 2. Next I claim $ f(x) \geq \frac{2}{2 - x} $ for all $ x \in [0, 2) $. This time let $ y \leq 2 $ and $ x = 2 - y $ in (a): $ f( y)f((2-y)f(y)) = f(2) = 0 $. But $ f(y) \neq 0 $ so it must be the case that $ (2-y)f(y) \geq 2 \rightarrow f(y) \geq \frac{2}{2-y}$.

Luckily, it turns out $ f(y) \leq \frac{2}{2 - y} $ as well. We assume not for contradiction: $ \exists y \in [0, 2) : f(y) > \frac{2}{2 - y} $. Note that $y \neq 0 $ since $ f(0) f(0 f(0)) = f(0 + 0) \rightarrow f(0) f(0) = f(0) \rightarrow f(0) = 1 = \frac{2}{2-0} $. Then given such an $ y $ we can find positive $ x < 2 $ such that $ x f(y) \geq 2 $ and yet $ x + y < 2 $. To see this let $ \alpha $ be such that $ f(y) = \alpha \frac{2}{2-y} $ and note that $ \alpha > 1 $. Then let $ x = \frac{2 - y}{\alpha} $ and we get: $ x \cdot f(y) = (\frac{2 - y}{\alpha}) (\frac{2}{2 - y} \alpha) = 2 $. Thus we have positive $ x, y $ s.t. $ 0 = f(y) f(x f(y)) = f(x+y) > 0 $. It remains to show that the function $f(y) = \frac{2}{2-y} $ (on $ [0,2) $ and zero elsewhere), but this is a matter of algebra with requirement (a) and left as an exercise to the tireless reader. $ \blacksquare $

#functions #imo #1986 #problem 5 #analysis

Australian Mathematics Competition 1984 p. 7

(stolen from TT's Solving Mathematical Problems: A Personal Perspective) Suppose $ f $ is a function on $ \mathbb{N} $ taking real values with the following properties:

(a) $ f(2) = 2 $ (b) $ f(mn) = f(m) f(n) $ (c) $ f(m) > f(n)$ if $m > n $ And the question is to find $ f(1983) $ but we're just going to find $ f $, of course. The claim is: $ f(x) = x$ $ \forall x \in \mathbb{N} $. This clearly holds on the powers of $ 2 $, by (a) and (b) (yes even $ 2^0 $, try $ f(2 \cdot 1) $ ). Now let $ k $ be any positive integer. Suppose, for contradiction, $ f(k) = k+\delta $ for some strictly positive $ \delta $. And finally, let $ x $ be a power of 2 satisfying $ k < x $. Then there exists$^{[1]}$ $ n, m $ such that $ k^n < x^m < (k+\delta)^n $, or equivalently $ k^n < x^m, $ and yet $ f(x^m) = x^m < (k+\delta)^n = (f(k))^n = f(k^n) $. So we have our contradiction with (c). By a symmetric argument $ \delta $ cannot be strictly negative, and so must be zero. $ \blacksquare $ [1] Just need $ m $ s.t. $ 2 \cdot x^m < (x + \delta)^m $ and this is certainly possible (check the limit). Then let $2^r $ be the largest power of 2 below $ x^m $, we have $x^m < 2^{r+1} < 2x^{m} < (x+\delta)^m $

#australian mathematics competition #1984 #p. 7

•18+ Adults Only

Watch Anya Live on Cam

Anya is live and ready to show you everything. Watch her strip, dance, and perform exclusive shows just for you. Interact in real-time and make your fantasies come true.

✓ Live Streaming✓ Interactive Chat✓ Private Shows✓ HD Quality

Anya is LIVE right now

FREE

Free to watch • No registration required • HD streaming

Putnam 2006 B2

Prove that, for every set $ X = \{ x_1,x_2,...,x_n \} \subset \mathbb{R} $, there exists a non-empty subset $ S $ of $ X $ and an integer $ m $ such that $ \mid m + \sum_{s \in S} S \mid \leq \frac{1}{n+1} $

Let $ \sigma_k = \{ \sum_{i=1}^k x_i \} $, where $ \{ z \} $ denotes the fractional part $ \{ z \} = z - \lfloor z \rfloor $ (note that this is greater than zero even for negative $ z $ ). Now, there are $ n+1 $ buckets of size $ \frac{1}{n+1} $ on $ [0,1] $, and each $ \sigma_k $ lies in one. Note that we are done if any lie in the first or last bucket, and so we assume otherwise. In that case we have $ n $ $ \sigma $'s, and $ n-1 $ buckets - two lie in one bucket. Suppose they are $ \sigma_i $ and $ \sigma_j $, then the set $ S = \{ x_{i+1}, ..., x_{j} \} $ must satisfy either $ \mid \{ \sum_{s \in S} s \} \mid \leq \frac{1}{n+1} $ (we never left the bucket, or else came around to it after some integer amount). And so in this case as well we are done. $ \blacksquare $

A highly related problem: given $ n+1 $ integers, there exists some subset whose sum is divisible by $ n $. The actors have changed, but the behaviours are identical, and the same proof works.

#Putnam #2006 #b2 #set

Putnam 2006 B1

Show that the curve $ x^3 + 3xy + y^3 = 1 $ contains exactly one set of points $ A, B, C $ forming the vertices of an equilateral triangle, and find its area.

This question is actually just factor-the-polynomial, in disguise. After plugging in a number of integers, you begin to suspect that the 'curve' may in fact consist of a straight line and single dot. Specifically the line $ x + y -1 = 0 $. This line can be a set of solutions iff it divides the original, and indeed long division gives us the decomposition \[ (x + y -1)(x^2 -xy + x + y +y^2 +1). \] Meanwhile applying the quadratic formula to our quotient gives us exactly one (real) solution: $ x = y = -1 $. Now we have the shape of the curve, the actual geometry is left as an exercise to the reader.

#Putnam #2006 #b1 #polynomial #factor

Trending Blogs

Last Seen Blogs

vacant catastrophe