Discrete mathematics is the study of mathematical structures that are fundamentally discrete rather than continuous.

learn more… | top users | synonyms

2
votes
2answers
48 views

Is this truth table correct?

Is this truth table correct? Sorry for the formatting Truth table for $p ∧ c$ and $p ∨ c$, with $c$ representing a contradiction: $$\begin{array}{cc|cc} p & c & p∧c&p∨c \\ \hline T ...
2
votes
1answer
38 views

Visiting Node in BFS and DFS in the same order [closed]

if G be a connected, undirected graph and has at least 3 vertex. we know the order of visiting node from a given vertex in BFS and DFS is the same. which of the following is false? a) G can be a ...
0
votes
2answers
31 views

How can I simplify and verify the logical equivalence using these laws?

∼(p ∨∼q) ∨ (∼p ^ ~ q) ≡ ~p Please help I don't know where to start. These are the laws I need to list in each step when simplifying. Commutative laws: p ∧ q ≡ q ∧ p p ∨ q ≡ q ∨ p Associative ...
1
vote
2answers
49 views

Discrete Mathematics - In how many ways can $A$ and $B$ exchange their books?

$A$ has $5$ different books and $B$ has $3$ different books. How many ways are there in which they can exchange their books so that each keeps his individual number of books unchanged? I got the ...
0
votes
1answer
24 views

Find the roots of a polynomial in Matlab

I have a polynomial $f$ of order 15 and I want to find its roots. For solve(f==0), the answer is ...
2
votes
1answer
27 views

average no. of color matches per position.

I've a problem whose solution is also stated below. I can't understand the explanation. There are two disks ,one smaller than the other, are each divided into 20 congruent sectors. In the larger ...
0
votes
3answers
26 views

List all the permutations for the letters a,c,t

I know a permutation is p(n,r)=n!/(n-r)! but I am confused how to go about solving this problem. Help please?
0
votes
2answers
24 views

Number of students and how many are taking X class (Discrete Structures)

So I have my first quiz tomorrow and want to get off on the good foot, but I'm studying some problems and this one is particularly confusing... There are a group of 191 students, of which 10 are ...
1
vote
2answers
43 views

How can logical equivalence be derived from this..

(p ∨∼q) ∧ (∼p ∨∼q) ≡ (∼q ∨ p) ∧ (∼q ∨∼p) by (a) ≡∼q ∨ (p ∧∼p) by (b) ≡∼q ∨ c by (c) ≡∼q by (d) Therefore, (p ∨∼q) ∧ (∼p ...
1
vote
1answer
21 views

Creating statements using symbols

Are these statements correct? And can anyone help me figure out letter c? Let h = Joe is healthy, w = Joe is wealthy, s = Joe is wise. a. Joe is healthy and wealthy but not wise. Answer: (h∧w) ∧ ~ ...
1
vote
1answer
22 views

Are these statements negated correctly using De Morgan's laws?

$-10 < x < 2$. Negation: $-10 \geq x$ or $x \geq 2$. $x \leq -1 \text{ or } x > 1$ Negation: $-1 > x \leq 1$
4
votes
0answers
52 views

local informatics Olympiad and Algorithm

I see one of recent local informatics Olympiad question. i have a trouble to solve it. any idea? hint? or solutions? thanks to all creative man. We have two function $P_1, P_2$ and input an array $n$ ...
1
vote
1answer
38 views

How can I write negations for this statement?

Are these negations correct using De Morgan's laws for this statement: This computer program has a logical error in the first ten lines or it is being run with an incomplete data set. Negation: This ...
1
vote
0answers
13 views

Simple random walk conditioning on non-return

Consider a simple symmetric random walk on $\mathbb{Z}$, $(S_t)_{t \geq 0}$, with $S_0=0$. Let $P_{k,j}$ be the probability that the walker hits the point $k$ without returning to the origin in ...
2
votes
1answer
29 views

Average no. of objects in a box,when m objects are filled in n boxes.$(m>n)$

The formula for the average no. of objects in a box,when m objects are filled in n boxes $(m>n)$ is given by $[m/n]$ ,if $(m/n)\in \mathbb Z$ and $[m/n]+1$,if $(m/n)\notin \mathbb Z$ . The thing ...
0
votes
4answers
60 views

a 2-regular graph is cyclic or not?

We know the common result : - If every vertex of a graph G has degree at least2, then G contains a cycle. Can I conclude that 2-regular graphs are cycles where degree is exactly two of every vertex? I ...
0
votes
2answers
25 views

Discrete mathematics equality

Suppose I have two sets A and B: $$A = \lbrace x \in \mathbb{R} : x^2 - 2x -3 < 0 \rbrace$$ $$B = \lbrace x \in \mathbb{R} : -1 < x < 3 \rbrace$$ I need to prove that A = B. Thus I need to ...
1
vote
4answers
49 views

Discrete mathematics subsets

Suppose I have two sets A and B: $$ A = \lbrace 2k-1 : k \in \mathbb{Z}\rbrace$$ $$ B = \lbrace 2l+1 : l \in \mathbb{Z}\rbrace$$ I need to prove that A = B. I know that to prove equality between ...
1
vote
2answers
42 views

Diffucult Tautology to Prove

I'm trying to show that the following is a tautology: (p or q) and (not p or r) implies (q or r) Can anyone help, as far as I can get is to the following: [(not p and q) or (p and not r)] or ...
1
vote
2answers
59 views

Show that this argument is valid.

¬p → C; ∴ p. Where C denotes a contradiction. What does it mean by ¬p → C;? Also another statement ¬p → F; ∴ p. Is there any differences between the two statement since from my understanding a ...
2
votes
1answer
48 views

Proving that a relation is an equivalence relation

I am having difficulties proving the relation IS an equivalence relation. Let $f: X\longrightarrow Y$ be a function from a set $X$ onto a set $Y$. Let $R$ be the subset of $X \times X$ consisting ...
1
vote
2answers
45 views

Is this a valid proof of $(A∧B’) ∧C↔(A∧C) ∧B’$?

So I am supposed to prove $(A∧B’) ∧C↔(A∧C) ∧B’$ using wffs and equivalence rules. I have never done such proof, and I want to check if my steps are correct. This assignment is only graded based off of ...
0
votes
1answer
29 views

How do I write this statement using symbols?

Juan is a math major but not a computer science major. (m= "Juan is a math major.", c= "Juan is a computer science major.") How do I write this is symbolic form using the letters and (and, or, not)?
4
votes
2answers
29 views

Solve $T(n) = 1 +\sum_{i=0}^{n-1}T(i)$

For the recurrence defined by $$T(n) = 1 +\sum_{i=0}^{n-1}T(i)$$ Apparently $T(n) = 2^n$ .. but I cannot see it. This recurrence pops up during analysis of the Rod Cutting Problem. I keep looking to ...
4
votes
1answer
46 views

Hashing With Chaining Collision

We have $1000$ elements with key=1 to 1000, and a hashing function $$ h(i)=i^3 \mbox{ mod } 10 $$ for an array with length $10$ (array index from $0$ to $9$) with chaining method. What is the ...
2
votes
1answer
112 views

Water Box with n Liter

I ran into a basic challenging problem. I see an high school local math Olympiad question. we have a box that keep n Liter water. each time we extract 1/k Water from box. how many times (minimum) we ...
3
votes
2answers
61 views

Ramsey Numbers involving Cycles, $R(K_3, C_5)$

I've been asked to determine the value of $R(K_3, C_5)$, but I'm having a lot of difficulty putting all the pieces together. We were given the hint of using $R(3,4) = 9$, and I've tried to apply ...
0
votes
2answers
28 views

Sorting out logic homework with a friend.

My friend and I were looking over my homework and he pointed out something that he thought was incorrect. I was to write sentances using logical connectives. The original sentance was: "To get ...
1
vote
1answer
37 views

Closed form for estimated sum with different asymptotic bounds?

I found asymptotic lower and upper bounds for a summation as follows: $$ 1 - O\left(\frac{\log_2^2 n}{n}\right) \le \sum_n f(n) \le 1 + O\left(\frac{1}{n}\right).$$ If you want to write it in a ...
0
votes
1answer
62 views

Diameter of a tree

$$T=(V,E) \text{ tree }$$ $$\text{diameter of a tree } = \max_{u,v \in V} \delta(u,v)$$ $$\delta(u,v)=\text{the length of the shortest path from the vertex u to the vertex v}$$ How can we calculate ...
2
votes
1answer
36 views

In how many ways you can put n white balls and 2n black balls into n boxes if at least one black ball have to be in each box

n - number of white balls 2n - number of black balls In how many ways you can put it into n boxes? It have to be at least one black ball in each box. My idea: First of all let's put one black ball ...
1
vote
3answers
50 views

Finishing Induction Step

I am currently writing a proof for the following problem $$ \sum\limits_{i=1}^n i^22^i = n^22^{n+1}-n2^{n+2}+3*2^{n+1}-6 $$ By induction on $n\ge0$ My question isn't really about how to correctly ...
4
votes
3answers
93 views

2000 Olympiad in Informatics Question on Box

I have an old Olympiad question on informatics. There are 31 boxes. In each box there is one number. We know the number if and only if we open the box. We want to calculate the minimum number of ...
0
votes
1answer
19 views

How do you solve a recurrence with a functin through induction?

I found the answer in part-A by substitution, as O(n) from; T(n/2^k) = T(1).... n/2^k = 1..... so k = 1og2(n)..... T(log2(n)) = T(n/n)+5.... so O(n) IS THE ANSWER, Correct me if am wrong because am ...
2
votes
3answers
55 views

how to fairly select a leader

I recently came across a rather practical problem: A large group (around 30 people) wanted to elect a new leader (someone who is not part of the group) of 4 possible candidates. Each of the ...
-3
votes
1answer
33 views

Find the length of a set. [closed]

Set S contains seventeen even numbers, eleven multiples of 6 and twenty three multiples of 3. What is |S| - the cardinality of the set S?
2
votes
1answer
45 views

The perimeter of triangle $ABC$ where $|BC|=293$, $|AB|$ is a square, $|AC|$ is a power of $2$, and $|AC|=2|AB|$

In triangle $ABC$ length of side $BC$ is $293$ (a prime). If length of side $AB$ is a perfect square, length of side $AC$ power of 2 and $AC$ twice length of $AB$, find the perimeter. Kind of ...
0
votes
3answers
47 views

recursive definition odd length strings

Given the alphabet {aaa bbb}, give a recursive definition for the language that only contains odd length strings. must be constructive definition we are suppose to treat aaa as one letter and bbb as ...
2
votes
0answers
23 views

Solution of partial difference equation

I want to find the explicit solution of the following difference equation $e_{i,j+1}=re_{i-1,j}+(1-2r)e_{i,j}+re_{i+1,j}+km_{i,j}$ where $r>0$, $k>0$ and $m_{i,j}$ are known and $e_{i,0}=0$. ...
0
votes
1answer
38 views

Recursive definition of the set of odd numbers

Show that the following is another recursive definition of the set ODD (keep in mind you’ll need say something about even numbers too): Rule 1: 1 and 3 are in ODD. Rule 2: If x is in ODD, then so is x ...
0
votes
1answer
50 views

Identities involving the floor function

Are either of these statements false? if so what is the counter example? $⌊x − 2⌋ = ⌊x⌋ − 2$ or for any odd integer n, $⌊(n^2/4) + 1⌋ = (n^2+3)/4$ also I'm struggling to make a proof of either if ...
0
votes
1answer
31 views

Proof for divisibility?

Prove either by contradiction or contraposition (using Fundamental Theorem of Arithmetic in either case) that: $$ ∀k ∈ \mathbb{Z}, [3|(k-2) → 3 |(k^2 - 1)] $$ Any help would be great! Thanks!
1
vote
5answers
68 views

Using Direct Proof. $1+2+3+\ldots+n = \frac{n(n + 1)}{2}$ [duplicate]

I need help proving this statement. Any help would be great!
1
vote
2answers
69 views

Finding a formula for $1+\sum_{j=1}^n(j!)\cdot j$ using induction

I need help with finding the formula and proving it by induction. Am stuck, but the professor says we should know this by now.
3
votes
1answer
38 views

Simplify a boolean algebra expression: xy + xz' + x'yz

I need to simplify xy + xz' + x'yz into xz' + yz. I know that these expressions are equal in truth value, but I'm not sure how ...
0
votes
1answer
37 views

Hanoi Algorithm With Different Nodes

http://en.wikipedia.org/wiki/Tower_of_Hanoi I need help developing a Hanoi algorithm which follows the same rules as the standard game, however the nodes that are transversed is different. In this ...
0
votes
2answers
36 views

Simplifying modulus expressions and an unknown expression? discrete math

I have a few questions below that I need help with a) I don't really understand what that symbol means and how to solve it b) How do u simplify this without a calculator c) I got 2^-r = 0, iss this ...
1
vote
3answers
45 views

Prove that $\forall k\in\mathbb{Z}$, $3|k-2$ implies $3|k^2-1$

I'm looking to answer this question Prove $\forall k\in\mathbb{Z}$, $3|k-2$ implies $3|k^2-1$. I'm not sure what to do. I'm trying to study but now I am getting stuck on these questions that don't ...
0
votes
1answer
22 views

∀a,b,c∈ Z, if a|b and a|c then a^2|(5b^2 + 7c^3)

My question is Prove the statement. ∀a,b,c∈ Z, if a|b and a|c then a^2|(5b^2 + 7c^3) I'm really stuck and have no idea where to start. any help would be great!
0
votes
0answers
6 views

Minimal vertex cover in bipartite graph question

How one can check for every vertex of bipartite graph whether it(vertex) belongs to every minimal vertex cover?