# Tag Info

### Completing the solution to a constrained Diophantine equation with inequality conditions

I reviewed and agree with all of the math given in the OP's (i.e. original poster's) presentation. First I should clarify a few things. The overall approach should be to let A = the enumeration of ...
• 38.1k
1 vote
Accepted

### Formalize a proof for the existence complete graph minor in a graph

Some notation before the answer: For a graph $G$, $V(G)$ is the vertex set of $G$ and $E(G)$ is the edge set of $G$. I am using $xy$ or $yx$ instead of $(x,y)$ to denote an edge, for brevity. For a ...
• 56
1 vote

### Finding the minimum of a convex injective function on $\mathbb{Z}$ with fewest evaluations

Your pseudo-code with two function calls per iteration is certainly not optimal, you should only make one function call per iteration. The correct algorithm is: We take two points $a$, $b$ with their ...
• 5,003

### Negating a multiply quantified statement

There are already a few good answers under your post, showing how to formally express the negation of that quantified statement. To help you see how it is false, let's phrase it this way: it says that ...
1 vote

### Solve the recurrence $T(n) = nT(n/2) +n - 1$

Making $n = 2^m$ we have $$T\left(2^m\right)=2^m T\left(2^{m-1}\right)+2^m-1$$ This recurrence can be recast as $$R(m) = 2^m R(m-1) + 2^m - 1$$ now if $R_h$ and $R_p$ are the homogeneous and ...
• 34.8k

### Negating a multiply quantified statement

Using a form of natural deduction, we have: (Screenshot) (Text version) Suppose... 1 ~EXIST(x):[x in r & ALL(y):[y in r => 2*x+y=7]] Premise Switch quantifier (EXIST --> ALL) 2 ~~ALL(x)...

### Negating a multiply quantified statement

There exists a real number $x$ such that for all real numbers $y,\; 2x+y=7.$ my textbook says that this statement is false. Let's rephrase the given statement: There is some real number $b$ for ...
• 40.7k

### The meaning of an implication with the existential quantifier

$∃x(P(x) → Q(x))$ never really makes sense. If $~\exists x (\neg P(x))~$ (usually a reasonable assumption), this will always be true for any predicate $Q$ whatsoever. So, it kind of "makes sense,...

### Negating a multiply quantified statement

The order of quantifiers matters. That is the reason why complex assumptions must always be written in mathematical language: because it allows no ambiguity. English language (or whatever your first ...
• 1,403

### Prove that $(A \times B)\setminus(A\times C) \subseteq A×(B \setminus C)$

Based on the definitions involved, one concludes that: \begin{align*} (A\times B)\backslash(A\times C) & = \{(x,y) \mid ((x,y)\in A\times B)\wedge((x,y)\not\in(A\times C))\}\\\\ & = \{(x,y) \...
• 17.5k
1 vote

### Find a perfect matching

The problem is symmetric for students and problems. Let $X$ be students, $Y$ be problems and $S \subseteq X$. If $0 < |S| \le 4$ then $|N(S)| \ge 4$ since every student solved at least $4$ problems....
• 7,091

### How to calculate the number of labelled trees with 6 vertices, at least 3 leaves, and a specific vertex as a leaf?

There are multiple different ways to count such tree, including careful consideration of all $1296$ labeled trees on $6$ vertices one by one. However I like the following solution. One of proofs of ...
• 7,091

### Number of rectangles with odd side lengths on a chess board?

We can say that the odd lengths in a chessboard are $1,3,5,7$ Let $W(n)$ be the number of times the width $n$ occur in a chessboard then $W(1)=8$, $W(3)=6$, $W(5)=4$, $W(7)=2$ Summing all the $W(n)$ ...
1 vote
Accepted

### Statistical bounds on number of digits for an element from a Fibonacci-like sequence

[We assume, per the comments, that $T_0, T_1 \geq 0$, even though technically positivity is only defined on $k > 1$. ] Observe that $T_k = F_{k-2} T_0 + F_{k-1} T_1$. (See Note 1 for details.) How ...
• 72.1k
Accepted

### arithmetic function to return an integer from lower "L" up to maximum "M", from any integer input

\begin{equation*} f(X) = \frac{1}{2}\Bigl(|X-L|-|X-M|+M+L\Bigr) \end{equation*} Note that $|x|$ can be written as $\sqrt{x^2}$, so this fits your criteria.
• 4,007

• 3,698
1 vote

### How can I learn to identify the class (P, NP, etc.) of a discrete optimization problem?

This is quite a wide question. First, search for polynomial by checking important polynomial classes: Horn clauses, linear algebra problem, linear programming problems (including some hiding with ...
• 5,003
1 vote
Accepted

• 72.1k
### Sketch the graph of the equation $⌊x⌋^2 +⌊y⌋^2 =4$.
COMMENT.- Confirmation that you are right, is given by Desmos itself by plotting $⌊x⌋^2+⌊y⌋^2\le4$ instead of $⌊x⌋^2+⌊y⌋^2=4$. In several cases, for example, with isolated points, Desmos does not ...
### Sketch the graph of the equation $⌊x⌋^2 +⌊y⌋^2 =4$.
Your graph is not correct. The rightmost square is at the wrong position. For any $(x,y)$ in that square, $\lfloor x\rfloor^2+\lfloor y\rfloor^2=1^2+0^2\neq 4$. In response to your situation about ...