Mathematics Stack Exchange
Mathematics 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.

Discrete mathematics is not the name of a branch of mathematics, like number theory, algebra, calculus, etc. Rather, it's a description of a set of branches of math that all have in common the feature that they are "discrete" rather than "continuous".

The term "discrete mathematics" is therefore used in contrast with "continuous mathematics," which is the branch of mathematics dealing with objects that can vary smoothly (and which includes, for example, calculus). Whereas discrete objects can often be characterized by integers, continuous objects require real numbers.

Though there cannot be a definite number of branches of Discrete Mathematics, the following topics are almost always covered in any study regarding this matter −

  • Sets, Relations and Functions
  • Mathematical Logic
  • Group theory
  • Counting Theory
  • Probability
  • Mathematical Induction and Recurrence Relations
  • Graph Theory
  • Trees
  • Boolean Algebra

For an overview, see the Wikipedia entry on Discrete mathematics.

and http://www.cs.yale.edu/homes/aspnes/classes/202/notes.pdf

Consider using a more specific tag instead, such as: , , , , , , , , etc.

32903 questions
9
votes
4 answers

Given $51$ natural numbers whose sum is $100$, show that it is possible to split them to $2$ sets such that each of them is $50$.

Given $51$ natural numbers whose sum is $100$. Show that it is possible to split them to $2$ sets such that for each the sum is $50$. Also, another interesting question is, what happens instead of natural numbers we have integers? Note: Assumption…
Ilan Aizelman WS
  • 4,128
9
votes
2 answers

What's wrong with this truth table for implication?

I completed this truth table in an assignment for an implication and got a few of the outputs wrong. I was wondering if anyone can help explain why I got them wrong. This is part of the truth table that I got wrong: PLEASE FORGIVE THE TYPO IN TABLE…
Broadsword93
  • 567
  • 6
  • 21
9
votes
4 answers

"If A then B" in Venn (or Euler) Diagrams

How can I represent "If A then B" in a diagram? I thought it would be a simple subset like $A ⊂ B$. However this material says that If $A$ then $B$ $=$ $A^c ∪ B$. Now I am confused.
Hyunjun Kim
  • 93
8
votes
4 answers

Let $a_n$ be the $nth$ term of the sequence $1, 2, 2, 3, 3, 3, 4, 4, 4, 4, \dots$

Question:Let $a_n$ be the $nth$ term of the sequence $1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6\dots$, constructed by including the integer $k$ exactly $k$ times. Show that $a_n = \lfloor \sqrt{2n} +…
JoeyAndres
  • 1,269
8
votes
3 answers

Coin problem with $6$ and $10$

I am doing a coin problem where: In a city where you only have denominations in $6$ and $10$. What is the largest value that this city cannot pay? In another problem that my teacher showed me, where instead the numbers were $5$ and $9$, we…
A A
  • 585
8
votes
2 answers

Can somebody explain to me Cantor's diagonalization argument?

Like..can somebody explain this to me as if I was a 5 year old or something? Every explanation I read repeats the same exact thing that I simply do not understand. This is what my book says: "The real numbers between 0 and 1 can be listed in some…
FrostyStraw
  • 1,045
8
votes
4 answers

"How many different integers does this give us?"

How many unique integers can you get from $\lceil2012/n\rceil$ where $n$ is a positive integer? I don't know at all where to begin to approach this problem. I thought it maybe had something to do with which factors the number has or anything like…
Andre Hansen
  • 83
8
votes
3 answers

Knight and Knaves logic problem

From "Discrete mathematics and its applications", a book by Kenneth H. Rosen, chapter 1.1 exercise 57, goes as: A says "I am a knave or B is a knight" and B says nothing. Knight always tell the truth and knaves always lie. We are to determine of…
Filip Markoski
  • 369
8
votes
6 answers

How many equivalence classes does $R$ have?

Let $A=\{a,b,c,d,e\}$. Suppose $R$ is an equivalence relation on $A$. Suppose also that $aRd$ and $bRc$, $eRa$ and $cRe$. How many equivalence classes does $R$ have? My thoughts: (Not sure if I have the right idea...) UPDATED/EDITED Since $R$ is an…
laser295
  • 253
8
votes
1 answer

$\{1, 2, . . . , 49\}$ is partitioned into $3$ subsets. Prove that at least $1$ of them contains $3$ different numbers $a,b,c$ such that $a+b=c$

As the title says, I'm asked to prove that at least one of the subsets contains three different numbers $a, b$ and c such that $a + b = c$. I tried to prove it but it is more difficult than it initially seemed to be. How would you do it? Edit: The…
Rr.Mar
  • 91
8
votes
3 answers

Subset vs. Proper subset

I'm a bit confused on the wording here.. For example: $$A = \{c, d, f, g\}$$ $$C = \{d, g\}$$ Is $C$ "subset" of $A$? Obviously, yes. But.. the proper subset states that: If $C$ and $A$ are any sets, then $C$ is a proper subset of $A$ if and only if…
dendritic
  • 315
8
votes
2 answers

Is the given relation transitive?

Consider the relation: $$R = \{(a,b), (a,c), (c,c), (b,b), (c,b), (b,c)\}$$ on the set $A = \{a,b,c\}$. Is $R$ transitive? I said no because $$[(c, c) \wedge (a, c)] \Longrightarrow (c,a)$$ is a false statement. Is my reasoning correct?
Hare Krishan
  • 221
7
votes
4 answers

Find the recurrence relation for the number of bit strings that contain the string $01$.

Question:Find the recurrence relation for the number of bit strings that contain the string $01$. Attempt: Since $01$ can appear in a lot of places, I focused on instances without $01$ first. Bit strings without $01$ in a bit string of length $n$.…
JoeyAndres
  • 1,269
7
votes
4 answers

Uniqueness Proof, Discrete Math Help

While reading I came across Uniqueness Proofs. Where a theorem asserts the existence of a unique element with a particular property. In order to prove this two steps are needed, Prove existence and Prove Uniqueness. The example given is Show that if…
user2205293
  • 73
7
votes
2 answers

Show that if seven integers are selected from the first 10 positive integers

a) Show that if seven integers are selected from the first 10 positive integers, there must be at least two pairs of these integers with the sum 11. b) Is the conclusion in part (a) true if six integers are selected rather than seven? I don't know…
user112636
  • 311
  • 2
  • 8
  • 13
1
2
3
…
99 100