Tag Info

Hot answers tagged

4

Yes, you could take $c_1=\frac{1}{4}$, then you have the following: $$ \frac{1}{4}x^3 \leq \frac{x^4 +7x^3+5}{4x+1} \Rightarrow \frac{4x^4+x^3}{4} \leq x^4+7x^3+5 \Rightarrow x^4+\frac{1}{4}x^3 \leq x^4+7x^3+5 \\ \Rightarrow \frac{27}{4}x^3 \geq -5 \Rightarrow x^3 \geq -\frac{20}{27} \Rightarrow x \geq - \sqrt[3]{\frac{20}{27}}$$ Since $x>0$ and $x \geq ...


4

The argument goes: after the first four hospital days ($H$), there must be a non-hospital day ($NH$). So we find a permutation of $$\{H,H,H,H,H,\overbrace{NH,NH,\ldots,NH}^{27}\}$$ of which there are $\binom{27}{5}$ then add $NH$ after the first four $H$s. For example, the permutation might come out as: ...


3

It is trivial to to compute square/squarefree parts if we are given the prime factorization. Currently we do not know any better way, and it is widely suspected that there is none, i.e the problem may prove to be equivalent to factorization. This problem is important because one of the main tasks of computational algebraic number theory reduces to it (in ...


3

Many objects in Computer Graphics are given by polygonal meshes. For processing these, techniques from Discrete Differential Geometry apply. See also: The Discrete Differential Geometry Forum Polygon Mesh Processing, especially Differential Geometry slides (Discrete) Differential Geometry slides


3

The usual proofs I've seen use a diagonal argument. First, enumerate computably all programs, $\phi_e$, and then to define: $$f(e)=\left\{\begin{matrix}\phi_e(e)+1 &\text{if }\phi_e(e)\downarrow\\ 0&\text{otherwise} \end{matrix}\right.$$ This is computable, because we can determine whether $\phi_e(e)\downarrow$ - that is, whether computing ...


3

Let's make sure we understand splitting, before we talk about joining. To subdivide a B├ęzier curve into two, you use the deCasteljau algorithm, as illustrated in the figure below. Suppose we are given a curve defined by four control points $A$, $P$, $Q$, $G$, and a splitting parameter value $u \in [0,1]$ (which you called $t_{\text{cut}}$). To split the ...


2

If you know that the two curves you have resulted from splitting a single initial curve, then you don't need both these curves; knowing either and the cut position is enough to restore the full initial curve. Have a look at this post on Stack Overflow. It discusses how you cut a curve. What you want to do is do the reverse. To find control points $Q_i$ for ...


2

Every set of three vertices forms a triangle in $K_{12}$, so before the removal, we have $\binom{12}{3}=220$ triangles. Removing a single edge destroys $\binom{10}{1}=10$ triangles (we just choose the last vertex that would have been in the triangle). Since we delete a perfect matching, no two edges we delete lie in the same triangle in $K_{12}$. We delete ...


2

Some languages have for loops that do this. It goes through the content of the for loop, then it updates j, then it checks j. So if we go through the loop for j=n, it will update j to be n+1 and THEN check if we want to use j if it's between 2 and n. So it decides it's not and exits. But it already incremented j. That is only if you aren't getting any ...


2

The for loop is equivalent to a while loop: for j <- 2 to n <stuff> end is equivalent to j = 2 while j <= n <stuff> j <- j+1 end On the last pass through the loop, on entering the loop body, j will have the value n. It will be incremented to n+1 at the bottom of the loop body and then the comparison will fail causing ...


2

Here is a nice simple method. If $x>1$ then $$\frac{x^4 +7x^3+5}{4x+1}<\frac{x^4+7x^4+5x^4}{4x}=\frac{13}{4}x^3$$ and $$\frac{x^4 +7x^3+5}{4x+1}>\frac{x^4}{4x+x}=\frac{1}{5}x^3\ .$$ That is, we have shown that if $x>1$ then $$\frac{1}{5}x^3<f(x)<\frac{13}{4}x^3\ .$$


2

This can be done with the Akra-Bazzi method. Using Wikipedia's notation, the setup is \begin{eqnarray*} a_i \equiv 1 \\ b_i = 2^{-i} \\ h_i(x) \equiv 0 \\ g(x) = x \\ \end{eqnarray*} The next step would be to solve $$f(p) \equiv \sum_{i=1}^k 2^{-ip} = 1$$ for $p$. But in this particular case we don't need to know what $p$ is. All we need to know is that ...


2

You are on the right track. However, rather than dividing by $x^3$, I would recommend multiplying by $(4x+1)$. The reason for this is so that you will have polynomials of degree $4$ on all sides of the inequality. It is okay to try different values for $k$ once you get a more simplified inequality. For this problem, I believe setting $k$ to $1$ will work ...


2

You can represent the 26 days when the doctor does not go to the hospital by 26 sticks, which create 27 gaps. If you select 5 of these gaps, this determines the 5 days when the doctor does go in; so this shows that your answer of $\binom{27}{5}$ is correct. Another way to see this is to let $x_1, \cdots, x_6$ be the number of days in the gaps created by ...


1

It might be helpful to consider graphic matroids. Here coloops correspond to bridges. We have the statement that coloops are not in any circuit which is equivalent to coloops being in every base. This corresponds to the statement that bridges are not in any cycle which is equivalent to bridges being in every spanning tree (forest). Now circuits are ...


1

An element that belongs to no circuit is called a coloop. Equivalently, an element is a coloop if it belongs to every basis. Circuits are minimal dependent sets, while bases are maximal independent sets. Now let $c\in E$ be a coloop, so it belongs to no circuit. Let $B\subseteq E$ be a basis and assume $c\notin B$. Since $B$ is maximal independent, ...


1

Just prove that (for all $x$) $$(2x+1)\in (A\oplus B)\oplus C \Longleftrightarrow (4x+3)\in A \oplus (B\oplus C)$$ $$(4x+2)\in (A\oplus B)\oplus C \Longleftrightarrow (4x+1)\in A \oplus (B\oplus C)$$ $$(4x)\in (A\oplus B)\oplus C \Longleftrightarrow (2x)\in A \oplus (B\oplus C)$$ Hence, (see 1-reduction) $$(A\oplus B)\oplus C \equiv_1 A \oplus (B\oplus ...


1

Assuming cycle periods $\tau_2\gt\tau_1$, cycle numbers $C=C_1+C_2=10^9$ and energy consumptions per cycle $E_2\lt E_1$, we want to find the largest $C_2$ not violating the time constraint $$\begin{align} C_1\tau_1 + C_2\tau_2 &\le T = 35s\\ (C - C_2)\tau_1 + C_2\tau_2 &\le T \\ C_2(\tau_2-\tau_1) + C\tau_1 &\le T \\ C_2 & \le \frac{T - ...


1

This is a special case of a previous problem I proposed and partially solved: If $T(n) = un + \sum_i T(\lfloor r_i n \rfloor) $, show that $T(n) = \Theta(n)$ My solution there does show that $T(n) = \Theta(n)$ and conjectures that $\dfrac{T(n)}{n} \to 2^k$.


1

We can solve another closely related recurrence that admits an exact solution and makes it possible to get precise bounds. Suppose we have $T(0)=0$ and for $n\ge 1$ (this gives $T(1)=1$) $$T(n) = n + \sum_{q=1}^p T(\lfloor n/2^q \rfloor).$$ Furthermore let the base two representation of $n$ be $$n = \sum_{k=0}^{\lfloor \log_2 n \rfloor} d_k 2^k.$$ Then ...


1

If you are writing a program to find the LCM, take a look at this post: Then once you obtain your LCM create a variable that is of primitive type int to take the modulo 100000007 of it. int a = (LCM)%100000007; return a;


1

Let $M$ be a matroid on ground set $E$, we have $$\rho_M(\lambda) = \sum_{S \subseteq E}(-1)^{|S|}\lambda^{r(M) - r(S)}$$ where notice we use the corank as our exponent instead of the rank. If our matroid has no loops then $r(\varnothing) = 0$ and $\varnothing$ is the only set of rank zero and we see that $\rho_M$ is monic with degree $r(M)$. (This property ...


1

I assume that you are talking about a simple graph (no loops, no multiple edges). Then every region in the graph has degree at least $3$. However if there is a region of degree more than $3$ then your condition is not satisfied. So every region has degree $3$ exactly. Also, the graph is connected as otherwise your condition is not satisfied. Therefore ...


1

The first two problems ask for Steiner Triple Systems. It is known that a Steiner Triple System exists if and only if $n \equiv 1 \text{ or } 3 \pmod 6$. For $K_7$ we have $7 \equiv 1 \pmod 6$, so one exists. An example is drawn on the Wikipedia page (with triangles are drawn as lines): (see also Fano plane). For $K_{12}$ we have $12 \equiv 0 \pmod ...


1

Obviously you cannot do this and get the rounding correctly done. However, one possible method is the following: Calculate the roundoff error, so for $1.515 \dots$ to $2$ the roundoff error is: $$|2 - 1.515...| = 0.4949\dots$$For the second entry, it would be: $$|3-3.0303\dots|=0.0303\dots$$ After you've done this for each entry, do the following: If the ...


1

Meaning they have an explicit solution that can be written with symbols, using some array of known elementary functions and special functions, as opposed to a numerically approximate solution.


1

"Tractable" means feasible, possible, solvable, workable, able to be handled. "Symbolically" (in this context) means by use of algebra (symbols and elementary functions), as opposed to numerical methods. So, a dynamical system is "symbolically tractable" if it can be solved by algebraic methods, rather than numerical ones. As the author implies, only a ...


1

It is not that $h(S_1)=h(S_2)$ is true; in fact $h(S_1)=a$ and $h(S_2)=c$, as explained in the example at pag. 80, where $h$ is the minhash function associated to the permutation $\{abcde\}\mapsto \{beadc\}$ and $S_1$ resp. $S_2$ are given in figure 3.3. What is true is that the probability of having $h(S_1)=h(S_2)$, for generic $S_1$ and $S_2$ obtained by ...


1

I'll use Enderton's system (see Herbert Enderton, A Mathematical Introduction to Logic (2nd - 2001)). We start with : $\forall x \exists y \varphi(x,y) \rightarrow \lnot \exists x \psi(x)$; the first step is to change the second bound $x$ to $z$, in order to avoid problems with "clashing" quantifiers : $\forall x \exists y \varphi(x,y) \rightarrow ...


1

(n + m x 200) x 838.8608 will give you 20000 numbers well spread out in the RGB space. Incrementing n will increase the green by two units and the blue by 71; incrementing m will increase the red by two or three units and green/blue by larger increments. In practice, you will see no correlation between (n, m) and the color.



Only top voted, non community-wiki answers of a minimum length are eligible