When you randomly shuffle a deck of cards, what is the probability that it is a unique permutation never before configured? I just came back from a class on Probability in Game Theory, and was musing over something in my head.

Assuming, for the sake of the question:

Playing cards in their current state have been around for approximately eight centuries
A deck of playing cards is shuffled to a random configuration one billion times per day
Every shuffle ever is completely (theoretically) random and unaffected by biases caused by human shuffling and the games the cards are used for
By "deck of cards", I refer to a stack of unordered $52$ unique cards, with a composition that is identical from deck to deck.

This would, approximately, be on the order of $3 \cdot 10^{14}$ random shuffles in the history of playing cards.

If I were to shuffle a new deck today, completely randomly, what are the probabilistic odds (out of $1$) that you create a new unique permutation of the playing cards that has never before been achieved in the history of $3 \cdot 10^{14}$ similarly random shuffles?

My first thought was to think that it was a simple matter of $\frac{1}{52!} \cdot 3 \cdot 10^{14}$, but then I ran into things like Birthday Paradox.  While it is not analogous (I would have to be asking about the odds that any two shuffled decks in the history of shuffled decks ever matched), it has caused me to question my intuitive notions of Probability.

What is wrong in my initial approach, if it is wrong?

What is the true probability?

And, if the probability is less than $0.5$, if we how many more years (centuries?) must we wait, assuming the current rate of one billion shuffles per day, until we reach a state where the probability is $0.5$+?   $0.9$+?

(Out of curiosity, it would be neat to know the analogous birthday paradox answer, as well)

Your original answer of $\dfrac{3 \times 10^{14}}{52!}$ is not far from being right. That is in fact the expected number of times any ordering of the cards has occurred.

The probability that any particular ordering of the cards has not occurred, given your initial assumptions, is $\left(1-\frac1{52!}\right)^{(3\times10^{14})}$, and the probability that it has occurred is 1 minus this value.  But for small values of $n\epsilon$, $(1+\epsilon)^n$ is nearly $1+n\epsilon$.  In particular, since $52!\approx 8\times 10^{67}$ and so $\dfrac{3\times10^{14}}{52!}\approx 3.75\times 10^{-54}$ is microscopically small, $1-\left(1-\frac1{52!}\right)^{(3\times10^{14})}$ is very nearly $\frac1{52!}\times (3\times10^{14})$.


The word "times" for multiplication...? The word "times" for multiplication operation which is quite touching to the concept of time (feeling time this way 0*1=0). When was introduced that term? Did any other language have the kind of term for multiplication?

See Anthony Lo Bello, Origins of mathematical words :  A Comprehensive Dictionary of Latin, Greek, and Arabic Roots (2013), page 218 :

  multiple This is derived from the Latin adjective multiplex, multiplicis, which means folded many times. In late Latin, multiplex became multiplus, and this accounts for the absence of the c in multiple.

See latin multiplico

  Etymology : From multus (“much, many”) + plicō (“fold, double up”).

This latin plicō, like the ancient Greek : πλεκτός - "plaited, twisted", comes from Indo-European pleḱ- : “to plait, to weave”.

See in English : to fold, manifold, twofold.

In "current" Italian, we can say :

  "due volte dieci fa venti"

for : "two times ten is twenty".

An ancient vernacular manuscript of around 1300 uses :

  "doi via dece fa vinti";

see :

Jens Høyrup, Jacopo da Firenze's Tractatus Algorismi and Early Italian Abbacus Culture (2007), page 204.

Both italian terms (the ancient and the current one) are not strictly connected with time; but in "due volte dieci" the word "volta" is used also in context like "dar la volta", which means : rovesciare, i.e. reverse.

Thus, it share with "times" and similar the role of express a "factor of repetition" or iteration, like in : "how many times ?"

Google says it was introduced in late middle English.


Proving every tree has at most one perfect matching In trying to prove that every tree, T, has at most one perfect matching, I came across this idea:

  Since the matchings are perfect, each vertex has degree $0$ or $2$ in the symmetric difference, so every component is an isolated vertex or a cycle.

Why is this true?  Why is it true that since each vertex is either of degree $0$ or of degree $2$, then all components are either isolated or a cycle?

First, why the claim is true. Take any vertex. If it's matches to the same vertex in both perfect matching, then it had degree zero on the symmetric difference. Otherwise it has degree two.

Second, after removing all isolated vertices in the symmetric difference, all vertices have degree two. Take any such vertex and follow its two edges. What you get is a growing path that eventually closed to a cycle since the graph is finite.

Since trees have no cycles, this implies that any two perfect matching are equal, by consisting their symmetric difference.

A different proof is by induction. The idea is that every leaf must be matched to its unique neighbor.

Since every tree of two or more vertices is two chromatic. Tree with even no of vertices will have the perfect matching as all the vertices with same color can be grouped together and a matching can be established between two groups. But any tree with odd no of vertex will have no perfect matching for obvious reason. Hence proved.


Can the field of fractions of an integral domain R be free as an R-module? We know any integral domain R when extended to a quotient field F, then F is free as an F-module on the set {1}.
Can this field be free as an R-module?

If $F$ is free of rank one over $R$ then $F=R\cdot1=R$ and $R$ was a field to begin with.

Otherwise suppose it is free of rank greater than one, so it has at least two summands which are copies of $R$ which must be generated by some fractions, which means $R\frac{a}{b}\cap R\frac{c}{d}=0$ must hold for some values $a,b,c,d\in R$... is that possible?

Any free $R$ module is isomorphic to $F=R\oplus R\oplus R \oplus ...$

Notice that if it has more than one component it has a proper ideal $I=R\oplus O\oplus 0\oplus...$ which is not possible for a field so we must have $F=R$. Thus, $R$ also must be a field.

If you mean only $(F,+)\cong (R\oplus R...R,+)$ and do not use natural multiplication on $R\oplus R..$ then it is possible.

Example: Let $R=Z_p$ where $p$ is prime and Let $M=Z_p\oplus Z_p$ then $M$ is an free $R$ module with rank $2$ then $(F,+)\cong M$ where $F=Z_p(i)\cong Z_p[x]/(x^2+1)$. (which means that by putting appropriate $*$ on $M$, we can get $(M,*,+) $ as field )


Finding the biggest $n$ that is divisible by all $m < \sqrt[3]{n}$ Find the biggest positive integer $n$ such that $n$ is divisible by all positive integers smaller than the integer part of the cubic root of $n$.

I'm quite sure it's $420$, but I need proof for that.

I think you mean "must be divisible by all positive integers less than its cube root". (Now confirmed in the comments.)

Suppose the number was at least 420. Then the floor of its cube root is at least 7, and hence it must be divisible by 1, 2, 3, ..., 7 and so must be a multiple of 420. If it is greater than 420 it must be at least 840 and hence its cube root is 8 and so it must be divisible by 840. But if it's at least 840 it must be divisible by lcm(1, 2, ..., 9) = 2520 and hence must be divisible by lcm(1, ..., 13) = 360360.

This pattern looks like it will continue, so let's prove it! If the next interval is at least twice as long as the last, it will contain a new prime (at least 11) and so the new interval will be at least 11 times longer than the previous. 11 > 8 so the cube root increases by a factor of > 2, and hence by Bertrand's postulate we get another prime next time. Done!


Generalization of Pythagorean triples Is it known whether for any natural number $n$, I can find (infinitely many?) nontrivial integer tuples $$(x_0,\ldots,x_n)$$ such that $$x_0^n + \cdots + x_{n-1}^n = x_n^n?$$

Obviously this is true for $n = 2$.

Thanks.

These Pythagorean triples can appear in the most unexpected place.

If:  $a^2+b^2=c^2$

Then alignment: $N_1^3+N_2^3+N_3^3+N_4^3+N_5^3=N_6^3$

$N_1=cp^2-3(a+b)ps+3cs^2$

$N_2=bp^2+3bps-3bs^2$

$N_3=ap^2+3aps-3as^2$

$N_4=-bp^2+3(2c-b)ps+3(3c-3a-2b)s^2$

$N_5=-ap^2+3(2c-a)ps+3(3c-2a-3b)s^2$

$N_6=cp^2+3(2c-a-b)ps+3(4c-3a-3b)s^2$

And more:

$N_1=cp^2-3(a+b)ps+3cs^2$

$N_2=bp^2+3bps-3bs^2$

$N_3=ap^2+3aps-3as^2$

$N_4=(3c+3a+2b)p^2-3(2c+b)ps+3bs^2$

$N_5=(3c+2a+3b)p^2-3(2c+a)ps+3as^2$

$N_6=(4c+3a+3b)p^2-3(2c+a+b)ps+3cs^2$

$a,b,c$ - can be any sign what we want.

And I would like to tell you about this equation:

$X^5+Y^5+Z^5=R^5$

It turns out the solution of integral complex numbers there. where: $j=\sqrt{-1}$

We make the change:

$a=p^2-2ps-s^2$

$b=p^2+2ps-s^2$

$c=p^2+s^2$

Then the solutions are of the form:

$X=b+jc$

$Y=-b+jc$

$Z=a-jc$

$R=a+jc$

$p,s$ - what some integers.


Number of People Required (Arena Survival Question) Slaves are fighting in an arena.  Each fight involves two slaves and results in one winner and one loser.  Two slaves may fight one another only if they have an identical number of wins.

A slave with $3$ losses will be kicked out of the arena.

A slave with $12$ wins will be freed from the arena.

  How many slaves do we need at least to free one slave?

Start with $43$ fighters named $f_1, f_2, f_3, \ldots, f_{43}$,
each of whom has neither won nor lost a fight.

The ten fighters $f_{33}, f_{35}, \ldots, f_{42}$
each fight three fighters from among $\{f_1, f_2, \ldots, f_{32}\}$,
losing each fight (so those ten fighters are thrown out),
and $f_{43}$ fights two of the remaining fighters, losing both fights.
We now have $32$ fighters each with one win and no losses,
and one fighter (whom we will not use again) with two losses and no wins.

Next, the eight fighters $f_{25}, f_{26}, \ldots, f_{32}$
each fight three fighters from among $\{f_1, f_2, \ldots, f_{24}\}$,
losing each fight, and are thrown out.
We now have $24$ fighters each with two wins and no losses.

Next, the six fighters $f_{19}, \ldots, f_{24}$ lose three fights each
with fighters among $\{f_1, f_2, \ldots, f_{18}\}$,
so we then have $18$ fighters each with three wins and no losses.

Next, $f_{14}$ loses fights with $f_1$ and $f_2$,
then $f_{15}$, $f_{16}$, $f_{17}$, and $f_{18}$ each lose three fights
with fighters among $\{f_3, f_4, \ldots, f_{14}\}$.
We now have $13$ fighters with four wins and no losses,
and one fighter ($f_{14}$) with four wins and two losses.

Next, the four fighters $f_{11}$, $f_{12}$, $f_{13}$, and $f_{14}$
lose a total of $10$ fights (one loss for $f_{14}$, three for each of
the others) against the ten fighters in $\{f_1, f_2, \ldots, f_{10}\}$.
We now have $10$ fighters with five wins and no losses.

Next, $f_6$ loses fights with $f_7$ and $f_8$, then $f_9$ and $f_{10}$ each
lose three fights with the fighters among $\{f_1, f_2, \ldots, f_6\}$.
We now have seven fighters with six wins and no losses,
and one fighter ($f_6$) with six wins and two losses.

Next, $f_7$ and $f_8$ each lose three fights against the six fighters
in $\{f_1, f_2, \ldots, f_6\}$.
We now have five fighters with $7$ wins and no losses, and one fighter
($f_6$) with $7$ wins and two losses.

Next, $f_1$ beats $f_2$, $f_2$ beats $f_3$, $f_3$ beats $f_4$,
$f_4$ beats $f_5$, and $f_5$ beats $f_6$, in that order.
This eliminates $f_6$ and we are left with one fighter ($f_1$) with $8$ wins
and no losses and four fighters with $8$ wins and one loss each.

Next, $f_2$ beats $f_1$, $f_3$ beats $f_4$, and $f_1$ and $f_4$ each beat $f_5$. At that time, $f_5$ is eliminated, $f_1$, $f_2$, and $f_3$
each have $9$ wins and one loss, and $f_4$ has $9$ wins and two losses.

Next, $f_1$ beats $f_2$, $f_2$ beats $f_3$, and $f_3$ beats $f_4$.
This eliminates $f_4$; $f_1$ has $10$ wins and one loss, and
$f_2$ and $f_3$ have $10$ wins and two losses each.

Next, $f_2$ beats $f_1$, then $f_1$ beats $f_3$ (eliminating $f_3$).
Now $f_1$ and $f_2$ have $11$ wins and two losses each.

Finally, $f_1$ beats $f_2$ and is freed.

The description above is a proof by construction that $43$ fighters
are sufficient to free one fighter.
Now we show that $43$ fighters are necessary; that is, it is not possible
for a fighter to be freed if we start with fewer than $43$.

First, some definitions. Round $n$ consists of all fights between
fighters with $n - 1$ previous wins.
Since every fight in round $1$ is between fighters with no previous fights,
and for $n>1$ every fight in round $n$ is between fighters who
fought in round $n - 1$, whatever sequence of fights leads to a
fighter being freed, we can reorder the fights so that all fights
of round $n$ precede all fights of round $n+1$ for each $n$.

At any given time, a fighter who has previously won $W$ fights and lost $L$ fights (which we'll abbreviate as "a $(W,L)$ fighter")
has a "value" $v(W,L)$.
The idea is to assign values so that the sum of values of all the fighters
can never increase, and so that the sum of values of all fighters who have
not yet been thrown out is always a reasonably tight lower bound of the
number of fighters we had to start with in order to produce fighters
with these win-loss records.

Clearly $v(0,0) = 1$ works for the value of the fighters at the start,
and $v(W,3) = 0$ works for fighters who have been thrown out after any
number of wins.
In round $1$, after each fight we subtract $\frac13$ from the loser's value, so that at the end of the round all $(0,3)$ fighters have value $0$.
Hence $v(0,L) = 1 - \frac13L$ for $0 \leq L \leq 3$.
But we set $v(1,L) = \frac43(1 - \frac13L)$, which means a
$(0,0)$ fighter gains $\frac13$ by winning a fight,
a $(0,1)$ fighter gains $\frac29$, and a $(0,2)$ fighter gains $\frac19$.
This maintains the requirement that the sum of values never increases,
but reflects that fact that to get $3N$ fighters with $(1,0)$ records,
it is necessary and sufficient to have $4N$ fighters at the beginning.

The general formula will be $v(W,L) = (1 - \frac13L)(\frac43)^W$.
So in round $W+1$, each loss reduces the loser's value by $\frac13(\frac43)^W$ and increases the winner's value by either
$\frac13(\frac43)^W$, $\frac29(\frac43)^W$, or $\frac19(\frac43)^W$,
depending on whether the winner had $0$, $1$, or $2$ losses already.

Now, working from the desired final state (a fighter with $12$ wins)
backward, since the loser of the last fight in round $n$ never advances
to round $n+1$, we must have had one fight in round $12$, two in
round $11$, three in round $10$, and so forth.
In particular, in the rounds after round $6$ we must have
$6 + 5 + 4 + 3 + 2 + 1 = 21$ fights to promote a single fighter to $12$ wins,
which means $21$ losses.
Moreover, these $21$ losses, plus whatever losses the fighters in round
$7$ already had at the start of the round, must add up to less than
three times the number of fighters in that round, since more losses than
that would get them all thrown out. That is,
if the $k$th fighter in round $7$ had $L_{7,k}$ losses at the start of the round, then over those fighters, $\sum(3-L_{7,k}) \geq 22$.

It follows that at least $\lceil 22/3\rceil = 8$ fighters had to
win round $6$ to advance to round $7$.
So at the start of round $6$ there are at least $29$ fights to go
and at the beginning of that round we must have
$\sum(3-L_{6,k}) \geq 30$ summed over the fighters in that round.

But $\left(\frac13\sum(3-L_{6,k})\right)(\frac43)^5$ is exactly the value
at the start of round $6$
of all the $(5,L_{6,k})$ fighters who fight in that round.
Therefore the value of those fighters is at least
$\frac13 \cdot 30 \cdot (\frac43)^5 \approx 42.14$,
so we must have started with more than
$42$ fighters, that is, at least $43$ fighters.

Assuming there are no fatalities.

For $n$ fighters and we fight until there are no more fights we can schedule by the rules given.

There must be exactly one fighter with no wins.
Win-less fighters can only fight win-less fighters, and somebody must lose that fight.

There cannot be two win-less fighters, or they would square off until there was only one.

For $n<12$ fighters there is one fighter for each $k, 0\le k< n$ wins.

If there are 13 fighters one fighter will amass 12 wins.


All the natural numbers are of form $x^2+y^2+z^2+w^2+xy+zw$ Is there any natural number that cannot be written as $x^2+y^2+z^2+w^2+xy+zw$, where $x,y,z,w$ are integers? If there is none, how do I prove that all the natural numbers are of form $x^2+y^2+z^2+w^2+xy+zw$?

$x^2 + xy+ y^2$ represents exactly the same numbers as $u^2 + 3 v^2.$ You are asking whether $$ s^2 + 3 t^2 + u^2 + 3 v^2   $$ is positive universal. It is.

More: a variation of quaternion multiplication shows that, when this form represents two numbers, call them $m,n,$ then it also represents $mn.$ Meanwhile,
$$ s^2 + 3 t^2 + u^2  $$ is a regular ternary form, in particular it represents $1,2,3,$ and all numbers not divisible by $3,$ which includes all other primes. From the multiplication property, it follows that all (positive) numbers are represented.

For information about what numbers are represented by $s^2 + 3 t^2 + u^2,$ see the entry for $1,1,3$ in Dickson_Diagonal_1939.pdf at TERNARY. Acomplete proof is given as Theorem 89, pages 97-99, of Dickson's book.

By the $15$ theorem, it suffices to check all naturals up to $15$. The margin is too small to fit my proof so the task is left to the reader.


Is $\mathbb{R}^n$ a polyhedron? A polyhedron is defined as the intersection of a finite collection of generalized halfspaces. In my book, a generalized halfspace is defined as a set where we allow the vector of coefficients $(a_1, a_2,\ldots, a_n )$ in the definition of a halfspace to vanish (or = 0).

I said yes. $\mathbb{R}^n$ is a polyhedron because a generalized halfspace can be all of $\mathbb{R}^n$. But I feel there's something wrong with that logic. Please help. Thanks.

$\mathbb{R}^n$ is not a polyhedron. You mentioned that a generalized halfspace can be all of $\mathbb{R}^n$, but that is not that case. By definition, a halfspace can only emcompass half of $\mathbb{R}^n$. I'm not sure what definition you're given for a generalized halfspace, but it's just the direct analogue of the three dimensional case.

Since a polyhedron is by definition the intersection of a finite collection of halfspaces, if $\mathbb{R}^n$ is a polyhedron then there must be at least one halfspace that describes it. However, as noted above, $\mathbb{R}^n$ cannot be described by a single halfspace. Additionally, whenever another halfspace is added to your collection of halfspaces that describe $\mathbb{R}^n$, the number of possible points described cannot increase (that is, at best you retain the same number of points in the intersection). Since a single halfspace does not describe $\mathbb{R}^n$ and the addition of other halfspaces cannot add points to the description of $\mathbb{R}^n$, $\mathbb{R}^n$ cannot be described by the intersection of a finite number of halfspaces. Thus, $\mathbb{R}^n$ is not a polyhedron.

Geometry isn't exactly my area of expertise, either. So let's start with the basics: What is the definition of a "generalized half-space"? Wikipedia's article on half-spaces gives the following definition:

  In geometry, a half-space is either of the two parts into which a plane divides the three-dimensional Euclidean space. More generally, a half-space is either of the two parts into which a hyperplane divides an affine space.

From this definition, I would say that $\mathbb{R}^n$ is not a generalized halfspace itself. Now, can we take the intersection of a finite collection of generalized halfspaces to get $\mathbb{R}^n$? Let's assume that we can do so. Name the collection $\mathbb{H}$. Now consider one of these generalized halfspaces $H \in \mathbb{H}$. Now we must have $\mathbb{R}^n \subseteq H$ because by our assumption $\mathbb{R}^n = \bigcap \mathbb{H}$. However, this is a contradiction.


Probability that each student will have a chair to their needs 20% of all students are left handed. A class of size 20 meets in a room with 5 left handed
and 18 right handed chairs. Find the probability that each student will have a chair to
their needs?

What type of distribution is this and how would I go about solving this?

Let $X$ be the number of left-handed students in the class, then (assuming that each student is left- or right-handed independently of the other students) $X$ is a binomial random variable with parameters $p=\frac{1}{5}$ and $n=20$.

Moreover, assuming that the students cooperate with each other, each student will have a suitable chair if and only if $2\leq X\leq 5$.

There are 4 left-handed students and 16 right-handed students. If they sit randomly, there are $\binom{23}{20}$ seating arrangements.

There are $$\binom{5}{4}\binom{18}{15}$$ ways to have students' needs met.

This looks like a hypergeometric distribution

with $N=23, K=5, n = 15, k = 4$


Random but very interesting probability question! There are 100 types of cards, each type with a number from 1 to 100 on it.
Each minute I am given a random card. Random means that the number of my card has an equal chance of being 1,2,3,...,100.
I stop when I have cards of each number, that is, I stop collecting once I have each number on at least one card.
How many minutes is this process expected to take? That is, find the expected value of the number of minutes I have to wait.

E.g. I could potentially get duplicates so this method will take a lot more than 100 minutes. Once I get 99 different cards, I will stop as soon as I get the other one which I haven't got yet.

Thanks for helping everyone!

Well the first card 1 minutes, the second card $\frac{100}{99}$ minutes, the third card $\frac{100}{98}$ minutes, and so on.
So it is expected to take $(1 + \frac{100}{99} + \frac{100}{98} + ... + \frac{100}{1})$ which is around 519 minutes.


Prove this rank related problem Suppose $A$ is a matrix such that $A^2\neq0$ but$A^3=0$.Then prove that $rank(A)>rank(A^2)$ and $rank(A)\neq tr(A)$.

$rank(AB)\leq$min{$rank A,rank B$}.Then $rank(A^2)\leq rank(A)$.How to prove the reamining part?

If $A^3=0$, then $A$ is nilpotent. Since $A$ is nilpotent, all of its eigenvalues are $0$, so its trace is also $0$ (because the trace is equal to the sum of the eigenvalues).

Now you just need to prove that the rank is strictly bigger than $0$. Can you take it from here?

As A^3=O so A is nilpotent matrix.So  eigan values of A are all zeros(0).
 Hence Trace(A)=0;.......(1) Since trace(A) is nothing but the summation of eigan values.

Now A is non zero matrix because A^2 is not a null matrix,so rank(A)>0;.........(2) Since rank(A)=0 iff A=O.

Hence from above (1) and (2) rank(A)>trac(A).

This comple the proof.


Mean Value Theorem Proofing For all $ x>0$ By applying the Mean Value Theorem to the function $f(t)=e^t$ defined on the interval $[0, x]$, where $x > 0$, show that for all $x > 0$, $e^x>1+x$.

What I have done...

$f(t) = e^t$
$f$ is continuous on $[0,x]$ and differentiable on $(0,x)$.

For at least one $C$ in domain $(0,x)$ such that
$(f(b)-f(a))/(b-a) = f'(C)$

$(e^0 - e^x)/(-x) = e^c$

$1-e^x = -xe^c$

How do I continue the proof from here?

By the mean value theorem, we have $c\in[0,x]$ such that

$f(x)-f(0)=f'(c)(x-0)$

That is, $e^x-1=e^cx$

Since $e^x$ is increasing and $c>0$ then $e^c>e^0=1$

Thus $e^x-1=e^cx>x$ and thus $e^x>1+x$

Hint: f'(c) is greater than 1, c in (0,x).


Implies sign in math I get myself confused sometimes when to use => or =

= x + y = x + 5 = x = -5

or

=> x + y => x + 5 => x = -5

Neither of those are right.  It should be:
$$x + y = x + 5 \implies x = -5.$$
(Though I have to say, I'm not exactly sure how $x = -5$ directly follows from $x + y = x + 5$ to begin with.)

Let's first distinguish between expressions and equations.  Expressions are things like $x + 2$ or $37$ or $x^2 - 2x$.  On the other hand, an equation is an equality between two expressions, such as $x + 2 = 3$ or $x = 1$ or $8 + 9 = 17$ and so on.  So, an equality says that two expressions are the same, and we use the equals sign $=$.

Note that an equality is making a logical claim (true or false), whereas an expression is not.  For example, $6 = 6$ is a true equality, whereas $1 = 2$ is a false equality, whereas $17$ is just an expression (not true or false).

Now, the implies sign $\implies$ is used to show that one equation can be logically deduced from another.  So, the implication
$$x + 2 = 3 \implies x = 1.$$
means that from the equation $x + 2 = 3$, we can conclude that $x = 1$.

Note that it does not make sense to use the implication arrow between expressions.  For example $x + y \implies x = -5$ does not make any sense, because the $x + y$ is an expression.  After all, what is the truth value of $x+ y$ anyway?  There isn't one.

I think that equal sign is used for showing equality between first and second step but implies that is used for getting into the next step.


In-depth example or implementation of adaptive control (direct/indirect MRAC)? I have seen some examples where adaptive control is used to counter sudden changes in a system with great success. Since I find the subject quite interesting, I would like to learn how to actually implement an adaptive control loop, with the end goal being to write a flight controller for a quadcopter (this is something for the future though). I have found some quite good theoretical text-books on the matter, but not really any good in-depth examples or implementations. The methods that seems most interesting to me are the direct and indirect MRAC.

So in short: Where can I find a good in-depth example/implementation of an adaptive control loop?

I would begin with the excellent book by Gang Tao: http://www.amazon.com/Adaptive-Analysis-Learning-Processing-Communications/dp/0471274526/ref=sr_1_1?ie=UTF8&qid=1365779105&sr=8-1&keywords=gang+tao+adaptive+control

You can very easily implement his algorithms in MATLAB/Simulink. For instance, the adaptive dead-zone and backlash algorithms are fairly straightforward.

Shiyu's answer, regrettably, contains a number of false assertions.

In any physical system, you are going to encounter parametric uncertainty. Consider a control actuator in a vehicle. You can spend millions of dollars attempting to identify what the free-play in the actuator will be. Then, you'll drive the vehicle, and the actuator will wear, and that free-play gap will change. Then, you'll bring it in for maintenance, and that gap changes again.

Then, the next vehicle rolls off the assembly line, and it will have a different operational/maintenance history, and have entirely different characteristics. Therefore, any parameter you identify experimentally will be obsolete, and using that value as a ground-truth for your parameterized system could actually be harmful.

MRAC is designed to identify and adapt to these parameters. Therefore, the controller will adapt to whatever the parameter happens to be. Furthermore, in many algorithms, convergence is guaranteed!

Model-building is a necessary step in any control scheme. MRAC allows you to use those same models for your adaptive controller. In fact, adaptive control schemes can sit on top of extant control laws without the need to modify the stable controller at all.

MRAC is not used in flight controls not because it is too slow or too risky; it's because Validation and Verification (V&V) is so expensive and difficult. But for a remote-controlled quadrotor, an adaptive controller is a completely suitable approach. The algorithms are real-time algorithms, so there is no need for multiple iterations per time step. If you have a simple linearized model, all you'll need is to be able to clear a few matrix-vector multiplications in each time step. That's not terribly difficult. Obviously, it depends on the dimensionality of your model, but your quadrotor model shouldn't be that complex.

First, I would recommend you to search and read some academic papers on what you are interested in. I believe there are many papers on designing adaptive control for quadrotors with implementations.

Second, in my opinion, it is not quite proper to apply adaptive control to flight control.
Reason 1: Adaptive control usually are applicable to systems with unknown but constant parameters. In flight control, usually it is required to build a very good flight model before you start to design controllers. A flight model with unknown parameters is not acceptable. If there is an unknown parameter, in stead of designing an adaptive controller to handle this parameter, we should do experiments to identify it. Reason 2: flight control requires controllers to response fast. But adaptive control usually are applied to relatively slow plants such as industrial processes. It is possible a quadrotor crashes before the adaptive control can stabilize it.

So if the model is not highly nonlinear, PID, LQR, $H_2$, $H_{\infty}$ probably are good choices. If the model is highly nonlinear, you need to employ some nonlinear control methods such as feedback linearization, backstepping, sliding mode control.


How to derive $\frac{d}{dn}n! = \Gamma(1 + n)\psi^{(0)}(n+ 1)$? How can you derive $\frac{d}{dn}n! = \Gamma(1 + n)\psi^{(0)}(n + 1)$? I have tried checking Wolfram Alpha for a step-by-step solution, but none is given. Moreover, of what is the second function, $\psi^{(0)}$, representative?

$\Gamma(n)=(n-1)!$

$\Gamma(n+1)=n!$

${d\over{dn}}n!={d\over{dn}}\Gamma(n+1)$

now just look arround you for the derivative of the gamma function


When is $\phi(n)=n$ true? For what values of n is $\phi(n)=n$ true? Just looking at tables of values it seems that $\phi(n)=n$ is true only for $n=0,1$ but I cannot come up with how to  prove this.

I realize that the value of $\phi(0)$ is not really well-defined (What is the Euler Totient of Zero?) but for the purpose of this question I'll assume it is.

First, $\varphi(n)$  is defined only for $n\ge 1$. Second, if $n=\prod\limits_{i=1}^r p_i^{r_i}$  for primes $p_1,\dots,p_r$, we have:
$$\frac{\varphi(n)}n=\prod_{i=1}^r\Bigl(1-\frac1p_i\Bigr).$$
Thus, $\varphi(n)=n\iff\dfrac{\varphi(n)}n=1$ can be true if and only if $r=0$, i. e. $n=1$.

By definition, $\phi(n)<n$ for $n\ge 2$ since, $(n,n)=n$.


$d_1^2\cdot d_2^2=a^2\cdot c^2+b^2\cdot d^2$ iff $A+C=\frac{\pi}{2}$ or $B+D=\frac{\pi}{2}$. Let $ABCD$ a quadrilateral,  $a,b,c,d$ the lengths of his edges and $d_1,d_2$ the lengths of diagonals. Show that $d_1^2\cdot d_2^2=a^2\cdot c^2+b^2\cdot d^2$ iff $A+C=\frac{\pi}{2}$ or $B+D=\frac{\pi}{2}$.

I tried to prove it with scalar product of vectors but I am stuck.

My idea:
$d_1^2=\vec{AC}^2=(\vec{AB}+\vec{BC})^2=AB^2+2 \vec{AB}\cdot \vec{BC} +{BC}^2$.

$d_2^2=\vec{BD}^2=(\vec{BC}+\vec{CD})^2=BC^2+2 \vec{BC}\cdot \vec{CD} +{CD}^2$.

I have checked the sufficiency by algebra, but there is more synthetic treatment, e.g. see this blog.


Why is the numbering of computable functions significant? My course is about computability theory, and I'm having troubles with one of the main concepts. This might be a really newb question, but I've been struggling with understanding it's significance (and I was stupid enough to not ask my teacher while in class).

Can someone give me an example in terms of something practical to why numbering
computable functions is helpful?

I'm a computer science student, so maybe an example from that field might help me understand.

EDIT: Okay, so with the assumption then that the halting problem is the main reason we number computable functions.

In that case, numbering the functions should help us always prove if a function will halt or not. So, say we take the gödel numbered program $P_{2057}$, which stands for the program S(1), S(1), J(2,1,1). This represents the function x+2, over the domain of $\mathbb{N}$.

How does knowing the number 2057 help us decide if this program will halt or not?

EDIT2: I tried reading the papers that @sav linked to me, although I find them relatively difficult to understand, as I'm not that good with theoretical things yet.

Our course book is Computability, An introduction to recursive function theory by Nigel Cutland. I've found online many people praising this book for being clear and easy to understand, but for me that hasn't always been the case. The teachers explanations don't always make sense either, and sometimes it feels like the book is the teacher, not her(which is one of the big reasons I finally decided to come here for help).

Therefore, another question I have is, the book claims the numbering of functions to be of utmost importance in both the s-m-n theorem, and universal functions. After reading through those parts multiple times, I still don't understand their significance, and yet they are constantly referenced in later parts. Could someone maybe try and explain this connection in another way?

You have already been numbering the computable functions, you just didn't know it at first. The first time you saw a definition of the computable functions, you saw it in the context of some specific model of computation, such as register machines. Each machine can be viewed as a "number" for the function it computes; by standard coding methods we really can represent each machine by a natural number, justifying the terminology. (For example, as soon as you can type something into a text file, you can view the file as a sequence of 0s and 1s. Prepending a 1 gives a single number representing the data you typed).

So a number is nothing more or less than a program for computing a function. Rather than viewing the program as a sequence of complex symbols, we can view it as a sequence of 0s and 1s, as a number. Of course, to make use of the program, you have to know what model of computation it was written in.

There are many different models of computation: register machines, Turing machines, WHILE programs, $\lambda$ calculus, $\mu$-recursive functions, etc.  Each of these, when fully specified, gives a different numbering of the set of computable functions.

A key point in computability theory, which is not always obvious in a first course, is that the main focus is not on any of these specific models of computation - the focus is on the computable functions themselves.

So, rather than attaching ourselves to any specific model of computation, we just assume that we have a reasonable numbering of the computable functions, and work with that numbering abstractly. "Reasonable" here means that the numbering has properties stated by the  s-m-n theorem, the recursion theorem, and the universal function theorem.

So, when you ask Why is numbering the computable functions helpful?, I would respond that they are already numbered! Why focus on "numbers" abstractly? We could just as well call the numbers "programs", and call the numbering a "programming system". Nothing new would come from that terminology change.

It is true that, if we have a numbering of the computable functions, knowing that some function has number 2234 instead of 2332 doesn't really mean much. The somewhat surprising thing is that the same is true in all the standard numbering systems. The undecidability of the halting problem shows, for example, that just knowing a particular register machine to compute a function is not sufficient, in general, to let you determine whether the function halts on given inputs.

In computer science, they would call this a "static analysis" of the program. The undecidability of the halting problem shows that static analysis has significant theoretical limitations.  But this is true in every reasonable programming system, and we know that because the theorem about the halting problem is proved abstractly starting with an abstract numbering of the computable functions.  We can prove it once and for all, rather than proving it separately for every model of computation.

The numbering is just a means to an end, and is significant only in the context of the proof in which it is used.

Consider an analogous example. Suppose we have 3 pigeons and 2 pigeon-holes. If each hole can hold only 1 pigeon, prove that there will always be at least 1 pigeon not in a hole. One answer: number the pigeons 1,2,3 by the order in which they enter a hole (exclude simultaneous entry for simplicity). Then by the time pigeon 2 enters, no holes are left for pigeon 3.

Numbering the pigeons just helps with this proof, with no claim to significance of the numbering outside the proof. Numbering the computable functions is similar.


How find this value $\overline{a_{1}a_{2}a_{3}a_{4}a_{5}}=?$ if the $a,b,c,d,e$ is  $a_{1},a_{2},a_{3},a_{4},a_{5}$ a  permutation

and $a_{i}\in[0,9],a_{i}\in N$,such
$$\overline{abcde}=5\overline{a_{1}a_{2}a_{3}a_{4}a_{5}}$$

Find the $\overline{a_{1}a_{2}a_{3}a_{4}a_{5}}$

where $a_{1},a\neq 0$

my idea:
$$\overline{abcde}=a\times 10^4+b\times 10^3+c\times 10^2+d\times 10+e$$
$$5\overline{a_{1}a_{2}a_{3}a_{4}a_{5}}=5a_{1}\times 10^4+5a_{2}\times 10^3+5a_{3}\times 10^2+5a_{2}\times 10+5a_{5}$$
so we must $$a_{1}=1$$
and $e=0$ or $5$

Then  I can't

This problem is creat this :How find this $\overline{a_{1}a_{2}a_{3}a_{4}a_{5}}$

Thank you,maybe this have no solution too?

I wrote a program in Python to check all possibilities. Assuming $a=1$, It puts all the digits in $\overline{abcde}$ in a list and all the digits in $5  \overline{abcde}$ in a list and checks to see if all the digits match. It returned no numbers, therefore there are no solutions.

Edit: Here is my ugly code:

for b in range(10):
    for c in range(10):
        for d in range(10):
            for e in range(10):
                new_num = str(50000 + 5000*b + 500*c + 50*d + 5*e)
                a_1, a_2, a_3, a_4, a_5 = new_num[0], new_num[1], new_num[2], new_num[3], new_num[4]
                a_1, a_2, a_3, a_4, a_5 = int(a_1), int(a_2), int(a_3), int(a_4), int(a_5)
                if sorted((1, b, c, d, e)) == sorted((a_1, a_2, a_3, a_4, a_5)):
                    print(new_num)

print("done")

Pick any $a_1$, $a_2$ etc so they are all either $0$ or $1$.
Now let
$$ a=5 a_1, b=5 a_2, c=5 a_3, d=5 a_4, e=5 a_5$$

By repeatedly taking the difference between the left and right side modulo $5$ and factoring out $5$ you get the above answer.

Example:
$$
\overline{50555} = 5 ~\cdot~\overline{10111}$$


Which number remains alive? There are $100$ people standing in a circle numbered from $1$ to $100$. The first person is having a sword and kills the the person standing next to him clockwise i.e $1$ kills $2$ and so on. Which is the last number to remain alive? Also if $1$ kills both the person standing next to him. Which is the last number standing? Can both of them be generalized?

The first case is similar to Josephus Problem and in general situation, we can use the following MATLAB code to get the remaining number:

First Case:

function RemainNum = JosephusProblem(n,m)
A = 1:n;
A = A';
for k = 1:n-1
  A = circshift(A,length(A)-mod(m+1,length(A)) + 1);
  A = A(1:(end-1));
RemainNum = A;

where $n$ is the total number of person in this circle and from the person #1, people count number one by one from 1 to $m$ circularly and the person who tells the number $m$ gets killed and this process doesn't end until there is only one person left, then the function returns this lucky guy by $\text{RemainNum}$. So in this case, $m=2$. People count like $1,2,1,2,...$ and persons who count 2 get killed.

Second Case:

Let $f(n)$ be the lucky number in this case, then I guess that
$$f(n) =
\begin{cases}
1,    &\text{if $n=1$}\\
n-1,  & \text{if $n$ is even} \\
n-2, & \text{if $n$ is odd}  \\
\end{cases}$$
Since every time at most 2 persons are killed and 1 person is killed only when there are only 2 person left, so when $n$ is even, finally there will be only 2 persons left after $\frac{n-2}{2}$ times killing and person $n-1$ gets the sword, so $f(n) = n-1$ in this case. When $n$ is odd, after $\frac{n-3}{2}$ times killing, there will be 3 person left, and person $n-2$ gets the sword and then kills the other two, so $f(n)= n-2$ in this case.

1 kills 2 ... 3 kills 5... in the process 1 is alive till 99 kills 100 and passes it back to 1. 1 kills 99 and 1 is ALIVE


Does the metric in the Theory of Relativity actually satisfy the definition of a metric? Allow me to give a brief introduction to the topic, which has to do with physics; my question will still be a mathematical one. I think my question is aimed at people with a background both in physics and in mathematics.

I am familiar with the Theory of Relativity, in which spacetime is described as a four-dimensional manifold with a notion of distance (invariant under the Poincare group). This distance is described by an object that is called the metric or the metric tensor. A simple example of such a metric is the Minkowski metric. This metric (tensor) is (at least as evaluated in some coordinate frame and up to certain conventions) described by the 4x4 matrix $\eta = diag(-1,1,1,1)$. As a result, the spacetime distance between two points $x,y$, described by their components $x^\mu, y^\mu$, $(\mu=0,1,2,3)$, is given by
\begin{equation}
d(x,y)=\eta_{\mu\nu} (x^\mu - y^\mu)(x^\nu - y^\nu)~,
\end{equation}
where summation over repeated indices is implied. Now comes my question. When we take $x$ and $y$ to be given, for instance, by $x = (2,0,0,0)$ and $y=(1,0,0,0)$, then we arrive at a negative distance:
\begin{equation}
d(x,y) = -1~.
\end{equation}
Now, regarding the Theory of Relativity, this is quite possible, but recently I came across the formal definition of a metric. And one of the conditions stated that a metric maps each pair of points in the space to a non-negative real number. But in our example of the Minkowski metric, this is clearly not the case. So the Minkowski metric does not seem to satisfy the definition of a metric.

So, is the metric in the Theory of Relativity just a different kind of metric, or does it have to do with a distinction between metrics and metric tensors? Or am I missing something here?

Metric in the sense of metric spaces and metrics in the sense of (pseudo)Riemannian metrics are very distinct concepts. It is one of the cases where the limits of language causes two or more distinct concepts to share one name. For other instances of this in mathematics consider the word "normal" or the word "distribution".

It is not a metric because, as you say, distance must be positive. So they use a different word for negative distance, called pseudometric distance. That is, the interval is not called a metric, it's called a pseudometric. That distinction is the most important fact in special relativity.  In my opinion, pseudometric (negative) distance is the most important concept in understanding what space, time, and the universe really are.


Defining Positive integers.. While reading Calculus by Apostol I  found the set of positive integers defined as "Set of Real numbers that belong to every Inductive set"...

The question is "Why we don't define the set of 1,1+1,1+1+1,...
I mean all such numbers as the set of positive integers?"

He has said that this will not define the set completely and so we use  "Inductive sets"

but can someone please explain it a bit more so it becomes actually clear to use inductive sets to define them..

The problem is, what does "all such numbers" actually mean?  You can write down any single number like $1+1$ or $1+1+1+1+1$ easily, but how can you say exactly what the set of all of them is?  You need to define what it means for a number to be "a sum of some number of copies of $1$", but how can you do that when you don't know what "number" (which in the context of this phrase would mean a positive integer number) means?  In order to rigorously prove things about the natural numbers, you will need a completely precise definition of what they are.  And it is quite difficult to say precisely what you mean by "all such numbers" in a non-circular way.  So you need to find a more precise way of defining the natural numbers, and that is the purpose of the definition using inductive sets.

For discrete mathematics the natural numbers (which is practically the same as positive integers without zero) is typically defined using 0 and the successor function S (the successor function being the same +1) $ x \in \mathbb{N} \iff x = 0 \lor \exists y \in \mathbb{N} : S(y)=x $.

Which is effectively the same definition you used so the claim that there exist positive integers that are not covered by that definition runs counter to the standard use of the term "Positive Integer".


Unique Topological Sort for DAG I have a DAG (directed acyclic graph) which has more than one valid topological sorting. I'm looking for a way to sort it topologically and always get the same, well defined result.

For example take this graph:

A-->B
A-->C
B-->D
C-->D

There are two solutions to a topological sort:

1: A, B, C, D and
2: A, C, B, D

We notice that B and C can be sorted in any order. Therefore we choose alphabetic sorting as secondary sorting to get only one solution: A, B, C, D.

Here's an other example:

E-->G
E-->H
H-->F

There are three solutions to a topological sort:

1: E, G, H, F
1: E, H, G, F
3: E, H, F, G

But here, there's no obvious solution. No solution seems to be more "alphabetic" than the others.

Is there a way to get a unique, deterministic solution for any DAG?

If you are programming the sort algorithm, unless you use a random choice of the child of a parent node, your algorithm will always return the same answer. In your example, make a program that, starting from E, will prefer G to H and so forth. It will always answer E, G, H, F.
EDIT : here is the algo.

While there is a vertex in the graph do
    Display the vertex with 0 incoming edge (if many choose the one with lower lexical order)
    Remove it and its out-going links from the graph
end

The order is what the algo displays.
It will start with E. It is displayed and removed. Then G and H are candidates. The one with the lower lexical order is G. It is displayed and removed. The next candidate is H. It is displayed and removed. Then F is displayed and removed.
The algo make a breadth-first search. Its display is E, G, H, F.

No. The Wikipedia article on topological sort does say that it's possible, in linear time, to determine whether a unique sort exists.


When can a sum and integral be interchanged? Let's say I have $\int_{0}^{\infty}\sum_{n = 0}^{\infty} f_{n}(x)\, dx$ with $f_{n}(x)$ being continuous functions. When can we interchange the integral and summation? Is $f_{n}(x) \geq 0$ for all $x$ and for all $n$ sufficient? How about when $\sum f_{n}(x)$ converges absolutely? If so why?

I like to remember this as a special case of the Fubini/Tonelli theorems, where the measures are counting measure on $\mathbb{N}$ and Lebesgue measure on $\mathbb{R}$ (or $[0,\infty)$ as you've written it here).  In particular, Tonelli's theorem says if $f_n(x) \ge 0$ for all $n,x$, then $$\sum \int f_n(x) \,dx = \int \sum f_n(x) \,dx$$ without any further conditions needed.  (You can also prove this with the monotone convergence theorem.)
Then Fubini's theorem says that for general $f_n$, if $\int \sum |f_n| < \infty$ or $\sum \int |f_n| < \infty$ (by Tonelli the two conditions are equivalent), then $\int \sum f_n = \sum \int f_n$.  (You can also prove this with the dominated convergence theorem.)
There may be weaker conditions that would also suffice, but these tend to work in 99% of cases.

Elaborating on request: the usual statement of Fubini's theorem goes something like this:

Let $(X,\mathcal{F}, \mu),(Y,\mathcal{G}, \nu)$ be $\sigma$-finite measure spaces, and let $g : X \times Y \to \mathbb{R}$ be measurable with respect to the product $\sigma$-algebra $\mathcal{F} \otimes \mathcal{G}$.  Suppose that $\int_X \int_Y |g(x,y)| \nu(dy) \mu(dx)$ is finite.  (Note: By Tonelli's theorem, this happens if and only if $\int_Y \int_X |g(x,y)|\mu(dx)\nu(dy)$ is finite, since both iterated integrals are equal.)   Then $$\int_X \int_Y g(x,y) \nu(dy)\mu(dx) = \int_Y \int_X g(x,y) \mu(dx) \nu(dy).$$

Let $X = \mathbb{R}$, $\mathcal{F}$ the Borel $\sigma$-algebra, and $\mu$ Lebesgue measure.  Let $Y = \mathbb{N}$, $\mathcal{G} = 2^{\mathbb{N}}$ the discrete $\sigma$-algebra, and $\nu$ counting measure.  Define $g(x,n) = f_n(x)$.  Exercise: since each $f_n$ is measurable, verify that $g$ is measurable with respect to $\mathcal{F} \otimes \mathcal{G}$.  Exercise: verify that integration with respect to counting measure is the same as summation, where the integral exists and is finite iff the sum converges absolutely.  (That is, given a sequence of real numbers $a_n$, define a function $b : \mathbb{N} \to \mathbb{R}$ by $b(n) = a_n$.  Then $\int_{\mathbb{N}} b\,d\nu = \sum_{n=1}^\infty a_n$.)
As such, the conclusion of Fubini's theorem reduces to the statement that was to be proved.

While most of the time I would use the Fubini/Tonelli conditions, the dominated convergence theorem is actually strictly stronger in this mixed sum/integral case, because it can take into account the order structure of the integers. An example (that I first worked up back in [2009])(http://artofproblemsolving.com/community/c7h294262p1593291):

Consider the calculation
\begin{align*}\ln 2 &= \int_0^1 \frac1{1+x}\,dx = \int_0^1\sum_{n=0}^{\infty} (-1)^n x^n\,dx\\
?&= \sum_{n=0}^{\infty}\int_0^1(-1)^n x^n\,dx = 1-\frac12+\frac13-\frac14+\cdots\end{align*}
Fubini's theorem isn't strong enough to justify the interchange. If we put absolute values on the terms, it blows up to $\int_0^1 \frac1{1-x}\,dx = 1+\frac12+\frac13+\frac14+\cdots=\infty$.

On the other hand, the dominated convergence theorem cares about the partial sums $\sum_{n=0}^{N}(-1)^n x^n$. By the alternating series estimate,
$$0\le \sum_{n=0}^{N}(-1)^n x^n\le 1$$
for all $x\in [0,1]$. $1$ is integrable on this interval, and the interchange
$$\int_0^1\left(\lim_{N\to\infty}\sum_{n=0}^{N}(-1)^n x^n\right)\,dx = \lim_{N\to\infty}\int_0^1 \sum_{n=0}^{N}(-1)^n x^n\,dx$$
is justified, proving the result $1-\frac12+\frac13-\frac14+\cdots=\ln 2$.

This situation with the dominated convergence theorem being stronger than Fubini's theorem can come up when we've got a reasonable bound on partial sums but not absolute convergence as a whole.
The monotone convergence theorem, on the other hand, is exactly the same as Tonelli's theorem - when everything's positive, either both sides are the same and finite or both sides are infinite.


Making a homeomorphism a $\mathscr{C}^k$-map I'm solving the following exercise and I just need a little push for the one step I'm failing to do:

  Let $M$ be a $\mathscr{C}^k$-manifold, $N$ be a topological manifold, and $\alpha: M\to N$ be a homeomorphism. Then there is a unique $\mathscr{C}^k$-structure on $N$ which makes $\alpha$ a $\mathscr{C}^k$-map.

So far, what I have done: if $\mathfrak{A}_M$ is a differential structure on $M$, we let $$\mathfrak{A}=\{(\alpha[U],\varphi\circ \alpha^{-1})\mid  (U,\varphi)\in \mathfrak{A}_M\}. $$Then $\mathfrak{A}$ is a $\mathscr{C}^k$-atlas for $N$, inducing a differential structure which makes $\alpha$ a $\mathscr{C}^k$-map.

Ok, now assume that we have another differential structure $\mathfrak{A}'$ which makes $\alpha$ a $\mathscr{C}^k$- map. It is enough to check that $\mathfrak{A}'$ is  $\mathscr{C}^k$-compatible with $\mathfrak{A}$. Given $(V,\psi)\in \mathfrak{A}'$ and $(\alpha[U],\varphi\circ \alpha^{-1})\in \mathfrak{A}$, we'd have to see both that $$\psi\circ (\varphi\circ \alpha^{-1})^{-1}:\varphi[\alpha^{-1}[V]\cap U]\to \psi[V\cap \alpha[U]] $$ and $$(\varphi\circ \alpha^{-1})\circ \psi^{-1}:\psi [V\cap\alpha [U]]\to \varphi [\alpha^{-1}[V]\cap U] $$are  $\mathscr{C}^k$ (as maps between open sets of Euclidean spaces). The first one is just the local representation of $\alpha$, which is $\mathscr{C}^k$ according to $\mathfrak{A}'$, hence is $\mathscr{C}^k$. But I don't know how to argue for the second one. Help?

Ok, we figured it out sometime ago but only now I could manage to come back here and write an answer. It goes like this: the result is not true as stated, we must have $\mathscr{C}^k$-diffeomorphism instead of $\mathscr{C}^k$-map. This is because the atlas $\mathfrak{A}$ defined in the original post actually makes $\alpha$ a $\mathscr{C}^k$-diffeomorphism (smoothness of the inverse is also trivial, the problem is that I missed this). This being said, if we assume that $\mathfrak{A}'$ also makes $\alpha$ a $\mathscr{C}^k$-diffeomorphism, then the smoothness of the second transition map follows from the exact same argument used in the smoothness of the first transition map (in other words, merely assuming that $\mathfrak{A}'$ makes $\alpha$ a $\mathscr{C}^k$-map is not strong enough to prove that $\mathfrak{A}$ and $\mathfrak{A}'$ are $\mathscr{C}^k$-compatible).

Suppose that we have, in any category, invertible functions
$$
A \overset{f}{\longrightarrow} B \overset{g}{\longrightarrow} C.
$$
Then we have the formula $(g \circ f)^{-1} = f^{-1} \circ g^{-1}$.

In your situation, this shows that the first map is the inverse of the second. Hence, you are able to apply the following standard theorem from calculus:

Diffeomorphism from Inverse function theorem


Is $f(x,y)=\frac{x|y|}{\sqrt{x^2+y^2}}$ continuous and differentiable? Let $$f(x,y)=\begin{cases}\frac{x|y|}{\sqrt{x^2+y^2}} &\textrm{ if } (x,y)\neq(0,0), \\ 0 &\textrm{ if } (x,y)= (0,0).\end{cases} $$
I want to know: is $f$ is continuous? Are the partial derivatives exists at the origin? Is $f$ differentiable?
First, I tried some different paths to prove that $f$ is discontinuous, but none path lead me to it.
I found the partial derivatives:
$$\frac{\partial f}{\partial x}(x,y)=\frac{(y^2-x^2)|y|}{(x^2+y^2)^{3/2}},\quad \frac{\partial f}{\partial y}(x,y)=\frac{x|y|(x^2-y^2)}{y(x^2+y^2)^{3/2}}. $$
By doing $(x,y)=(0,t)$, the limit of the first partial derivative does not exist:
$$\lim_{t\rightarrow 0}\frac{t^2|t|}{t^3}=\lim_{t\rightarrow 0}\frac{|t|}{t} $$
Is this sufficient to  conclude that $f$ is not differentiable? What can I do?

Continuity: $(x-|y|)^2=x^2+y^2-2x|y|\geq0 \iff \frac{x^2+y^2}{2}\geq x|y|$

Partial Derivatives: $\frac{\partial f}{\partial x}(0,0)=\lim_{h\to0} \frac{f((0,0)+h(1,0))-f(0,0)}{h}$ and it is analogous for $\frac{\partial f}{\partial y}(0,0)$.

Derivability: Consider the linear application, $L$ , such that for any $(x,y)\in\mathbb{R^2}:L(x,y)=0$ then
$$\lim_{(x,y)\to(0,0)} \frac{f(x,y)-f(0,0)-L((x,y)-(0,0))}{||(x,y)-(0,0)||}=\lim_{(x,y)\to(0,0)} \frac{x|y|}{x^2+y^2}$$

Can you take it from here?

Firstly $f$ is continuous, indeed by polar coordinates we have
$$\frac{x|y|}{\sqrt{x^2+y^2}}=r\cos \theta |\sin \theta| \to 0$$
For differentiability by the definition we have
$$\frac{\partial f}{\partial x}(0,0)=\frac{\partial f}{\partial y}(0,0)=0$$
and
$$\lim_{(h,k)\to(0,0)} \frac{\frac{h|k|}{\sqrt{h^2+k^2}}}{\sqrt{h^2+k^2}}=\lim_{(h,k)\to(0,0)} \frac{h|k|}{h^2+k^2} \neq 0$$
and therefore $f$ is not differentiable.
As noticed, we cannot conclude for differentiability from the discontinuity of partial derivatives.


Probability that either the word BAD or CAD can be formed. From the six letters A, B, C, D, E and F, three letters are chosen at random with replacement.What is the probability that either the word BAD or the word CAD can be formed from the chosen letters?

I think this is a easy problem but as I am weak in probability I am not sure whether I have done it correctly or not.

What I have done is probability that letter B is chosen is ${1\over6}$ similarly probability for A and D will also be ${1\over6}$ (due to replacement) and multiply them which give me ${1\over216}$, now multiply it with 2 (for CAD) and my final answer will be ${2\over216}$.

Since there are $6^3$ ways to choose the 3 letters,

and there are $3!$ ways to obtain B,A,D and similarly for C,A,D,

the probability is $\displaystyle\frac{2\cdot3!}{6^3}=\frac{1}{18}$.

You state that "three letters are chosen at random with replacement", as you also ask "What is the probability that ... can be formed from the chosen letters?" what we want to look at is unordered sampling with replacement.

Take the set $\Omega=\left\{A,B,C,D,E,F\right\}$, then we need to see how many multisets of size 3 can be formed from $\Omega$. It is a known fact that the number of multisets of length $k$ from a set of size $n$ is given by $\binom{n+k-1}{k}$.

From this, we know that there are 56 different possible multisets of length 3 with elements taken from $\Omega$. Now, As each of these multisets has no particular ordering, there is exactly one that corresponds to $BAD$ and exactly one which corresponds to $CAD$, thus, the probability of selecting the words $BAD$ or $CAD$ (i.e. the multisets $\left\{\left\{A,B,D\right\}\right\}$ or $\left\{\left\{A,C,D\right\}\right\}$) is $\frac{2}{56}$.


Meaning of Dimension Is a (non-straight) curve in the xy-plane considered to be a 1-dimensional or 2-dimensional entity?

Depending on the answer, what is the term used to describe its other attribute (either its oneness, consisting in its similarity to a line, or its twoness, consisting in its need to be defined by at least two axes)?

Similarly, which of these categories does a line in the xy-plane not parallel to the x-axis or y-axis fall into?

The two notions you describe are both useful enough that folks have invented words to describe them. For a curve in the plane (like a circle, or a slanted line, or a horizontal line), we speak of the "intrinsic dimension" as 1, but the "ambient dimension" as two (because the object is sitting in a 2-dimensional plane). (We say that the dimension is 1 because in a small part of the shape, 1 number is sufficient to tell is where we are. On a circle for instance, points in a little part of the circle near "3 o'clock" can be described as being so many degrees clockwise from 3 o'clock or counterclockwise from 3 o'clock. This works well for the region from 2 to 4 o'clock, bad badly if we use the whole circle, because then the 9 o'clock point has two different descriptions: both 180 degrees CW and 180 degrees CCW).

If we take that same circle and think of it as living in 3-dimensional space, then the ambient dimension becomes 3, but the intrinsic dimension is still 1.

There's a third notion that sometimes arises, which is "how big must the ambient dimension be?" For a circle, we cannot really put it nicely into a line -- if we try to do so, we always find that some point on the line corresponds to 2 or more points of the circle (indeed, this usually happens for many points of the line). But in 2-dimensions, there's "plenty of room".

In general, an $n$-dimensional (smooth) object will fit nicely in $2n$ dimensions, and with a mild restriction called "orientability", in $2n-1$ dimensions. Thus all orientable surfaces (2-dimensional smooth things) fit nicely in three dimensions. Some non-orientable surfaces need four dimensions to "fit" without self-intersections, though. For some folks, this "smallest dimension in which the thing will fit" gets called its "dimension" as well, so they say that a circle is two-dimensional.That's entirely reasonable, but it's not the common language used by those who study topology and geometry.

The discussion I've given here assumes we're talking about "smooth" things, without self-intersections. A figure-8, for instance, doesn't quite fit this description, and a disc with a line drawn sticking out from one side, like a lollipop, also does not. Defining dimension for things like that is substantially trickier.

I've also taken a topologist's view of dimension here; there are also approaches based more on analysis, which are the starting point for things like fractal dimensions, but they're more complicated (to me), and I know less about them, so I'll stop here.

Spatial dimensions are just axis perpendicular to each other. When in one spatial dimension, you can go from side to side but not up or down. To make a curve, you need to go up and down and side to side. Thus it requires two axis so it is a 2d object


Finding value of determinant, Where $A+B+C+P+Q+R=0$ Finding value of Determinant $$\begin{vmatrix}
\tan (A+P) & \tan(B+P)  & \tan(C+P)\\\\
 \tan (A+Q)& \tan (B+Q)  & \tan (C+Q)\\\\
 \tan (A+R)&\tan (B+R)  & \tan(C+R)
\end{vmatrix}$$ for all values of $A,B,C,P,Q,R$ Where $A+B+C+P+Q+R=0$

I did not understand how to start it, Could some help me, Thanks

We have that if $X+Y+Z = 0$, then $\tan X+ \tan Y+\tan Z = \tan X \tan Y \tan Z$.

Hence for example $$\tan (A+P) \tan (B+Q) \tan (C+R) = \tan (A+P) +\tan (B+Q) +\tan (C+R)$$

Hence when you expand from R1, the determinant expands as

$$\begin{align} & \left(\tan (B+Q) +\tan (C+R)-\tan (C+Q) - \tan (C+R)\right)\\
+ & \left(\tan (C+Q)+\tan (A+R) - \tan (A+Q)-\tan (C+R)\right)\\
+ & \left(\tan (A+Q)+\tan (B+R) - \tan (A+R) - \tan (B+Q)\right)\end{align} = 0$$

We want to find the determinant of this Matrix.
$$
\begin{pmatrix}
Tan(A+P) & Tan(B+P) & Tan(C+P)\\
Tan(A+Q) & Tan(B+Q) & Tan(C+Q)\\
Tan(A+R) & Tan(B+R) & Tan(C+R)
\end{pmatrix}
$$
The determinant of this matrix gives us \to
$$
-Tan(A+R) \cdot Tan(B+Q) \cdot Tan(C+P)\\
+Tan(A+Q) \cdot Tan(B+R) \cdot Tan(C+P)\\
+Tan(A+R) \cdot Tan(B+P) \cdot Tan(C+Q)\\
-Tan(A+P) \cdot Tan(B+R) \cdot Tan(C+Q)\\
-Tan(A+Q) \cdot Tan(B+P) \cdot Tan(C+R)\\
+Tan(A+P) \cdot Tan(B+Q) \cdot Tan(C+R)
$$
But I still don't know how to depress it after this, even though you said
$
A+B+C+P+Q+R = 0
$


Variance of sample variance? What is the variance of the sample variance? In other words I am looking for $\mathrm{Var}(S^2)$.

I have started by expanding out $\mathrm{Var}(S^2)$ into $E(S^4) - [E(S^2)]^2$

I know that $[E(S^2)]^2$ is $\sigma$ to the power of 4. And that is as far as I got.

Here's a general derivation that does not assume normality.

Let's rewrite  the sample variance $S^2$  as an average over all pairs of indices:
$$S^2={1\over{n\choose 2}}\sum_{\{i,j\}} {1\over2}(X_i-X_j)^2.$$
Since  $\mathbb{E}[(X_i-X_j)^2/2]=\sigma^2$, we see that $S^2$ is an unbiased estimator for $\sigma^2$.

The variance of $S^2$ is the expected value of
$$\left({1\over{n\choose 2}}\sum_{\{i,j\}} \left[{1\over2}(X_i-X_j)^2-\sigma^2\right]\right)^2.$$

When you expand the outer square, there are 3 types of cross product terms
 $$\left[{1\over2}(X_i-X_j)^2-\sigma^2\right] \left[{1\over2}(X_k-X_\ell)^2-\sigma^2\right]$$
depending on the size of the intersection $\{i,j\}\cap\{k,\ell\}$.

When this intersection is empty, the factors are independent and the expected cross product is zero.
There are $n(n-1)(n-2)$ terms where  $|\{i,j\}\cap\{k,\ell\}|=1$ and each has an expected cross product of $(\mu_4-\sigma^4)/4$.
There are ${n\choose 2}$ terms where  $|\{i,j\}\cap\{k,\ell\}|=2$ and each has an expected cross product of $(\mu_4+\sigma^4)/2$.

Putting it all together shows that $$\mbox{Var}(S^2)={\mu_4\over n}-{\sigma^4\,(n-3)\over n\,(n-1)}.$$ Here $\mu_4=\mathbb{E}[(X-\mu)^4]$ is the fourth central moment of $X$.

I will use this as an example of this theorem(from Seber, G.A. and Lee, A.J. (2012))
Let $X_1, X_2, ... , X_n$ be independent rvs with means $(\theta_1, \theta_2, ... ,\theta_n)$,common $\mu_2,\mu_3,\mu_4$. If A is any n x n symmetric matrix and $a$ is a column vector of the diagonal elements of A, then
$$var[X'AX]=(\mu_4-3\mu^2_2)a'a+2\mu^2_2tr(A^2)+4\mu_2\theta'A^2\theta+4\mu_3\theta'Aa
$$
denote $1_n$ as n-dim column vector that all elements are 1, notice that for sample variance
$$S^2=\frac{1}{n-1}X'AX, where A=I_n-\frac{1}{n}1_n1_n'
$$
and we have$A^2=A$, $a=(1-\frac{1}{n})1_n$
since $X_i$ in our case are iid, let's say their mean is $\mu$, then $\theta=\mu1_n$
so the third and fourth term is $0$,since
$$
A^2\theta=A\theta=\mu(1_n-\frac{1}{n}1_n(1_n'1_n))=0\\
Aa=(1-\frac{1}{n})(1_n-\frac{1}{n}1_n(1_n'1_n))=0
$$
then$$
var[S^2]=\frac{1}{(n-1)^2}[(\mu_4-3\mu_2^2)(1-\frac{1}{n})^2n+2\mu_2^2(n-1)]=\frac{\mu_4}{n}-\frac{n-3}{n(n-1)}\mu_2^2
$$


Conditional expectation given a sigma algebra Let $Z$ be a random variable defined on $(\Omega,\mathcal{F},p)$, $E(Z)=1$ and $Z\geq0$ $a.s$.

Let's take the probability measure $q$ induced by $Z$ as $q(A)=E(I_{A}Z)$ for any $A \in \mathcal{F}$ now define $U=E(Z|\mathcal{G})$ where $\mathcal{G}$ is a sub $\sigma$-algebra of $\mathcal{F}$

Prove that $E_q(X|\mathcal{G})=\frac{E(XZ|\mathcal{G})}{U}$ for any bounded $X$.

$\mathbf{Solution}$

By definition $E_q(X|\mathcal{G})$ is such that $E_q(E_q(X|\mathcal{G})S)=E_{q}(XS)$ for any $S$ bounded and $\mathcal{G}$ measurable.
This is the same as
$E(E_q(X|\mathcal{G})SZ)=E(XSZ)$.

Now by taking $XZ$ as a random variable one has $E(XSZ)=E(E(XZ|\mathcal{G})S)$

$E(E_q(X|\mathcal{G})SZ)=E(E(XZ|\mathcal{G})S)$

But now I am missing the part of $U$, anyone knows what to do from here on?

Let us first show that $Y := E_q(X|\mathcal G)$ is a.s. $p$-bounded. Let $|X|\le C$. Acually, $Y$ is defined via $\int YZS\,dp=\int XZS\,dp$, so $Y$ can be anything where $Z=0$. Let us put $Y = C/2$ on $\{Z=0\}$. Then
$$
C\int_{Y\ge 2C}Z\,dp\ge\int_{Y\ge 2C}XZ\,dp = \int_{Y\ge 2C}YZ\,dp\ge 2C\int_{Y\ge 2C}Z\,dp.
$$
Hence, $\int_{Y\ge 2C}Z\,dp= 0$, which implies $Z=0$ on $\{Y\ge 2C\}$. By our definition of $Y$ on $\{Z=0\}$, this is impossible, so that $p(Y\ge 2C)=0$ follows. Similarly, $p(Y\le -2C) = 0$.

Now, for all bounded $S$ we have that $E_q(YS) = E_q(XS)$, that is, $E((YZ)S) = E((XZ)S)$. The  latter means that $E(XZ|\mathcal G) = ZY$. Hence, since $Y$ is bounded,
$$
E(E(XZ|\mathcal G)S) = E(Z(YS)) = E(E(Z|\mathcal G)YS).
$$
This implies
$$
E(XZ|\mathcal G) = E(E(XZ|\mathcal G)|\mathcal G) = E(Z|\mathcal G)Y,
$$
which we had to prove.


If $f(\mathbb{R})$ is a subset of $\mathbb{Q}$, is it continuous or differentiable I'm doing a practice paper before my exam and I came across the following question, but I don't have the memo. I know if a function is differentiable then it it must continuous, so that rules out choice C. Other than that, I don't know how to answer this. I'm assuming it's continuous the answer is D but I'm really uncertain

Let $f:\mathbb{R}\to\mathbb{R}$ such that $f(\mathbb{R})\subset\mathbb{Q}$. Then:

A. $f$ is not continuous.

B. $f$ is continuous but not differentiable.

C. $f$ is differentiable but not continuous.

D. $f$ is differentiable and monotonic.

E. $f$ is continuous if and only if $f$ is constant.

A. $f$ is not continuous since for conrinuous functions $f(\Bbb R)$ is an interval, but $\Bbb Q$ is not the interval.

D. Yes, if $f$ is a constant function. For nonconstant ones this is false.

E. True.


Is $\cos(x^2)$ the same as $\cos^2(x)$? I want to know something about trigonometrical functions, is $\cos(x^2)$ the same as $\cos^2(x)$ ?

One of the first things you may observe is that $(\cos {\small{(}}x{\small{)}})^2\geqslant0$ whereas $\cos(x^2)$ may be equal to a negative number. (Why?)

In blue, a graph of the function $\color{blue}{\cos^2(x)}$ and in red a graph of the function $\color{red}{\cos(x^2)}$.

Some say, a good plot is worth a million words! :-)

No. $\cos x^2=\cos(x^2)=\cos(x\times x)$ while $\cos^2(x)=\cos(x)\times \cos(x)=(\cos(x))^2$.


needs help with checking an integral I've been asked to integrate

$$\int\frac{\sqrt{1+\ln(x)}}{x\ln(x)}\,dx$$

and I'm well aware that actually there are some ways to solve this problem, so I challenge myself with a slightly longer solution.
I rewrite above integrand as

$$\int\frac{\sqrt{1+\left(\sqrt{\ln(x)}\right)^2}}{x\ln(x)}\,dx$$

$\sqrt{\ln(x)} = \tan(a)$

$\dfrac{1}{2x\sqrt{\ln(x)}}\, dx = \sec^2(a)\, da$.

and so, above expression turn into:

$$2\int\frac{\sec^2(a)\sqrt{1+\tan^2(a)}}{\tan(a)}\, da$$

$$2\int\frac{\sec^3(a)}{\tan(a)}\, da$$

$$2\int\sec^2(a)\csc(a)\, da$$

Here I using integral by parts

$$\int f'g = fg-\int fg'$$

I took,

$$\sec^2(a)= g' ，\tan(a) = g ，\csc(a) = f，-\csc(a)\cot(a)=f'$$

and so above integral resulting:

$$ 2\left[\csc(a)\tan(a)+ \ln\vert \sin(a)+\tan(a)\vert\right]+C$$

and here the consequences of those variable

opposite       : $\sqrt{\ln(x)}$

adjacent       : $1$

hypotenuse  : $\sqrt{\ln(x)+1}$

$$ 2\left[\sqrt{\ln(x)+1}+\ln\left\vert \frac{\sqrt{\ln(x)}}{\sqrt{\ln(x)+1}}
+\sqrt{\ln(x)}\right\vert\right]+C$$

Personally, I don't think I made mistakes but when I check on the calculator, calculator ruled that this answer is wrong, I've been tracking i back over and over but i can't find where I did go wrong,
so please help me to identify my mistakes since if this right the difference should be no more than a constant.

Almost all of your work is correct, apart from the integration by parts step. For $\displaystyle\int \sec^2(a)\csc(a) \, \mathrm da$, let $u = \csc(a)$ and $\mathrm dv = \sec^2(a) \, \mathrm da$ (as you did). Hence, $\mathrm du = -\csc(a)\cot(a) \, \mathrm da$ and $v = \tan(a)$. Using $\displaystyle \int u \, \mathrm dv = uv-\displaystyle\int v \, \mathrm du$, you get:

$$\int \sec^2(a)\csc(a) \, \mathrm da = \csc(a)\cot(a)-\int -\tan(a)\csc(a)\cot(a) \, \mathrm da$$

Clearly, $\tan(a)\cot(a) = 1$ and you can get rid of the double negatives, so:

$$\int \sec^2(a)\csc(a) \, \mathrm da = \csc(a)\cot(a)+\int \csc(a) \, \mathrm da$$

It seems like your only problem was integrating $\csc(a)$, which gives $-\ln\vert \csc(a)+\cot(a)\vert+C$ and not $+\ln\vert \sin(a)+\tan(a)\vert+C$. The rest of your answer, however, is correct, so what you'll get is:

$$\int\frac{\sqrt{1+\ln(x)}}{x\ln(x)}\, \mathrm dx = 2\left[\sqrt{\ln(x)+1}-\ln\left\vert \frac{\sqrt{\ln(x)+1}}{\sqrt{\ln(x)}}
+\frac{1}{\sqrt{\ln(x)}}\right\vert\right]+C$$

Extra: I'm suspecting that was just an accident. But here's an explanation in case it wasn't. In order to see how that works, recall that $\dfrac{\mathrm d}{\mathrm da} [\csc(a)] = -\csc(a)\cot(a)$ and $\dfrac{\mathrm d}{\mathrm da}[\cot(a)] = -\csc^2(a)$, so adding them together gives $\dfrac{\mathrm d}{\mathrm da} [\csc(a)+\cot(a)] = -\csc(a)[\csc(a)+\cot(a)]$ (just factoring). Isolating for $\csc(a)$ gives:

$$\csc(a) = -\dfrac{\dfrac{\mathrm d}{\mathrm da}[\csc(a)+\cot(a)]}{\csc(a)+\cot(a)}$$

The RHS is just $-\dfrac{f'(a)}{f(a)}$, which just gives $-\ln\vert f(a)\vert+C$ when integrated by substitution, so:

$$\displaystyle\int \csc(a) \, \mathrm da = -\ln \vert \csc(a)+\cot(a)\vert +C$$

Please find the answer, I solved it for you. Let me know if you have questions.


A multiplication algorithm found in a book by Paul Erdős: how does it work? I am trying to understand the following problem from Erdős and Surányi's Topics in the theory of numbers (Springer), chapter 1 ("Divisibility, the Fundamental Theorem of Number Theory"):

We can multiply two (positive integer) numbers together in the following way. Write the two numbers down next to each other. Divide the first in half, rounding down to an integer, and write the result below it. Double the second number, writing the result below it. We continue this halving / doubling until we are left with $1$ in the first column. Cross out all those numbers in the second column that are opposite an even number and add the remaining numbers in this column together to get the product. Prove that this works.

And this is an example, $73 \cdot 217$:

$(73,217)$
$(36, 434)$
$(18, 868)$
$(9, 1736)$
$(4, 3472)$
$(2, 6944)$
$(1, 13888)$

Then $73 \cdot 217 = 217+1736+13888 = 15841$, which is correct.
... and I really cannot visualize the reason why it works. My thoughts so far:

We are dividing by $2$ in the left column, so only those values that are odd are coming from a division of a previous even number in the left column, and that means that the previous division by $2$ was "perfect", meaning without decimals.

I can approximate the value of the product of two natural numbers $p \cdot q$ if I divide the first number by $2$ continuously until it arrives at $1$ and multiply the second by $2$ at the same time (so the final value of the second one is an approximation of the product).

But why do we remove some of them for the final sum? I would like to ask the following questions:

How does it work?

We are summing the numbers of the second column that are opposite an odd number. Then what does the sum of the numbers that we do not use from the second column represent?

This is all probably pretty obvious, but I cannot see the light.

This method is often called "Russian peasant multiplication".

It's often justified by thinking about writing the first number in binary. Here's another way to explain it. At each step, we're replacing a pair $(p,q)$ either by $(\frac{p}{2}, 2q)$ (when $p$ is even) or by $(\frac{p-1}{2},2q)$ (when $p$ is odd).

In the first case, when $p$ is even, the product of the two numbers doesn't change: $p \cdot q = \frac{p}{2} \cdot 2q$.
In the second case, when $p$ is odd, $\frac{p-1}{2} \cdot 2q = p \cdot q - q$. So the product has decreased by $q$, and we should set $q$ aside for later.

Eventually, we get to a pair $(1,r)$ whose product is easy to compute: it's just $r$. Because we've kept track of how the product of a pair has changed, we know that the original product is equal to this product, plus all the numbers we've set aside.

But we set aside $q$ from the pair $(p,q)$ whenever $p$ is odd. So adding the numbers we set aside to the final number just corresponds to adding up the second number in every pair whose first number is odd.

You also wanted to know what the sum of the numbers opposite an even number represents.

Given a $p$ and $q$ you want to multiply, choose $k$ such that $2^{k-1} - 1 < p \le 2^k - 1$. (In other words, $2^k$ is the next power of $2$ after $p$, not including $p$ itself.)

Then if we use this algorithm to find $(2^k-1)\cdot q$, we'll take the same number of steps to get to $1$ on the left-hand side, but all the left-hand numbers along the way are odd. This tells us that the sum of all the right-hand numbers should be the product $(2^k-1) \cdot q$.

Since the sum of all the right-hand numbers opposite an odd left-hand number is $p \cdot q$, the sum of all the right-hand numbers opposite an even left-hand number is their difference $(2^k-1-p) \cdot q$.

(Note by OP: as a complement to the answers, @ixi has kindly written a Python snippet that performs the Russian peasant algorithm)

def russian_peasant_multiplication(a,b, acc = 0):
    print(a,b,acc+b)
    if a == 1:
        return b + acc
    elif (a%2) == 0:
        return russian_peasant_multiplication(a//2,b*2,acc)
    else:
        return russian_peasant_multiplication(a//2,b*2,acc+b)
assert russian_peasant_multiplication(73, 217) == 15841


Derivation of multivariable Taylor series I am having trouble grokking why it is, assuming that the function is analytic everywhere (and many other assumptions that I am, no doubt, naively assuming), that this is true:

$f(x,y)=f(x_0,y_0)+[f'_x(x_0,y_0)(x-x_0)+f'_y(x_0,y_0)(y-y_0)]+\frac{1}{2!}[f''_{xx}(x_0,y_0)(x-x_0)+2f''_{yx}(x_0,y_0)(x-x_0)(y-y_0)+f''_{yy}(x_0,y_0)(y-y_0)^2]+...$

I am familiar with the one-variabled Taylor series, and intuitively feel why the 'linear' multivariable terms should be as they are.

In short, I ask for a proof of this equality. If possible, it would be nice to have an answer free of unnecessary compaction of notation (such as table of partial derivatives).

As a auxiliary question, I see a direct analogy with the first 2 terms  $f(x,y)=f(x_0,y_0)+[f'_x(x_0,y_0)(x-x_0)+f'_y(x_0,y_0)(y-y_0)]$ and the total differential $f(x,y)-f(x_0,y_0)=\Delta f(x,y)=f'_x(x_0,y_0)\Delta x+f'_y(x_0,y_0)\Delta y$.

When $\Delta x $ and  $\Delta y $ are not infinitesimally small, can I use the third term in the Taylor multivariable series to get closer to the real total differential?

Let $\phi(\boldsymbol{r})$ be a scalar field, and $\boldsymbol{a} \cdot \nabla \phi$ gives the directional derivative of $\phi$ in the direction of $a$.  That is,

$$\boldsymbol{a} \cdot \nabla \phi(\boldsymbol{r}) = \lim_{t\to 0} \frac{\phi(\boldsymbol{r} + \boldsymbol{a} t) - \phi(\boldsymbol{r})}{t}$$

Now let's consider $\Phi(t) = \phi(\boldsymbol{r}_0 + \boldsymbol{a}t)$ for some finite $t$.  Now, let's expand this in powers of $t$.  This is a one-dimensional Taylor series.

$$\Phi(t) = \Phi(0) + \Phi'(0)t + \frac{1}{2!} \Phi''(0) t^2 + \ldots$$

To substitute back in $\Phi(t) = \phi(\boldsymbol{r}_0+\boldsymbol{a}t)$, we must compute derivatives of $\Phi$ in terms of $\phi$.  Again, we resort to the basic definition of the derivative.

$$\Phi'(0) = \lim_{t\to 0} \frac{\phi(\boldsymbol{r}_0+\boldsymbol{a}t) - \phi(\boldsymbol{r}_0)}{t} = \boldsymbol{a} \cdot \nabla \phi(\boldsymbol{r})\Big|_{\boldsymbol{r}=\boldsymbol{r}_0}$$

And similarly for higher derivatives.  This enables us to write,

$$\phi(\boldsymbol{r}_0+\boldsymbol{a}t) = \phi(\boldsymbol{r}_0) +  [\boldsymbol{a} \cdot \nabla \phi(\boldsymbol{r})] \Big|_{\boldsymbol{r}=\boldsymbol{r}_0} t + \frac{1}{2!} [\boldsymbol{a} \cdot \nabla][\boldsymbol{a} \cdot \nabla]\phi(\boldsymbol{r}) \Big|_{\boldsymbol{r}=\boldsymbol{r}_0} t^2 + \ldots$$

It is not difficult to show that this form reproduces the form of the original question.  Take $t=1$ and let $\boldsymbol{a} = (x-x_0, y-y_0)$ and $\boldsymbol{r}_0 = (x_0, y_0)$.  Thus, we have built multivariate Taylor series from the well-established case of a single variable, just by use of the directional derivative.

Intuitively its quite clear: the multivariable analog of the first derivative is the gradient, which is exactly the second term evaluated at Ro.  The second derivitave generalizes to the Hessian, which is best represented in matrix form, and that is your second term...  The trick in deriving this is to define an s=R-R0 so g(s) = f(R-Ro) and use the chain rule/mean value theorem as usual.


What is the area bounded by the two graphs $y =\sin x$ and $y =\sin x\cos2x$? $(0\le x\le\pi)$ What is the area bounded by the two graphs $y =\sin x$ and $y =\sin x\cos2x$? $(0\le x\le\pi)$

My approach

$$\int^\pi_0\sin x -\sin x \cos2x \ dx$$
$$\int^\pi_0\sin x (1-\cos2x) \ dx$$

As $\cos2x = \cos(x+x)$

$\cos2x =\cos x \cos x -\sin x \sin x =\cos^2x-\sin^2x$

And as $\sin^2x + \cos^2x=1,$

$$\int^\pi_0\sin x (1-\cos2x) \ dx = \int^\pi_0\sin x \left(\sin^2x + \cos^2x-(\cos^2x-\sin^2x)\right) \ dx$$

$$=\int^\pi_0\sin x (2\sin^2x) = \int^\pi_02\sin^3x \ dx$$

Doing the integration gives me

$$\left[\frac{\sin^4x}{2\cos x}\right]^\pi_0$$
which is 0. Using technology to verify this answer, it was $\frac{8}{3}$ instead of 0. A calculator suggests my approach is valid, but there is clearly something wrong in my calculation.

Once you arrived to
$$=\int^\pi_0\sin x (2\sin^2x) dx$$
you do the following
$$\int_0^{\pi } 2 \sin (x) \left(1-\cos ^2(x)\right) \, dx$$
and then substitute $\cos(x)=u\rightarrow -\sin(x)\,dx=du$
The integral becomes
$$\int_1^{-1} -2 \left(1-u^2\right) \, du=\left. 2 \left(\frac{u^3}{3}-u\right)\right|_1^{-1}=\frac{8}{3}$$

Cause your last integral is incorrect, $$ \int^\pi_02\sin^3x \ dx = \left[\frac{1}{12} (\cos(3 x) - 9\cos(x))\right]_0^{\pi}  \ne \left[\frac{\sin^4x}{2\cos x}\right]^\pi_0$$


How to apply Chinese Remainder Theorem for $x$ If:

$$x \equiv 0 \pmod{17}$$ and $$x \equiv -1 \pmod{9}$$ Then how is:

$$x \equiv 17 \pmod{153}$$

I get that since $\gcd(9, 17) = 153 $ the solution will be $\pmod{153}$ but how do you get the $17 \pmod{153}$ ?

Hint first solve
$$ 9x\equiv 1\mod 17$$
which gives $x\equiv2\mod17$. Then solve
$$17x\equiv1\mod 9$$
which gives $x\equiv-1\mod9$. Then you will get
$$ x\equiv 2\times0\times 9+(-1)\times(-1)\times 17=17\mod 153. $$


Statistics and the addition rule. i dont get why 2/3*2/3 is not 4/6... plus if i am to use the addition rule, it will be 2/3+2/3 -(The correct answer)  what will that be then?

The question was.P((3 or 5 on the first toss of a die) or (3 or 5 on the second toss of a die)) and i seem to be getting stuck.

$$
\frac 2 3 \times \frac 2 3 = \frac {2\times2}{3\times3} = \frac 4 9.
$$

The probability of $3$ or $5$ on the first trial is $1/3.$

The probability that that happens on the first toss or the second is not $\frac 1 3 + \frac 1 3$ because those two events are not mutually exclusive: they could both happen.

One way to find the probability that one of these or the other (or both) occurs is to find the probability that they both fail to occur. The probability that the first one fails is $2/3$ and the probability that the second one fails is $2/3.$ The probability that the first one fails and the second one fails is $\frac 2 3 \times \frac 2 3 = \frac 4 9.$ Therefore the probability that you don't get two failures, i.e. that you do get at least one success, is $1- \frac 4 9 = \frac 5 9.$


Antiderivative of $e^{au}$ I cannot seem to figure out $\int e^{au}du$.  I have tried u-substitution (of course with a variable other than u) and can't get it to work out to the right answer.  Any help is appreciated.

Thanks!

Notice $$d(e^{au}) = a e^{au} du \implies \int d(e^{au}) = \int a e^{au} du \implies \int e^{au} du = \frac{1}{a} e^{au} + K$$


Stable Marriage / Stable Matching / Gale-Shapley where men rank a subset of women Given n men and n women, preference rankings for the women, does Gale-Shapley still find a stable matching if the men only rank a subset of women.

From this variation, it's possible that we end up with single people, but that's ok as this situation is still stable.

In this variation, some men may not be matched to a woman
But in that case, the man is content being single
Since women rank all men, some woman preferred that man, but that man didn't prefer that woman
Therefore having unmatched men and women is stable since

My problem is justifying the rest of the matching is also stable
Do I prove it by contradiction?

Imagine you're the president-for-life and you've decided that your population is too small and needs to grow, so you've made it a crime to be single!

Whenever someone, man or woman, refuses to rank everyone of the opposite sex, you simply invent a ranking for him, putting those he doesn't like below those that he does. Go by alphabetical order or draw lots, that doesn't matter. Then run the algorithm and force-marry everybody to whom the algorithm decides they should marry. Some of the marriages will be unhappy. Tough luck -- what are they gonna do, sue the president-for-life?

Now in reality those that ended up in an unhappy marriage in the thought experiment will instead be single. But the partial matching you have after dissolving the unhappy marriages will still be stable.

Namely if there's any pair of people who would choose to elope in reality, those two people would still choose to elope in the imaginary world. (They must like each other, so even if one or both of them is single, they would just be unhappily married in the imaginary world and therefore willing to elope with anyone they do like).

But Gale and Shapley tell us that the matching in the imaginary world; therefore nobody will elope in reality either.

Gayle-Shapely fails to find the matching somteimes

Suppose that we have 2 men and 2 women. Suppose that $m_1$ has preference
ranking $w_1$, $w_2$, and $m_2$ has preference ranking $w_1$ (and vetoes $w_2$).
Also suppose that $w_1$ has ranking $m_1$, $m_2$. The ranking for $w_2$ is unknown but doesn't matter. Now, there is 1 perfect matching of men to women they have not vetoed.
Namely, match $m_2$ to $w_1$ and $m_1$ to $w_2$. However, this is not stable, since $m_1$ and $w_2$ prefer each other over such a matching.

(The matching in which $m_1$ is matched to $w_1$ and $m_2$, $w_2$ remain isolated is stable but Gayle-Shapely fails to find it.)


Notation for there exists and let I sometimes encounter proofs as the following:

$\exists n\in\mathbb N$ such that …. Then $n$…

But the fact in that $n$ is not defined in the second sentence. A correct proof would contain instead:

$\exists n\in\mathbb N$ such that …. Let such a $n$. Then $n$…

Is there a notation to mean "there exists and let"?

You are asking about notation for "there exists and let". Note that the first part of this, "there exists," is a statement telling how something is, while "let" is an imperative telling the reader what to do. They have different roles in the proof and they have somewhat different formal languages.
The formal notation of statements contains things like quantifiers ($\forall,\ \exists$) and implications ($\implies$), while the formal notation for a proof rather is a deduction tree containing statements:
$$
\dfrac
{
  \begin{matrix}\\A \lor B\end{matrix}
  \quad
  \begin{matrix}\\ [A]\end{matrix}
  \quad
  \dfrac{[B] \quad B \rightarrow A}{A}
}
{
  A
}
$$
(The example proves $A$ from $A \lor B$ and $B \rightarrow A.$)
In a proof, "there exists" will be true either by some definition or by some other theorem or lemma, and the text would read "By definition/theorem $X,$ there exists $x$ such that $P(x).$ Take such an $x.$ Then ..." Here's a deduction tree for that:
$$
\dfrac
{
  \begin{matrix}\\ \triangledown \\ \hline \exists x\ P(x)\end{matrix}
  \quad
  \begin{matrix} [P(x)] \\ \vdots \\ Q \end{matrix}
}
{
  Q
}
$$
where $\triangledown$ denotes "definition/theorem $X$" and $\vdots$ that there is some deduction tree deriving $Q$ from $P(x).$ The left part above the horizontal line corresponds to "By definition/theorem $X,$ there exists $x$ such that $P(x),$ and the right part corresponds to "Take such an $x.$ Then $P(x)$ so ... Thus $Q(x).$"

In $(\exists x \in X)R(x)$ in $R(x)$ $x$ is actually defined, because it is same as $(\exists x) (x \in X \land R(x))$.
Addition.
If we consider $(\exists x \in X)R(x) \land S(x)$, then it same as $(\exists y \in X)R(y) \land S(x)$.


If $E/F$ is a finite extension and $E$ is algebraically closed, then $F$ is perfect. The problem is

  Let $E$ be a finite extension of $F$ and suppose $E$ is algebraically closed. Show that $F$ is perfect.

I know that a field $F$ is called perfect if every irreducible polynomial in $F[x]$ is separable, and a field $F$ is perfect if and only if it has characteristic $0$, or it has characteristic $p$ and $F=F^p$; then, fields of characteristic $0$ and finite fields are perfect.

You can prove:

If every extension of F splits, then F is perfect.
Let F ⊆ K ⊆ E a tower of fields. If E/F is algebraic and splits, then K/F splits.

And finally use the definition of algebraically closed.


Basic Modular Exponentiation reasoning I am trying to understand the modular exponentiation algorithm. Why is it that:

$x^2 \mod5 = (x\mod5)(x\mod5) \mod 5$

What is the basic reasoning behind this?

Write $x = m + 5n$ with $0 \leq m \leq 4$. No matter what you multiply $5n$ by, the result will be a multiple of $5$ and subsequently dropped by the "mod $5$" at the end. So, you might as well have dropped the $5n$ to begin with. That is, you could just take $x$ mod $5$ before carrying out the multiplication.

I am not sure about the doubt in  ur mind but i hope i am answering ur question!
The reason for the last mod5 in the rhs is to ensure that the lhs and the rhs are compatible.As the lhs is a residue it is by defn a value between 0 & 5.However if u drop the final mod5 the rhs may not be a residue(note that it is a product of two residues,so not necessarily a residue by itself!). eg x=4 implies lhs =1
                         without the final mod5 the rhs value=16 !


Integrate with the definition $\int_{-\infty}^{0}e^x\sqrt{1-e^x}\,dx$ I am sorry for not providing any suggestion or info, but I really don't know where to start. I think that it could be related to Riemann Sum, but I don't have a clue about how to do this. I would really appreciate any kind of help. $$\int_{-\infty}^0 e^x\sqrt{1-e^x} \, dx$$

Change of variable $u=e^x$ leads to :

$$\int_{-\infty}^0e^x\sqrt{1-e^x}\,dx=\int_0^1\sqrt{1-u}\,du$$

This last integral is easy to compute !

If I want to give a HINT for this kind of thing, here's what I write:
$$
\int_{-\infty}^0 \sqrt{1-e^x} \Big(e^x\,dx\Big).
$$
That should suggest $du = e^x\,dx.$ Rather than write $u=e^x$ as in "Adren"'s answer, I'll go with $u=1-e^x$ so that $du = -e^x\,dx$ and the expression in the big parentheses is $-du$. Then we have
$$
\int_\text{?}^\text{?} \sqrt u \big( {-du}\big)
$$
and we need to figure out what to put where the two question marks are. When $x=0$ then $u=1-e^0=0.$ As as $x\to-\infty$ then $e^x\to0$ so $u\to1.$ We get
$$
\int_1^0 \sqrt u \big( {-du}\big) = \int_0^1 \sqrt u \, du =\cdots\cdots
$$


Prove the following statement using the contrapositive method. If $ n^2 $ is divisible by 3 then n is divisible by 3. Prove the following statement using the contrapositive method. If $ n^2 $ is divisible by 3 then n is divisible by 3.
I tried using contrapositive method by assuming if not b then not a, i.e., if n is not divisible by 3 then $ n^2$ is not divisible by 3. and prove it.
Is this the correct way to do it or am I doing it wrong?
If anyone could layout an explanation could be helpful. Thanks!

With contrapositive method：
If n is not divisible by 3, let n = 3m + k, where m, k are integers and k=1,2 only.
好
Then
$n^2$  = $(3m+k)^2$=9$m^2$+6mk+$k^2$.
If k=1, $n^2$  = $(3m+k)^2$=9$m^2$+6mk+1=3(3$m^2$+2mk)+1, not divisible by 3.
If k=2, $n^2$  = $(3m+k)^2$=9$m^2$+6mk+3+1= 3(3$m^2$+2mk+1)+1,  not divisible by 3.
This is in contradictory with the assumption $n^2$ is divisible by 3. So n must be divisible by 3.


Symbol for "probably equal to" (barring pathology)? I am writing lecture notes for an applied statistical mechanics course and often need to express the notion that something is very probably true for functional forms found in the wild, without launching into a full digression for pathological exceptions.

For example, I would like to remind students that a function's Taylor series sometimes has the useful property of converging to the function's value.

Is there a mathematical symbol for this type of "equality" that is more dignified than my current options:
$$ f(x) \stackrel{\textrm{(good odds)}}{=} \sum_{k=0}^{\infty} \frac{(x-a)^k}{k!} f^{(k)} (a)$$
or
$$ f(x) \texttt{ ¯\_(ツ)_/¯ } \sum_{k=0}^{\infty} \frac{(x-a)^k}{k!} f^{(k)} (a)$$

I recommend handling this issue simply, such as:

1) "Under mild conditions we get from Fourier theory:"

$$ f(x) = \sum_{k=0}^{\infty} a_k \cos(2\pi k x) $$

2) "Under mild conditions we get from Taylor series theory:"

$$ f(x) = \sum_{k=0}^{\infty} a_k (x-a)^k $$

It is understood that the precise conditions under which equality holds can be obtained by looking at the details of that theory.

I would avoid:

-Unclear notation or phrases.
-Unclear, loaded, or advanced terminology.

For example: It sounds like you are talking about a class of problems for which no probability model is defined  (or relevant). Thus, unclear phrases like "strong odds" will confuse.  Funky equality signs will evoke laughter, but it will be nervous laughter since nobody will know what you are talking about. Advanced measure theory concepts such as "almost surely" will drive your teaching ratings down ("The professor expects us to know advanced probability which is not a prerequisite for this course...")

Here's the symbol I use.

≈  you can type it using alt+2248 in MS Windows.


Minimizing a function involving several modulus terms $f(x)=3|x+1|+|x|+3|x-1|+2|x-3|$

finding minimum value of this function

One conventional way would be to make five cases regarding the various inequalities and hence simplifying to find minimum value in a graph as in

I was trying another way

  method : Aim is to minimise each term .Since difference of x and 1 would matter thrice as much as that between x and 3 would , the value of x should be closer to 1 .

Applying this thought,x={3(1)+3(-1)+2(3)+1(0)}\9 which gives as x=2/3 .
This way comes to be incorrect.

I wanted to know if there were shorter solutions to this problem rather than using the graphical approach each time as when the modulus terms increase to 10 terms , it would be unreasonable to make 11 cases.

We want a point where the derivative goes from negative to positive. For |x-a|, the derivative is negative if x < a and positive if x > a. If f(x) = $\sum|x-a_i|$, then the derivative at x is thus going to be (sum of all $a_i$ greater than x) minus (sum of all $a_i$ less than x). So we want a point where those are equal. That is, we want a number where as many numbers are less than it as greater than. That's called the median. Note that if you have an even number of terms, then there will be a region between the two "middle" terms where the function is constant and minimal. Also note that when calculating the median, you should take repetition into account; that is, if an absolute value term has a coefficient of n, take n copies of the associated $a_i$. For example, in this case you should take the median of -1,-1,-1,0,1,1,1,3,3. And finally, note that it's a bit more complicated if some of the absolute value terms have negative coefficients.

Hint:  For the (convex) function $f(x) = \sum \lambda_n|x-a_n|$, ($a_n$ are distinct numbers). we always have a minimum point where derivative does not exist (it is not hard to prove this).

Hence,
 $$\min{f}=\min\{f( a_1),f(a_2),...,f(a_n)\}$$

I added this part to prove my claim! (Although it is somehow trivial! I am writing this exclusively for down-voter)

Proof :
We want to show that there is a minimizer which happens to be nondifferentiable point.
we assume $\lambda_n > 0$ (actually we don't need assume this as long as we are sure minimum exist!) Let $c \in \Bbb R$ be the minimum point then it has to be critical point too which means either $f'(c) =0$ or $f'(c) = \text{does not exist}.$  In second case we are done! So assume first case has been happened. So we have $f'(c) =0$. Since $f$ is pieacewise linear, there exist a maximal interval say $[a,b]$ containing $c$ such that $f$ is constant on it. Also note $ -\infty < a< b < + \infty $ because $\lim_{x \to \pm \infty} f(x) = + \infty$. This shows $f(a) = f(b)= f(c)$ and so $a,b$ are minimizer too and moreover (it is easy to show that)  $a,b$ are nondifferentiable points.

Conclusion: In order to find a minimum point, just evaluate $f$ at Absolutvalues' roots and pick the smallest one! Then you don't need think about graphical method which may lead to $11$ cases.


Algebraic Identity $a^{n}-b^{n} = (a-b) \sum\limits_{k=0}^{n-1} a^{k}b^{n-1-k}$ Prove the following: $\displaystyle a^{n}-b^{n} = (a-b) \sum\limits_{k=0}^{n-1} a^{k}b^{n-1-k}$.

So one could use induction on $n$? Could one also use trichotomy or some type of combinatorial argument?

I have no idea what you mean by "use trichotomy," but here is the combinatorial argument.  $a^n$ counts the number of words of length $n$ on the alphabet $\{ 1, 2, ... a \}$ and $b^n$ counts the number of words of length $n$ on the alphabet $\{ 1, 2, ... b \}$.  Assume $a > b$.  Then $a^n - b^n$ counts the number of words of length $n$ on the alphabet $\{ 1, 2, ... a \}$ such that at least one letter is greater than $b$.

Given such a word, suppose the last letter greater than $b$ occurs at position $k+1$.  Then there are $a - b$ choices for this letter, $a^k$ choices for the letters before this letter, and $b^{n-k-1}$ choices for the letters after this letter.  Thus there are $(a - b) a^k b^{n-k-1}$ such words, and summing over all $k$ gives

$$a^n - b^n = (a - b) \sum_{k=0}^{n-1} a^k b^{n-k-1}$$

as desired.

If you know the sum of a geometric sequence, then set $x=a/b$ and conclude
$
x^n-1 = (x-1)(1+x+x^2+\cdots+x^{n-1})
$. Now multiply by $b^n$. (If $b=0$, then the identity is obvious.)


Which one is bigger: $\;35{,}043 × 25{,}430\,$ or $\,35{,}430 × 25{,}043\;$? Which of the two quantities is greater?
Quantity A: $\;\;35{,}043 × 25{,}430$
Quantity B: $\;\;35{,}430 × 25{,}043$

What is the best and quickest way to  get the answer without using calculation, I mean using bird's eye view?

If we have two pairs of numbers, and both pairs add up to the same total, then the pair with the larger product will be the pair that's closer together. So the answer is the first pair.

(This picture might help: if you want a rectangle with a fixed perimeter to have the biggest possible area, you want it to be a square.)

Imagine an extreme case of shopping where you have 3 Louis Vuitton bags costing £1,000,000 each. Which is cheaper, getting a discount of £1 per item or putting one bag back? This tells you that 3 x 999,999 is larger than 2 x 1,000,000. And that tells you whether increasing the little term or the big term has a greater effect.


Condition on definition of dual norm In a review I'm reading, the dual norm is defined as $$||z||_*=\max_{||w||\leq 1}\langle w,z\rangle.  $$

Though I'm having a hard time understanding why $||w||\leq 1$ isn't equivalent to $||w||=1$, as given a $w$ such that $\langle w,z\rangle\geq 0$, if $||w||<1$, then using $\tilde{w}=1/||w||*w$ will give a larger inner product.

when $T$ is a linear operator $X \to Y$ between two normed vector spaces

$$\max_{\|z\| \le 1} \|T z\| \qquad\qquad \text{and} \qquad\qquad\max_{\|z\| = 1} \| T z \|$$  are the same.
this is because a norm asks for $\| a z\| = |a| \ \|z\| $ for any constant $a$ and $T$ is linear so  $\| T (a z)\| = |a| \ \|T z\| $.

here your linear operator is $$\begin{array}{ll}T : &X \to \mathbb{R} \ \ \ (\text{ or } \mathbb{C}) \\&z \to \langle w,z\rangle\end{array}$$ and its (operator) norm is $$\| T\| = \max_{\|z\|=1} | T z| = \max_{\|z\|=1} | \langle w,z\rangle | $$

here it is not the case but don't forget many linear operators are unbounded, sometimes  $\|T\| = \infty$

Consider the case where $z$ has negative components, or a certain set of
negative components. We may want to consider minimizing them by inputing
a smaller length $w$ vector rather than choosing the largest possible $w$
vector available, as an example, consider when $w = <.6,.2>, z = <-.6,-.2>.$
We see that
$$\langle w,z \rangle \approx -.52$$
while
$$\langle \frac{w}{\|w\|}, z \rangle \approx -.822.$$
In this case, we get a strictly greater solution when we do not normalize
$w$.