New answers tagged discrete-mathematics
0
votes
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
0
votes
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
0
votes
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)...
- 15k
4
votes
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
5
votes
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,...
- 15k
4
votes
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
6
votes
Negating a multiply quantified statement
The statement is saying that there exists a single number $x$ such that the following equations all hold simultaneously:
$2x+1=7$
$2x+2=7$
$2x+3=7$
...
And so on and so forth, for every real number $...
- 6,843
9
votes
The meaning of an implication with the existential quantifier
"Someone is a comedian and that means they are funny" actually means $$\exists x\, C(x)\land \forall x\,\big(C(x)\to F(x)\big),$$ which is a logically stronger assertion than $$∃x\,\big(C(x) ...
- 40.7k
18
votes
Accepted
The meaning of an implication with the existential quantifier
Example c was written: $ \exists x (C(x) \to F(x))$
The answer to that example was given as "Someone is a comedian and that means they are funny"
That is an incorrect translation. Imagine a ...
- 10.5k
1
vote
Alternative way to obtain a closed form of a continued fraction
Your attempt fixups. The solution of your ODE for $S(z)$, rewritten as
$$
(1-xz)^2 S'(z)-(1+x-x^2 z)S(z)=D:=S_1-(1+x)S_0,
$$
with $S(0)=S_0$, is
$$
S(z)=\frac1{1-xz}\exp\left(\frac1{x(1-xz)}\right)\...
- 40.9k
0
votes
Accepted
I need help with this basic discrete math problem
Each string is of length 2, and each character of the string can be chosen from any of the 3 characters in $\{0,1,2\}$. So there are a total of $3^2 = 9$ possible strings. I would suggest you start by ...
- 76
1
vote
Prove that $(A \times B)\setminus(A\times C) \subseteq A×(B \setminus C)$
$(A \times B) \setminus (A \times C) $ is the set of $(x,y)$ where $(x,y) \in A \times B \land (x,y) \notin (A \times C$)
This means that $((x \in A \land x \notin A)\land y\in B) \lor (x\in A\land (y ...
- 1,473
5
votes
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
0
votes
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
0
votes
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
0
votes
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
2
votes
Where I am going wrong in translating this sentence from natural language to logical symbols?
Your answer was $$(\lnot s \land w) \implies d.$$
Recalling that $p \implies q$ is equivalent to $\lnot p \lor q$, and also recalling de Morgan's laws, your answer is equivalent to
$$ (s \lor \lnot w) ...
- 101k
8
votes
Accepted
Approximations for a Fibonacci-Like Sequence
The general solution to the linear recurrence
$$
T_0 = a_0, \; T_1 = a_1, \; T_i = T_{i-1}+T_{i-2}\; (i\ge2)
$$
is given by
$$
T_i = F_{i-1}a_0 + F_i a_1
$$
where $F_i$ is the usual Fibonacci sequence ...
- 85.1k
7
votes
Approximations for a Fibonacci-Like Sequence
A general sequence $(T_n)_{n=0}^\infty$ satisfying the Fibonacci recurrence with $T_0 = a$ and $T_n = b$ will be given by $T_n = a F_{n-1} + b F_n$. To make sure that $T_0, T_1, \dots, T_{n-1}$ are ...
- 147k
0
votes
Is every argument with false premises and conclusion valid?
Is every argument with false premises and conclusion valid?
can an argument still be valid even if the premises and conclusion are all false?
An argument with a false premise and false conclusion ...
- 40.7k
1
vote
Accepted
Between any two cities in a certain country, there are either direct flights or direct buses, but not both. Please prove or disprove some questions.
Your modelling of the problem in graph-theoretic terms is completely correct. Cities are vertices, and the travel options can be represented as a 2-colouring of the edges of the complete graph on ...
- 1,322
3
votes
Accepted
Alternative formulation proof for Gould's sequence
The $G(n)$ is essentially counting how many of the binomial coefficients $\binom{n}{i}$ are odd. But these are the coefficients of $(1+x)^n$, so we just need to look at non-zero coefficients of $(1+x)^...
- 17.3k
1
vote
Accepted
Find the chromatic polynomial of a graph using deletion and contraction
You've done the deletion-contraction correctly, but your chromatic polynomials for all four graphs you get at the end are wrong. All of them can be solved in the same way, which I'll illustrate on the ...
- 147k
6
votes
Accepted
Are incomplete magic squares with some integral entries necessarily purely integral
Here is an example of a non-integer unique solution to a question with integers:
Given
\begin{array}{|c|c|c|}
\hline
1 & ? & 2 \\ \hline
? & ? & ? \\ \hline
3 & ? & ? \\ \hline
...
- 161k
0
votes
Need clarification on what makes an argument invalid or valid
$5$ is not an even number.
If $5$ is an even number, then $7$ is an even number.
$\therefore\quad 7$ is not an even number.
the hypotheses and conclusion are all true, so isn't the argument ...
- 40.7k
0
votes
Set partition with some conditions
I think there is a mistake in @Mike Earnest's solution(wrote here because my reputation is below $50$).
Pick any $k\geq 2$ and think about $P$ having two different parts $B_1$, $B_2$ such that ...
- 31
0
votes
Set partition with some conditions
Claim. Each set partition of $[n]$ into $k$ parts can be bijectively correspond to set of $n-k$ ordered pairs of form $(i, j)$ $(1\leq i<j\leq k)$ such that following condition holds;
Each number ...
- 31
0
votes
Is the Kronecker Delta equivalent to this expression? $\delta_{ij} = \lfloor e^{-|i-j|} \rfloor$
Don't worry too much. There are no issues with the details you provided. In fact, in mathematics, it is normal for a function to have many different representations. It is just seems to that a person ...
0
votes
Sketch the graph of the equation $⌊x⌋^2 +⌊y⌋^2 =4$.
Your right square $[1,2)\times[0,1)$ is wrong. It is not included in the solution set. Its corner $(1,0)$ does not satisfy the equation. It must have been $$[2,3)\times[0,1)$$
instead. You have to ...
- 12.5k
5
votes
Accepted
A bijection of a connected graph that preserves 2-distances but is not an automorphism
Let $G$ be a line with three segments, i.e., $V=\{a,b,c,d\}$ and $E=\{\{a,b\},\{b,c\},\{c,d\}\}.$ Let $\varphi=\{(a,a),(b,d),(c,c),(d,b)\}.$ This is not an automorphism because it maps a vertex of ...
- 2,460
0
votes
Are a fixed amount of pairs sufficient to output any permutation here?
I feel like the first part of your question is a bit confusing, at least to my understanding. Should $X$ not be a subset of $C\times C$? It's perfectly fine to think of this as an $n$-entry array ...
- 159
0
votes
$A \subset B$ if and only if $B^c ⊂ A^c$
Use some definitions and the law of contraposition:
$\bigg(A\subseteq B \bigg) \iff \bigg( x\in A\implies x\in B \bigg)\iff \bigg( x\notin B\implies x\notin A\bigg) \iff \bigg( x\in B^c\implies x\in ...
- 53
0
votes
Number of ways to arrange 7 $D$s and 8 $R$s with no four consecutive same letters
We consider a binary alphabet built from letters $\mathcal{V}=\{D,R\}$. Words which do not have any consecutive equal letters are called Smirnov words. A generating function for Smirnov words is given ...
- 110k
0
votes
Any subset of size $6$ from the set $S = \{1,2, 4, \dots 9\}$ must contain two elements whose sum is $10$.
If $A$ does not contain two elements whose sum is $10$, then
for $x \neq 5$, $x \in A \implies 10 -x\notin A$ whose process stops at $4$ distinct $x$'s since there are only $4$ distinct pairings that ...
- 2,731
0
votes
Proving a collection of sets is a partition within a surjective function
If $A$ is any set, an equivalence relation on $A$ is a relation $\sim$ which satisfies the following: for any $a,b,c \in A$ we have
$a \sim a$ (reflexive)
if $a\sim b$ then $b \sim a$ (symmetric)
if $...
- 6,134
0
votes
Show that $a_n x^n + a_{n-1} x^{n-1} + \cdots + a_1 x + a_0$ is $\Omega(x^n)$
$$\lim_{x\to\infty}\frac{a_nx^n+a_{n-1}x^{n-1}+\cdots a_0}{a_nx^n}=\lim_{x\to\infty}\left(1+\frac{a_{n-1}}{a_nx}+\cdots\frac{a_0}{a_nx^n}\right)=1$$ so that for $x$ sufficiently large,
$$1-\epsilon<...
- 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
Floor function of type $\left \lfloor\frac{c}{x}+b \right\rfloor + \left \lfloor \frac{b}{x}+c \right\rfloor = d$
Hint:
Using
$$\frac ax-1<\left\lfloor\frac ax\right\rfloor\le\frac ax$$
the given equation can be rewritten as a bracketing
$$\frac{b+c}x-2<w\le\frac{b+c}x.$$
This gives you a possible range of $...
- 3,698
2
votes
Accepted
Sum of $2023$ numbers in $2022$nd power can be shown in at least $100$ different ways.
Let $x$ be an arbitary positive integer.
There are $x$ $2022$-th powers from $1$ to $x^{2022}$.
There are $x^{2023}$ distinct sequences of $2023$ $2022$-th powers from $1$ to $x^{2022}$.
Each sequence ...
- 2,021
1
vote
What is the difference between combinatorics and discrete mathematics?
I believe that this is an important and poorly understood question with implications for education.
In my opinion, combinatorics and discrete mathematics are two different types of things, and thus ...
- 149
0
votes
Compute the number of ways the frog can move from A to B.
Alternative approach, which is based on partitioning an integer.
To partition $~5~$ into terms all less than 3:
P5a: 2 - 2 - 1
P5b: 2 - 1 - 1 - 1
P5c: 1 - 1 - 1 - 1 - 1
To partition $~6~$ into ...
- 38.1k
0
votes
Compute the number of ways the frog can move from A to B.
This is not a 3D DP problem (in an algorithm sense) given the constraint that the frog can't move $k$ steps in the same direction consecutively ($k=3$ in this case), because the state of the frog is ...
- 36
2
votes
Accepted
Existence of a line wich contain $c|A|$ points
Problem 1 is not true, and hence Problem 2 is not true.
Consider the set of $n^2$ points $ (i, j, 0)$ where $ 1 \leq i, j \leq n$.
Observe that the set of generated planes is just the x-y plane, so $|...
- 72.1k
0
votes
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 ...
- 30.7k
3
votes
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 ...
- 968
Top 50 recent answers are included