Determine the equation of a function knowing the tangent line and points How can I resolve these problems?

Find the equation of a function $f:\mathbb{R}\rightarrow\mathbb{R}$ such that it has the tangent line $y=4x+8$ at $x=-1$ and such that $f(0)=f(1)=0$.
Find a function $h:\mathbb{R}\rightarrow [0,+\infty)$ such that it has the tangent line $y=2x$ at $x=1$.
Find a function $g:\mathbb{R}\rightarrow (-\infty,0]$ such that, for all $k\in[-1,0]$, the equation $g(x)=k$ has infinitely many real solutions.

For (2) I thought of reasoning about the exponential function, and for (3) about the sine or cosine function (for example $-1-\sin x$, but this function is $\mathbb{R}\rightarrow [-2,0]$), but what is the reasoning in general?

1) If the tangent line at $x=-1$ is $y=4x+8$, it implies that $$f'(-1)=4, \quad f(-1)=4(-1)+8=4. $$
Combined with conditions $f(0)=f(1)=0$, if we try  a polynomial, it must have at least degree $3$ and be divisible by $x(x-1)$. So we try with
$$f(x)=x(x-1)(ax+b).$$
The condition  $\,f(-1)=4$ yields the relation $2(b-a)=4$, whence $b=a+2$, and the condition $\,f'(-1)=4$ becomes
$$4=5a-3b=-1-3a,$$
whence $a=-\dfrac53$, $\;b=\dfrac13$, and finally
$$f(x)=\frac13x(x-1)(x-5).$$

3) The function $g$ defined as
$$g(x)=\begin{cases}
-\biggl|\sin \dfrac1x\biggr|&\text{if }\,x\ne 0,\\[1ex]
0&\text{if }\,x=0,
 \end{cases}$$
satisfies the condition.

1) $f'(-1) = 4, f(0)= 0, f(1) = 0$

We have 3 variables to solve for.

For the sake of easy calculations lets assume that $f(x)$ is a polynomial.

$f(x) = ax^2 + bx + c\\
f'(x) = 2ax + b$

Now plug the values above, and we get 3 linear equations.

$-2a + b = 4\\
c = 0\\
a+b = 0$

$f(x) = -\frac {4}{3} x^2 + \frac {4}{3}x$

But we could choose a trig function if we wanted to.

$f(x) = -\frac {4}{\pi} \sin \pi x$ will work just as well.

Is surjectivity a requirement?  Usually, it is not.

If you need a surjective function.  Start with a cubic.

$f(x) = ax^3 + bx^2 + cx\\
f'(x) = 3ax^2 + 2bx + c\\
3a - 2b + c = 4\\
a+b+ c = 0\\
f(x) = 2x^3 -2x$

2) $h(x) = 2|x|$ is the simplest function I see that fits the bill.

3) A periodic function sounds like a good idea.  $g(x) = -\sin x - 1$ will work.  unless it is a requirement that your function be surjective.

you could say $g(x) = \begin{cases} \tan x &\frac {\pi}{2}<x\le \pi\\\sin x - 1 & \text {elsewhere} \end {cases}$


Proving the remainder when a polynomial is divided by an integer. How should I go around proving that $\forall x \in \mathbb{Z}$, the remainder when $x^2+2x$ is divided by $3$ is $0$ or $2$?

Do I use the division algorithm for this one?

Exhaust the possibilities:

When $x\equiv 0$: $x^2+2x\equiv 0+0\equiv 0$.

When $x\equiv 1$: $x^2+2x\equiv 1+2\equiv 0$.

When $x\equiv 2$: $x^2+2x\equiv 4+4\equiv 2$.

As one can show, the remainder of a sum equals the sum of the remainders*
$$(a+b)\text{ rem } m=((a\text{ rem } m)+(b\text{ rem } m))\text{ rem } m.$$
And the remainder of a product equals the product of the remainders*
$$(a\cdot b)\text{ rem } m=((a\text{ rem } m)\cdot(b\text{ rem } m))\text{ rem } m.$$
(*provided you take the reminder once again to avoid exceeding the divisor.)

Then $$(x^2+2x)\text{ rem }3=(x^2\text{ rem }3+2x\text{ rem }3)\text{ rem }3=((x\text{ rem }3)^2+2(x\text{ rem }3))\text{ rem }3.$$
As $x\text{ rem }3$ can take only the values $0,1,2$, it suffices to evaluate for these.


Is there an integer $y>0$ such that for all $x>y$, at least $4$ of $x+1, x+2, x+3, x+4, x+5$ are divisible by a prime greater than $5$? As I understand it, the answer to this question is yes.

I would appreciate it if anyone could provide a counter example or provide details on how to resolve this question.

My thinking is that this is true for $y > 80$

Here's my thinking:

We can assume that there is at least on integer in the sequence $x+i$ such that $x+i = 2^a3^b5^c$ where $a,b,c \ge 0$ and $a+b+c > 0$ and $1 \le i \le 5$
So, I am trying to prove that there is no solution for $x>24$ where $2^a3^b5^c + d = 2^e3^f5^g$ and $1 \le d \le 5$
Let $f=gcd(2^a3^b5^c,2^e3^f5^g)$ and we need only deal with the following forms:

Case 1:  $2^a \pm 1 = 3^b5^c$ where $a,b,c > 0$

Since $a > 1$, we know that $b$ is even since $(-1)^b(1) \equiv \pmod 4$
Since $a > 2$, we know that $c$ is even since $(1)^{\frac{b}{2}}(-3)^c \equiv 1 \pmod 8$
But then $(3^{\frac{b}{2}}5^{\frac{c}{2}} + 1)(3^{\frac{b}{2}}5^{\frac{c}{2}} - 1)  = 2^a$ which is impossible for $a > 1$
Let's look at $2^a-1 = 3^b5^c$
There is no solution for $a$ is even because $(2^{\frac{a}{2}} - 1)(2^{\frac{a}{2}} + 1)= 3^b5^c$ which is impossible since $b,c > 1$
There is no solution for $a$ is odd because $(-1)^a - 1 \not\equiv 0 \pmod 3$

Case 2:  $3^a \pm 1 = 2^b5^c$ where $a,b,c > 0$

Let's start $3^a+1 = 2^b5^c$
$a$ cannot be odd because only $(-2)^{4x+2} + 1 \equiv 0 \pmod 5$
$a$ cannot be even since $(-1)^a + 1 \not\equiv 0 \pmod {10}$
Let's look at $3^a - 1 = 2^b5^c$
$a$ cannot be even since $(3^{\frac{a}{2}}-1)(3^{\frac{a}{2}}+1) = 2^b5^c$ is impossible for $b > 5,c>0$ or for $b >0,c>1$
$a$ cannot be odd since only $(-2)^(4x) - 1 \equiv 0 \pmod 5$

Case 3:  $5^a \pm 1 = 2^b3^c$ where $a,b,c > 0$

Let's look at $5^a + 1 = 2^b3^c$
We know if there's a solution that $b=1$ since $(1)^a + 1 \equiv 2 \pmod 4$
Since $c>1$, it follows that $a=6k+3$ since $5^a \equiv -1 \pmod 9$
$5^{6k+3}+1\equiv 0 \pmod 7$
But $2^b3^c \not\equiv 0 \pmod 7$
Let's look at $5^a-1 = 2^b3^c$
$a$ cannot be even since $(5^{\frac{a}{2}}-1)(5^{\frac{a}{2}}+1) = 2^b3^c$ is impossible for $b>1,c> 0$
$a$ cannot be odd since $(-1)^a-1 \not\equiv 0 \pmod 6$

Case 4:  $2^a \pm 1 = 3^b$ where $a,b > 0$

Case 5:  $2^a \pm 1 = 5^b$ where $a,b > 0$

Case 6:  $3^a \pm 1 = 5^b$ where $a,b > 0$

Case 4,5, and 6 are impossible for $x > 24$ by the proof behind Catalan's conjecture.

Edit: Eric Towers has pointed out that $\{80,81\}$ do not have a prime greater than $5$.  It seems that my logic in Case 2 did not account for $(3^2 - 1)(3^2 + 1) = 2^4*5$

I've updated my assumption to $y > 80$.  This removes the counter example.  I will spend time reading up on smooth numbers and spending time verifying that $80$ is the correct value for $y$.  If anyone has a precise formulation, that will be greatly appreciated.  :-)

tl;dr:  If $x+1 \geq 321$, then the five consecutive integers starting at $x+1$ have at most one 5-smooth member.

It is sufficient to ask how often 5-smooth numbers are nearby.  If there are a pair of 5-smooth numbers with difference < 5, then no consecutive 5 integers containing the pair can satisfy the proposed divisibility pattern.  A 5-smooth number is a number with no prime factor greater than 5.

Størmer has shown that there are only a finite number of consecutive 5-smooth numbers.  More on these kinds of questions here.  Pillai conjectured that for fixed $A$, $B$, and $C$, $A x^n - B y^m = C$ has only a finite number of solutions $(x,y,m,n)$.  Erick Wong, in his answer to this problem, has demonstrated a reduction of the posted question to this form, such reduction being a (large-ish) list of such polynomials with exponent greater than three.  In fact, these are irreducible binary forms of degree three, so Thue's theorem applies and each has at most a finite number of solutions.  (Strictly, not all the forms on the raw list are irreducible, but this is no obstruction.)  Thue has shown that each equation has at most a finite number of solutions.  Wong's reduction thereby shows that there are a finite number of pairs of 5-smooth numbers that differ by less than 5.

Update: 20140410  Added extreme summary at the top.  The following paragraphs and code with results of PARI/GP solution of many Thue equations, replaces the subsequent paragraphs.

Rather than work through a reduction of the number of equations, we use very fast code in PARI-GP (2.7.0) to solve the problem quickly.  The code

{ for (a2 = 0, 2,
    for (a3 = 0, 2,
      for (a5 = 0, 2,
        for (b2 = 0, 2,
          for (b3 = 0, 2,
            for (b5 = 0, 2,
              ti = thueinit(2^a2*3^a3*5^a5*x^3 - 2^b2*3^b3*5^b5, 1);
              for (d = 1, 4,
                str = Strprintf("[% d, % d, % d] :  % s ",
                  2^a2*3^a3*5^a5, 2^b2*3^b3*5^b5, d, thue (ti, d));
                print (str);
                write ("some-output-file.txt", str);
 ) )))))) }

solves the Thue equations we are interested in in a few seconds.  (Note that by default, the thueinit() function sets up internal state to search for solutions assuming the generalized RH.  We have given the option to not make this optimistic assumption.  Consequently, the set of solutions found is unconditionally exhaustive.)  Of the 2916 equations, only 304 have solutions and the union of those sets contains 334 pairs (not all distinct).  Examples (ordered pairs are $(x,y)$):  $$ 1 x^3 - 1 y^3 = 1 : \{(0,-1),(1,0)\} $$
$$ 1 x^3 - 3 y^3 = 3 : \{(0,-1),(3,2)\} $$  The pairs of nearby 5-smooth integers produced by these solutions are frequently repeated.  Collecting pairs, sorting, and ignoring negative integers, the many equations give the following set of candidates (some of which are spurious):

$\{ (1,2), (1,3), (1,4), (1,5), (2,3), (2,4), (2,5), (2,6), (3,4), (3,5), (3,6), (4,5), (4,6), (4,8), (5,6), (5,8), (5,9), (6,8), (6,9), (6,10), (8,9), (8,10), (8,12), (9,10), (9,12), (10,12), (12,15), (12,16), (15,16), (15,18), (16,18), (16,20), (18,20), (20,24), (24,25), (24,27), (25,27), (27,30), (30,32), (32,36), (36,40), (45,48), (48,50), (50,54), (60,64), (72,75), (80,81), (96,100), (125,128), (160,162), (240,243), (320,324), (6859,6860), (13718,13720), (20577,20580), (27436,27440) \}$

Except for the last four pairs, this agrees with the previous list (see below) which was generated by brute force calculation of 5-smooth numbers with exponents less than 200.  The last four pairs are spurious solutions because $6859=19^3$, $6860=2^2 \cdot 5 \cdot 7^3$ and the subsequent three pairs are this pair multiplied by $2$, $3$, and $4$.  (Interestingly, only 7 and 19 appear as spurious factors in any of the solutions generated by the mass of polynomials.)

The PARI-GP code's output was parsed by the Mathematica 9.0 code

Module[{ inFile,   lines, nonempty, instances  },
  inFile = StringSplit[ Import["some-output-file.txt"], "\n" ];
  lines = ToExpression[ StringReplace[
     "{" <> # <> "}", {"[" -> "{", "]" -> "}", ":" -> ","}]] & /@ inFile;
  Print["Total equations: ", Length[lines]];

  nonempty = Select[lines, #[[2]] =!= {} &];
  Print["Satisfiable equations: ", Length[nonempty]];

  (* Switch from equation indexed to per-solution lists. *)
  Print["Total solutions: ", Length[Flatten[nonempty[[All, 2]], 1]]];

  instances[{eqn_, pairs_}] :=
     {eqn[[1]]*#[[1]]^3, eqn[[2]]*#[[2]]^3} & /@ pairs;

  Select[Split[Sort[
     Sort /@ Flatten[instances /@ nonempty, 1]
     ]][[All, 1]],
     #[[1]] > 0 &
  ]
]

generating only mildly syntactically different output from that listed above.

We therefore ...

... know there are only a finite number of solutions to the exponential Diophantine equations which are satisfied by counterexamples to the 5-consecutive 5-smooth numbers problem.
... have generated the complete set of solutions of polynomial relaxations to the exponential equations.  This introduced only a handful of spurious solutions.
... have eliminated the spurious solutions.
... showed the complete solution set is that found by previous direct (but not provably complete) generation of small 5-smooth integers.

Discarded 20140410 starts here:
Unfortunately, although we can show that each item in the list of equations has at most a finite number of solutions, part of the general solution method boils down to laboriously checking which of some set of potential solutions are actual solutions.  The bounds on the sizes of these sets are rather large, so this becomes impractical even for modest sizes of the coefficients.  Just $45x^n - y^n = 1$ is not easily disposed (in Mathematica 9.0).  The equations with coefficients $>100$, e.g., $900x^n - y^n = 4$, are likely infeasible at present.

A few small 5-smooth number pairs that differ by less than 5, skipping the near continuum up to 27: {27,30}, {30,32}, {32,36}, {36,40}, {45,48}, {48,50}, {50,54}, {60,64}, {72,75}, {80, 81}, {96,100}, {125, 128}, {160, 162}, {240, 243}, {320, 324}.  There may be more pairs.  There might not.  (There is no other with powers of 2, 3, and 5 less than 200.)

Edit 20140326:  Removed the first, wrong, sentence, "The question of even whether $2^m - 3^n = 5$ only finitely many times, a specialization of the generalized Tijdeman's conjecture, is still open.", and the rest of the first paragraph, largely replacing it with the second paragraph, above.  Tijdeman has shown that the quoted sentence is false and Erick Wong was right to insist that this is the case.

...no such $y$ exist. Suppose otherwise, and let $p>5$ be such a prime, then $p|x+i$ and $p|x+(i+1)$ for some i, $1<=i<5$, hence $p|(x+i+1)-(x+i)$ or $p|1$, a contradiction...


Find entire functions that satisfy the following inequalities I am trying to determine whether there exist two entire functions $f(z),g(z):\mathbb{C}\to\mathbb{C}$ that satisy the following inequalities (independently):

$$(1): |e^{|z|}-f(z)|<e^{-|z|}\\(2):|g(\bar{z})|\geq e^{|z|}$$

Well, as for inequality $(1)$, I figured that if there exists an entire function $f(z)$, it has to be some sort of an exponent. A (finite) polynom wouldn't work, because the LHS of the inequality would always be unbounded (whereas the RHS is indeed bounded). I tried substituting $f(z)=e^{az}$ for some $a\in\mathbb{C}$ but couldn't figure out what to do further.

Same goes for inequality $(2)$. Whereas I need the inequality to be true for every $z\in\mathbb{C}$, no matter what function I plug in, I find out that some sort of a connection between $\Re{(z)}$ and $\Im{(z)}$ must happen for the inequality to hold.

Those consequences led me to think that maybe there don't exist entire functions as required, but I couldn't prove why is this true. Something tells me that I need to use Liouville's Theorem, but I couldn't find the connection. I tried, for example, in equality $(1)$, to multiply both sides by $e^{|z|}$. Then, the new LHS is bounded. I wanted to say it is constant because of Liouville's Theorem, but the problem is that the LHS I get is not an entire function (thus I cannot use the theorem); neither in inequality $(2).$ Of course there's a chance that I'm wrong and just don't know enough entire functions in order to find a good example.

I'm pretty lost right now so I'd be happy to hear your thoughts. Thanks!

(1) would imply that $f$ is non-zero on the whole complex plane, then the function $1/f$ would be entire and bounded, hence constant. This is not possible.

For (2) it's the same trick: consider $1/g$, which must be entire and bounded.

There are no such entire functions. Since a polynomial has sub-exponential growth, this is immediate from the following (which I bet was a previous result or a previous exercise in the book):

    Lemma. If $f$ is an entire function and $\lim_{|z|\to\infty}|f(z)|=\infty$ then $f$ is a polynomial.

Indeed. say $$f(z)=\sum_0^\infty c_nz^n.$$Then $$f(1/z)=\sum_{-\infty}^0c_{-n}z^n.$$

But $\lim_{z\to0}|f(1/z)|=\infty$, which bt definition says $f(1/z)$ has a pole at the origin. Looking back at the section on Laurent series for functions with various sorts of singularities, we see this implies $$f(1/z)=\sum_{-N}^\infty a_nz^n.$$So uniqueness of the Laurent series implies that $$c_n=0\quad(n>N).$$


Prove that $\triangle ABC$ is equilateral, If $(a+b-c)^{a}\cdot (b+c-a)^{b}\cdot (c+a-b)^{c}\geq a^a\cdot b^b\cdot c^c$ If $a,b,c$ are the sides of a $\triangle ABC\;,$ such that $$\left(1+\frac{b-c}{a}\right)^{a}\left(1+\frac{c-a}{b}\right)^{b}\left(1+\frac{a-b}{c}\right)^{c}\geq 1,$$
then proving $\triangle$ is equilateral.

$\bf{My\; Try::}$ We can write it as $$\left(1+\frac{b-c}{a}\right)^{a}\left(1+\frac{c-a}{b}\right)^{b}\left(1+\frac{a-b}{c}\right)^{c}\geq 1$$
So $$\left(\frac{a+b-c}{a}\right)^{a}\cdot \left(\frac{b+c-a}{b}\right)^{b}\cdot \left(\frac{c+a-b}{c}\right)^{c}\geq 1$$
So $$(a+b-c)^{a}\cdot (b+c-a)^{b}\cdot (c+a-b)^{c}\geq a^a\cdot b^b\cdot c^c$$
Now how can i solve after that, Help required, Thanks

The title's inequality is wrong. I'll prove a reversed inequality.
Let $a=y+z$, $b=x+z$ and $c=x+y$.
Since our inequality does not changed after substitution $a\rightarrow ka$...,
we can assume that $x+y+z=3$.
And we need to prove that $\sum\limits_{cyc}(3-x)\ln\frac{2x}{3-x}\leq0$ or
$\sum\limits_{cyc}\left(3(x-1)-(3-x)\ln\frac{2x}{3-x}\right)\geq0$, which is true because
$3(x-1)-(3-x)\ln\frac{2x}{3-x}\geq0$ is true for all $x\in(0,3)$.
The equality occurs for $x=y=z=1$.
Thus, $a=b=c$ and we are done!
Maybe you mean the following problem.

If $a,b,c$ are the sides of a $\triangle ABC\;,$ such that $$\left(1+\frac{b-c}{a}\right)^{a}\left(1+\frac{c-a}{b}\right)^{b}\left(1+\frac{a-b}{c}\right)^{c}\geq 1,$$
then proving $\triangle$ is equilateral.

Let $a+b+c=1$.
Hence, by Jensen $a\ln\left(1+\frac{b-c}{a}\right)\leq\ln\sum\limits_{cyc}(a+b-c)=1$.
Thus, $\left(1+\frac{b-c}{a}\right)^{a}\left(1+\frac{c-a}{b}\right)^{b}\left(1+\frac{a-b}{c}\right)^{c}\leq 1$ and with the given we obtain $a=b=c$.

Another solution:
Prove: $$\left ( a+ b- c \right )^{a}\left ( b+ c- a \right )^{b}\left ( c+ a- b \right )^{c}\leq a^{a}b^{b}c^{c}$$
By weight power mean:
$$\sqrt[a+ b+ c]{\left ( \frac{a+ b- c}{a} \right )^{a}\left ( \frac{b+ c- a}{b} \right )^{b}\left ( \frac{c+ a- b}{c} \right )^{c}}\leq  \frac{1}{a+ b+ c}\left ( a. \frac{a+ b- c}{a}+ b. \frac{b+ c- a}{b}+ c. \frac{c+ a- b}{c} \right )= 1$$
i.e.


How do we get the formula of the sequence? A woman is walking home with distance $d$ and speed $v$.
The dog is happy and runs at speed $\frac{3v }{ 2}$ always between woman and House back and forth.
(i) At what distances $(d_n)_{n\geq 1}$ do women and dogs meet?
(ii) Determine the total path length of the dog with the help of $(d_n)_{n\geq 1}$.
$$$$
EDIT:
Let $x$ be the distance between the woman and the house and let $s$ be the distance between the dog and the house.
At the beginning we have $x_0=d$ and $s_0=0$.
It holds that $x=d-vt$ and $s=\frac 32v t$.
The woman and the dog meet at $x=s=d_1$ for $t=t_1$.
From $x=s$ we get $d-vt=\frac{3}{2}vt \Rightarrow \frac{5}{2}vt=d \Rightarrow t=\frac{2d}{5v}$, so $t_1=\frac{2d}{5v}$.
So we have that $d_1=x(t_1)=d-v\cdot \frac{2d}{5v}=d- \frac{2d}{5}=\frac{3d}{5}$.
After the meeting of the woman and the dog, the dog goes back to the house and then again to the woman.
At time $t_1$ the dog is at $s_1=\frac{3d}{5}$.
The dog goes in direction of the house, so $s=\frac{3d}{5}-\frac{3v}{2}t$.
When $s=0$ the dog arrived at the house, so $t=\frac{2d}{5v}$.
Then the dog goes back in direction of the woman, so $s= \frac{3}{2}vt$ with $t>\frac{2d}{5v}$.
At time $t_1$ the woman is also at $x_1=\frac{3d}{5}$.
The woman continues in diection to the house, so $x=\frac{3d}{5}-vt$.
For the second meeting, it holds $x=s=d_2$.
We get \begin{equation*}\frac{3d}{5}-vt=\frac{3}{2}vt \Rightarrow \frac{3d}{5}=\frac{5}{2}vt \Rightarrow t=\frac{6d}{25v}\end{equation*} So  they meet at \begin{equation*}d_2=x(t_2)=\frac{3d}{5}-v\cdot \frac{6d}{25v}=\frac{9d}{25}\end{equation*}.
So the $n$-th meeting is at $d_n =\left (\frac{3}{5}\right )^nd$.
Is that correct so far?
For the second question do we take the sum of all the terms $d_n$ ? Or should we take twice each term $d_n$ since the dog goes back and forth?

The distance of the woman from home is given by $d-vt$, and that of the dog by $d-\frac32vt$, until it reaches it, at time $t_1=\frac23\frac dv$. It comes back to its mistress with equation
$$\frac32v(t-t_1)=\frac32vt-d.$$
The moment they meet is obtained by solving
$$\frac32vt_2-d=d-vt_2$$ or $$t_2=\frac25\frac dv,$$ at a distance $\frac35d$ of home.

Now this repeats proportionally, substituting $\frac35d$ for $d$, and we have a geometric progression of common ratio $\frac35$.
The distances of the meetings are given by the partial sums of the sequence
$$\frac25d,\frac25\frac35d,\frac25\frac9{25}d,\cdots\frac25\frac{3^n}{5^n}d,\cdots$$
which indeed converges to $d$.
The dog travels $\frac32$ times more than the woman, hence $\frac32d$.

If the woman and dog start at distance $d$ from the house and re-meet when the woman is at distance $\delta$ from the house, the woman will have walked a distance $d-\delta$ and the dog will have run a distance $d+\delta$. Now since the dog runs fifty percent faster than the woman walks, it goes fifty percent further in any given amount of time, meaning
$$d+\delta={3\over2}(d-\delta)$$
and thus $\delta={1\over5}d$. So the sequence of distances (from the house) that the woman and the dog meet up is $d_n=\left(1\over5\right)^nd$. The total distance the dog runs is
$$\begin{align}
(d+d_1)+(d_1+d_2)+(d_2+d_3)+\cdots
&=d+2d\sum_{n=1}^\infty\left(1\over5\right)^n\\
&=d+2d{1/5\over1-1/5}\\
&=d+2d{1\over5-1}\\
&=d+{2d\over4}\\
&={3\over2}d
\end{align}$$
which agrees with what we said earlier: the dog goes fifty percent further than the woman.


$ \triangle ABC$ is a right triangle, $AX$ bisects $\angle A$ and ... Assume $ \triangle ABC$ is a right triangle where $\angle C= 90°$. Suppose that
$ \overline {AX} $ bisects $\angle A$ and point $X$ lies on $BC$. Assume that the circumcircle of triangle $AXB$ intersects $AC$ on $Y$.

a) Show that if lengths $BC$ and $CY$ are intergers divisible by a prime $p$, then $AY$ is also an intenger divisible by $p$.

b) Show that if $CY= k$ and $BC= 3k$ ($k$ is an interger), then the lengths of sides of the triangle $ABC$ must be intergers.

This is what I have done:

Aplying power of point of $C$, we get:

$$CY (CA) = (CX)(CB)$$

$$CY(CY+AY)= CB(CB -XB)$$

$$ (CY)^2+ CY(AY) = (CB)^2 - CB(XB)$$

$$CY(AY) = (CB)^2 - (CY)^2 - CB(XB)$$

$$ AY = \frac{(CB)^2 - (CY)^2 - CB(XB)}{CY}$$

But this doesn't prove that $AY$ is divisible by $p$ or that it is an interger.

I did that considering this figure. I think I may be wrong because that might not be what a circumcircle is.

Since $\angle BAX = \angle XAY$ and $BXYA$ are concyclic, it means that $BX=XY$. Thus

$$
CX = BC - BX \land CX^2 = BX^2 - CY^2
$$
$$
(BC - BX)^2 = BX^2 - CY^2
$$
$$
BC^2 + BX^2 - 2BC\cdot BX = BX^2 - CY^2
$$
$$
BX = \frac{BC^2+CY^2}{2BC}
$$
From the power of the point:
$$
AC = \frac{BC\cdot BX}{CY} = \frac{BC^2 +CY^2}{2CY}
$$
Why is it divisible by $p$?

You might find it useful:
The power of point equation you wrote is correct.
$CY⋅CA=CX⋅CB$
Also, according to the internal bisector theorem:
$\frac{CX}{CA}=\frac{BX}{AB}$


Show that , if $a \ge 9/8$, then $f '(x) \ge 0$ My questions are to do with the solution of the following question:

  Let $f(x)=ax-\frac{x^3}{1+x^2}$ , where $a$ is a positive constant.
  Show that if $a\ge\frac{9}{8}$ then $f'(x)\ge0$ for all $x$.

Differentiating we get :
$$f'(x)=\frac{a+(2a-3)x^2+(a-1)x^4}{(1+x^2)^2}$$

Next the following is said/done:
"We can use the inequality $a\ge\frac{9}{8}$ immediately after finding f'(x) since $a$ appears in f'(x) with a plus sign always:
$$f'(x)=\frac{a+(2a-3)x^2+(a-1)x^4}{(1+x^2)^2}\ge\frac{\frac{9}{8}+(\frac{9}{4}-3)x^2+(\frac{9}{8}-1)x^4}{(1+x^2)^2}=\frac{(x^2-3)^2}{8(1+x^2)^2}\ge0$$

My questions pertain to everything in bold and after the bold statement:

How is the author using the inequality $a\ge\frac{9}{8}$ to get to the final result?
What is the significance of $a$ appearing with a positive sign always?

First the sign of $f'(x)$ is the sign of its numerator, which is a biquadratic polynomial, so setting $u=x^2$, we obtain a quadratic polynomial:
$$p(u)=(a-1)u^2+(2a-3)u+a.$$
Supposing $a\ne 1$, so we have a quadratic polynomial, it has a constant sign (or is $0$) if and only if is discriminant is non-positive:
$$\Delta=(2a-3)^2-4a(a-1)=9-8a\le 0.$$
So the condition is indeed $a\ge \frac98$.
Last, since the sign of $p(u)$ is constant, it is also the sign of $p(0)=a$.

We must show $(a-1)x^4+(2a-3)x^2+a\geq 0$ ,
and can easily assume $a\geq 1$.

1: exception case If  $a=1$, $f'(x)=-x^2+1$

This eventually become negative.

2: If axis$\leq0⇔ -\frac{2a-3}{a-1}\leq0⇔a\geq\frac{3}{2}$ or $a<1 $, this need only $f(0)=a\geq0$

3: If axis $>0⇔ 1<a<\frac32$, this need $D\leq0$

$D=(2a-3)^2-4a(a-1)=-8a+9\leq0$

We get $a\geq\dfrac98$ by these 3 cases.


find g(x) given f(x) and the composition (g o f)(x) I've been stuck on this final math problem for ages

I'm given $$f(x) = x^2 + 1$$

and the final composition is $$(g \circ f)(x) = \frac{1}{x^2 + 4}$$

I'm asked to find that $g(x)$ was in order to make this true, but i'm not sure how?

This becomes way easier if you have the knowledge of inverse functions.

Let me make this clear. You have $f(x) = x^2 + 1$ and  $g(f(x)) = 1/(x^2 + 4)$. Now pause and think about the second function. The function is defined as $g(f(x))$, right. now what if there is some way that you could manipulate this function and some how change it to $g(x)$. Or think about with what other function should you multiply $f(x)$ [the function in $g(f(x))$ ] to get $x$ [so that the function would be $g(x)$]. It is $f(x)^{-1}$ right.

So let us find $f(x)$ inverse.
      $f(x) = x^2 +1$ then $f(x)^{-1} = \sqrt{x - 1}$ right [ just swipe the $x$ with $f(x)$ and solve for $f(x)$ that should give you this result]
now go to the first function $g(f(x))$ [this function is the same as $g(x^2 + 1)$ right.]

Now find $g(\sqrt{x -1})$ (that is $g$ of the inverse function you have found) in the function which is $g( x^2 + 1)$.

Thus the result becomes
$$g((\sqrt{x - 1})^2 + 1) = \frac{1}{(\sqrt{x - 1})^2 + 4}.$$
Now here comes the beauty: what is $(\sqrt{x-1})^2 + 1$? It is $x$, so the value of $g((\sqrt{x-1})^2 + 1) = g(x)$.
Now $$g(x) = \frac{1}{(\sqrt{x - 1})^2 + 4} = \frac{1}{x + 3 }.$$


Divide set into two subsets of equal sum and maximum this sum Original Question: https://stackoverflow.com/questions/47492444/create-two-sub-lists-from-given-list-of-integers-with-equal-sum-and-maximize-thi

You are given a list S of positive integers. You are to create two sub-lists S1 and S2 taking elements from S, such that

sum of S1 is equal to sum of S2
maximize this sum and output it
no need to put all elements of S into S1 or S2, you can ignore any number of elements of S.
For example: if S= [2, 6, 5, 1, 2, 5] then answer will be 10, (with S1= [6, 2, 2] and S2= [5, 5] with ignoring 1)

Constraints:

(i) if N is length of S, 1<= N <=50

(ii) if MAX is the maximum element of S, 1<= MAX <=1000

(iii) if SUM is the total sum of S, 1<= SUM <=1000

I can think only below brute-force approach:

as 1<=SUM<=1000, our answer can be between 0 and 500.

so, for each subset (SUB) of S, I am finding sum (SUBSUM) of SUB and checking whether SUBSUM can be obtained from list S - SUB using subset-sum algorithm. I am returning largest such SUBSUM. So my time complexity is O(N*(SUM/2)*2^N)

Any faster way?

Any DP approach?

I am pretty sure you have found an answer by now, but I am leaving an answer here for any possible future reference.

The previous answer said that this problem is NP-Complete under sufficiently large n, but I maintain that this problem can be solved in O(n*sum) time, via a DP-approach.

Here's how (in C++, and I'm sorry that my code is a little messy):

#include<cstdio>
int previous_index[51][1001], val[51], n;
bool chk[51];
int abs(int a){ return a>0?a:-a; }
void fill_table_with_minus_one(int n,int sum){
    for(int i=1;i<=n;i++)
        for(int s=0;s<=sum;s++)
            previous_index[i][s] = -1;
}
void fill_table(int ind, int sum_till_ind_minus_one, int last_summed){
    if(ind > n) return;
    if(previous_index[ind][sum_till_ind_minus_one] != -1) return;
    fill_table(ind+1, sum_till_ind_minus_one, last_summed);
    previous_index[ind][sum_till_ind_minus_one + val[ind]] = last_summed;
    fill_table(ind+1, sum_till_ind_minus_one + val[ind], ind);
}
int main(){
    int sum=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&val[i]);
        sum += val[i];
    }
    fill_table_with_minus_one(n,sum);
    fill_table(1,0,0);
    int saveind=0,saveval=0;
    for(int local_sum = 0;local_sum <= sum/2; local_sum++)
        for(int i=1;i<=n;i++)
            if(previous_index[i][local_sum] != -1){
                saveind = i;
                saveval = local_sum;
            }
    while(saveind > 0){
        printf("%d %d\n",saveind, saveval);
        chk[saveind] = 1;
        int temp = val[saveind];
        saveind = previous_index[saveind][saveval];
        saveval -= temp;
    }
    for(int i=1;i<=n;i++)
        if(chk[i])
            printf("%d ",val[i]);
    printf("\n");
    for(int i=1;i<=n;i++)
        if(!chk[i])
            printf("%d ",val[i]);
}

First we scanned the input, saved to n and val[], then filled the DP table according to the following rules:

previous_index[i][sum] shall have a value of -1 if and only if the value sum cannot be reached with by adding/not adding one of each first i numbers;
If val[i] was added to the available values until the i-1 th, then the previous_index[i][sum] shall store the index of the number that was previously added, that is, before val[i]. If none was, then 0 will be stored.

And then now we have the values, it isn't really that hard to track back and print the values.

This is Partition problem. And is NP-Complete. There cannot be a deterministic P-time algorithm to solve this efficiently for sufficiently large $n$ unless $P=NP$.


Any information on this sum I was wondering if we know what this sum converges to? How can we show it? It's just an odd looking sum I came across in some work.

It does converge.

$$\sum_{m=1}^{\infty} \sum_{n=1}^{\infty} \frac{1}{(2n)^{2^m} -1}$$

And/or it's alternating series.

Note that by Cauchy condensation test

$$ 0 \ \leq\ \sum_{n=1}^{\infty} f(n)\ \leq\ \sum_{n=0}^{\infty} 2^{n}f(2^{n})\ \leq\ 2\sum_{n=1}^{\infty} f(n)$$

the series

$$\sum_{m=1}^{\infty} \sum_{n=1}^{\infty} \frac{1}{(2n)^{2^m} -1}$$

converges if and only if the following converges

$$\sum_{m=1}^{\infty} \sum_{n=1}^{\infty} \frac{1}{m}\frac{1}{(2n)^{m} -1}$$

which diverges since for m=1

$$ \sum_{n=1}^{\infty} \frac{1}{2n -1}$$

diverges.

Ok, lets assume it converges, I wrote a small code which takes few seconds to evaluate n=10000, and m=10000.
the partial sum is

 0.5757556130311484

I will post the code here:

format long e
x=0;

for m=1:10000
    for n=1:10000
        x=x+1/((2*n)^(2^m)-1);
    end
end
x


How to (efficiently) compute the sum of the digits of evey number lying between two given numbers? Given two integers A and B , how to efficiently compute the sum of all the digits of every number int the set  $\{N | A \le N \le B \} $.

For example: A = 100  and B = 777, then the required answer is 8655.

I am interested in deriving an formula/efficient algorithm for the same.

You should find the formula $f(n)$ for the sum of digits for numbers from 1 to n, then do $f(B)-f(A)$.  It is not very clean.  The sum of digits of all k digit numbers, that is from $10^{(k-1)} \text { to } 10^k-1$, is $45*(10^k-1)/9$.  Stopping part way is harder, but you can do it by recursion.  If you want the sum of digits of numbers up to $7655$, say, you can do sum of digits up to $999$, plus $1000*6*5/2$ (for the thousands digits up through 6) + $6*$sum of digits up to $999$ (for the last three digits for $1000$ through $6999$) + $7*656$ (for the thousands in the $7$s) + sum of digits up to $655.$  The last has one less digit, so you just call your subroutine with that.

Just summing them altogether first would produce a number that has the same digit-sum as stringing them altogether.

For example: 101-103

101, 102, 103 -> 1+0+1+1+0+2+1+0+3 -> 9

101+102+103 = 306 = 3+0+6 = 9

Use the Gauss method to add the numbers quickly...
That is, if I have the numbers in a set like 1-10
1+2+3+4+5+6+7+8+9+10 = 1+10+2+9+3+8+4+7+5+6 = (1+10)+(2+9)+(3+8)+(4+7)+(5+6) = (11)+(11)+(11)+(11)+(11) = 11*(10/2) <--- 10 is the upper-limit of the given range.

Then add the digits together by dividing by 10 and adding the remainder to one storing variable. (ex. 52 = 5+2 = 7.... 52 --> 52/10 --> 5r2... "2"+? .... 5/10 = 0r5 --> "2"+"5" = 7.)


Induction proof. Explain in detail why it’s incorrect Can somebody give a clear explanation why this is incorrect? thank you

  Theorem 1:
  All positive integers are equal.

Proof:
We show that any two positive integers are equal, from which the result follows. We do this by induction
on the maximum of the two numbers. Let $P(n)$ be the statement “if $r$ and $s$ are positive integers and $\max \{ r, s \} =
n$ then $r = s$.”

Clearly $P(1)$ is true. Suppose that $P(n)$ is true and let $r$ and $s$ be positive integers whose maximum is $n + 1$. Then
$\max \{ r − 1, s − 1 \} = n$. By the inductive hypothesis, $r − 1 = s − 1$ and hence $r = s$. Thus $P(n + 1)$ is true.

The result is now proved by mathematical induction.

There's nothing wrong with the other answers already posted, but I'd like to step back and address a slightly broader question: if presented with this argument, how would you find the flaw?

Well, if the proof worked then it would establish P(1) and then P(2) and then P(3) and so on. If it doesn't, then one of these steps must fail. Here are two ways we can identify where it goes wrong. All of them are useful heuristics when tracking down bugs in proofs.

1. If it fails, it probably fails early. Let's look at the steps in order. P(1) is certainly correct, so what about the transition from P(1) to P(2) -- the first application of the inductive step? Let's plug in some specific numbers and see what happens: r=1,s=2 perhaps. Then r-1,s-1 are 0,1 ... and, aha, this doesn't fit our inductive hypothesis.

2. Compare doubful things against what we know is actually true. So, P(n) says that all positive integers up to n are equal. That's true for n=1 but false for n=2. So, again, this tells us to focus on n=2 and see what happens.

So, to recap, here are some general principles.

When an inductive proof fails, it usually fails "early". So try looking at small simple cases.
In particular, the very first actual inductive step is especially likely to be wrong. More generally, look at "edge cases".
If you can't immediately see the flaw in the reasoning, try out a concrete example.
Compare what the proof says should be true with what you know by other means is true. Look for the first point at which the proof jumps from something you believe is true to something you believe is false.

A very simple definition of mathematical induction can be found here

which states that it has two basic steps,defining the base case and then proving the induction step.

Base case: is to prove the given statement for the first element of the given set (set of positive integers in this case)
"if r and s are positive integers and max{r,s}=n then r=s"
for the base case, let r=s= 1
then max(1,1)=1 which is true

Now consider the induction step.
Induction step: is to prove that, if the statement is assumed to be true for any one natural number, then it must be true for the next natural number as well.
So if P(n) (which means max(r,s) = n ) is true then P(n+1) (which is max(r+1,s+1)=n+1 ) should also be true


In how many ways can the letters of the word $PATNA$ be arranged? In how many ways can the letters of the word $PATNA$ be arranged ?

$a)\ 60 \\
 b)\  120 \\
 c)\ 119 \\
 \color{green}{d)\ 59 }\\
$

I thought it would be $\dfrac{5!}{2}=60$ but in book answer is given $59$ which puzzled me

I look for a short and simple way.

I have studied maths upto $12$th grade.

They mean other ways of arranging the letters. So the result is what you found minus the original word: 59.

The question should be framed as
"In how many ways can it be rearranged". Then $59$ would be right.
Otherwise, $60$ is the answer.


Existence of an injection between $\mathbb{Z}$ and $[0,1]$ Is the statement that there is an injection between $\mathbb{Z}$ and $[0,1]$ true or false
$\mathbb{Z}\xrightarrow{(1-1)} [0,1]$
i've build it on the definition of cardinality that is if $\lvert A \lvert \leq \lvert B \lvert$
then there exists an injection $f:A\longrightarrow B$ and one knows that
$\lvert \mathbb{Z} \lvert \leq \lvert [0,1]\lvert$
thus there exists an injection

Consider the function $f : \Bbb Z \longrightarrow [0,1]$ defined by $$
f(n) = \left\{
        \begin{array}{ll}
            \dfrac {1} {1-2n} & \quad n \leq 0 \\
            \dfrac {1} {2n} & \quad n > 0
        \end{array}
    \right.
$$

It is true, take for example a function $f:\mathbb{Z} \to [0,1]$ $$f(n)=\cases{{1\over 2|n|+1};\;\;\; n\leq0\\{1\over 2n};\;\;\; n>0}$$


What's wrong in this proof of $10$ is a solitary number? Friendly numbers are two or more natural numbers with a common abundancy, the ratio between the sum of divisors of a number and the number itself. Two numbers with the same abundancy form a friendly pair.
A number that is not part of any friendly pair is called solitary. I have found a very elementary proof of 10 being a solitary number which is an open problem. So I would like to find a mistake in my proof. Let $\sigma(n)$ be the sum of divisor function.

For $10$ to have a friendly pair we have to find another solution to $$\sigma(5x)=9x$$
 $$6 \ \sigma(x) = 9x \ \text{(Assuming (5,x)=1)}$$
 $$2\ \sigma(x)=3x$$
Now Let $x=2^kp$ where $p \in \mathbb{N}$ ,$(p,z)=1$
$$2(2^{k+1}-1) \sigma(p)=3 \cdot 2^kp$$
$$\frac{\sigma(p)}{p}=\frac{3 \cdot 2^{k-1}}{2^{k+1}-1}$$
Now as any number has atleast two prime factors one and itself hence ,
$$\frac{\sigma(p)}{p}>1$$
$$ \implies3 \cdot 2^{k-1}>2^{k+1}-1$$
Which can be showed impossible for $k>0$.

Now  let us assume that $x$ is in the form $x=5^t2^kq$
$$\frac{2(5^{t+1}-1)(2^{k+1}-1) \sigma(q)}{4}=3 \cdot 5^t \cdot 2^k \cdot q$$
$$(5^{t+1}-1)(2^{k+1}-1) \sigma(q)=3 \cdot 5^t \cdot 2^{k+1} \cdot q$$
$$\frac{\sigma(q)}{q}=\frac{3 \cdot 5^t \cdot 2^{k+1} }{(5^{t+1}-1)(2^{k+1}-1)}$$
Which by proceeding as above ie. by the fact $\frac{\sigma(q)}{q}>1$ can be shown not possible.

Thus no friendly pair of $10$ is possible. Thus $10$ is solitary.

Here is the main problem. First of all, since:

$$\frac{\sigma(10)}{10} = \frac{\sigma(2)\sigma(5)}{10} = \frac{(1+2)(1+5)}{10} = \frac{18}{10} = \frac95$$

a hypothetical friend $x\in\mathbb{N}$ of $10$ must satisfy:

$$\frac{\sigma(x)}{x}=\frac95$$

You search for $2\sigma(x)=3x$ which is wrong. In your very first equation the "5" is inside the $\sigma$ function when it should be outside. Therefore "5" becomes "6" in your proof attempt which is wrong. The irrelevant equation $\frac{\sigma(x)}{x}=\frac32$ is solved by $x=2$ only, by the way. The fact that $2$ is solitary is not new.

according to my proof 0 is not solitary
a solitary number is a number which does not have any friends.
Solitary Number include all primes, power of prime(i can give you the proof) and number which have g.c.d.(n,Sigma(n))=1

So here n = 10
And Sigma(n=10)=18[can be found easily
so g.c.d.(10,Sigma(10))=2
therefore 10 is not solitary number

in case of any defect you can mail me the defect in the proof
thanks


Why $\int\limits_{\sin(-5π/12)}^{\sin(5π/12)}\frac{dx}{1-x^2}=\ln\frac{1+\sin\frac{5π}{12}}{1-\sin\frac{5π}{12}}$? Why does an integral $$\int \frac{dx}{1-x^2}$$ with the limitless (undefined) interval equal to $$\frac 12\ln\frac{1+x}{1-x},$$ yet an integral $$\int\limits_{\sin(-5π/12)}^{\sin(5π/12)}\frac{dx}{1-x^2}$$ with an interval from $\sin\frac{-5π}{12}$ to $\sin\frac{5π}{12}$ has $$\ln\frac{1+\sin\frac{5π}{12}}{1-\sin\frac{5π}{12}}$$ without one half attached to ln?

Since there are already good answers explaining the computation of the definite integral, let me point out what I consider a misunderstanding of the indefinite integral, thus answering the OP question why.

The primitive or indefinite integral is not a function, but a representation of a whole set of functions, all of them when differentiated produce the original function under the integral sign. All these functions differ by a constant, and that is why the computation of the indefinite integral is usually expressed by choosing any of these primitives plus a constant $C$, i.e.:
$$\int \frac{dx}{1-x^2}=\frac 12\ln\frac{1+x}{1-x}+C$$
but you could also write:
$$\int \frac{dx}{1-x^2}=\frac 12\ln \left(2\frac{1+x}{1-x}\right)+C$$
since these two primitives differ by a constant.

Now you can compute a definite integral by Barrow's rule:
$$\int_a^bf(x) dx=F(b)-F(a)$$
where $F'(x)=f(x)$, i.e. $F$ is any primitive or, if you want, the primitive with any value of the constant $C$.

Since you are free to choose the value of $C$, the "aspect" of the primitive can be deceiving with respect to the value of the definite integral, unless you carry out all the detailed computation.


How can I find the saddle point of $Z = x^2 + 3y^2 + 3xy – 6x + 3y – 6$ $$Z = x^2 + 3y^2 + 3xy  –  6x + 3y – 6$$

how can I find the maxima, minima and the saddle points of this equation?

I tried this by finding $fx, fy,fxx,fyy,fxy$
$$fx=2x+3y-6$$$$fy=6y+3x+3$$$$fxx=2$$$$fyy=6$$$$fxy=3$$

$$fx=fy=0$$
find $(x,y)$
$$x=15$$$$y=-8$$
But when I calculate $Z$ I get $Z=-63$ but in my textbook it says $Z=-51$ what am I doing wrong?

I also did the calculations, there's nothing wrong with your calculations, maybe there's a mistake in your textbook.

all your calculations are correct$$x=15$$$$y=-8$$
$$Z(15,-8)=-63$$

Your calculations are correct. I have use MatDeck to do the math and the result is the same. You can find the link for calculation in MatDeck bellow

Saddle point calculation in MatDeck


Trying to simplify $A'B'C'D + A'B'CD + A'BC'D + AB'CD + ABCD$ My solution so far:

$A'(B'C'D + B'CD + BC'D) + A(B'CD + BCD)$

$= A'(C'D(B' + B) + B'CD) + A(CD(B'+B))$

$= A'(C'D(1) + B'CD) + A(CD(1))$

$= A'C'D + A'B'CD + ACD$

$= D(A'C' + AC) + A'B'CD$

$= D(A\text{ xnor }C) + A'B'CD$

$= D[(A\text{ xnor }C) + A'B'C]\text{ <<< Can't seem to get any further than this.}$

Did I perhaps screw up somewhere? Or not do it as well as I could have? Maybe missed using a rule?

Thanks!

K

I'd start by plotting the Karnaugh map.

$A′B′C′D+A′B′CD+A′BC′D+AB′CD+ABCD$ is an sum of five minterms, thus the Karnaugh map will show five ones (I've left out zeroes for greater visual contrast):

$$
\begin{matrix}
     & A'B' & A'B & AB & AB' \\
C'D' &                       \\
C'D  &  1   &  1             \\
CD   &  1   &     &  1 &  1  \\
CD'  &
\end{matrix}
$$

This can be covered as a sum of three products, of which two are essential, in two ways.

$$
F = A'C'D + ACD + B'CD = ((A\ xnor\ C) + B'C)D \\
F = A'C'D + ACD + A'B'D = ((A\ xnor\ C) + A'B')D
$$

Which are both one term shorter than your original: $((A\ xnor\ C) + A'B'C)D$. Note how you used disjoint terms as a covering for the function. This often happens when you simplify as expression without looking at the Karnaugh map.

Starting from the same Karnaugh map, you can also choose to start with a product of sums. As a product of three sums, all essential:

$$
F = D(A'+C)(A+B'+C')
$$

Or if you prefer, an inverted sum of products:

$$ F = not(D'+AC'+A'BC) $$

It simplifies to $[(A+B)'C+A' + B'D +BD]'$.


How many polynomial functions exist such that $f(x^2) = (f(x))^2 = f(f(x))$ How many polynomial functions $f$ of degree $\geq1$ satisfy
$f(x^2) = (f(x))^2 = f(f(x))$ for all real $x$?

Hint: if $f(x)$ has degree $n \geq 1$ then $f(f(x))$ has degree $n^2$, but $f(x^2)$ and
$f(x)^2$ have degree $2n$. For what $n \in \mathbb{N}$ is $2n=n^2$?

Once you find out just solve the equations for the coefficients.

May $x_1$ be a complex root of the polynomial $f$.

By the property $f(x^2) = (f(x))^2$, then, $f(x_1^2) = f(x_1)^2 = 0$.

Side note: By the last relation, we get $f(0) = 0$, but it's not needed.

Therefore, $\forall k \in \mathbb{R} ^+ , x_1^k$ is a root of $f$. So $f$ has infinitely many roots. So $f$ is equal to zero on its whole interval, because it is a polynomial with infinitely many roots.

It satisfies the last relation as well.

Edit: Side note: If you need a proof of the property for infinitely many roots polynomial, there it is: Polynomial with infinite roots

Edit:
my solution doesn't apply whenever $0$ is the only root. I can apply it for a polynomial whose only root is 0: $x^m$. Using the first equality, we get $x^{2m} = x^{2m}$ which is useless. The second equation gives $x^{2m} = x^{m^2}$ which leads to $m=0$ and $m=2$.


Proof that there are only finitely many $1$-cells that have a $0$-cell as a boundary point in a CW complex Below is a lemma from John Lee's Introduction to Smooth Manifolds.

Suppose $M$ is a $1$-manifold endowed with a regular CW decomposition. We want to show that every $0$-cell of $M$ is a boundary point of exactly two $1$-cells.

I cannot understand a line from the proof, namely:

It can be shown that the boundary of every $1$-cell of $M$ consists of exactly two $0$-cells. Now, suppose $v$ is a $0-$cell of $M$. Then why are there only finitely many $1$-cells that have $v$ as a boundary point?

Okay so after reviewing the chapter I figured it out. We need to use that the CW decomposition is locally finite. Proposition 5.16 of the text states that a CW complex is locally compact if and only if it is locally finite. A manifold is locally compact, so the CW complex here is locally finite. This means that $\{\bar{e}:e \in \mathscr{E}\}$, the collection of the closures of the cells is locally finite. Hence, $v$ has a neighborhood that intersects at most finitely many closures of cells, hence so does $v$.

If a 0-cell has no 1-cells attached, this point has no open set around it homeomorphic to $\mathbb{R}$ since it every small enough open set is a point. If a 0-cell has a single 1-cell attached, then every small enough open neighborhood looks like $[0,\infty)$ (since otherwise it would be attached on both ends by a 1-cell but this is not regular) which you can show is not homeomorphic to $\mathbb{R}$. If you have two or more 1-cells attached, you are a wedge of more than 2 copies of $[0,\infty)$ which can be shown to not be homeomorphic to $\mathbb{R}$.


Evaluating $\int\frac{x\sin^{-1}(x)}{\sqrt{1+x^{2}}}\mathrm{d}x$ How can we evaluate:

$$\int\frac{x\sin^{-1}(x)}{\sqrt{1+x^{2}}}\mathrm{d}x$$

I tried to use integration by parts, but the positive sign of the $x^2$ in the square root doesn't cancel with the integral of $\sin^{-1}(x)$, so how can I proceed ?

Yes, integration by parts is the route to go...

Try putting $u = \sin^{-1} x \implies du = \dfrac {dx}{\sqrt{1-x^2}}$

and put $dv = \dfrac x{\sqrt{1 + x^2}}\implies v = \sqrt{1 + x^2}$

$$I = uv - \int u'v$$

As the existing integral is not elementary

I assume the Question to be $$I=\int\frac{x\sin^{-1}x}{\sqrt{1-x^2}}dx$$

Setting  $\sin^{-1}x=\phi\implies \sin\phi=x, \cos\phi=+\sqrt{1-x^2}$ as the principal value of $\sin^{-1}x$ lies in $\left[-\frac\pi2,\frac\pi2\right]$

$$I=\int\phi\sin\phi d\phi $$

Now integrate by parts $$I=\int\phi\sin\phi d\phi=\phi\int\sin\phi d\phi-\int\left(\frac{d\phi}{d\phi}\cdot\int\sin\phi d\phi\right)d\phi $$

$$=-\phi\cdot\cos\phi+\int \cos\phi d\phi=\cdots$$


Taking Seats on a Plane This is a neat little problem that I was discussing today with my lab group out at lunch. Not particularly difficult but interesting implications nonetheless

Imagine there are a 100 people in line to board a plane that seats 100. The first person in line realizes he lost his boarding pass so when he boards he decides to take a random seat instead. Every person that boards the plane after him will either take their "proper" seat, or if that seat is taken, a random seat instead.

Question: What is the probability that the last person that boards will end up in his/her proper seat.

Moreover, and this is the part I'm still pondering about. Can you think of a physical system that would follow this combinatorial statistics? Maybe a spin wave function in a crystal etc...

Here is a rephrasing which simplifies the intuition of this nice puzzle.

Suppose whenever someone finds their seat taken, they politely evict the squatter and take their seat.  In this case, the first passenger keeps getting evicted (and choosing a new random seat) until, by the time everyone else has boarded, he has been forced by a process of elimination into his correct seat.

This process is the same as the original process except for the identities of the people in the seats, so the probability of the last boarder finding their seat occupied is the same.

When the last boarder boards, the first boarder is either in his own seat or in the last boarder's seat, which have both looked exactly the same (i.e. empty) to the first boarder up to now, so there is no way the poor first boarder could be more likely to choose one than the other.

I have come up with my own solution using a revolutionary war analogy, which is quite fun and intuitive I think.

We classify passengers as two groups: (i) "rebels": the first man and those who do not end up sitting at their own seats; (ii) "rulies": those who end up sitting at their own seat. We will refer to the First Man's seat as "the throne" due to its significance. We will refer to each passenger as "the n-th man" by their order of entrance. We will refer to appointment of the 100-th man (the one true saviour) as a rebel as ultimate victory of the rebellion. Anyone other than the saviour seating on the throne will doom the revolution.

Each rebel (assuming he is the n-th man, including the first man) has 3 choices:

(i) Doom the rebellion: with probability $\frac{1}{101-n}$, sit at the throne and thus effectively ending the rebellion and ensure no more rebels thereafter; this fails the rebellion

(ii) Win the rebellion: with probability $\frac{1}{101-n}$ appoint the 100-th man, the saviour, as rebel by sitting at 100-th man's seat, thus winning the rebellion;

(iii) Leave it to future generations: with remaining probability, appoint a rebel other than the saviour and thus does not doom or win the rebellion on his watch.

We can see that we have equal chance to win the rebellion or lose it under each rebel's command. So the result is with probability $1/2$ we lose the rebellion, which is the event the last passenger sits at his own seat.


Do I use the rule of multiplication here? Why not here? A die is rolled.  What is the probability that the number is even and
  less than 4?

  Event $A$:  Numbers on a die that are even:  2, 4, 6
  Event $B$:  Numbers on a die that are less than 4:  1, 2, 3
  There is only one number (2) that is in both events A and B.
  Total outcomes $S$:  Numbers on a die: 1, 2, 3, 4, 5, 6  (total = 6)

Ok, so obviously the one possible outcome in this example is $1/6$. But if I use the rule of multiplication which states that if the sample space is the same, which I think it is, then $P(a)P(b)$ should give me the right answer, which it doesn't: $1/4$.

(My logic here is that less than 4 is 50% chance and the even numbers are 50% chance).

So the big question is, why doesn't the multiplication rule work here?

There is a way of recovering a  version of the multiplication rule.

Let $A$ and $B$ be as in your post. We cannot write $\Pr(A\cap B)=\Pr(A)\Pr(B)$, since $A$ and $B$ are not independent.

However, we have
$$\Pr(A\cap B)=\Pr(A)\Pr(B|A),$$
 where $\Pr(B|A)$ means the (conditional) probability $B$ happens given that $A$ happens.

Given that $A$ happened, meaning the number is even, the probability it is between $1$ and $3$ is $1/3$, since only one-third of evens are between $1$ and $3$. So $\Pr(A\cap B)=(1/2)(1/3)$.

To apply multiplication rule, the intersection of values of the individual sets should be null matrix.
i.e A \cap B = null matrix


Convergence of sequence with subsequences Let ${a_n}$  be a bounded sequence such that any of its convergent proper subsequences converge to the same limit $l$. Prove that ${a_n}$ converges to $l$.

Any hints please?

Hint: Suppose $a_n$ does not converge to $l$. Then there is $\varepsilon \gt 0$ and an increasing sequence $n_k \in \mathbb{N}$ such that $|a_{n_k} - l| \gt \varepsilon$ for any $k \in \mathbb{N}$. By Bolzano-Weierstrass $a_{n_k}$ has a convergent subsequence. Show that the limit of this subsequence cannot be $l$ and use this to conclude.

It would be a good start assuming that the sequence does not converge to $l$.
Then try to find a proper subsequence that does not converge to $l$.


Find the upper bounds for the real roots of the equation $2x^3-5x^2-7x+4 = 0$ Problem: Find the upper bounds for the real roots of the equation $2x^3-5x^2-7x+4 = 0$

Reading the definition in the book, If upon dividing f(x) by (x-r), r is an upper bound if it is greater than or equal to 0 and the coefficients of the quotients of the quotient as well as the remainder are positive.

Trial: The question gave an equation but no given (x-r) or r. What I did is get the roots of the cubic equation.

Root 1 = 3.36374665

Root 2 = 0.4519194497

Root 3 = -1.3256661

It says that for r to be upper bound, first it should be greater than zero, so I ignored the root -1.32

@root 1; f(r) = $2(3.36374665)^3-5(3.36374665)^2-7(3.36374665)+4 = 1.0014 x 10^-9$

And with that I know what I'm doing is wrong so I stopped. So, how to answer these kinds of problem? By the way, the choices are : 4,2,3 and 5.

Any help would be appreciated.

4 is a upper bound.
By rational root theorem, the possible zeros are $\frac{4}{1},-\frac{4}{1},\frac{4}{2}, -\frac{4}{2}$ or $4, -4, 2, -2$

By the rules of bounds, you divide the polynomial by $4$, $(x-4)$, by using synthetic division, and the numbers of the last row are all positive or zero. Therefore, $4$ is a upper bound.

Check you definition of an upper bound.  An upper bound of a set of reals is any number greater than or equal to all members of the set.  When the set is finite the set of upper bounds is all values from the greatest to $\infty$.


Show that the series $\sum_{n=1}^{\infty} n^{q}x^{n}$ is absolutely convergent, and that $\lim_{n\to\infty} n^qx^n=0$. Let x be a real number with $|x|<1$, and q be a real number. Show that the series $\sum_{n=1}^{\infty} n^{q}x^{n}$ is absolutely convergent, and that $\lim_{n\to\infty} n^qx^n=0$.

My attempt:

Let $c = n^q$

Then since, $$\sum_{i=m}^{n} (ca_i) = c(\sum_{i=m}^{n} a_i),$$ we can write

$$c\sum_{n=1}^{\infty} x^{n}$$
and by a Lemma concerning geometric series, if $|x|<1$ then $$\sum_{n=1}^{\infty} x^{n}$$ is  absolutely convergent. If it is absolutely convergent it is also conditionally convergent. Now I can use the zero test and we see that the limit of $x^n$ as n->infinity = 0.

Our series has $n$-th term $a_n=n^qx^n$ and thus$$\frac{a_{n+1}}{a_n}=x\cdot \left(\frac{n+1}{n}\right)^q=x\cdot \left( 1+\frac1n \right)^q$$

It follows that $\lim\limits_{n\to\infty} \left \lvert \frac{a_{n+1}}{a_n}\right \rvert=\lvert x \rvert <1$, so by the ratio test the series $\sum\limits_{n\geq 1} a_n$ converges absolutely.

EDIT: Granted, if $\sum\limits_{n\geq 1} \lvert a_n \rvert$ converges, then $\lvert a_n\rvert \to 0$, so $\lim\limits_{n \to \infty} n^qx^n=0$ whenever $\lvert x \rvert <1$.

By ration test we examine

$$
\lim_{n\rightarrow +\infty} \frac{a_n}{a_{n+1}}=\lim_{n\rightarrow +\infty} \frac{n^q}{(n+1)^q}=\lim_{n\rightarrow +\infty} \left(\frac{n}{n+1}\right)^q=1
$$

Here we actually applied Cauchy-Haramard theorem

So we know that this power series absolutely converges on (-1,1) (on -1,1 the series obviously diverges)


Prove that $f_{n}:[1,+\infty[ \rightarrow \mathbb{R} : x \rightarrow \frac{x^n}{1+x^{n}}e^{-x}$ is increasing By definition, I want to prove that $f_{n+1}(x)-f_{n}(x)\ge0$ for $x \in [1,+\infty[$

So, we obtain : $e^{-x}(\frac{x^{n+1}-x^{n}}{(1+x^{n+1})(1+x^{n})})$

But for $x \in [1,+\infty[$ we have : $e^{-x}>0$, and also $(1+x^{n+1})(1+x^{n})>0$ for all $n \in \mathbb{N}.$

and we know that : the sequence $(x^n)_{n \in \mathbb{N}}$ is increasing which means that :

$x^{n+1}-x^{n}\ge 0$ so $f_n$ is increasing.

Is this method correct ?

Thanks in advance.

No, you are on the wrong trace. To prove that $f_n(x)$ is increasing, you should pick $x_1<x_2$ and show that $f(x_1)\le f(x_2)$.

Or you can verify that $f_n'(x)>0$.


Showing that the fifteenth cyclotomic polynomial is ireducible over $\mathbb{Q}$ I need to show that $\Phi_{15}(x) = x^8 - x^7 + x^5 - x^4 + x^3 -x + 1 = \prod_{i \in \mathbb{Z}_{15}^{\times}}(x - \omega^i)$ is irreducible over $\mathbb{Q}$, where $\omega = e^{\frac{2\pi i}{15}}$.

It is true in general that every cyclotomic polynomial is irreducible over $\mathbb{Q}$, but I am not allowed to use this result, so am looking for a way of proving this special case.

This is an exam question from a previous year, and the amount of time allowed suggests that there is a fairly quick way of doing it, which rules out any kind of major algebraic bash.

Any help would be very much appreciated.

Let $\omega$ be a primitive $15$-th root of unity and let $G$ be the Galois group. For $\sigma \in G$, we must have $\sigma(\omega) = \omega^a$ for some $a \in (\mathbb{Z}/15 \mathbb{Z})^{\times}$. If $\sigma(\omega) = \omega^a$ and $\tau(\omega) = \omega^b$ then $\sigma(\tau(\omega)) = \sigma(\omega^b) = \sigma(\omega)^b = \omega^{ab}$, so we get an embedding of $G$ into $(\mathbb{Z}/15 \mathbb{Z})^{\times}$. The question is what subgroup it is. I see two easy things to show:

$G$ contains the element $-1 \in (\mathbb{Z}/15 \mathbb{Z})^{\times}$, because this is the action of complex conjugation.
The Chinese remainder theorem shows that $(\mathbb{Z}/15 \mathbb{Z})^{\times} \cong (\mathbb{Z}/3 \mathbb{Z})^{\times} \times (\mathbb{Z}/5 \mathbb{Z})^{\times}$. The projection of $G$ onto the two factors $(\mathbb{Z}/3 \mathbb{Z})^{\times}$ and $(\mathbb{Z}/5 \mathbb{Z})^{\times}$ gives the action of $G$ on the roots of the $3$-rd and $5$-th cyclotomic polynomial. Those polynomials are irreducible by the usual argument with Eisenstein's criterion, so $G$ acts transitively on those roots, so the projection of $G$ onto each factor is surjective.

Now, $(\mathbb{Z}/3 \mathbb{Z})^{\times} \times (\mathbb{Z}/5 \mathbb{Z})^{\times} \cong C_2 \times C_4$. Switching to additive notation, we are looking for a subgroup of $C_2 \times C_4$ which surjects onto $C_4$ and contains $(1,2)$. I leave it to you to show that the only such subgroup is all of $C_2 \times C_4$. More generally, this argument works for $3p$ for any prime $p$ which is $1 \bmod 4$.

I would be interested to see a short proof that the $21$-st cyclotomic polynomial does not have Galois group contained in the $6$ element subgroup of $(\mathbb{Z}/21 \mathbb{Z})^{\times}$ generated by $-4$.

First, observe that $\mathbb{Q}(\omega) = \mathbb{Q}(\omega^3)(\omega^5) = \mathbb{Q}(\omega^3)(\sqrt{-3})$ is a quadratic extension of $\mathbb{Q}(\omega^3)$.  Assuming you've proved that $\mathbb{Q}(\omega^3) = \mathbb{Q}(e^{2\pi i}/5)$ is Galois over $\mathbb{Q}$ (which follows from the fact that $\Phi_5$ is irreducible), then we know that $\operatorname{Gal}(\mathbb{Q}(\omega) / \mathbb{Q}(\omega^3))$ must be a normal subgroup of $\operatorname{Gal}(\mathbb{Q}(\omega) / \mathbb{Q})$ of order 2.

Now, for example, let us consider the automorphism $\sigma$ on $\mathbb{Q}(\omega^3)$ which maps $\omega^3 \mapsto \omega^6$.  Then this automorphism has an extension to an automorphism $\bar \sigma$ on $\mathbb{Q}(\omega)$; and by it being an extension, we can conclude that $\bar \sigma(\omega) \in \{ \omega^2, \omega^7, \omega^{12} \}$.  But since $\omega^{12}$ is a fifth root of unity, that image is impossible.  And in fact, from the order of $\operatorname{Gal}(\mathbb{Q}(\omega) / \mathbb{Q}(\omega^3))$, which is the kernel of the restriction homomorphism $\operatorname{Gal}(\mathbb{Q}(\omega) / \mathbb{Q}) \to \operatorname{Gal}(\mathbb{Q}(\omega^3) / \mathbb{Q})$, we know that both $\bar \sigma(\omega) = \omega^2$ and $\bar \sigma(\omega) = \omega^7$ must be possible.

Generalizing this argument, it should be straightforward to show that for every $k$ with $\gcd(k, 15) = 1$, there exists an automorphism $\bar\sigma \in \operatorname{Gal}(\mathbb{Q}(\omega) / \mathbb{Q})$ with $\bar\sigma(\omega) = \omega^k$.  Therefore, any nontrivial monic divisor of $\Phi_{15}$ must have all such $\omega^k$ as roots and therefore must be equal to $\Phi_{15}$.


Expected time until a given interval between Poisson process events The system I am trying to model is as follows:

A program takes time $T$ to run
The computer crashes on average every $\text{MTBF}$ time units
The program is repeatedly run until it completes without a crash
What is the expected time to completion?

I tried to calculate this by working out how many times the program is expected to fail before it completes:

If failures are modelled by a Poisson process of rate $\frac{1}{\text{MTBF}}$ then the probability of no failure occurring during the program is $e^{-\frac{T}{\text{MTBF}}}$

Therefore the number of failures until a success is modelled by a Geometric distribution and hence the expected number of failures is $e^{\frac{T}{\text{MTBF}}}-1$ (by standard result that the expectation $=\frac{1-p}{p}$)

Therefore the time to completion is given by $(e^{\frac{T}{\text{MTBF}}}-1)*t+T$ where $t$ is the expected length of each failed run. But I'm not sure how to calculate this value $t$? Is this just going to be the expected time between events in the Poisson process conditioned on this time being $<T$?

Is there a more direct way of working out this expected time until a gap $T$ between two Poisson process events?

Let $X$ denote the time of the first crash and $C$ the time to completion, thus $X$ is exponentially distributed with parameter $a=1/\textrm{MTBF}$, and $C=T$ if $X>T$ while $C=X+C'$ if $X<T$, where $C'$ is distributed as $C$ and independent of $X$. Thus, $$E(C)=E(T\mathbf 1_{X>T})+E((X+C')\mathbf 1_{X<T})=TP(X>T)+E(X\mathbf 1_{X<T})+E(C)P(X<T)$$ which implies that the expected time to completion $E(C)$ is $$E(C)=\frac{TP(X>T)+E(X\mathbf 1_{X<T})}{P(X>T)}=T+\frac{E(X\mathbf 1_{X<T})}{P(X>T)}$$
Now, $P(X>T)=e^{-aT}$ and
$$E(X\mathbf 1_{X<T})=\int_0^Tx\,ae^{-ax}dx=\left[-(x+a^{-1})e^{-ax}\right]_0^T=a^{-1}-(T+a^{-1})e^{-aT}$$ which yields
$$E(C)=\frac{e^{aT}-1}a$$
that is,
$$E(C)=\textrm{MTBF}\cdot(e^{T/\textrm{MTBF}}-1)$$

t is the expected length of each failed run

You already have the value of t, you state it in bullet #2 in your premise.

  The computer crashes on average every MTBF time units

The expected length of each failed run equals how long (on average) it runs before it crashes.  So, t = MTBF.

  Is this just going to be the expected time between events in the Poisson process conditioned on this time being less than T?

No.

In your Poisson distribution, you use λ = T/MTBF (a time rate).

The expected number of crashes during time T therefore is T/MTBF.

I was initially tempted to calculate the "inter crash rate" of 1/λ (i.e. MTBF/T) but this doesn't apply in your case.

Since you start over the process after a crash, you "re-set" the timer on the Poison process.


Explicit inverse in Shapiro's Lemma For a seminar on group cohomology I want to avoid having the students talk about group rings and resolutions for the time being and do everything with explicit inhomogenous cochains.

Now let $A$ be a $G$ module where $G$ is a (finite) group. Let $H$ be a subgroup (not necessarily normal). Let $CoInd_H^G(A)=Map(G/H,A)$ be the coinduced module with the $G$ action given by $(g.f)(x)=g.(f(g^{-1}x))$ for $x\in G/H$.

Evaluation at $H$ gives a map $p:Map(G/H,A)\rightarrow A$.

Given a cochain $f:G^n\to CoInd_H^G(A)$ we obtain a map $p\circ f|_H:H^n\to A$. This induces $H^n(G,CoInd_H^G(A))\rightarrow H^n(H,A)$.
I want to see that this is an isomorphism, but I cannot find the inverse.

D. Naidu constructs an explicit inverse map $H^n(H,A) \rightarrow H^n(G,CoInd_G^H(A))$ for the case $n=1,2$. For the construction and proof, check out lemma $2.1, 2.2$ in his paper https://arxiv.org/pdf/math/0605530.pdf.


$\epsilon-N$ Proof of sequence convergence $\{\frac{3+5n^2}{n+n^2}\mapsto 5\}$ Here's what I have so far:
$|\frac{3+5n^2}{n+n^2}-5| < |\frac{3}{n}-5|$.
I don't know what to do from here.

I can't see a good use for the inequality you produced. I would evaluate:
$$\bigg|\frac{3+5n^2-5(n+n^2)}{n+n^2}\bigg|=\bigg|\frac{3-5n}{n+n^2}\bigg|=\bigg|\frac{\frac3n-5}{1+n}\bigg|$$
As $n\to \infty, \frac 3n$ vanishes, so we see that $$\bigg|\frac{\frac3n-5}{1+n}\bigg|<\bigg|\frac{-5}{1+n}\bigg|<\bigg|\frac{-5}{n}\bigg|$$
To see this, notice that $n>0\implies \frac 3n-5<0\implies |\frac3n-5|=5-\frac 3n$, and so we have added to the numerator, thus getting a larger number in the first step. In the second step, we subtract from the denominator (i.e. divide by a smaller number), so we again get a larger number.
Then, we have $\bigg|\frac 5n\bigg|=\frac5n<\epsilon\implies n>\frac 5\epsilon$, so take $N=\lceil\frac 5\epsilon\rceil$

$\bigg|\frac{3+5n^2}{n+n^2}-5\bigg| = \bigg|\frac{3/n^2+5}{(1/n+1)}-\frac{5(1/n+1)}{{(1/n}+1)}\bigg|$ = $\bigg|\frac{3/n^{2}-5/n}{1/n+1}\bigg| = \bigg|\frac{3/n-5}{1+n}\bigg| = \bigg|{\frac{(3/n)}{(1+n)} - \frac{5}{1+n}}\bigg| \leq \bigg|{\frac{(3/n)}{(1+n)}\bigg| + \bigg|\frac{5}{1+n}}\bigg|$ by a corollary of the triangle inequality. To make both $\bigg|{\frac{(3/n)}{(1+n)}}\bigg|$ and $\bigg|{\frac{5}{1+n}}\bigg| < \frac{\epsilon}{2}$. We need ${\frac{5}{1+n}} < \frac{\epsilon}{2}$ and the necessary $n$ is found by simple algebra. For $ {\frac{(3/n)}{(1+n)}} <\frac{\epsilon}{2}$ we get $\frac{6}{\epsilon} < n^{2} + n^{3}$ so it is enough to make $\frac{6}{\epsilon} < n^{2} + n^{2}=2n^{2}$. Then we get the necessary $n$.  Since both of these are requirements to satisfy $\bigg|{\frac{(3/n)}{(1+n)}}\bigg| + \bigg|{\frac{5}{1+n}}\bigg| < \epsilon,$ choose $n > \max\{\frac{10-\epsilon}{\epsilon},\sqrt\frac{3}{\epsilon}\} $.


Why is the arithmetic mean the more typical value of a data set Aristoteles said, By the mean of a thing I denote a point equally distant from either extreme. Let's call that equidistant point y. Considering two data points y1 and y2, the equidistant point y would be found by setting the equality

y1−y = y−y2 and solving for y

y=y1+y2/2

which is the arithmetic mean of  y1 and  y2.
Departing from this formula of mean being an equidistant point from the extremes, how do we come to the conclusion that the general formula for mean represent the average value, or most typical value of the data set.

Let the "thing" whose mean we wish to find be the number of children born to a single woman.

Of course there are women who in their whole lives never gave birth to any children, so one extreme of the number of children is zero.
At the other extreme, The Guinness Book of World Records
says one woman gave birth to $69$ children in the 18th century.
Therefore, by Aristotle, the mean number of children that a woman might bear is $\frac{0+69}{2}=34.5,$ or at least we should say it was that much in the 18th century.

But other sources say the fertility rate in the 18th century was more like $6$ or $7$ mean births per woman.
In fact, even at that time $69$ births was an extremely unlikely number, much less likely than zero. To consider only the two extremes, zero and $69,$ and give them equal weight does not make much sense.

Think probabilities and expectation. Let's say you have a probability distribution over the set $A = \{x, y\}$, i.e. $\mathbb{P}(x) = \mathbb{P}(y) = \frac{1}{2}$. Let $x, y$ be real numbers. The expectation of a random variable $X$ drawn from this particular distribution over $A$ is as follows $\mathbb{E}[X] = \frac{1}{2} \cdot x + \frac{1}{2}\cdot y = \frac{x + y}{2}$. Thus, you can say that this formula is arrived by placing a uniform distribution over the set of numbers.

Note that this generalizes readily. If $A = \{a_1, \ldots, a_n\}$, and you placed a probability mass of $\frac{1}{n}$ on each of the elements of $A$, you'd get that the expected value is $\frac{a_1 + \ldots + a_n}{n}$.

I want to repeat the main message of my answer. You are placing a uniform distribution over the elements. The uniform distribution says that each of the values is equally likely. So equally likely $\equiv$ most typical value. I hope this helps.


Conjugacy class $A_4$ I want to find all conjugacy classes of $A_4$. So basically what I did, I took all elements of $A_4$ and calculated their conjugates. I had no problems with $$\{e\}, \{(123),(134),(142),(243)\}, \{(132),(143),(124),(234)\}$$but I don't understand why the rest of $A_4$ elements $$(12)(34),(13)(24),(23)(14)
$$is in one conjugacy class? Because, for example, computing the cojugates of (12)(34) gives me:
$$(12)(34)(12)(34)(12)(34)=(12)(34)$$
$$(13)(24)(12)(34)(13)(24)=(12)(34)$$
$$(14)(23)(12)(34)(14)(23)=(12)(34)$$
(here $(ab)(cd)^{-1}=(ab)(cd)$). My result is that $(12)(34)$ is the only member of the conjugacy class generated by it. Same for $(13)(24)$ and $(14)(23)$. I get three different conjugacy classes. Where am I wrong?

Hint-
For $\pi \in A_n$, its conjugacy class in $S_n$ remains as a single conjugacy class in $A_n$ or it breaks into two conjugacy classes in $A_n$ of equal size. The conjugacy breaks up if and only if the lengths in the cycle type of $\pi$ are distinct odd numbers.

NB-1.See Keith Conard's notes on Conjugacy class for details

2.Follow this link for details

The conjugacy classes of a subgroup of the symmetric group are all of the permutations with the same structure.

if we look at $S_5,$ a representative from each congjugacy class would be:

$()\\
(12)\\
(123)\\
(1234)\\
(12345)\\
(12)(34)\\
(12)(345)$

I think of linear algebra.  $P^{-1}AP$ gives a matrix similar to $A.$  It keeps the eigenvalues unchanged, and for the right choice of $P$ it diagonalizes the matrix.

With the symmetric group, we get a conjugate, but something remains unchanged by conjugation, and that is the structure of the permutation.

The symmetric group is a set of functions with group action of composition.  Whenever we have the a concatenation of functions of the form, $g{-1}hg$  We can think that $g$ translates from the domain of $g$ to the domain of $h, h$ does whatever $h$ does, and $g^{1}$ takes you back to the domain of $g.$

The congugacy class of $(12)(34)$ in $A_4$

$()(12)(34)() = (12)(34)\\
(132)(12)(34)(123) = (13)(24)\\
(123)(12)(34)(132) = (14)(23)$

and if conjugate $(12)(34)$ with any of the other 3 cycles we will get the same members.


Is the composition of the two following functions differentiable. I was trying to prove it via the general defintion of differentiablity.
My result was

$(h_{1}^{3}+h_{2}^{3})/(h_{1}^{2}+h_{2}^{2})^{(3/2)}$. However, i do not how to evaluate it beyond that point.

Moreover, is the function $f$ differentiable at $(x,y) = (0,0)$, because it seems like it isn't. I was thinking about proving this using partial derivatives, would this be the right way to go about it?

So the question has a typo: read    $\gamma_{a,b}(t)=(at,bt)$. If both $a,b$ are zero, this is a constant function, so the composition is also constant, hence differentiable.  Assume that not both $a,b$ are zero. Then for $t\ne 0$ we have
$$f(\gamma_{a,b}(t))= \frac{(at)^3+(bt)^3}{(at)^2+(bt)^2} = t \frac{a^3+b^3}{a^2+b^2} \tag{1}$$
and for $t=0$, of course, $f(\gamma_{a,b}(t))=f(0,0)=0$. Thus, (1) holds for all $t$.
This is a linear function of $t$, hence differentiable.


Using Jensen's inequality to prove another inequality? Suppose $u(\cdot)$ and $v(\cdot)$ are two differentiable, strictly increasing, and strictly concave real functions. Specifically, $v(\cdot)$ is "more concave" than $u(\cdot)$ in the sense that there exists an increasing and strictly concave function $\phi(\cdot)$ such that $v(x)=\phi(u(x))$ at all $x$. It is also equivalent to
\begin{equation}
\frac{v''(x)}{v'(x)}<\frac{u''(x)}{u'(x)} \textrm{ for any }x\,.
\end{equation}

Let $p_i\in(0,1), \sum_{i\in I}p_i=1$ be probabilities and $|I|>2$. Let $x_i$ and $y_i$ be strictly positive for all $i\in I$. Assume
\begin{equation}
\sum_{i\in I}p_ix_i<\sum_{i\in I}p_iy_i,
\end{equation}
and
\begin{equation}
\sum_{i\in I}p_iu(x_i)=\sum_{i\in I}p_iu(y_i).
\end{equation}

Conjecture:
\begin{equation}
\sum_{i\in I}p_iv(x_i)>\sum_{i\in I}p_iv(y_i).
\end{equation}
I believe this is right (after trying many numerical examples) and I think a clever use of Jensen's inequality (or its variants) will do this. But I'm stuck on doing it formally. Any hints/thoughts on providing a formal proof?

Remark: this is related to my other post: Proving an inequality of the expectation of concave functions?

Update: after some more attempts, I believe some techniques in convex analysis would be helpful. Geometrically, the middle equation represents a hyperplane in the $R^{|I|}$ space, and the desired result (very roughly) says that a concave transformation of that hyperplane should be separated from a convex transformation of it.

To be clear, I wasn't saying the conjecture should be generally true. Any thoughts on finding any sufficient conditions to make it work would be very helpful.

The reverse inequality holds. A  differentiable  function of one variable is concave on an interval $J$ if and only if the function lies below all of its tangent, i.e.,
$$f(x) \leq f(y) + f'(y)(x-y)$$
for all $x,y\in J$. In particular, if $f′(c) =0$, then $c$ is a global maximum  of $f(x)$.

Applying this for $v$, we have
$$p_i(v(x_i) - v(y_i)) \le p_i v'(y_i)(x_i-y_i)$$ for all $p_i\in(0,1)$ and all $i\in I$.

Summing up over $i$
\begin{align}
\sum_{i\in I}p_i(v(x_i) - v(y_i)) &\le \sum_{i\in I} p_i v'(y_i)(x_i-y_i) \\
&\le  \sum_{i\in I} p_i |v'(y_i)|(x_i-y_i) \qquad \text{since} \,\,  w\le |w|, \forall w \in \mathbb{R} \\
&\le \min_i |v'(y_i)|\sum_{i\in I} p_i  (x_i-y_i) <0.
\end{align}
The second inequality holds since $v$ is increasing so that  $|v'|=v'$ iff $v'>0$.


Bayes Theorem - Having trouble applying it I'm trying to apply Bayes Theorem in a assignment's problem but I'm having trouble with it.

Here is the question:

"A insurance company classify its insureds into two risk categories: 80% of them are classified as "low risk" and 20% of them are classified as "high risk". The probability that one "low risk" insured dies is 0.1 and the probability that one "high risk" insured dies is 0.5. We know that one person died this year. What is the probability that this person was classified as "high risk"?" The answer is $\frac{5}{9}$

Here is what I did:

First, we have two events:

A: Being a person classified as high risk and
B: Die

So, the problem asks P(A|B), correct?

I did like that, so: P(A|B) = $\frac{P(A\bigcap B)}{P(B)}$ = $\frac{P(B|A)P(A)}{P(B)}$ = $\frac{0.5 * 0.2}{0.1*0.8 + 0.5*0.2} = \frac{0.1}{0.18}$

P(B|A) = 0.5 (it was given in the exercise), P(A) = 0.2 (it was given too) and P(B) = 0.1 * 0.8 + 0.5 * 0.2 = 0.18

What I did wrong? The correct answer is $\frac{5}{9}$

P(H|D) = probability that person is high risk given that he is described as "high risk"

By bayes theorem

P(H|D) = (P(H)*(D|H))/P(D)
P(H) = 0.20
P(D|H) = 0.5

P(D) = P(H)P(D|H) + P(L)P(D|L) = 0.20*0.5 + 0.80*0.1

0.20*0.5/(0.20*0.5 + 0.80*0.1) = 5/9


Find a sequence with an interesting property I was reading an Elon Lages Lima's book ("Curso de Análise", IMPA) and there is an interesting question. Find a function $f$ from $\mathbb N$ onto $\mathbb N$ such that $\forall n\in \mathbb N$, the preimage set $f^{-1}(\{n\})$ is infinite. I don´t have any idea how to construct that.

Let $f(n) = k$ if $n = 2^k \cdot (2l -1)$ for natural numbers $k, l$ -- in other words, if $2^k$ is the highest power of $2$ that divides $n$. Then $f^{-1}(k) = \{2^k \cdot 1, 2^k \cdot 3, 2^k \cdot 5, 2^k \cdot 7\ldots \}$.

How about this:

{x1: x1 is prime OR 1}$\to 1$.
{x2: $x_2=2\cdot p$, for prime p>2}$\to 2$.
{x3: $x_3=3\cdot p$, for prime p>3}$\to 3$.
{x4: $x_4=4\cdot p$, for prime p>4}$\to 4$
etc.

Sorry, I was a little sloppy.


Axiom of Choice : Is it Axiom? or Trivial Fact? This question might be rude or inappropriate, but I am very beginner of studying mathematics.

Today I had learned the concept of Axiom of Choice, which states that $
\forall$ nonempty indexed set $S_i$, there $\exists$ indexed family of element $x_i$ where $\forall x_i \in Si$.

To me, at first it reached out to me as a just mere fact, but can't understand why this axiom must have been accepted as an axiom.

It's little confusing to me.

To wrap up the notion of this OP, it could be summarized as below:

Why does the concept of axiom of choice must be accepted as axiom?
What makes a statement to be valued to be designated as an axiom?

In "naive" set theory, sets are collections of things. In "axiomatic" set theory, sets are whatever satisfies the axioms -- abstract mathematical objects. Just as chess pieces need not be pieces of wood that are moved on a board sitting on a table, but may be bits of information in a computer, so also sets need not be sets of the kind you were told about in seventh grade.

Similarly in geometry, points and lines need not be points and line in physical space but can be whatever satisfies the axioms. And one finds that certain axioms are satisfied by things that don't satisfy the parallel postulate. Likewise the axioms of set theory other than the axiom of choice can be satisfied by things that don't satisfy the axiom of choice.

Is there are "set of all left socks" when infinitely many pairs of socks exist and in each pair there is no objective way to single out which one is to be the "left" sock? Some people object on philosophical grounds to the idea that there can be a set containing one element of each pair when there is no rule to say in each case which one belongs to that set.


Solving algebraic equations involving factorials - without trial and error. The question is defined as follows:

$$\frac{(x!)^3}{x}-1=3455$$

I first did the basics which was getting rid of the 1 onto the left and getting rid of the $x$, then I factorised both sides to get an expression
as seen below:

$$x!=3456^{1/3}\cdot x^{1/3}$$

$$x(x-1)!=x\cdot 3456^{1/3}\cdot x^{-2/3}$$

$$3456^{1/3}/(x-1)!=x^{2/3}$$

I then got rid of the power of x and tried using an iterative process, however it got messy because negative integers and square roots don’t go well together.

So I wanted to know: can you solve this question without trial and error? And if so, please can you exemplify your justification in mathematical notation?

We have $3456=2^7\cdot 3^3$. So, you have

$$(x!)^3=3456x=2^7\cdot 3^3\cdot x.$$

In particular, no prime $>3$ can divide $x!$, and so $x\leq 4$. You also need $2^7 \cdot 3^3 \cdot x$ to be a cube, so $2x$ should be a cube, which means $x=4$. Now you can just test it and it works! so you're done.

Let $\,a_n=\dfrac{\left(n!\right)^3}{n}\,$ then $\,a_{n+1}=n(n+1)^2a_n\,$. It's quite obvious that $\,a_n\,$ grows very fast, and the first few terms are $\,a_1=1, a_2=4, a_3 = 72, a_4=3456\,$. The latter gives the solution $\,x=4\,$.


Why the double integral does not exist? Consider $([-1,1]\times[-1,1],\mathcal{B}[-1,1]\times\mathcal{B}[-1,1],dx\,dy)$. Let $f(x,y)=\dfrac{xy}{(x^2+y^2)^2}$. Show the double integral does not exist.

My solution:
\begin{align}
\int_{[-1,1]\times[-1,1]}|f(x,y)|\,dx\,dy&\ge\int_{x^2+y^2\le1}\left|\frac{xy}{(x^2+y^2)^2}\right|\,dx\,dy\tag{1}\\
&=\int_0^{2\pi}d\theta\int_0^1\left|\frac{r\cos\theta\cdot r\sin\theta}{r^4}\right|\,r\,dr\tag{2}\\
&\ge\int_0^{\pi/2}\cos\theta\cdot\sin\theta \,d\theta\int_0^1\frac{1}{r}\,dr\tag{3}\\
&=\frac12\ln r|_0^1\tag{4}\\
&=+\infty.\tag{5}
\end{align}
Any comment is appreciated.

You immediately changed the region over which you're integrating from a square to a circle, so that won't work.

I would construe the assertion that the double integral does not exist to mean that the integrals of the positive and negative parts are both infinite.  If one of them is infinite and the other is finite, I would say the integral exists and is either $+\infty$ or $-\infty$.  By Fubini's theorem, the positive and negative parts must both be infinite if the two iterated integrals are unequal, i.e.
$$
\int_{-1}^1\left(\int_{-1}^1 f(x,y)\,dx\right)\, dy \ne \int_{-1}^1\left(\int_{-1}^1 f(x,y)\,dy\right)\, dx.
$$
The symmetry of the function and of the region over which we're integrating should cut our work in half.
$$
\int_0^1 \frac{xy}{(x^2+y^2)^2}\,dx = \int_0^{\pi/4} \frac{y^2\tan u}{(y^2\tan^2 u+y^2)^2} \, \left(y\sec^2 u \, du\right)
$$
$$
= \int_0^{\pi/4} \frac{y^2\tan u}{(y^2\tan^2 u+y^2)^2} \, \left(y\sec^2 u \, du\right) = \int_0^{\pi/4} \frac{y^2\tan u}{y^4\sec^2 u} \, \left(y \sec^2 u\,du\right)
$$
$$
= \frac{1}{y}\int_0^{\pi/4} \tan u\,du = \left.\frac{-1}{y} \log(\cos u)\right|_0^{\pi/4} = \frac{\log 2}{2y}.
$$
The integral of this function of $y$ from $0$ to $1$ is $+\infty$.  So over that square we get $+\infty$, and by symmetry, over each of the second and fourth quadrants we get $-\infty$ (and over the third we get $+\infty$).

There's no need to attempt to evaluate the integral. Simply consider the neighbourhood around $(0,0)$.

As $(x,y) \rightarrow (0,0)$ from the $x$- or $y$-axis, $f(x,y) \rightarrow 0$.
As $(x,y) \rightarrow (0,0)$ along the line $y=x$, $f(x,y) \rightarrow \infty$.

This means that a partition around $(0,0)$ will have differing upper and lower sums for any arbitrarily small partition, so $f$ is not Riemann integrable on $[-1,1]\times[-1,1]$.


Show that a group with $|G| = 33$ contains an element of order $3$ Show that a group with $|G| = 33$ contains an element of order $3$.

Using Lagrange's theorem, the possible orders are $1$,$3$,$11$, and $33$ (from the factors of $33$).

If there is a subgroup containing an element with an order of $33$, then we are done.

There is only one identity element with an order of $1$.

I am currently left with elements of orders $3$ or $11$. What is the best way to show that any element of order $11$ is a contradiction?

Suppose that all the non-identity elements in $G$ have order $11$. Choose an $x_1 \in G, x_1 \ne e$; then $H_1 = \langle x_1 \rangle$ is a subgroup of order $11$.

Now choose $x_2 \in G - \langle x_1 \rangle$; $x_2$ has order $11$, and we again form $H_2 = \langle x_2 \rangle$. Now as a consequence of Lagrange's theorem, $$H_1 \cap H_2 = \{e\}$$

(there is only one proper subgroup of either $H_1, H_2$); thus $H_1 \cup H_2$ account for $11 + 11 - 1 = 21$ elements in the group.

Rinse and repeat to get $H_3$. Argue as before to conclude that this is almost disjoint from both $H_1$ and $H_2$. This accounts for $11 - 1 = 10$ more elements, and a total of $31$.

  Question: How do we get the remaining two elements?

First of all, if there's a non-identity element that is of order one, then you have 2 distinct identities, which must be identical. Contradiction.

Now to the main point, look at an element $g \in G$  and the cycle $\langle g \rangle$ it generates. That must have order $|\langle g \rangle| =  3, 11,$ or $33$ since we can safely avoid the cycle of order $1$. If we have $3$ then we're done. If it has order $33$ then $G = \langle g \rangle$ which means $g^{11}$ has order $3$. But if $|\langle g \rangle| = 11$ then by Lagrange's Theorem $|G/ \langle g \rangle| = 3$. This is vacuously cyclic so choose one of the generating elements. It has order $3$.


Solving a Polynomial Equation by Factoring. $n^3+12n^2+48n+64$
I know the sum of two cubes formula, $(a+b)(a^2-ab+b^2)$. I'm not sure how to apply it here? Any help would be appreciated.

Hint: remember the binomial theorem $(a+b)^3 = a^3 + 3 a^2 b + 3 b^2 a + b^3.$
Now guess what $a$ and $b$ might be here.

I'm not sure what the question is; Is it to find what $a$ and $b$ are? If so, we multiply out the right side and receive a . Now, set $n=a$. Then the $b^3$ term must correspond to 64 (otherwise there would be an n). Therefore, $64 = b^3$, so $b = 4$.


Showing reducibility of a polynomial in a Discrete Valuation Ring Let $R$ be a complete discrete valuation ring with uniformiser $\pi$. I would like to show that a polynomial $f$ in $R[X]$ is reducible. Does it suffice to show that $f$ is reducible in $\frac{R}{\pi^i}[X]$ for all $i\in\mathbb{Z}_{\geq{1}}$?

Thoughts: I think it does because $R$ complete means it is the inverse limit of the  $\frac{R}{\pi^i}$'s. Moreover each factorisation of $f$ in $\frac{R}{\pi^i}[X]$ passes down to $j\leq i$. But I kind of need to pass down from $i$ equal to infinity to make this work. I feel like I've seen something like this before somewhere else as well where it was made to work but I can't remember the argument...

The example I'm interested in is when $R$ is a $\mathbb{Z}_p$ and $\pi=p$ where $p$ is a rational prime.

If $R/(\pi)$ is a finite field, then $R$ is compact for the $\pi$-adic topology, which gives an easy proof of this.

Denote $R_n[X]$ the set of polynomials of degree at most $n$ with coefficients in $R$. You can give it the product $\pi$-adic topology (two polynomials are close when all their coefficients are close) and it is also compact.

Your hypothesis says that you have factorisations $f = P_kQ_k \pmod {\pi^k}$, that is, you have an infinite sequence $(P_k,Q_k)$ such that $\lim (P_k Q_k) = f$ and $1 \le \deg P_k, \deg Q_k < \deg f$, and so $(P_k, Q_k)$ are in the compact space $R_{\deg f-1}[X]^2$.

Therefore the sequence $(P_k,Q_k)$ has one (maybe several) limit point $(P,Q)$. And since the multiplication map is continuous, you must have $PQ = f$, and $\deg P, \deg Q < \deg f$ so this is a nontrivial factorisation.

Concretely, you can just look at your sequence $(P_k,Q_k)$, first select an infinite subsequence where all the $(P_k,Q_k) \pmod \pi$ agree to some $(p_1,q_1) \in (R/\pi)[X]^2$, then select an infinite subsequence where all the $(P_k,Q_k) \pmod {\pi^2}$ agree to some $(p_2,q_2) \in (R/\pi^2) [X]^2$, and so on.

The family $(p_l,q_l)$ you get is compatible, and defines an element $(p,q)$ in the projective limit $R[X]^2$

Here it is. There is a well known result (exercise ?) saying that $\mathbf Q_{p}(w)$ , where $w$ is a primitive p-th root of 1, is equal to $\mathbf Q_{p}(\sqrt[p-1]-p)$, so the polynomial $X^{p-1} + p$ is irreducible over $\mathbf Z_{p}$ , but is reducible modulo all powers of p .

Edit. This counter-example is not correct, see Mathmo's remark.


Infinite product $\Gamma(\tfrac14)=\mathrm{A}^3e^{-\mathrm{G}/\pi}2^{1/6}\sqrt{\pi}\prod_{k\ge1}\left(1-\frac1{2k}\right)^{(-1)^k k}$ I saw the following infinite product on Wikipedia:
$$\Gamma\left(\tfrac14\right)=\mathrm{A}^3e^{-\mathrm{G}/\pi}2^{1/6}\sqrt{\pi}\prod_{k\ge1}\left(1-\frac1{2k}\right)^{(-1)^k k}\tag{1}$$
where $\mathrm A$ is the Glaisher constant, and $\mathrm G$ is Catalan's constant. I am looking for a proof of this product.

I haven't gotten very far with this product, other than noting that if
$$\zeta_*(s)=\sum_{k\ge1}\frac1{(1-\frac1{2k})^{(-1)^k ks}}$$
then
$$\zeta_*'(0)=3\ln\mathrm A+\frac16\ln2+\frac12\ln\pi-\frac{\mathrm{G}}{\pi}-\ln\Gamma\left(\tfrac14\right),\tag2$$
of course, assuming that $(1)$ is true. Perhaps $(2)$ is easier to prove. Could I have some help? Thanks.

The log of the product can be expressed in term of $\frac12\beta'(-1)-\frac12 \beta'(0)$ and  $\frac12\eta'(-1)$

where $\beta(s) = \sum_{k\ge 0} (2k+1)^{-s} (-1)^k$
, it is a L-function with a functional equation.

$G =\beta(2)$, $\log A = 1/12-\zeta'(-1)$

Finally $e^{\beta'(0)}$ can be expressed in term of $\Gamma(1/4)$ and $\Gamma(1/2)$ infinite products.

I don't think giving more details is useful.


Number invariant problem: replacing any two numbers $a$ and $b$ with $a - 1$ and $b + 3$ Numbers 1, 2, 3, ..., 2014 are written on a blackboard. Every now and then somebody picks two numbers $a$ and $b$ and replaces them by $a - 1$, $b + 3$. Is it possible that at some point all numbers on the blackboard are even? Can they all be odd?

I cannot figure out how to use the terms $a - 1$ and $b  + 3$ to form a invariant.

Hint: subtracting $1$ or adding $3$ changes a number's parity (i.e. it goes from odd to even or vice versa).  When you do this to two numbers, the number of odd numbers on the blackboard  changes by either $-2$, $0$ or $+2$.

Yes, at some point all the numbers on the board can be odd (or even).  The possibilities for each step are the following:

Erase two even numbers, then write two odd numbers.
Erase two odd numbers, then write two even numbers.
Erase an even number and an odd number, then write an odd number and an even number.

Initially there are $1007$ even numbers and $1007$ odd numbers on the board.  Repeat step (1) until all the numbers but one are odd (or even).  Then carry out step (3).  Just after you erase $a$ and $b$, and before you write $a-1$ and $b+3$, all the numbers on the board are odd (or even).


How to find a dead end in a graph? For a project about GPS systems, I'm trying to understand how can we see that there is a dead end thanks to an adjacency matrix.

I know that the adjacency matrix definition is

  Assumed that $G=(V,E)$ is a simple graph, where $\left|V\right|=n$. Assumed also that the vertices number are arbitrarily numbered $v_1,\ldots,v_n$. The adjacency matrix $A$ of $G$ of this set of vertices is A with
  $$a_{ij}=\left\{\begin{array}{rl} 1 & \mbox{if } (v_i,v_j)\in E \\        0 & \mbox{else.}\end{array}\right.$$

Here is the adjacency matrix I found corresponding on the top and on the side to the vertices $[1,2,9,10,11,12]$:
\begin{pmatrix}
   1 & 1 & 0 & 0 & 0 & 1 \\
   1& 1 & 0 & 0 & 1 & 0 \\
   0 & 0 & 1 & 1 & 1 & 0 \\
   0 & 0 & 1 & 1 & 1 & 0 \\
   0 & 1 & 1 & 1 & 1 & 1 \\
   1 & 0 & 0 & 0 & 1 & 1 \\
\end{pmatrix}

How can I know that some are dead end?

To my mind we can only know that thanks to the

The correct adjacency matrix is (observe that this is a directed graph)
$$\begin{pmatrix}0&1&0&0&0&1\\
0&0&0&0&0&0\\
0&0&0&1&1&0\\
0&0&0&0&1&0\\
0&1&1&0&0&1\\
0&0&0&0&0&0\end{pmatrix} $$
The rows corresponding to $2$ and $12$ are all zero, indicating that there is no way out.

120002
010000
011221
011121
022112
000001

matrix C 'could' or 'might' apply where:

a. each number (from 1 to 12) is independently self sufficient (i.e. 'on')
b. access to corresponding figures in 'the chain' is possible (via other numbers) - to constitute 'on'
c. a ternary introduction can be applied for direct value relationships. i.e. self sufficient independency (value: 1/on) + direction of travel (using direct access) to another chain figure = 2 (value)

there is probably a better way to express the unique 9 to 11 or 11 to 9 relationship (dual direction / exchange) but i don't have sufficient time to explore that right now.

ta.


Three circles within a larger circle Let's say that the radius of the bigger circle is R. Every circle inside touches the perimeter of the bigger circle and two other circles. How to find the radius of the smaller circles (all are identical).

To illustrate:

Any tips and ideas would be awesome.

The middle stanza of Soddy's Kiss Precise gives the formula:
Four circles to the kissing come.
The smaller are the benter.
The bend is just the inverse of
The distance from the center.
Though their intrigue left Euclid dumb
There's now no need for rule of thumb.
Since zero bend's a dead straight line
And concave bends have minus sign,
The sum of the squares of all four bends
Is half the square of their sum.
Applied here it says $$\frac 3{r^2}+\frac 1{R^2}=\frac 12 \left(\frac 3r-\frac 1R\right)^2\\\frac 3{r^2}+\frac 1{R^2}=\frac {9}{2r^2}+\frac 1{2R^2}-\frac 3{rR}$$  As all the we can get is the ratio, let $r=1$ and we have $$3+\frac 1{R^2}=\frac 92+\frac 1{2R^2}-\frac 3R\\0=3R^2-6R-1\\R=\frac 16(6\pm\sqrt{48})=\frac 13(3\pm2\sqrt{3})$$ and we want the plus sign.

Let $R$ be radius of enclosing circle and $r$ be the radii of the three internal circles. Since three internal circles kiss each other their centers form a  equilateral triangle with sides of $2r$. The centroid of this equilateral triangle is also center of enclosing Circle of radius $R$.There is a smaller space filling Circle that kisses the three inner circles. This Circle has radius $z$ where

$$R=2r+z$$

Centroid of triangle is $2/3$ length from vertex to midpoint of opposite side. For equilateral triangle this is $\sqrt 3 r/2$ This gives $z$ as function of $r$. Also, $R = 2r + z$.


relation between $\zeta(2)$ and the fourier transform of $x^2$ I have problem with see the relation between the transform of $x^2$ in $[-\pi,\pi]$ and the function $\zeta$ de Riemann in the point 2, this say that using the transform fourier of $x^2$ prove that $\zeta (2)$ is equal to $\sum_{n=1}^{\infty}\dfrac{1}{n^2}=\dfrac{\pi^2}{6}$, but here is not my trouble because I did this part but the answer me which is the relation between $\zeta(2)$ the fourier tranform of $x^2$?

After you get the Fourier series for $x^2$  in $[−\pi,\pi]$, put $x=\pi$, and there you go!


Find all values of $a$ and $b$ that make the following function differentiable for all values of $x$ Problem
Find all values of $a$ and $b$ that make the following function differentiable for all values of $x$:
$$
f(x) =
\begin{cases}
 ax + b, x > - 1\\
 bx^2 - 3, x \leq -1\\
\end{cases}
$$

I was reviewing all my works for the last 3 years, and suddenly I found this problem in one of my homework assignment. Unfortunately, this assignment lacks the solution. I was 100% sure that I used to solve it correctly, but without a textbook I couldn't recall my poor memory. I knew this is a very basic question for the first calculus course, but I totally forgot how to start, could anyone give me a "tiny" hint? Thank you.

The only value of $x$ that gives any trouble is $x=-1$. You want $f$ to be continuous there, which gives you one equation in $a$ and $b$, and you want it to have the same derivative whichever formula you use, and that gives you a second equation.

Plug in "-1" for x in both equations.
Set the 2 equations equal to each other.  Simplify as much as possible.
Go back to the original two equations and take the derivative of each one.
Plug "-1" into the derivative equations for x.
Set the 2 derivative equations equal to each other and simplify.
You now should have 2 equations (from steps 2 and 5).  Solve these together using substitution.


How to form a recurrence for a $n$-digit sequence using digits $0,1,2,3$ so that we have even no of $0$'s? If we assume $T(n)$ to be the function representing the case where we have even number of $0$'s then $T(1)=3$ precisely strings $1, 2$ and $3$.
$T(2)= 10$ ($00,11,22,33,12,21,13,31,23,32$). Likewise I got $T(3)=36$ and $T(4)=124$.

Now how to proceed from here?

Consider a representation with even number of zeros at step $n-1$. At the next step $n$, you can construct $3$ even number of zeros by following it with $1,2,3$. Similarly if you have a representation with odd number of zeros, you have to follow it with $0$ to keep it still even $0$s.

So at $i$th step let $n_{odd,i}$ be the number of odds and $n_{even,i}$ be the number of even. We have that
\begin{equation}
n_{even,i+1}=3n_{even,i}+n_{odd,i},~n_{odd,i+1}=3n_{odd,i}+n_{even,i}
\end{equation}
These are your recurrence relations. The starting point is $n_{even,1}=3$, $n_{odd,1}=1$.

You can verify by induction that $n_{even,i}=2^{i-1}(1+2^i)$ is the general formula.

Its:

$3^n$ ...... no occurence of 0

$+3^{n-2}(\binom{n-1}1)$ ...... occurence of two consecutive 0's

$+3^{n-2}(\binom{n-1}2)$ ...... occurence of two separated 0's

$+3^{n-4}(\binom{n-3}1+\binom{n-3}2\binom{3}1+\binom{n-3}3\binom{3}2+\binom{n-3}4\binom33) $ ..... occurence of 4 gathered or separated 0's

$+...$

$+3^{n-2k}(\binom{n-2k+1}1+\binom{n-2k+1}2\binom{2k-1}1+\binom{n-2k+1}3\binom{2k-1}2+\binom{n-2k+1}4\binom{2k-1}3 ....) $

$+...+1$   where all sequence is filled by 0's

for n=1:20;
h=0;for k=n:-2:1
a=3^k;v=1;s=0;
while (v<=n-k+1)&(v<=k)
s=s+nchoosek(n-k+1,v)*nchoosek(k-1,v-1);v=v+1;
end
h=a*s+h;
end
fprintf('%d ',h+mod(n+1,2));
end

Writing this piece of code through matlab gives following results:

  3 10 36 136 528 2080 8256 32896 131328 524800 2098176 8390656 33558528 134225920 536887296

which matches OEIS A007582


Trace of an inverse inequality $\text{Tr}(A^{-1}) \ge n^2 \text{Tr}(A)^{-1}$ Let $A \in \mathbb{R}^n$ be a positive definite matrix. Then, it is well known that
\begin{align}
\text{Tr}(A^{-1}) \ge n^2  \text{Tr}(A)^{-1}
\end{align}
The proof follows by using the fact that trace is and a sum of eigenvalues and using AMGM inequality.

My question: Does this inequality hold with equality iff and only if $A$ is a diagonal matrix?

I know also that this inequality holds with equality iff eigenvalues of $A$ are identical.   But not sure of this implies that $A$ is a diagonal matrix.

All positive-definite matrices are unitary diagonalizable $A=UDU^T$ and
$$
\operatorname{Tr}A=\operatorname{Tr}UDU^T=\operatorname{Tr}DU^TU=\operatorname{Tr}D.
$$
Similarly, $\operatorname{Tr}A^{-1}=\operatorname{Tr}D^{-1}$. Thus, it makes no restriction to assume that $A$ is diagonal. Of course, it is not going to be equality for a diagonal matrix in general (otherwise, it would be equality for all positive-definite matrices). It is equality iff all eigenvalues are equal, that is, iff $A=cI$, a scalar multiple of the identity matrix.

P.S. Just for completeness: the proof of the inequality follows immediately from Cauchy-Schwarz
$$
\left(\sum\sqrt{\lambda_i}\cdot\frac{1}{\sqrt{\lambda_i}}\right)^2\le \sum\lambda_i\cdot\sum\frac{1}{\lambda_i}
$$
with equality iff $(\sqrt{\lambda_1},\ldots,\sqrt{\lambda_n})$ and $(\frac{1}{\sqrt{\lambda_1}},\ldots,\frac{1}{\sqrt{\lambda_n}})$ are parallel, i.e. all $\lambda_i$ are equal.

Edit : I missed the assumption that the matrix should be symmetric.

There is equality if and only if all the eigenvalues of $A$ are equal. This does not imply that $A$ is diagonal. For instance, take $$A = \begin{pmatrix} 1&1\\0&1\end{pmatrix} \, . $$
It is not diagonal but saturates your inequality.