Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [discrete-mathematics]

The study of discrete mathematical structures. Consider using a more specific tag instead, such as: (combinatorics), (graph-theory), (computer-science), (probability), (elementary-set-theory), (induction), (recurrence-relations), etc.

0
votes
0answers
13 views

Discrete Event Arrivals

If a concert starts at $8$ AM, assume that all passengers arrive between $7$:$00$ and $8$AM. If the show is sold out with $1000$ seats and one had to guess the inter-arrival times of patrons, what ...
4
votes
1answer
57 views

Finding the closed form for $x_n^2 = -x_{n-1}^2+6x_{n-2}^2+n$

I'm trying to find a closed form for the recurrence relation $x_n^2 = -x_{n-1}^2+6x_{n-2}^2+n$, with $x_1 = \frac{1}{4}, x_2=\frac{\sqrt{13}}{4}$ and $x_i \in \mathbb R^+$. My attempt was to let $z_n=...
0
votes
0answers
16 views

Help with discrete mathematics - inference and logical equivalence

I'm doing textbook homework for discrete mathematics and I'm struggling to understand how to solve the following practice problem. I would understand if they gave me variables and asked me to use ...
0
votes
1answer
19 views

Graph Theory - Discrete math

Can someone explain how to solve or start with this challenging equation? I have come to one conclusion which is to try the pigeonhole principle but can't get it right. Harry, being ahead of a ...
-1
votes
1answer
43 views

Just want to ask an mathematical induction question which I've tried to solve.. but still cannot get the LHS and RHS.

I have tried to solve this question, but it's kinda tricky here when I form a LHS equation by myself it doesn't equals to the RHS. Can anyone here provide me a step by step guide to proof it? ...
1
vote
1answer
30 views

A checkboard and sums problem, prove that there is a column or row such that the absolute value of sum doesn't exceed $2018^2/2$

Now we have a $2018\times 2018$ checkboard. Each space is filled with one integer with absolute value not bigger than $2018$. Suppose the sum of all the numbers is $0$, prove that there is a column ...
0
votes
2answers
21 views

Prove that each integer n ≥ 12 is a sum of 4's and 5's using strong induction

So I've been given the following problem: Prove that each integer n ≥ 12 is a sum of 4's and 5's What I have so far: (Basis): n ≥ 12 Therefore, 12 ≤ 4(x) + 5(y) x = 3 | y = 0 ...
1
vote
1answer
28 views

If a graph has less then $2n$ vertices, then it can't have $n$ spanning trees such that each pair is edge disjoint

If a graph has less then $2n$ vertices, then it can't have $n$ spanning trees such that each pair is edge disjoint This must apply for $n\geq 3$ I am not sure how to prove this. Probably the best ...
1
vote
1answer
34 views

show that the number $n = 11$ is not a sum of $4$'s and $5$'s

I don't know how to get started with this question. $11 = 4(x) + 5(y)$ What I've tried is : $x = 0, y = 2$ $11 = 4(0) + 5(2)$ $11 = 10$ $11$ is not equal to $10$. Wouldn't that be ...
8
votes
2answers
83 views

Combinatorial proof of $\sum_{k=1}^n k^2 =\binom{n+1}{3} + \binom{n+2}{3}$

What reason or hint would there be that $$\sum_{k=1}^n k^2 =\binom{n+1}{3} + \binom{n+2}{3}$$ Every combinatoric proof I have seen, seemed quite intuitive with the equation already giving hints to ...
0
votes
1answer
16 views

What kind of output does True or False give you?

I was working on proving that a statement ... $ p → ¬(¬q ∧ (p → q))$ ... is a tautology using logical equivalences and wound up at this step: $ T ∨ F $ I'm unsure if the output would be true ...
2
votes
1answer
36 views

A poker hand contains five cards. Find the probability that a poker hand can be…

a) Four of a kind (Contains four cards of equal face value) So for this one, we want four cards that have the same face value, different suit. And the last card can be any remaining card. There are ...
-2
votes
1answer
33 views

Find the probability that in a hand of $5$ cards from an ordinary deck of $52$ cards

Find the probability that in a hand of $5$ cards from an ordinary deck of $52$ cards, some suit appears on $2$ cards in the hand and each of $3$ other suits appears on $1$ card in the hand. Okay, so ...
0
votes
1answer
35 views

Expected values, covariance [on hold]

Let's say I want to calculate the covariance of something, for instance the number that occurs on a first die compared to a second die rolled. Using the covariance formula we get: $Cov(X,Y) = E(XY)−E(...
0
votes
1answer
25 views

Can we say that conclusion in this argument: (P v Q), P |- Q breaks “The Law of Excluded Middle”?

Can we say that the conclusion in this argument: (P v Q), P |- Q breaks "The Law of Excluded Middle"? And that is the reason why argument is invalid? I recently studied "The Law of Excluded Middle":...
0
votes
0answers
35 views

In the given argument ~(P v Q) |- P, is premise true or false?

While going through argument analysis section while studying logic. I came across this argument: ~(P v Q) |- P. Premise: ~(P v Q) Conclusion: P What I know: The given formula: ~(P v Q) ...
0
votes
0answers
18 views

Optimize taking advantage of guessing (physically) biased numbers in a known-biased sequence

The domain problem can be simply modelled as follows: There is a (quite small) real (physical) bias in what can be thought of as a 5x36 lottery (draw and guess 5 distinct numbers out of 36 different ...
0
votes
2answers
45 views

Find generating function of $ a_n=2a_{n-1}-3a_{n-2}+4n-1 $

I have to find generating function of $ a_n=2a_{n-1}-3a_{n-2}+4n-1 $ where $a_0=1$ and $a_1=3$. I'm currently stuck at the form: $f(x) = \sum_{n=0}^\infty a_nx^n = 1 + 3x +2x\sum_{n=2}^\infty(a_{n-1}...
0
votes
1answer
44 views

Prove the identity $\binom{2n}{2}$ = $\binom{n}{2}+\binom{n}{n-2}+n^2$ where $n\geq2$ using a combinatorial proof.

Prove the identity $\binom{2n}{2}$ = $\binom{n}{2}+\binom{n}{n-2}+n^2$, where $n\geq2$, using a combinatorial proof. I've tried to think of it in terms of a counting problem. I think that for the ...
0
votes
1answer
44 views

Peaks of a curve. [on hold]

I'd like to find the peaks corresponding to a curve most likely by using slope of tangent to the curve. enter image description here The attached curve has multiple peaks. I'm looking for an algorithm ...
0
votes
0answers
57 views

For which positive integers k can a simple graph G = (V, E) be constructed such that G is bipartite and its complement is bipartite?

For which positive integers k can a simple graph G = (V, E) be constructed such that: G has k vertexes, that is, |V| = k, G is bipartite, and its complement G is bipartite? Supply a proof to prove ...
2
votes
2answers
75 views

Find the total number of 20 digit codes that can be formed using the numbers {0,1,2,3,4}, such that consecutive digits have a difference of 1?

To start with an example of such a code can be: $34321210123212343210$ I have no clue how this property can be mathematically counted. I actually even have a short solution of this question which I ...
0
votes
2answers
21 views

Equivalency of these two logical statements

I need some help figuring out how these two logical statements are equivalent. p <--> ~q == (~p && q) OR (p && -q) I made a truth table and found that they are no equivalent BUT ...
1
vote
1answer
40 views

Prove that amongst 10 sticks of length 1 to 55 there are 3 that form a triangle

I'm trying to prove, that amongst 10 sticks, which length can vary from 1cm to 55cm, there are 3 (or at least 3), using which one can form a triangle. I feel like I should use Dirichlet's pigeon ...
0
votes
1answer
16 views

Propositional logic: Simplify p -> (q -> r)

My approach is to first get rid of the if-thens. p -> (q -> r) p -> (~q v r) by Implication law ...
1
vote
1answer
36 views

Slick way to solve P(pattern A appears before pattern B) type of problems in a coin toss process

Let's consider a fair coin and an infinite toss game. We frequently got asked about how to compute the probability of pattern $A$ appearing before pattern $B$ where $A$ and $B$ are both one of the ...
0
votes
0answers
25 views

intersection of fuzzy sets [on hold]

How to solve tasks with fuzzy sets, if in a subset several values of a subset of x? I figured out how to do tasks, where in the submultiple there is one value x, but how to do the next task? We must ...
2
votes
0answers
17 views

Prove convergence rate to zero increases as n increases

I am trying to prove that in the equation: $$F_{i,n} = \prod_{0}^{n-1}𝑃_{𝑖−(𝑛+1)}𝑃_{𝑖−𝑛}$$ as $i > n$, $i > 1$, $n \ge 1$, $n \longrightarrow \infty$ and $𝑃_{𝑖−𝑛} \longrightarrow 0$, $...
-1
votes
0answers
13 views

Distinct minimum spanning tree

For a connected, weighed, undirected graph G: G has a unique MST, if for every cut of G there is a unique minimum weight edge crossing the cut. Is this statement true? I think false because for the ...
1
vote
3answers
73 views

How to prove these two functions are always equal?

If $a$ and $b$ are positive integers and $/$ stands for integer division, we have these two functions: $$f(a,b) = (a + b - 1) / b$$ and $$g(a,b) = \begin{cases} a/b, & \text{if $a \mod b = 0$}...
0
votes
0answers
5 views

Number of odd contiguous sets under permutation

Part of a problem that I'm trying to solve involves the following situation: let $S = \{t_1,...,t_n\}$ be a set of n points in a line. Let $W = \{t_{i_1},...,t_{i_k}\}$ be a k-subset of S, such that ...
-5
votes
0answers
33 views

Which of the following sets are finite, which are infinite but countable, and which are uncountable? [on hold]

could I get some help on this problem? Which of the following sets are finite, which are infinite but countable, and which are uncountable? • $(f : N →$ {0, 1} $| ∀n ∈ N.f(n) ≤ f(n + 1))$ • $(f : N ...
0
votes
1answer
34 views

Stars and Bars with odd constraints.

Given $n$ indistinguishable items, 7 people have at least 23 of those indistinguishable items. In how many ways can an 8th person take exactly 23 of those items from the 7 people such that there are ...
1
vote
1answer
50 views

Suppose the edges of a complete graph of $10 $ vertices are coloured each either blue or red. Show that there is a blue triangle or a red tetrahedron

Could I get any help with this one, I'm lost. We know that the Ramsey number $R(3, 3)$ equals $6$. Suppose the edges of a complete graph of $10$ vertices are coloured each either blue or red. Show ...
-3
votes
0answers
36 views

Draw a venn diagram of $(A-C) ∩ (C-B)$ [on hold]

I want to know how to draw a venn diagram of $(A-C) ∩ (C-B)$
0
votes
1answer
22 views

Generating function for a special binary string

Let $S$ be the set of binary strings consisting of a (nonempty) block of $0$s followed by a (nonempty) block of $1$s, such that if the block of $0$s has odd length, then the block of $1$s has even ...
0
votes
1answer
16 views

What is a nontrivial minimizer?

I came across a statement that x is a nontrivial minimizer of some function, but couldn't find a definition of "nontrivial minimizer" on the Internet. Can anyone help point out some references for ...
0
votes
2answers
41 views

One of the following statements is true and one is false: If xy and x are both rational, then y is too…

One of the following statements is true and one is false: If xy and x are both rational, then y is too. If x − y and x are both rational, then y is too. I was able to find a proof for the first ...
-4
votes
1answer
21 views

Prove by induction that for every nonnegative integer n, 3|((2^(2n)) − 1). [on hold]

Rewrite your proof using proof by smallest counterexample. Please explain your answer
0
votes
1answer
35 views

Let $f(x)=ax+b$ and $g(x) = cx +d$. Determine necessary and sufficient conditions on the constants so that $f \circ g = g \circ f$

I want to ask a follow up question to this one: Let $f(x) = ax + b$ and $g(x) = cx + d$, where $a, b, c, d$ are constants. Determine for which constants $a, b, c, d$ it is true that $f ◦ g = g ◦$ I ...
3
votes
4answers
64 views

Provide a counterexample: If $n^2-1$ is divisible by $5$, then $n$ is divisible by $2$ or $3$

Provide a counterexample: If $n^2-1$ is divisible by $5$, then $n$ is divisible by $2$ or $3$ My book doesn't have an answer to this question, but I think it's $n=6$. Since $6^2-1=35$, which is ...
0
votes
1answer
17 views

How is the joint proportionality (joint variation) equation (i.e. $y = kxz$) logically correct?

If $y$ is proportional to $x$, and $y$ is also proportional to $z$, then how are we able to arrive at the equation: $y = kxz$ ? My understanding so far of proportionality, which comes from this ...
-2
votes
0answers
40 views

Does a graph exist with degree sequence (4, 3, 3, 1, 1) [on hold]

Does a graph exist with degree sequence (4, 3, 3, 1, 1) Simple graph; if not, why?
3
votes
4answers
59 views

Proving logical equivalences in the statements $(∃𝑥)(𝑃(𝑥) → 𝑄(𝑥))$ and $(∀𝑥)𝑃(𝑥) → (∃𝑥)𝑄(𝑥)$

For this I must show that the two statements $(∃𝑥)(𝑃(𝑥) → 𝑄(𝑥))$ and $(∀𝑥)𝑃(𝑥) → (∃𝑥)𝑄(𝑥)$ are logically equivalent. The issue I'm coming up with is that I'm unsure about the proper methods ...
1
vote
2answers
29 views

Solving Recurrence Relation Using Substitution/Geometric Series

$$ T(n) =4T(\frac{n}{2})+ n^\frac{5}{2} $$ I'm having trouble solving this recurrence relation above to identify the time complexity below by using substitution/plugging. I'm able to do it using ...
1
vote
1answer
31 views

By using a diagonal argument, show that the powerset $P(N) = (S|S ⊆ N)$ is uncountable. [duplicate]

Any tips or solutions for this one? By using a diagonal argument, show that the powerset $P(N) = (S|S ⊆ N)$ is uncountable.
1
vote
1answer
29 views

Find the number of ways we can form words using each letter in the word $DISKRET$ exactly once, if certain words may not appear as subwords.

Good evening, any solutions or tips for this problem? Find the number of ways we can form words using each letter in the word $DISKRET$ exactly once, if none of the words $RET$, $SEK$ or $DIS$ may ...
1
vote
1answer
19 views

probability that at least two part will be defective

Question The probability that a part manufactured by a company will be defective is $0.05$. If $15$ such parts are selected randomly and inspected, then the probability that at least two part will ...
4
votes
1answer
61 views

$n|a^n-b^n\Rightarrow n|\frac{a^n-b^n}{a-b}$ [duplicate]

Let $n\in\mathbb{N}$ and $(a,b)\in \mathbb{Z}^2$. Show that: $$n|a^n-b^n\Longrightarrow n|\frac{a^n-b^n}{a-b}$$ I’ve tried an induction, but I gave up. Is there a direct proof? To admin: Please ...
1
vote
0answers
20 views

Open problems in Cellular Automata field

here there is a link on Wolfram about 20 open problems of CA theory. Has anyone of them been solved or tested? I'm searching for literature.