Challenge Math Challenge - December 2018

[fresh_42]

@fresh_42 Re Problem 8:

For every case that two person can be in front of their card, the need to both be n steps away from their card, so when the turns exactly $n$ steps, their card will get in front of them.(n = 0~11)

Now, inorder for a counter example to exist, they each must have different steps away from their cards(The step from the cards are clockwise).
Starting from Mr.0, he can only sit right in front of his card(0).That's our first person.(Mr.n needs to sit n steps away from his card)
For Mr.1, he can only sit at 2;(He should sat on 1 if he follows the card)(The position here is relative,counting from the first guy's point which is 0.Clockwise.)
For Mr.2, he can only sit at 4;
For Mr.3, he can only sit at 6;
For Mr.4, he can only sit at 8;
For Mr.5, he can only sit at 10;
For Mr.6, he can only sit at 12,which is the same as 0, which Mr.0 already sat there.Therefore, a counter example to the problem does not exist.

This proof is kind of weird and hard to understand, but it should work.
View attachment 235466

I think you have all necessary arguments in your solution, well done!

Let me add the solution that is a bit more "mathematical". It doesn't differ from your thoughts, I just want to add it, as I think it's a bit shorter:

If we denote the distance of a guest to his expected seat by $\pi(n)-n$ for the given permutation (distribution guests - seats) $\pi \in S_{12},$ then the question is: Are there always two numbers $n,m$ such that for any $\pi \in S_{12}$ we have a cycle (rotation) $\sigma \in \mathbb{Z}_{12}$ such that $\sigma(\pi(n))-n=\sigma(\pi(m))-m\,?$ (If we have a rotation such that two guests have the same distance to their seats after the rotation, then there is also a rotation which will make this difference zero.)

Assume this is not the case. Then $\{\,\sigma(\pi(n))-n\,|\,0<n<13\,\} = \{\,1,2,\ldots ,12\,\} =: Set_{12}$ and $\sum_{k\in Set_{12}} k = \sum_{k=1}^{12} (\sigma(\pi(k))-k)=\sum_{k=1}^{12} (\pi(k)-k)=0\,.$ On the other hand is $\sum_{k\in Set_{12}} k= 78 \equiv 6 \operatorname{mod}12$ which cannot both be true.

 

[YoungPhysicist]

I think you have all necessary arguments in your solution, well done!

Let me add the solution that is a bit more "mathematical". It doesn't differ from your thoughts, I just want to add it, as I think it's a bit shorter:

If we denote the distance of a guest to his expected seat by $\pi(n)-n$ for the given permutation (distribution guests - seats) $\pi \in S_{12},$ then the question is: Are there always two numbers $n,m$ such that for any $\pi \in S_{12}$ we have a cycle (rotation) $\sigma \in \mathbb{Z}_{12}$ such that $\sigma(\pi(n))-n=\sigma(\pi(m))-m\,?$ (If we have a rotation such that two guests have the same distance to their seats after the rotation, then there is also a rotation which will make this difference zero.)

Assume this is not the case. Then $\{\,\sigma(\pi(n))-n\,|\,0<n<13\,\} = \{\,1,2,\ldots ,12\,\} =: Set_{12}$ and $\sum_{k\in Set_{12}} k = \sum_{k=1}^{12} (\sigma(\pi(k))-k)=\sum_{k=1}^{12} (\pi(k)-k)=0\,.$ On the other hand is $\sum_{k\in Set_{12}} k= 78 \equiv 6 \operatorname{mod}12$ which cannot both be true.

Though I can’t fully understand that,but it seems way better than “Mr.n”

 

[fresh_42]

Though I can’t fully understand that,but it seems way better than “Mr.n”

The trick is the same as yours:

If we cannot achieve at least two same distances, then all distances on the finite set $\{\,1,2,\ldots ,12\,\}$ have to occur. Then we sum them up twice, $1+2+ \ldots +12=78$, and sum over possible permutations. Both summations have to have the same remainder when divided by $12$, which is not the case.

I only encoded the difference a bit more explicitly: actual place (permutation of seats $\pi(n)$) minus expected place ($n$) and wrote the rotation of the table as another special permutation (cycle $\sigma$).

A cycle is a permutation that shifts numbers. In general $\sigma = (n_1\,n_2\,\ldots\, n_k)$ means $n_1 \mapsto n_2 \mapsto n_3 \mapsto \ldots \mapsto n_{k-1} \mapsto n_k \mapsto n_1$. Here we have a cycle where $n_i=n_{i-1}+k$ for a certain fixed number $k$ and $\{\,n_i\,\}=\{\,1,2,\ldots ,12\,\}$. This means, our rotation is of the form $\sigma=(1\,2\,3\,\ldots\,12)^k$ with $\sigma^{12}=id$, so this is basically the group $\mathbb{Z}_{12}$ of all remainders by division with $12$.

 

[YoungPhysicist]

σ12=idσ12=id\sigma^{12}=id

Where does the id come from?

 

[fresh_42]

Where does the id come from?

That means "identity". The neutral element, which in case of functions is the one that maps all $n \mapsto n$. If you have a cycle $\sigma$ of length $n$, then $\sigma^n= id = 1$. E.g. $(1,2,3)$ maps $1 \mapsto 2\, , \,2\mapsto 3\, , \,3 \mapsto 1$. Now if you apply this function three times on any of the numbers $1,2,3$ then you will end up where you began.

In case of our table it means: If we turn the table twelve times, always by the same amount of seats, then we will be back at where we started.

 

[Delta2]

Problem 7.1
It is a well known result (for example see https://en.wikipedia.org/wiki/Surface_integral#Surface_integrals_of_scalar_fields) that the surface of a function $z=f(x,y)$ is given by the integral $\iint_A\sqrt{{\frac{\partial f}{\partial x}}^2+{\frac{\partial f}{\partial y}}^2+1}dxdy$ where $A=[-1,1]\times[-1,1]$ in our case.

for $z=f(x,y)=x^2+y^2$ we have $\frac{\partial f}{\partial x}=2x,\frac{\partial f}{\partial y}=2y$ hence the surface is $\iint_A\sqrt{4x^2+4y^2+1}dxdy$
for $z=f(x,y)=x^2-y^2$ we have $\frac{\partial f}{\partial x}=2x,\frac{\partial f}{\partial y}=-2y$ hence again the surface is $\iint_A\sqrt{4x^2+4y^2+1}dxdy$
Q.E.D

 

[fresh_42]

Problem 7.1
It is a well known result (for example see https://en.wikipedia.org/wiki/Surface_integral#Surface_integrals_of_scalar_fields) that the surface of a function $z=f(x,y)$ is given by the integral $\iint_A\sqrt{{\frac{\partial f}{\partial x}}^2+{\frac{\partial f}{\partial y}}^2+1}dxdy$ where $A=[-1,1]\times[-1,1]$ in our case.

for $z=f(x,y)=x^2+y^2$ we have $\frac{\partial f}{\partial x}=2x,\frac{\partial f}{\partial y}=2y$ hence the surface is $\iint_A\sqrt{4x^2+4y^2+1}dxdy$
for $z=f(x,y)=x^2-y^2$ we have $\frac{\partial f}{\partial x}=2x,\frac{\partial f}{\partial y}=-2y$ hence again the surface is $\iint_A\sqrt{4x^2+4y^2+1}dxdy$
Q.E.D

Yes. A bit more detailed for the younger ones (and because physicists use the normal vector all the time):

We choose the parameterization $\Phi(u,v)=(u,v,u^2+v^2)^\tau \; , \;u,v\in [-1,1]$ for $P$ and get the normal vector
\begin{align*}
\vec{N}_P(u,v)&=\dfrac{\partial \Phi}{\partial u} \times \dfrac{\partial \Phi}{\partial v}\\
&= (1,0,2u)^\tau\times (0,1,2v)^\tau\\
&= (-2u,-2v,1)^\tau
\end{align*}
and we get for the area $$|P|=\int_\Phi 1\,d\sigma =\int_{[-1,1]^2} ||\vec{N}_P(u,v)||\,d(u,v) = \int_{[-1,1]^2}\sqrt{4u^2+4v^2+1}\,d(u,v)$$
The parameterization of $H$ is given by $\Psi(u,v)=(u,v,u^2-v^2)^\tau$ whose normal vector $\vec{N}_H(u,v)=(-2u,2v,1)^\tau$ has the same norm as $\vec{N}_P$ and thus yields the same area integral.

 

[SSequence]

6. Show that $(0,1) \subset \mathbb{R}$ cannot be written as a countable disjoint union of closed intervals.

Here is a rough sketch I thought about. I am not sure whether it is detailed enough to count, but since I spent a decent number of hours thinking about it, I suppose I might as well post it. Note that, admittedly, I have skipped a lot of detail (a little too much honestly) in this decimal stuff (so its fine if it doesn't get credit). Posting this mostly for the sake of reference (so I could improve it) and also (possibly) alternative viewpoint.

This approach goes around by using decimal numbers. Now suppose there were disjoint intervals $I_n$ (where $n \in \mathbb{N}^+$) such that there union equaled $X=(0,1)$. Now whenever I say enumeration of intervals $I_n$ it simply means counting them in order $I_1,I_2,I_3,I_4,...$.

We basically want to select a subset collection of these intervals. Let's denote these intervals by $J_n$ (where $n \in \mathbb{N}^+$). First we set $I_1=J_1$. Then we keep enumerating our intervals until we find one which is to the "right" of $I_1$. We call this $J_2$ (note that if $J_2$ doesn't exist then trivially the union of intervals $I_n$ fails to equal $X$). Similarly, we keep up with our enumeration until we encounter an interval that is between $J_1$ and $J_2$. Call this $J_3$. Keep up the enumeration again until we encounter an interval between $J_3$ and $J_2$. Let's call this $J_4$. And so on...

We will denote the right end-points of $J_1$,$J_3$,$J_5$,$J_7$,... as $L_1$,$L_2$,$L_3$,$L_4$,... etc. Similarly we denote the left end-points of $J_2$,$J_4$,$J_6$,$J_8$,... as $R_1$,$R_2$,$R_3$,$R_4$,... etc.

Now with this out of the way what do we do next? I am sure the following approach works (but my reasoning is probably missing some points). Anyway here is how it goes. We divide into two cases:
(1) $lim_{i \rightarrow \infty } |R_i-L_i|>0$
In that case let:
$L=lim_{i \rightarrow \infty } L_i$
$R=lim_{i \rightarrow \infty } R_i$
Now $L$ and $R$ can't be equal. Because they aren't equal there is some $d>0$ so that:
$R-L=d$
So a point such as $L+d/2$ wouldn't be included in the union of the intervals $I_n$.

(2) $lim_{i \rightarrow \infty } |R_i-L_i|=0$
In that case we can use the following "algorithm" to produce a real number which isn't in the union of the intervals $I_n$.

Check the decimal positions to which $L_1$ and $R_1$ agree and finalise those positions
Check the decimal positions to which $L_2$ and $R_2$ agree and finalise those positions
...
Check the decimal positions to which $L_i$ and $R_i$ agree and finalise those positions
...

The idea here is that if we write the resulting number that is produced as $r$, then we have:
$r>L_i$ (for all $i$)
$r<R_i$ (for all $i$)
And because of this it seems reasonably clear that $r \notin X$.

But this algorithm does seem to require some justifications. First note that we don't use an expansion like $0.49999...$. Instead we will write $0.5$ in its place. Note that the justifications are merely very very rough sketches.

(a) First of all we implicitly assumed that if $L_i$ and $R_i$ agree up till certain number of decimal positions then so do $L_{i+1}$ and $R_{i+1}$.
For example, suppose $L_i$ and $R_i$ started with a $4$ in the first position after decimal and disagreed afterwards. Then we can immediately deduce that:
$0.4 \ge L_i,R_i < 0.5$
Now because we have $L_i<L_{i+1}<R_{i+1}<R_i$ we can immediately deduce that $L_{i+1}$ and $R_{i+1}$ also include a $4$ in the first position after decimal (they might or might not agree afterwards).

(b) The algorithm leads to a non-terminating decimal number. Suppose we had finalized the first position in our number $r$. What we wish to know is whether there will be a non-zero value that will occur in some future positions?
So we might know that $r$ has the form $r=0.4xxxxxxx...$. For $r$ to be a non-terminating decimal it is a necessary condition that there is a next point (after the first one) where the digit in its decimal expansion is non-zero. Once again we can conclude from the form of $r$ that we have a stage $i$ where:
$L_i \ge 0.4$
$R_i < 0.5$
Now because $R_i \neq L_i$ and $R_i > L_i$, we can conclude that $R_i>0.4$. Further we can also conclude that $R_n>0.4$ (for all $n \geq i$) ... since otherwise it would violate our condition that all $R_i$'s are greater than all $L_i$'s. And we can also conclude that $L_n>0.4$ (for all $n > i$)
So now, we only need to show that there will be future position $m>i$ at which $L_m$ and $R_m$ agree on more than one position. I think this should follow from $lim_{i \rightarrow \infty } |R_i-L_i|=0$ in someway.

(c) How do we show that:
$r>L_i$ (for all $i$)
$r<R_i$ (for all $i$)

If we consider a number such as $L_5$, then $r$ at least has some initial digits agreeing with it (till the point where $L_5$ and $R_5$ agree). But what about after that? Well eventually $L_5$ will disagree with all other $L_i$'s after some fixed number of digits $N$ (in fact its $N+1$-th digit will be smaller). Furthermore, there will be a point in the future iterations where $r$ will agree with some $L_i$ ($i>5$) for more than $N$ digits. From this we can conclude that $r>L_5$.

Note:
I think if we wanted to avoid all this cubersome decimal stuff, we could basically use some more elegant representation (probably one based upon shrinking intervals subset of each other). I don't really re-call it off-hand and I don't have enough energy to look it up in detail. So I will probably give it a rest here.

 

[Infrared]

@SSequence Your idea is good! You're right that there are some annoyances with using decimals, and thankfully your argument can be done without appealing to them. For example, to define your r, you can argue that since L_i are increasing and bounded above, they must converge to a limit, and likewise the R_i too. Since |L_i-R_i| goes to zero, the limits are the same, and you can define this limit to be r (no need to care about whether the decimal representation is terminating or not). Since the L_i (resp. R_i) are increasing (resp. decreasing), it's immediate that r&gt;L_i (resp. r&lt;R_i).

I'll accept the solution, but everyone else is also free to submit different solutions too.

 

[SSequence]

Since making the last post, I thought of another solution that doesn't use decimals much except on one small point (its a small variation on one that I already described). But it is just that I found the simple explicit "algorithm" for finding decimal expansion (of the point that isn't in the union of intervals) pretty interesting.

(1) This is mostly a rephrasing of what you said. As you mentioned, one way is to consider the sequences of reals:
$L_0,L_1,L_2,L_3,L_4,...$
And now because for all $i$ we have $L_i <R_0$, this sequence/set is bounded above. Hence it converges to some real number $L$ (by completeness).

And because we have:
$L_0<L_1<L_2<L_3<L_4,...$
it follows that:
$L>L_i$ (for all $i$)

Now we just have to show that:
$L<R_i$ (for all $i$)
By contradiction, suppose that we had something like $L \geq R_5$. But this can't be true! To see this, we already know the following facts:
$R_6<R_5$
$L_i<R_6$ (for all $i$)
From these we can conclude that $L <R_5$. The same reasoning can be generalized to any $R_i$.

(2) Another point I was thinking was to explicitly give a sequence of increasing rationals:
$l_0,l_1,l_2,l_3,l_4,l_5,...$
which converge to some real $r$. Note that we want:
$L_0<l_0<L_1$
$L_1<l_1<L_2$
... and so on

By reasoning same as before, we can conclude that the limit $r$ of these rationals will be greater than all $L_i$'s and less than all $R_i$'s.

P.S. Note that for any two reals $a,b$ (so that $a<b$) we can give an explicit "algorithm" to calculate a rational $x$ so that $a<x<b$ (via inspection of the decimal expansions of $a$ and $b$).

 

[mfb]

If $\lim_{i \rightarrow \infty } |R_i-L_i|=0$ then the identical limits for $R_i$ and $L_i$ will be the only point that is missing.

 

[SSequence]

Yes, you are right. It is just that I am not fully sure (how to show rigorously that) that why the "algorithm" in post#38 (call it $r_1$) yields the same result as the limit of $L_0,L_1,L_2,L_3,L_4,...$ (call it $r_2$) in the case when $lim_{i \rightarrow \infty } |R_i-L_i|=0$.
Perhaps one way might be to consider that since there is only one point $r$ which satisfies the property that (in the case $lim_{i \rightarrow \infty } |R_i-L_i|=0$):
$r>L_i$ (for all $i$)
$r<R_i$ (for all $i$)
and because of that conclude that $r_1=r_2$ (by showing separately that $r_1$ and $r_2$ both satisfy the mentioned property).

[EDIT : Actually I think I should add that the stated algorithm in post#38 isn't quite accurate as stated (so some corrections would definitely be needed in the second half of that post. Since apparently, at least for (some) terminating decimals it doesn't work (which is enough to render it incorrect as stated). For example, if the missing point was 0.80 the $L_i$'s will always be of the form $0.7xxxx...$ and $R_i$'s will always be of the form $0.8xxxx$. It likely works with an exception or two added though.]But anyway, it is not what the actual question was asking. The reasoning similar to described in post#39,40 works fine and it seems that we don't even have to consider separate cases for $lim_{i \rightarrow \infty } |R_i-L_i|$ being zero or non-zero.

 

[YoungPhysicist]

Problem 10:

Spoiler

The sum of every natural number from $1$ to $100$ is $5050$.
Add up every number that John said, then the difference from the sum and 5050 will be the missing number.

 

[David Lethe]

Re: Problem 2a and PeroK's response

You claim that (1,6,6) is not possible because one person is the oldest. I disagree. Ask any twin and he/she will tell you which of their siblings is the oldest twin. Babies are not born simultaneously. As a result, there are two answers that work.

 

[Mark44]

Re: Problem 2a and PeroK's response

You claim that (1,6,6) is not possible because one person is the oldest. I disagree. Ask any twin and he/she will tell you which of their siblings is the oldest twin. Babies are not born simultaneously. As a result, there are two answers that work.

Aren't the two older ones both 6? We don't speak about someone being 6.2035 years old and his or her twin being 6.2032 years old. The ages are whole number values, for the most part.

 

[YoungPhysicist]

Aren't the two older ones both 6? We don't speak about someone being 6.2035 years old and his or her twin being 6.2032 years old. The ages are whole number values, for the most part.

I believe what he mean is that twins can have the same “age” but have an elder and younger one.

 

[Mark44]

I believe what he mean is that twins can have the same “age” but have an elder and younger one.

That's like saying two numbers can have the same value, but one is larger and one is smaller.

 

[fresh_42]

@Mark44 is completely right. The setup is a conversation between seat neighbors on a flight. In 99.999% of all cases, a question about the age of another one's children will be answered like "the twins are ..." if there are twins.

Nevertheless, the point was a different one, namely to draw information from a statement with seemingly no use: "the factorization isn't sufficient". It has been an exercise in exact reading, not in biology. If I had dealt with the twin situation, someone would have come up with adopted children, children from previous marriages or whatsoever. It wasn't a meeting at a divorce lawyer.

 

[lpetrich]

I will attempt to solve problem 12.

Spoiler

Since $x_{n+1} = n (x_n + x_{n-1})$, it is evident that every solution is a linear combination of two solutions, a combination that can be specified with the values of $x_0$ and $x_1$.

It is easy to show that $x_n = n!$ is a solution.
$n(n! + (n-1)!) = n(n + 1)\cdot(n-1)! = (n+1)!$.

With Mathematica and a lot of trial and error with series, I came up with a trial solution that seems to be linearly independent of the first one:
$$x_n = \sum_{k=0}^\infty \frac{(-1)^{k+n} (k+1)}{n(n+1) \cdots (n+k)}$$
Since k = (n+k) - n, this solution can be split in two: $x_n = y_n + (1-1/n)y_{n+1}$ where
$$y_n = \sum_{k=0}^\infty \frac{(-1)^{k+n}}{n(n+1) \cdots (n+k-1)} = - (n-1)! \sum_{k=(n-1)}^\infty \frac{(-1)^k}{k!} = - (n-1)! \left( \frac{1}{e} - \sum_{k=0}^{n-2} \frac{(-1)^k}{k!} \right)$$
One can verify the x-y equation with the help of
$$y_{n+1} = - \sum_{k=0}^\infty \frac{(-1)^{k+n}}{(n+1)(n+2) \cdots (n+k)}$$
The y expression with 1/e in it gives us
$$x_n = - n! \left( \frac{1}{e} - \sum_{k=0}^n \frac{(-1)^k}{k!} \right)$$
It is now time to verify this solution, to show that it satisfies the problem's recurrence relation. For this purpose, we find
$$x_{n-1} = - \frac{1}{n} n! \left( \frac{1}{e} - \sum_{k=0}^n \frac{(-1)^k}{k!} \right) - \frac{(-1)^n}{n}$$
$$x_n = - (n+1) n! \left( \frac{1}{e} - \sum_{k=0}^n \frac{(-1)^k}{k!} \right) - (-1)^n$$
It can easily be shown that this solution satisfies the recurrence. The general solution for x can now be expressed as
$$x_n = n! \left(A + B\sum_{k=0}^n \frac{(-1)^k}{k!}\right)$$
for some A and B. Solving $x_0 = 0 = A + B$ and $x_1 = 1 = A$, we get $A = 1$ and $B = -1$. This gives us the solution for the problem:
$$ x_n = n! \left(1 - \sum_{k=0}^n \frac{(-1)^k}{k!}\right)$$
and in the limit of large n,
$$ \frac{x_n}{n!} = 1 - \sum_{k=0}^n \frac{(-1)^k}{k!} \to 1 - \frac{1}{e} \approx 0.632121 $$

 

[lpetrich]

I will solve problem 13.

Spoiler

Consider a group Gpq with order pq, where both p and q are prime numbers and p > q.

If Gpq is abelian, then according to a well-known theorem, it is a product of cyclic groups Z(x^m), where each x is a prime factor of |G|, the order of G, and m is between 1 and the power where x appears in |G|, inclusive. This means that if Gpq is abelian, then it must be composed of a product of powers of Z(p) and Z(q). By Cauchy's theorem, Gpq has elements of order p and q, thus subgroups Z(p) and Z(q). This means that Gpq must be at least Z(p)*Z(q). But the order of Z(p)*Z(q) is pq, the order of Gpq. So abelian Gpq is Z(p)*Z(q).

By Bézout's identity, since p and q are relatively prime, there is some u and v such that up + vq = 1. So if a generates a Z(p) and b generates a Z(q), and if c = a^vb^u, then c^q = a^vqb^uq = a^1-up = a and c^p = a^vpb^up = b^1-vq = b.

So Z(p)Z(q) = Z(pq), and thus abelian Gpq is cyclic.

For possible nonabelian Gpq, we use Sylow's theorems. One of these theorems states that for every prime x dividing |G|, the group has a subgroup with order x^m, where x appears in |G| with power m. Another of these theorems states that these subgroups need not be unique, and that all such subgroups in a group are related by conjugation. Still another states that there are kx+1 of these subgroups, where kx+1 evenly divides |G|/x^m. If k = 0, then the subgroup is normal.

Since p and q are the only prime factors, the Sylow subgroups must be the Z(p)'s and Z(q)'s in Gpq. Since p > q, that means that there is no k that makes (kp +1) = q, therefore, the Z(p) is normal and there is only one of it in Gpq. But it may happen that (kq+1) = p, and in that case, there are (kq+1) = p copies of the Z(q) subgroup of Gpq, copies that are all conjugates of each other. That makes the group nonabelian. But that is only possible if p mod q = 1. If not, then there is only one of the Z(q) in Gpq, and it is normal.

If Gpq has only one Z(p) subgroup and only one Z(q) subgroup, then it has the identity, (p-1) elements with order p, (q-1) elements with order q, and (p-1)(q-1) elements with a different order. Since pq is only evenly divisible by itself, 1, p, and q, that additional order must be pq, and an element with that order will generate the entire group. Thus arriving at the cyclic Gpq group.

Thus, if p mod q is not 1, then the only possible group Gpq is the cyclic one.

 

[lpetrich]

I will solve problem 9.

Spoiler

The integral
$$ I = \int_1^{\infty} \frac{dx}{p(x)} $$
can be done in indefinite form for n = 0 or 1.

For n = 0, p(x) = 1, and the indefinite integral is x. It diverges for $x \to \infty$.

For n = 1, p(x) = x + a₁, and the indefinite integral is $\log(x + a_1)$. It also diverges for $x \to \infty$.

Thus, the integral $I$ is always divergent for $n \leq 1$.

This leaves the case where $n \geq 2$. This problem will be solved by bounding the integrand, and showing that this gives a finite integral. That will then make $I$ finite.

If p(x) has all-negative roots, then it must be uniformly positive or negative over x in the domain of integration of the problem's integral, $[1,\infty)$. Let us choose a form for p(x) that will make it possible to show that $I$ is bounded from above. This form is p(x) = xⁿ q(1/x), where
$$q(u) = 1 + a_{n-1} u + a_{n-2} u^2 + \cdots + a_0 u^n$$
As $x \to \infty$, $q(1/x) \to 1$, which is positive, thus, p(x) is uniformly positive over x in $[1,\infty)$. That also makes q(1/x) uniformly positive over that interval. This also means that 1/p(x) is uniformly positive, thus making $I$ also positive, bounded from below by 0.

We must now show that 1/p(x) is bounded from above, and bounded from above in a way that makes $I$ finite. This is equivalent to showing that p(x) is bounded from below in this sort of fashion, and this can be done by bounding q(u) for u in $(0,1]$. By the extreme value theorem, q(u) must have a minimum value for some value of u in that interval. Since q(u) is always positive in that interval, that means that its minimum value in that integral must also be positive. I will call that value Q. Thus, $q(1/x) \geq Q$ for all x in $[1,\infty)$, giving $p(x) = x^n q(1/x) \geq Q x^n$ for all x in that interval. This makes $1/p(x) \leq 1/(Q x^n)$ over that interval, and thus,
$$ I = \int_1^{\infty} \frac{dx}{p(x)} \leq \int_1^{\infty} \frac{dx}{Q x^n} = \frac{1}{(n-1)Q} $$
Thus, $I$ is bounded from both above and below, and the integral always converges for $n \geq 2$.

In summary, this integral always diverges for $n \leq 1$ and always converges for $n \geq 2$.

 

[fresh_42]

I will solve problem 13.
Consider a group Gpq with order pq, where both p and q are prime numbers and p > q.

If Gpq is abelian, then according to a well-known theorem...

Fundamental theorem of finitely generated Abelian groups.
https://en.wikipedia.org/wiki/Finitely_generated_abelian_group#Classification

... it is a product of cyclic groups Z(x^m), where each x is a prime factor of |G|, the order of G, and m is between 1 and the power where x appears in |G|, inclusive. This means that if Gpq is abelian, then it must be composed of a product of powers of Z(p) and Z(q). By Cauchy's theorem, Gpq has elements of order p and q, thus subgroups Z(p) and Z(q). This means that Gpq must be at least Z(p)*Z(q). But the order of Z(p)*Z(q) is pq, the order of Gpq. So abelian Gpq is Z(p)*Z(q).

By Bézout's identity, since p and q are relatively prime, there is some u and v such that up + vq = 1. So if a generates a Z(p) and b generates a Z(q), and if c = a^vb^u, then c^q = a^vqb^uq = a^1-up = a and c^p = a^vpb^up = b^1-vq = b.

So Z(p)Z(q) = Z(pq), and thus abelian Gpq is cyclic.

For possible nonabelian Gpq, we use Sylow's theorems. One of these theorems states that for every prime x dividing |G|, the group has a subgroup with order x^m, where x appears in |G| with power m.

1st of Sylow's theorems.
https://en.wikipedia.org/wiki/Sylow_theorems

Another of these theorems states that these subgroups need not be unique, and that all such subgroups in a group are related by conjugation.

The 2nd of Sylow's theorems says, that all maximal p-groups contain a conjugate of any other p-subgroup. In our case, this means that all p-subgroups, resp. q-subgroups are conjugate. The general statement is a corollary to Sylow's theorems.

Still another states ...

3rd of Sylow's theorem.

... that there are kx+1 of these subgroups ...

Sylow x-groups, i.e. a maximal x-subgroup

... where kx+1 evenly divides |G|/x^m. If k = 0, then the subgroup is normal.

A corollary of Sylow's theorems.

Since p and q are the only prime factors, the Sylow subgroups must be the Z(p)'s and Z(q)'s in Gpq. Since p > q, that means that there is no k that makes (kp +1) = q, therefore, the Z(p) is normal and there is only one of it in Gpq. But it may happen that (kq+1) = p, and in that case, there are (kq+1) = p copies of the Z(q) subgroup of Gpq, copies that are all conjugates of each other. That makes the group nonabelian. But that is only possible if p mod q = 1. If not, then there is only one of the Z(q) in Gpq, and it is normal.

If Gpq has only one Z(p) subgroup and only one Z(q) subgroup

Haven't you already shown, that both have to be normal? In this case $\mathbb{Z}_p \times \mathbb{Z}_q$ is a direct product and isomorph to a subgroup of $G$. Since both have $pq$ elements, they have to be equal.

... then it has the identity, (p-1) elements with order p, (q-1) elements with order q, and (p-1)(q-1) elements with a different order. Since pq is only evenly divisible by itself, 1, p, and q, that additional order must be pq, and an element with that order will generate the entire group. Thus arriving at the cyclic Gpq group.

Thus, if p mod q is not 1, then the only possible group Gpq is the cyclic one.

 

[fresh_42]

I will solve problem 9.

The integral
$$ I = \int_1^{\infty} \frac{dx}{p(x)} $$
can be done in indefinite form for n = 0 or 1.

For n = 0, p(x) = 1, and the indefinite integral is x. It diverges for $x \to \infty$.

For n = 1, p(x) = x + a₁, and the indefinite integral is $\log(x + a_1)$. It also diverges for $x \to \infty$.

Thus, the integral $I$ is always divergent for $n \leq 1$.

This leaves the case where $n \geq 2$. This problem will be solved by bounding the integrand, and showing that this gives a finite integral. That will then make $I$ finite.

If p(x) has all-negative roots, then it must be uniformly positive or negative over x in the domain of integration of the problem's integral, $[1,\infty)$. Let us choose a form for p(x) that will make it possible to show that $I$ is bounded from above. This form is p(x) = xⁿ q(1/x), where
$$q(u) = 1 + a_{n-1} u + a_{n-2} u^2 + \cdots + a_0 u^n$$
As $x \to \infty$, $q(1/x) \to 1$, which is positive, thus, p(x) is uniformly positive over x in $[1,\infty)$. That also makes q(1/x) uniformly positive over that interval. This also means that 1/p(x) is uniformly positive, thus making $I$ also positive, bounded from below by 0.

We must now show that 1/p(x) is bounded from above, and bounded from above in a way that makes $I$ finite. This is equivalent

Proof?

to showing that p(x) is bounded from below in this sort of fashion, and this can be done by bounding q(u) for u in $(0,1]$.

Proof?

By the extreme value theorem, q(u) must have a minimum value for some value of u in that interval.

What about $x=0$? I think you must first get rid of the open end of this interval, at least formally.

Since q(u) is always positive in that interval, that means that its minimum value in that integral must also be positive. I will call that value Q. Thus, $q(1/x) \geq Q$ for all x in $[1,\infty)$, giving $p(x) = x^n q(1/x) \geq Q x^n$ for all x in that interval. This makes $1/p(x) \leq 1/(Q x^n)$ over that interval, and thus,
$$ I = \int_1^{\infty} \frac{dx}{p(x)} \leq \int_1^{\infty} \frac{dx}{Q x^n} = \frac{1}{(n-1)Q} $$
Thus, $I$ is bounded from both above and below, and the integral always converges for $n \geq 2$.

In summary, this integral always diverges for $n \leq 1$ and always converges for $n \geq 2$.

I think you should work out the three points I mentioned. You claim equivalences which can probably easily be shown, and you must deal with the boundary $0$.

 

[Infrared]

I will attempt to solve problem 12.

Spoiler

Since $x_{n+1} = n (x_n + x_{n-1})$, it is evident that every solution is a linear combination of two solutions, a combination that can be specified with the values of $x_0$ and $x_1$.

It is easy to show that $x_n = n!$ is a solution.
$n(n! + (n-1)!) = n(n + 1)\cdot(n-1)! = (n+1)!$.

With Mathematica and a lot of trial and error with series, I came up with a trial solution that seems to be linearly independent of the first one:
$$x_n = \sum_{k=0}^\infty \frac{(-1)^{k+n} (k+1)}{n(n+1) \cdots (n+k)}$$
Since k = (n+k) - n, this solution can be split in two: $x_n = y_n + (1-1/n)y_{n+1}$ where
$$y_n = \sum_{k=0}^\infty \frac{(-1)^{k+n}}{n(n+1) \cdots (n+k-1)} = - (n-1)! \sum_{k=(n-1)}^\infty \frac{(-1)^k}{k!} = - (n-1)! \left( \frac{1}{e} - \sum_{k=0}^{n-2} \frac{(-1)^k}{k!} \right)$$
One can verify the x-y equation with the help of
$$y_{n+1} = - \sum_{k=0}^\infty \frac{(-1)^{k+n}}{(n+1)(n+2) \cdots (n+k)}$$
The y expression with 1/e in it gives us
$$x_n = - n! \left( \frac{1}{e} - \sum_{k=0}^n \frac{(-1)^k}{k!} \right)$$
It is now time to verify this solution, to show that it satisfies the problem's recurrence relation. For this purpose, we find
$$x_{n-1} = - \frac{1}{n} n! \left( \frac{1}{e} - \sum_{k=0}^n \frac{(-1)^k}{k!} \right) - \frac{(-1)^n}{n}$$
$$x_n = - (n+1) n! \left( \frac{1}{e} - \sum_{k=0}^n \frac{(-1)^k}{k!} \right) - (-1)^n$$
It can easily be shown that this solution satisfies the recurrence. The general solution for x can now be expressed as
$$x_n = n! \left(A + B\sum_{k=0}^n \frac{(-1)^k}{k!}\right)$$
for some A and B. Solving $x_0 = 0 = A + B$ and $x_1 = 1 = A$, we get $A = 1$ and $B = -1$. This gives us the solution for the problem:
$$ x_n = n! \left(1 - \sum_{k=0}^n \frac{(-1)^k}{k!}\right)$$
and in the limit of large n,
$$ \frac{x_n}{n!} = 1 - \sum_{k=0}^n \frac{(-1)^k}{k!} \to 1 - \frac{1}{e} \approx 0.632121 $$

Yes, this is right! Can you find a way to solve the problem without guessing the second linearly independent solution?

 

[YoungPhysicist]

Problem 14:

Spoiler

First, the number must start with 1or 2, since everything bigger than that will make it a six digit number after multiplying by 4.

But 1 isn’t possible, since no number from 0 to 9 can end with 1 after multiplying by 4.

2xxxx

Then,it must end with a 8 or 9,since that’s the only two possibility of 2xxxx multiplying by 4.

But 9 isn’t correct,because 9x4 = 36, which doesn’t end with 2.

2xxx8

The second digit can be 0,1, or 2.

After checking all multiples of 4 by 8,18,28...98, I found 0 and 2 impossible, since the second two digits of the previous multiple only consists 3,7,1 and 5.

That leads to only two possibilities:

21x28
21x78

Then I found the first one impossible since 21xxx x 4 always end up with 84xxx or bigger, but 21x28 requires the first two digits to be 82, which can’t happen.

21x78

After trying all ten possibilities, I get 21978.

 

[member 587159]

15:

Spoiler

In what follows, I will assume that already is established that Boolean rings are commutative.

Let $P$ be a prime ideal. Our goal here is to prove that $P$ is maximal. I.e., we want to show that $R/P$ is a field.

Let's examine the quotient ring a little further.

Take an element $[x] \in R/P$.

Observe that $(x-1)^2 = x-1$, and thus by distributivity: $x-1 = (x-1)(x-1) = x^2 -x -x +1$

Hence, $(x-(1+1))(x-1) = x^2 - x - x - x +1 +1 = 0 \in P$, and because $P$ is prime it follows that $(x - (1 +1)) \in P$ or $x - 1 \in P$. But now observe that $1+1 = 0$, because $1 +1 = (1+1)^2 = 1 + 1 +1 +1$. Thus we either have $x \in P$ or $x-1 \in P$, which means that $[x] = [0] = 0$ or $[x] = [1] = 1$.

We thus have shown that the quotient ring contains 2 elements, that is $R/P \cong \mathbb{F}_2$ and we are done.

 

[fresh_42]

15:

Spoiler

In what follows, I will assume that already is established that Boolean rings are commutative.

Let $P$ be a prime ideal. Our goal here is to prove that $P$ is maximal. I.e., we want to show that $R/P$ is a field.

Let's examine the quotient ring a little further.

Take an element $[x] \in R/P$.

Observe that $(x-1)^2 = x-1$, and thus by distributivity: $x-1 = (x-1)(x-1) = x^2 -x -x +1$

Hence, $(x-(1+1))(x-1) = x^2 - x - x - x +1 +1 = 0 \in P$, and because $P$ is prime it follows that $(x - (1 +1)) \in P$ or $x - 1 \in P$. But now observe that $1+1 = 0$, because $1 +1 = (1+1)^2 = 1 + 1 +1 +1$. Thus we either have $x \in P$ or $x-1 \in P$, which means that $[x] = [0] = 0$ or $[x] = [1] = 1$.

We thus have shown that the quotient ring contains 2 elements, that is $R/P \cong \mathbb{F}_2$ and we are done.

Just in case you're interested in a shorter version:

Let $x,y \in \mathcal{B}/P - \{\,0\,\}$ and $z:=x\cdot y\,.$ Then $xz=x(xy)=(xx)y=xy$ and $0=x(z-y)\,.$ As $\mathcal{B}/P$ is an integral domain and $x\neq 0$, we have $y=z$ and similarly $x=z$. So all elements different from $0$ are identical. Because $P \neq\mathcal{B}$ we get $\mathcal{B}/P \cong \mathbb{Z}_2\,.$

 

[lpetrich]

I will attempt to solve problem 16.

Spoiler

I first establish coordinate conventions. The center of the square is at (x=0, y=0) for coordinates x and y, and the four edges are at x = 1, y = 1, x = -1, and y = -1. This makes the area of the square $(1 - (-1))^2 = 4$.

The solution comes in two parts:

1. Find which region is closer to an edge than to the center
2. Find the area of that region

The first part requires finding for each edge, the region that is closer to the center than to the edge. Once that is done, then the region that is closer to the center than to any edge is the intersection of all these four regions.

For finding the region closer to the center than to some edge, I will do the x = 1 case, and then generalize with the help of symmetries. For x = 1, the inequality that gives the region is
$$ \sqrt{x^2 + y^2} < 1 - x $$
Squaring both sides gives
$$ x^2 + y^2 < 1 - 2x + x^2 $$
Solving for x gives
$$ x < \frac12 (1 - y^2) $$
A parabola. Using reflection symmetries, the solution region is

• (x = 1): $x < (1/2)(1 - y^2)$
• (y = 1): $y < (1/2)(1 - x^2)$
• (x = -1): $x > - (1/2)(1 - y^2)$
• (y = -1): $y > - (1/2)(1 - x^2)$

Since the region's boundary is given in piecewise fashion, we must find where the boundary pieces intersect. For (x=1) and (x=-1), it is easy: $y = \pm 1$, and similarly for (y=1) and (y=-1). That is well outside the region. For (x=1) and (y=1), I find two real solutions:

• $x = y = \sqrt{2} - 1$
• $x = y = - (\sqrt{2} + 1)$

The second solution is clearly outside of the region, as one can tell from the inequalities derived from the third and fourth edges, but the first one is not. Thus, the four intersection points are
$$ x = \pm (\sqrt{2} - 1) ,\ y = \pm (\sqrt{2} - 1) $$

Having found the solution region, we now find its area. This can be done with the help of the square's symmetries. The square can be divided into eight triangles that have vertices (center), (edge center), (nearby vertex). All eight triangles have equal area, and for convenience, I will choose the one with vertices (0,0), (0,1), and (1,1). The part of the solution region in this triangle is given by lines (x = 0) and (y = x), and the (y = 1) region boundary, $y = (1/2)(1-x^2)$. The second two boundaries intersect at $x = y = \sqrt{2} - 1$. So the integral for area A is
$$A = \int_0^{\sqrt{2}-1} \left( \int_x^{(1/2)(1-x^2)} 1 \, dy \right) \, dx = \int_0^{\sqrt{2}-1} \frac12 (1 - 2x - x^2) \, dx = \frac{4\sqrt{2} - 5}{6}$$
The area of the entire region is thus $8A = (4/3)(4\sqrt{2} - 5)$, and dividing by the square's area gives us
$$ \frac{\text{(area of solution region)}}{\text{(area of square)}} = \frac{4\sqrt{2} - 5}{3} \approx 0.218951 $$
This is the fraction of success of winning an extra point. I have approximately verified it by doing some simple numerical integration.

 

[lpetrich]

I will solve problem 18.

Spoiler

The problem may be restated as: find all nonnegative-integer x less than 1000 such that the power identity $x^n = 1000 m + x$ for positive integers n and nonnegative integers m. It can be reduced to a much simpler problem, because the power identity is true for n = 2, and because its truth for n = 2 implies its truth for all n. This can easily be shown by mathematical induction. Let $x^2 = 1000 m_0 + x$, and use the power identity's truth for some value of n. Then
$x^{n+1} = x^n x = 1000 m x + x^2 = 1000 (m x + m_0) + x$
Since m and x are both nonnegative integers, their product will also be a nonnegative integer, and thus $m x + m_0$ will be a nonnegative integer. That proves the power identity for n+1, and thus for all values of n.

So we only need to find some x that satisfies the power identity for n = 2: $x^2 = 1000 m + x$.

We first consider the possible ones digits. There are four possibilities: 0, 1, 5, and 6.

0² = 0, 1² = 1, 5² = 5, 6² = 6.

For the tens digit, 0 has only one possibility: 0. Likewise, 1 has 0, 5 has 2, and 6 has 7.

00² = 00, 01² = 01, 25² = 625, 76² = 5776

For the hundreds digit, 00 has only one possibility, 0. Likewise, 01 has 0, 25 has 6, and 76 has 3.

000² = 000, 001² = 001, 625² = 390625, 376² = 141376

So this problem's solutions are 000, 001, 625, and 376.

 

[mfb]

There is an interesting pattern in problem 18:

Spoiler

The remainder from a division by 2³=8 depends on the last three digits only. To stay the same it has to be either 0 or 1.
The remainder from a division by 5³=125 depends on the last three digits only. To stay the same it has to be either 0 or 1.

=> We get the trivial 000 and 001 and the option to have multiples of 125 or 8.
625 = 5*125, the only one in range with a remainder of 1 in a division by 8.
376 = 47*8, the only one in range with a remainder of 1 in a division by 125.

This is a general pattern for bases that are the product of two primes independent of the number of trailing digits we look at. In other bases things are different. If the base is a prime or prime power then 0 and 1 are the only options, for example.