Math Challenge - June 2021

In summary: Problem #9I don't know what "stochastically independent" means, but it's clear thatand
  • #36
kshitij said:
I shouldn't write I should have directly wrote that from the only solution we get is and (as there are no pythagorean triplets with 2), I was thinking something else when I wrote .

I don't like that solution anyway, maybe I can think a better one later.
You only claimed to know c and k are rational.

I think problem 15 has been pieced together correctly, but I think it's important to understand why the first attempt failed on the last line. If you still aren't sure please post here again.

@BWV I think A and B are independent. I haven't checked carefully what you wrote but consider the outcome of the sum being odd after you fix both die rolls (which completely determines B) and also two of the coins just for fun. What is the probability of event A? Any event that is determined just by the die rolls must be independent of A because of this.

That leaves the fun part of checking the triple.
 
Last edited:
Physics news on Phys.org
  • #37
You are right - need to divide the 7/72 by P(B) which gives 1/2 so they are independent
 
  • #38
Ok one last shot (maybe can delete the previous?)
An ideal coin is thrown three times in a row and then an ideal dice is thrown twice in a row. Each time you toss a coin you get one point if the coin shows "tails" and two points if the coin shows "heads". If you add the total of the two dice rolls to this number of points, you get the total number of points.

Let A be the event "the total number of points achieved is odd", B be the event "the total of the two dice rolls is divisible by 5", and C the event "the number of points achieved in the three coin tosses is at least 5". Investigate whether A, B, C are pairwise stochastically independent. Also investigate whether A, B, C are stochastically independent.

T=total = (5:18)

Probabilities:

A = P(odd) =½ (even number of integer outcomes, symmetrical prob)

B= P(Dice total div by 5)=1/9+1/12=7/36

C=Pcoin(>=5)= ½ (p(6)=1/8+p(5)=3/8)
Two events independent if P(A∩B)= P(A)P(B) or, alternatively P(A|B)=P(A) and P(B|A)=P(B)

A and B independent as

P(A)=1/2, P(A|B)=1/2

DicePCoinP
3​
1/8​
5​
1/9​
4​
3/8​
5​
3/8​
10​
1/12​
6​
1/8​
SumpOdd?
8​
1/72​
FALSE​
0​
9​
1/24​
TRUE​
1/24​
10​
1/24​
FALSE​
0​
11​
1/72​
TRUE​
1/72​
13​
1/96​
TRUE​
1/96​
14​
1/32​
FALSE​
0​
15​
1/32​
TRUE​
1/32​
16​
1/96​
FALSE​
0​
7/72​
7/72 / 7/36 = 1/2

A and C independent as

P(A)P(C)=1/4 = P(A∩C)=P(A|C)P(C)=1/4

B and C independent as

P(B)P(C)=7/72 = P(B∩C)=P(B|C)P(C)=7/72

A,B,C not jointly independent as
P(A)P(B)P(C)=(1/2)(1/2)(7/36) = 7/144 <> P(C|AB) (only outcomes =11,15 above on A and B)= 1/72+1/32 = 13/288
 
  • #39
Hölder continuous implies uniformly continuous. So, we'll show that these conditions are not equivalent.

The set is compact and as . Hence is uniformly continuous.

Assume for a contradiction is Hölder continuous. That is, there exist and such that

In particular (taking ) we have for every that

But as . E.g apply L'Hopital to as . This is a contradiction, so cannot be Hölder continuous.
 
Last edited:
  • #40
I have two ways for problem 3, but can't think of a third right now.
i) by direct substitution:then .

ii) Given for some then if at some point then by the implicit function theorem there's some neighbourhood where and so . Then . Similarly writing gives , which proves the reciprocity relation [and same for the other two combinations].

Now given writehence .
 
  • #41
@BWV that looks good to me now.

I think this is just a complicated version of you flip 2 coins which give values 1 if tails and 2 if heads, and let A= coin 1 is even, B= coin 2 is even, C=coin1+coin2 is even. If you want a simpler example in your toolbox :)

nuuskur said:
Hölder continuous implies uniformly continuous. So, we'll show that these conditions are not equivalent.

The set is compact and as . Hence is uniformly continuous.

Assume for a contradiction is Hölder continuous. That is, there exist and such that

In particular (taking ) we have for every that

But as . E.g apply L'Hopital to as . This is a contradiction, so cannot be Hölder continuous.
This looks good. An exercise for the reader I guess is to show that any continuous function on a compact interval is uniformly continuous.

ergospherical said:
I have two ways for problem 3, but can't think of a third right now.
i) by direct substitution:then .

ii) Given for some then if at some point then by the implicit function theorem there's some neighbourhood where and so . Then . Similarly writing gives , which proves the reciprocity relation [and same for the other two combinations].

Now given writehence .

This looks good to me. I think you might have made your second method too complicated. Once you have , then you also have by just copying the symbols in the same pattern
.

Fresh provided three methods that were implicit function theorem, and implicit differentiation to solve for the derivatives. I feel like the third method from here is a little non-obvious, so I'll just say it's computing the actual functions , and directly before taking any derivatives.
 
  • Like
Likes ergospherical and BWV
  • #42
Problem 12

Let such that

So we get,

We can see that as

Now let and be the roots of the quadratic equation

Putting the value of in the above equation as , we get

Similarly, putting the value of as , we get

As we can see that and are also rational numbers, moreover, as is a natural number, and should also be natural numbers

So, we get,

And

Putting that value of ,

Now, and are the only possible ways of writing as a product of two natural numbers,

So, the only solutions are
from this we get which is not possible
and from this and which is again not possible
and which gives and which is also not possible

So, cannot be a rational number if is a natural number.
 
  • #43
julian said:
Hi @kshitij . Sorry, for the delay. I've been seriously preoccupied.

OK, so you were assuming that:



holds and you wanted to show that it follows that



This condition, , is the final statement. You start with the final statement and what you do is you keep making changes that until something comes up, which together with the use , is true. But the changes that you make along the way must result in equivalent conditions so that finally you can write them down in the backward direction and end up with .

You correctly deduced that condition is equivalent to:



However, you didn't give a valid justificiation as to why the condition:



is equivalent to , and so you can't work backwards from to . That's the problem.
Hey @julian, Thanks for your reply, but I still have the same question,

you said that,

is correct

But as we have,

Similarly,

Now if we have a relation like,
, and
Then we can write
because the order between is

So, in our case, we have , , and

From we had , from we got and from we got

So, again the order between is

That gives

So, from we deduced that is true, then why is this wrong?
 
  • #44
julian said:
This condition, (∗∗), is the final statement. You start with the final statement and what you do is you keep making changes that until something comes up, which together with the use (∗), is true.
I do agree with what you said here, I also agree with your solution which was discussed earlier in this thread, but I think that there is another method of doing this problem which is with the use of orders which I mentioned above.

julian said:
But the changes that you make along the way must result in equivalent conditions so that finally you can write them down in the backward direction and end up with (∗∗).
But this statement is confusing for me.

If the problem involved only equalities, e.g., from we had to prove that
Then in this case we can always work backwards from to
We just have to show that , and
this would give us the only possibility, i.e.,

But if the question involves inequalities, e.g., from we had to prove that
Then in this case how can we always work backwards from to

unlike the first case, even if could have shown that , and
then that doesn't mean that if
because there are multiple possible orders between like
, , , etc
and all of them satisfy , and

In case of equality there is only one possibility i.e., but in case of inequalities there are multiple numbers between them so there are multiple possible orders between them

In other words we cannot do anything only using the relation by which we will end up with a fixed possible order between

So, how can we work backwards in this case if there are multiple possibilities?

Even in your solution, I cannot think how to work backwards from,

to get,
 
Last edited:
  • #45
kshitij said:
I do agree with what you said here, I also agree with your solution which was discussed earlier in this thread, but I think that there is another method of doing this problem which is with the use of orders which I mentioned above.But this statement is confusing for me.

If the problem involved only equalities, e.g., from we had to prove that
Then in this case we can always work backwards from to
We just have to show that , and
this would give us the only possibility, i.e.,

But if the question involves inequalities, e.g., from we had to prove that
Then in this case how can we always work backwards from to

unlike the first case, even if could have shown that , and
then that doesn't mean that if
because there are multiple possible orders between like
, , , etc
and all of them satisfy , and

As are not equal so there are multiple numbers in between them, similarly for as well

In case of equality there is only one possibility i.e., but in case of inequalities there are multiple numbers between them so there are multiple possible orders between them

In other words we cannot do anything only using the relation by which we will end up with a fixed possible order between

So, how can we work backwards in this case if there are multiple possibilities?

Even in your solution, I cannot think how to work backwards from,

to get,
On rereading, I get this feeling that may be I'm doing something wrong here, but I'm confused as we are dealing with inequalities here, if we had been dealing with equalities then everything you said makes sense to me.
 
  • #46
I think the simplest way to think about the 15 attempt is to actually just flip the order of everything. You wanted to prove (*) and took a bunch of steps to get from (*) to (****). But your actual goal was to start with (****) and get to (*). Often if you can go in one direction you can go in the other direction but it's not always true.

As a dumb example if then but the other direction is not true. There's nothing special about inequalities here.

If the steps are actually reversible, you should just reverse them. Start with (****) and get to (*) at the end.

I'll check your new 12 attempt later today.
 
Last edited:
  • #47
I think I figured out what was wrong

(refer to my first attempt of problem 15)

I wanted to show that
I knew that
is true.

I assumed that is also true

First I showed that and then I showed
so I concluded that
Now I did the same process with i.e., I first showed that and then by which I concluded that,

which is the same result that I got with

And here I concluded that since I got the same result with both the relations (this is known to be true) and (this I assumed to be true) then they both must be true!

However, when I do the same thing but this time assuming that and can still be true.

To elaborate, see the image below,
diagram-20210625.png

Lets say that and then after showing that and , I can say that,

Now see the situation of ,
diagram-20210625 6.png

It is known that and I showed again using and that
But unlike the previous case is known to be true, so must be true as well.

Now what if ?
diagram-20210625 5.png

You can clearly see that everything I did assuming can also be done using because still we can see that and

So, even though whatever I did with might be correct and even the relation is also correct, but that clearly didn't give us a relation between and !
And that is why the first attempt is incomplete (infact I achieved nothing new, I just played around with )
 
  • #48
kshitij said:
I think I figured out what was wrong

(refer to my first attempt of problem 15)

I wanted to show that
I knew that
is true.

I assumed that is also true

First I showed that and then I showed
so I concluded that
Now I did the same process with i.e., I first showed that and then by which I concluded that,

which is the same result that I got with

And here I concluded that since I got the same result with both the relations (this is known to be true) and (this I assumed to be true) then they both must be true!

However, when I do the same thing but this time assuming that and can still be true.

To elaborate, see the image below,
View attachment 285014
Lets say that and then after showing that and , I can say that,

Now see the situation of ,
View attachment 285015
It is known that and I showed again using and that
But unlike the previous case is known to be true, so must be true as well.

Now what if ?
View attachment 285016
You can clearly see that everything I did assuming can also be done using because still we can see that and

So, even though whatever I did with might be correct and even the relation is also correct, but that clearly didn't give us a relation between and !
And that is why the first attempt is incomplete (infact I achieved nothing new, I just played around with )
Now this looks quiet confusing to read as a third person who doesn't know what's going in my head, but to me it makes perfect sense!

Still if someone wants to read that, then the case was in the original attempt (see post #21 of this thread)
And the case was
And finally was

And yes and are basically the same thing but that doesn't make much difference in the process which I was explaining
 
Last edited:
  • #49
Office_Shredder said:
As a dumb example if x=y then x2=y2 but the other direction is not true. There's nothing special about inequalities here.
How do you consistently come up with an example that I overlook? 😅
 
  • #50
I really like that solution to 11* Writing that quadratic equation is pretty cool.
 
  • Like
Likes kshitij
  • #51
kshitij said:
Hey @julian, Thanks for your reply, but I still have the same question,

you said that,

is correct
Hi @kshitij. I'm preoccupied at the moment so I'll just address a couple of points.

I didn't say it was correct. I was saying that this condition:



is equivalent to this condition:



which follows from the fact that



Sorry, I'm tired at the moment. You do understand that you are supposed to be proving that is true - yeah?
 
Last edited:
  • #52
kshitij said:
Even in your solution, I cannot think how to work backwards from,

to get,
So you were assuming that



holds and you wanted to show that it follows that



is true.

We proved that:



We rewrite this as



and use it in our assumption to obtain:



We rewrite this as:



which is the same as



i.e. we have proven that holds.
 
  • Like
Likes kshitij
  • #53
julian said:
Hi @kshitij. I'm preoccupied at the moment so I'll just address a couple of points.

I didn't say it was correct. I was saying that this condition:



is equivalent to this condition:



which follows from the fact that



Sorry, I'm tired at the moment. You do understand that you are supposed to be proving that is true - yeah?
I did realize my mistake, thank you for your help and also for showing how to work backwards from to
 
  • Like
Likes julian
  • #54
I want to explicitly say thank you to @Office_Shredder for managing this month's Challenge thread. It was a great relief to have a break while he bothered incoming answers. Thanks a lot!
 
  • #55
Problem #5:

Question (a): Let be an automorphism of the symmetric group such that sends transpositions to transpositions, then prove that is an inner automorphism.

Question (b): Determine the inner automorphism groups of (i) the symmetric groups and (ii) the alternating groups for .

Answer (a):

The transpositions are a generating set for for . We have that for , where and where . As and don't commute, their images and don't commute. As such their intersection is a single number. WOLG we assume that .

We prove that for . Assume otherwise, that is assume that for some we have that . As does not commute with we must have that . Similarly, as and don't commute. Therefore, . But then we would have



which is in contradiction with the fact that is injective.

Thus the transpositions transforms the element , and WLOG we can assume for all . All the integers and are all distinct. So we have that , , and for .

Consider the element defined by and . We have



and



and when :



Thus we have shown that agrees with the inner automorphism on all the generators of the group and so it is an inner automorphism of .

QED

Answer (b) (i):

Lemma 1: Let be a group with centre . Then .

Proof: Let . An inner automorphism of is given by

Define a group homomorphism:



by



is clearly surjective. We identify the kernel of . We have that:



We then apply the first isomorphism theorem.

QED

The centre of for is the identity permutation .

Proof: Suppose that is an arbitrary element of which is not the identity. Choose such that . Because there is and let . Then:



so that does not belong to the centre.

QED

Using this result in lemma 1 we obtain that



Answer (b) (ii):

The centre of for is the identity permutation .

Proof: Suppose that is an arbitrary element of which is not the identity. Choose such that . Because we can choose distinct and such that and let . Then:



so that does not belong to the centre.

QED

Using this result in lemma 1 we obtain that

 
Last edited:
  • #56
Problem #8:

By definition



If we can show that:



where is an integer then we would have



Since none of the factors in divide no in the numerator can be canceled out. Thus would divide the numerator.

In the polynomial



the term is given by



If we can show that that will solve the problem.

We have .

Fermat's little theorem says that for any integer . It follows that modulo , that has the roots roots . So that:



Note that modulo , and have the same roots.

Also, Wilson's theorem says that:



Using all of the above in the polynomial we obtain



As this is a polynomial of degree with the solutions by Lagrange's theorem divides all the coefficients.

Putting in gives



Subtracting from both sides, dividing by , and then rearranging gives



As we are taking , and as each of the coefficients is proportional to the RHS is equal to where is an integer.

If were equal to 3 we couldn't say that the term is proportional to as . The result clearly doesn't apply to :

 
Last edited:
  • #57
This is a variation on the first proof I gave for problem #8 in the previous post. It avoids mod arithmetic and knowing theorems:

Again we solve the problem by showing that



is equal to where is an integer.

First we prove that if is prime and , then . We have



As none of the factors in can divide the cannot be cancelled. Hence divides .

Consider the polynomial



where the 's are the same as before. We will prove that the coefficients are all divisible by when is an odd prime.

Proof: Note that



and so



implying



Hence,



By equating coefficients if of we obtain:



From the first equation, using that , we have that . Using this in the second equation together with , we have that . And so on. So we have .

QED

Putting into



then rearranging gives



As we are taking , and as each of the coefficients is proportional to the RHS is equal to where is an integer. Solving problem #8.

QED
 
Last edited:
  • #58
Problem #6:

By definition



where be the Hamming distance of and . A bound is proved by bounding the quantity



in two different ways. On the one hand, there are choices for and for each such choice, there are choices for . Since by definition for all and (), it follows that



The other inequality is obtained by writing down all the codewords of into a -matrix. Let denote the number of times the element of the alphabet (with elements) occurs in the th column. For each choice of in the th column there are elements not equal to in the same column. Then



Combining the two bounds gives



or



If the bound can be rearranged as

 
Last edited:
  • Like
Likes fresh_42
  • #59
Problem #7:

We start with a reminder of the definition of the Cantor dust. Define as:



Take the two intervals and split them into thirds. Then remove each of their open middle thirds to get



To get the next set , split each of the four intervals of into three equal parts and remove their open middle thirds. Continue this way for each . The Cantor dust is the intersection of all these :



To prove it is uncountable, first we express any number in the unit interval in its tri-adic expansion



where takes the values zero, one or two. We can write the tri-adic expansion in base three notation, to obtain



As with the decimal expansion, the base three expansion's coefficients are unique, provided we always round up. Thus we will say that



for example (the case we leave as it is).

In terms of the base three expansion



We prove that the Cantor dust is uncountable by contradiction. We assume there is a bijective map and then prove that there is a number in that not in the image of , contradicting that is surjective.

Let us list the images of our assumed bijection :



Note that the , etc are now fixed numbers that are either or , given to us by the assumed bijection. We will construct a new number that cannot appear in the above list, thereby contradicting the assumption that is surjective. Set



Note that is if and is if . Thus



Likewise, is if and is if and so



And so on indefinitely. Since the base three expansions are unique, and since each is defined so that it is not equal to the term in , we must have that is not equal to any , meaning that cannot be surjective.

With Cantor dust, the portion of the object corresponding to the initial one-third of the original segment is an exact replica of the complete object, but at 1/3rd its scale. Note, moreover, that you need 2 copies of the scaled-down object to cover the object at full-scale. Hence, the Hausdorff–Besicovitch dimension is

 
  • Like
Likes fresh_42
  • #60
julian said:
Problem #5:

Question (a): Let be an automorphism of the symmetric group such that sends transpositions to transpositions, then prove that is an inner automorphism.

Question (b): Determine the inner automorphism groups of (i) the symmetric groups and (ii) the alternating groups for .

Answer (a):

The transpositions are a generating set for for . We have that for , where and where . As and don't commute, their images and don't commute. As such their intersection is a single number. WOLG we assume that .

We prove that for . Assume otherwise, that is assume that for some we have that . As does not commute with we must have that . Similarly, as and don't commute. Therefore, . But then we would have



which is in contradiction with the fact that is injective.

Thus the transpositions transforms the element , and WLOG we can assume for all . All the integers and are all distinct. So we have that , , and for .

Consider the element defined by and . We have



and



and when :



Thus we have shown that agrees with the inner automorphism on all the generators of the group and so it is an inner automorphism of .

QED

Answer (b) (i):

Lemma 1: Let be a group with centre . Then .

Proof: Let . An inner automorphism of is given by

Define a group homomorphism:



by



is clearly surjective. We identify the kernel of . We have that:



We then apply the first isomorphism theorem.

QED

The centre of for is the identity permutation .

Proof: Suppose that is an arbitrary element of which is not the identity. Choose such that . Because there is and let . Then:



so that does not belong to the centre.

QED

Using this result in lemma 1 we obtain that



Answer (b) (ii):

The centre of for is the identity permutation .

Proof: Suppose that is an arbitrary element of which is not the identity. Choose such that . Because we can choose distinct and such that and let . Then:



so that does not belong to the centre.

QED

Using this result in lemma 1 we obtain that

Right. You could have saved some time in the second part by observing that are simple for and which have no center. For the Klein four-group adds to the candidates for a center, but isn't Abelian.
 
  • #61
julian said:
Problem #8:

By definition



If we can show that:



where is an integer then we would have



Since none of the factors in divide no in the numerator can be canceled out. Thus would divide the numerator.

In the polynomial



the term is given by



If we can show that that will solve the problem.

We have .

Fermat's little theorem says that for any integer . It follows that modulo , that has the roots roots . So that:



Note that modulo , and have the same roots.

Also, Wilson's theorem says that:



Using all of the above in the polynomial we obtain



As this is a polynomial of degree with the solutions by Lagrange's theorem divides all the coefficients.

Putting in gives



Subtracting from both sides, dividing by , and then rearranging gives



As we are taking , and as each of the coefficients is proportional to the RHS is equal to where is an integer.

If were equal to 3 we couldn't say that the term is proportional to as . The result clearly doesn't apply to :

Right. The result is known as the Theorem of Wolstenholme.
 
  • #62
julian said:
Problem #6:

By definition



where be the Hamming distance of and . A bound is proved by bounding the quantity



in two different ways. On the one hand, there are choices for and for each such choice, there are choices for . Since by definition for all and (), it follows that



The other inequality is obtained by writing down all the codewords of into a -matrix. Let denote the number of times the element of the alphabet (with elements) occurs in the th column. For each choice of in the th column there are elements not equal to in the same column. Then



Combining the two bounds gives



or



If the bound can be rearranged as

The bound is called Plotkin bound.
 

Similar threads

3
Replies
100
Views
9K
4
Replies
114
Views
8K
2
Replies
61
Views
9K
3
Replies
86
Views
11K
2
Replies
67
Views
9K
2
Replies
42
Views
8K
2
Replies
56
Views
8K
2
Replies
61
Views
11K
3
Replies
93
Views
13K
2
Replies
60
Views
10K
Back
Top