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.

learn more… | top users | synonyms

0
votes
2answers
31 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
45 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
22 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
28 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
64 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
45 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
15 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
73 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
26 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
51 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
46 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
62 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
58 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
33 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
31 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 ...
6
votes
1answer
54 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
62 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
33 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
44 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 ...
1
vote
1answer
70 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
37 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
96 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
39 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
46 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
4answers
57 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
24 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
51 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
56 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
75 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
73 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
70 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
44 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
44 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
64 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
7 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?
1
vote
1answer
65 views

Prove $1! + 2! + . . . + n! < (n + 1)!$ using mathematical induction [duplicate]

$1! + 2! + . . . + n! < (n + 1)!$ This question has left me stumped for quite some time. I am not sure how to approach it. (I am really bad at induction).
1
vote
3answers
63 views

Explanation for the number of partitions of $\{1,\dots,n\}$ into $k$ parts

A partition of the set $\{1, 2, . . . , n\}$ into $k$ parts is a way of writing the set as a disjoint union of $k$ subsets. For example $\{1, 2, 3, 4, 5\} = \{1, 4\} \cup\{2, 3\} \cup \{5\}$ is a ...
5
votes
3answers
98 views

How to find the sum of sequence $ 1+4+4^2+\cdots+4^{X+Y} $?

I see the following sequence and it's: $$h=1+4+4^2+\cdots+4^{X+Y}=\frac{4^{X+Y+1}-1}{4-1}$$ how we get this sequence? I know this is a primary question but I confused :)
3
votes
3answers
92 views

Domain and Function Relationship

This is a very basic question I guess, if I have something like f:A->B, should all the elements in set A be used for f to be a function?
0
votes
0answers
39 views

Every DPDA has an equivalent DPDA that always reads the entire input string

I am trying to understand the proof from Michael Sipser's Introduction to the Theory of Computation, page 132. I don't understand why if $q \in F′$ then $\delta(q,a,\$)$ is set to ...
0
votes
2answers
42 views

Minimum cut in a graph does not change when the weight of all edges is increased by one

Suppose we have a Graph $G$ in which weight of all edges is $> 1$ (positive). If we increase weight of all edges by one, why does the minimum cut $(S, T)$ of $G$ into two graphs remain the same? ...
3
votes
4answers
59 views

Show $P\left(A-B\right)=P\left(A\right)-P\left(A \cap B \right)$

I'm trying to show that, given two events $A,B \in \Omega$ ($\Omega$ is a sample space): $$P\left(A-B\right)=P\left(A\right)-P\left(A \cap B \right)$$ I know $A-B = A \cap B^C$, but I don't know how ...