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

learn more… | top users | synonyms

0
votes
0answers
3 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
11 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
0answers
21 views

How to find the approximate basic frequency or GCD of a list of numbers?

I could't actually summarize the question in the title, so I'll explain my situation. I want to tell the integer numbers which act as the best approximate basic frequencies of a list of real numbers: ...
2
votes
1answer
303 views

Recurrence Relation, Discrete Math problem(Homework)

There is a disk, separated into n sections, as indicated in the graph. For each section, you can paint it with one color out of four: Red, Yellow, Blue, Green. The rule is adjacent sections can't have ...
0
votes
0answers
7 views

Finding Sub-Array Pairs From Array

Take the following array of integers: [60, 45, 30, 45, 45, 5, 60, 45, 30, 30, 45, 60, 60, 45, 30, 30, 60, 30, 30] They need to be sorted into pairs of sub-arrays. The first sub-array in each pair ...
1
vote
2answers
56 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.
4
votes
5answers
185 views

$A \oplus B = A \oplus C$ imply $B = C$?

I don't quite yet understand how $\oplus$ (xor) works yet. I know that fundamentally in terms of truth tables it means only 1 value(p or q) can be true, but not both. But when it comes to solving ...
1
vote
1answer
22 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 ...
-3
votes
1answer
30 views

CONFUSE about this asgmnt [on hold]

How many nonzero entries does the matrix representing the relation R on $A=\{1,2,3,\ldots,20\}$ consisting of the first $20$ positive integers have if $R=\{(a,b) \mid a >b\}$?
2
votes
0answers
43 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 ...
1
vote
3answers
47 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 ...
2
votes
1answer
31 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 ...
33
votes
0answers
761 views

Why are asymptotically one half of the integer compositions gap-free?

This is a longish post about something that has been haunting me for a while about a kind of restricted composition, namely gap-free and complete compositions. First, I will define the terms that are ...
3
votes
1answer
42 views

Is it possible to find plaintext from ciphertext if (n) and (a) are known?

I have a couple of questions pertaining to a RSA problem. I need to decipher some ciphertext and find out what the original plaintext was. n = 2537 and a (or the exponent) = 11. Encrypting function: ...
0
votes
1answer
42 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
90 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
307 views

Principle of Inclusion and Exclusion

Annually, the 65 members of the maintenance staff sponsor a “Christmas in July” picnic for the 400 summer employees at their company. For these 65 people, 21 bring hot dogs, 35 bring fried chicken, 28 ...
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
1answer
40 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 ...
1
vote
2answers
328 views

Proving two numbers $q1, q2$ are relatively prime, related to the the $gcd(a,b)$

$a,b > 1$ and are integers, and $g: = gcd(a,b)$ is their greatest common divisor. Show that if $a= g * q1$ and $b = g * q2$, then $q1$ and $q2$ are relatively prime.
2
votes
3answers
52 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 ...
0
votes
3answers
40 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 ...
3
votes
2answers
397 views

Linear Homogeneous Recurrence Relations and Inhomogenous Recurrence Relations

I'm having some difficulty understanding 'Linear Homogeneous Recurrence Relations' and 'Inhomogeneous Recurrence Relations', the notes that we've been given in our discrete mathematics class seem to ...
-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?
1
vote
1answer
38 views

Proving $n^2$ is even whenever $n$ is even via contradiction?

I'm trying to understand the basis of contradiction and I feel like I have understood the ground rules of it. For example: Show that the square of an even number is an even number using a ...
2
votes
0answers
19 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
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
33 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 ...
-1
votes
1answer
29 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, ...
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
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!
3
votes
1answer
30 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
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 ...
0
votes
1answer
35 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 ...
1
vote
1answer
800 views

Sets induction problem (complement of intersection equals union of complements)

Let $n\ge 2$ and $A_1,\dots,A_n$ be sets in some universe $S$. In this problem we will give a proof by induction of the identity $$\left(\bigcap_{i=1}^nA_i\right)^c=\bigcup_{i=1}^nA_i^c\;.$$ ...
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 ...
1
vote
1answer
31 views

I want to prove this identity involving the binomial coefficients

Can you help me prove the following identity? I know it holds because I simulated it. For positive integers $n,m,k$ and for $i=0,\ldots,n$ and for $n \leq m$ we have: $$\sum_{j=0}^i (-1)^{i+j}\binom ...
1
vote
1answer
207 views

compatible total order of hasse diagram

So I was assigned this problem for homework and I was able to all of them except for part D I would really appreciate any help or hints I have no clue where to ...
1
vote
1answer
202 views

Prove that Idempotent property of lattices follows from commutative, associative and absorption property.

I tried but I am not able to prove this. I am able to prove $a+a=a$ but not $a\cdot a=a$. This is what i did so far: $$a+(a\cdot b)=a+a=a.$$ Thus $a+a=a$.
0
votes
2answers
732 views

Colored ball probability [on hold]

A triangular box contains five differently colored balls: red (R), green (G), blue (B), white (W), and yellow (Y). Define an appropriate sample space to study the outcome of an experiment where a ...
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?
0
votes
4answers
70 views

Number theory divisibility - simple way to prove this is prime?

Suppose that $y$ is a positive integer, and $z$ is the largest factor of $y$ such that $z<y$, then let $x=y/z$. Prove that $x$ must be a prime number. Is there a simple way to solve this? It ...
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 ...
-3
votes
2answers
44 views

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

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 [closed]

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).