Challenge Math Challenge - December 2018

  • Thread starter fresh_42
  • Start date
355
40
You are missing 0.303030... in base 4, for example, which is 4/5 in the decimal system. It is behind the first interval, then in front of the second interval you put in there, then behind the next one, and so on.
This is interesting. Are there infinite number of points missing? I am guessing so, because finite number of points missing can be fixed.
 

fresh_42

Mentor
Insights Author
2018 Award
11,719
8,246
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 = 1~12)

But since 12 steps(a complete turn) away in the same as 0 steps away,that leads to only 11 ways of "how far they are from their cards".
So, in order for the probelm to not be true, everyone has to sit ##n## steps away from there card and everyone's ##n## cannot be the same.

But since there are 12 people choosing from 11 possibillities, there must be two person with the same ##n##.
What if one person is seated correctly, then there are only 11 persons for 11 possibilities?
 
33,452
9,179
This is interesting. Are there infinite number of points missing? I am guessing so, because finite number of points missing can be fixed.
Sure. You are missing all numbers with only 0 and 3 in their base 4 expansion where the expansion doesn't end. This is an uncountable set. It is a variation of the Cantor set.


Edit: Concerning problem 8: Note that this can be impossible with 3 people. If A, B, C face cards A, C, B, then every rotation will only make one person seated correctly.
 
@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.
28D858F0-B6AA-4C61-B4FB-5C58BB8A8695.jpeg
 

Attachments

Last edited:
355
40
Sure. You are missing all numbers with only 0 and 3 in their base 4 expansion where the expansion doesn't end. This is an uncountable set. It is a variation of the Cantor set.
Yes, I think I have gotten a bit of intuition (after working around for while) why we can have decimals that will escape this kind of construction (by considering a construction in parts of 10 instead of 4). Not certainly in a good enough manner, but at least enough to convince myself. Thanks for pointing out the problem.
 
Last edited:

fresh_42

Mentor
Insights Author
2018 Award
11,719
8,246
@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.
 
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”:wink:
 

fresh_42

Mentor
Insights Author
2018 Award
11,719
8,246
Though I can’t fully understand that,but it seems way better than “Mr.n”:wink:
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##.
 

fresh_42

Mentor
Insights Author
2018 Award
11,719
8,246
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

Homework Helper
Insights Author
Gold Member
2,408
681
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

Mentor
Insights Author
2018 Award
11,719
8,246
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.
 
355
40
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

Science Advisor
Gold Member
371
118
@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 [itex]r[/itex], you can argue that since [itex]L_i[/itex] are increasing and bounded above, they must converge to a limit, and likewise the [itex]R_i[/itex] too. Since [itex]|L_i-R_i|[/itex] goes to zero, the limits are the same, and you can define this limit to be [itex]r[/itex] (no need to care about whether the decimal representation is terminating or not). Since the [itex]L_i[/itex] (resp. [itex]R_i[/itex]) are increasing (resp. decreasing), it's immediate that [itex]r>L_i[/itex] (resp. [itex]r<R_i[/itex]).

I'll accept the solution, but everyone else is also free to submit different solutions too.
 
355
40
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##).
 
Last edited:
33,452
9,179
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.
 
355
40
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.
 
Last edited:
Problem 10:
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.
 
Last edited:
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.
 
32,835
4,552
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.
 
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.
 
32,835
4,552
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

Mentor
Insights Author
2018 Award
11,719
8,246
@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.
 
983
173
I will attempt to solve problem 12.
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 $$
 
  • Like
Reactions: mfb
983
173
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, it is a product of cyclic groups Z(xm), 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 = avbu, then cq = avqbuq = a1-up = a and cp = avpbup = b1-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 xm, 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|/xm. 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.
 

Want to reply to this thread?

"Math Challenge - December 2018" You must log in or register to reply here.

Related Threads for: Math Challenge - December 2018

Replies
50
Views
4K
Replies
175
Views
11K
Replies
63
Views
5K
Replies
82
Views
6K
Replies
16
Views
3K
Replies
62
Views
5K
Replies
28
Views
2K
Replies
57
Views
5K

Hot Threads

Top