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

learn more… | top users | synonyms

1
vote
0answers
37 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
29 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
44 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 ...
0
votes
1answer
41 views

Big-Oh notation proofs [on hold]

a) $f(n) \quad \Omega (g(n))$ b) $f(n) \quad \Theta (g(n))$ c) $f(n) \quad \Theta (g(n))$ d) $f(n) \quad \Theta (g(n))$ Am not sure why I got lots of $\Theta (g(n))$ , am I correct in the ...
4
votes
3answers
89 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
50 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
32 views

Find the length of a set. [on hold]

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
38 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
39 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
18 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$. ...
-2
votes
0answers
23 views

use logical way to calculate the least percentage [on hold]

If 70 per cent. have lost an eye, 75 per cent. an ear, 80 per cent. an arm, 85 per cent. a leg q1: what is the least percentage lost all four q2: what is the least percentage lost one of them q3 what ...
0
votes
1answer
32 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
46 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
28 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
votes
1answer
24 views

Sets and set operations [on hold]

Answer the following with short explanation. We consider a set $X$. Recall that P(X) is the power-set of X. 1) If the size of $X$ is 5, what is the size of $P(X)$? 2) If the size of $P(X)$ is 1024, ...
1
vote
5answers
66 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
49 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
29 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 ...
-6
votes
0answers
24 views

Arithmetic question Urgent [on hold]

If delta Hm/T = 13.5, T=298 and R is 19.8 will the final equation be: log Xi = - 0.01 (Tm' – 298) OR log Xi = 0.01 (Tm' – 298)
0
votes
1answer
34 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
35 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
41 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
4 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?
-3
votes
2answers
44 views

how many ways are there to distribute seven indistinguishable balls into five distinguishable bins? [on hold]

This was my findings but got wrong $5 \times 5 \times 5 \times 5 \times 5 \times 5 \times 5 \times =78,125$
-6
votes
1answer
25 views

how many different strings can be made from the letters in aardvark [on hold]

I got 360 few times but when I input says wrong 8 letters total A=3 R=2 D=1 V=1 K=1
1
vote
1answer
60 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
59 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 ...
4
votes
3answers
83 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 :)
4
votes
3answers
81 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
34 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
29 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
49 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 ...
2
votes
0answers
21 views

Number of nonnegative solutions of linear diophantine inequality

Given inequality $Ax + By \le C$, where $A, B, C$ are integers, $A$ and $B$ are coprime and $C < AB$. I need to find number of non-negative integer solutions of it. Is there exists algorithm which ...
4
votes
0answers
80 views

An interesting math problem I created for an old-school RPG game.

The point of this is to try to have the best stats as possible at the beginning of the game and stay at level 1 before doing any quests. Starting group at creation menu: ...
2
votes
2answers
74 views

Solution of an equation involving even integers

If $x$ is any positive even integer $> 1$. I compute: $$ c = x + x! $$ Now assume instead $c$ (even integer) is given, and I want to get back the value $x$. Is it possible to find a simple ...
0
votes
1answer
31 views

Induction Problem Number of Tiles on Floor

I took a discrete math course about a year ago, and I recently decided to crack open my book again as a refresher on induction proofs and problems. I ran across this problem, which I didn't remember ...
3
votes
2answers
242 views

A number is a perfect square if and only if it has odd number of positive divisors

I believe I have the solution to this problem but post it anyway to get feedback and alternate solutions/angles for it. For all $n \in \mathrm {Z_+}$ prove $n$ is a perfect square if and only if $n$ ...
0
votes
0answers
37 views

Block design: derived designs

I am now study some theorems of block design. I have a question about the derived designs. Let $B$ be the oringinal design $t-(v,k, \lambda)$. Suppose we omit one of the points, say $P$, then we have ...
1
vote
1answer
47 views

Bijection between $N^3$ and $N$ [closed]

How can we say that there exists a bijection between $N^3$ and $N$. Kindly give me a detailed solution. How can we say that $N^3$ is countably infinite?
1
vote
1answer
16 views

How many boolean functions $F(x, y, z)$

Question:How many boolean functions $F(x, y, z)$ are there so that $F(\bar{x}, y, z) = F(x, \bar{y}, z) = F(x, y, \bar{z})$ for all values of the Boolean variables $x, y,$ and $z$? I'm at loss on ...
3
votes
2answers
43 views

A sum of difference of floors

I have the sum ( $M$ is any integer $> 1$ ): $$ \sum_{h = 1}^{M}\left(\,\left\lfloor\, 2M + 1 \over h\,\right\rfloor -\left\lfloor\, 2M \over h\,\right\rfloor\,\right) $$ and looking for a way to ...
1
vote
1answer
59 views

prime division problem

$a,b,c \in$ {0,1,2,...,9} with at least one of $a,b,c$ nonzero. Prove that the six-digit integer $abcabc$ is divisible by at least 3 distinct primes. My thinking is not to use induction as there is ...
1
vote
1answer
34 views

Laws of equivalence needed to prove $\;q \leftrightarrow (¬p ∨ ¬q) ≡ (¬p ∧ q)\;?$

I'm not sure which laws should be applied and how I can tell for myself how to discern which laws I should use - any and all help is appreciated.
0
votes
0answers
7 views

Histogram Separation Energy Equation

I am working in level set method, specially Lankton method paper. I try to implement Histogram Separation (HS) Energy problem (Part III.C). It based on Bhattacharyya to control the evolution of ...
0
votes
0answers
48 views

Prove that $f: \Bbb R \setminus \{2 \} \to \Bbb R \setminus \{3 \}$ is bijective

I wanna know how can I have a formal proof for this one $$f: \Bbb R \setminus \{2 \} \to \Bbb R \setminus \{3 \}.$$ I understand that for functions like this $f(x)=2x+1$. I can know if its is ...
3
votes
0answers
34 views

A probability of a monochromatic cycle on a randomly colored lattice graph.

Let $G$ be an undirected $6 \times 6$ lattice graph. The $36$ vertices of $G$ are each randomly colored with one of $5$ colors with equal probability. Such a coloring is called "successful" if and ...
0
votes
0answers
16 views

discrete-time vs. continuous-time energy

Could any one please explain why the energy of a continuous pulse shape is larger than its discrete-time samples by a factor of bit period $T$? Thank you, Elnaz
0
votes
1answer
12 views

How many ways between 2000 and 5000 can be written from the digits 2,3,4,5,7 if: a. no digit is repeated b. digits must be repeated?

How many ways between 2000 and 5000 can be written from the digits 2,3,4,5,7if: a. no digit is repeated b. digits must be repeated?