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
3
votes
2 answers

Counting Problem (Sums of a set from 1 to 100)

In how many ways can you select two distinct integers from the set {1, 2, 3, . . . , 100} so that their sum is: (a) even? (b) odd? I'm studying for a discrete midterm this coming Monday and saw the following problem on a practice midterm my…
Chris T
  • 813
3
votes
3 answers

Finding the possible positions of chess knight mathematically relative to a given position

From this website I found the following question: A chess board’s 8 rows are labelled 1 to 8, and its 8 columns a to h. Each square of the board is described by the ordered pair (column letter, row number). (a) A knight is positioned at (d, 3).…
direprobs
  • 490
3
votes
1 answer

Prove $2^{X \cap Y \cap Z} = 2^X \cap 2^Y \cap 2^Z$ for any three sets $X, Y, Z$

Could anybody check my solution to this question please? Question: Prove $2^{X \cap Y \cap Z} = 2^X \cap 2^Y \cap 2^Z$ for any three sets $X, Y, Z.$ My solution: If $a \in 2^X \cap 2^Y \cap 2^Z$, then $a \in 2^X, a \in 2^Y, a \in 2^Z$. So $a \subset…
CrossGuard
  • 297
3
votes
1 answer

Using Euclid's algorithm to find Multiplicative Inverse 71 mod 53

I begin by writing out the recursion until a mod b == 0 53 -> 71-> 53-> 18-> 17 ->1 -> 0 to get in the form $sa+tn$ starting with $1 = 18-17$ I then substitute $17 = 53-(18\cdot2)$ this gives me $18\cdot3-53$ I then substitute $18 = (71-53)$ which…
Daniel Murphy
  • 281
3
votes
1 answer

Probability with pigeon hole principle

A gambler buys at least one lottery ticket everyday, maybe more. During the whole year he buys at most $400$ tickets. Show that during the year there exists a sequence of consecutive days for which the total number of tickets bought is…
Robert MingHao
  • 51
3
votes
2 answers

Prove by contradiction Irrational number

I Need to prove this by contradiction : If $a$ is Irrational then $\frac{2a-3}{2a+3}$ is Irrational. I did: Iff $p$ is Irrational, then $\frac{2a-3}{2a+3}$ is Rational and a Rational number can be written as $\frac{p}{q}$ where p and q are…
user290335
  • 930
3
votes
5 answers

How to write a definition of less than $<$?

I'm learning the fundamentals of discrete mathematics, and I have been requested to solve this problem: According to the set of natural numbers $$ \mathbb{N} = {0, 1, 2, 3, ...} $$ write a definition for the less than relation. I wrote this: $a <…
InfZero
  • 875
3
votes
1 answer

Number of ways to put $k$ balls in $n$ boxes

Compute the number of ways to spread $k$ identical balls over $n$ different cells (where $k \geq n$) with the condition that every cell will have at least one ball. So if $k=n$ then, we have only one option, because they're identical. otherwise,…
Ilan Aizelman WS
  • 4,128
3
votes
2 answers

Prove: if $a \equiv b \pmod 5$ then $2a \equiv 2b \pmod{5}$?

Prove only using of the definition of congruence: if $a \equiv b \pmod 5$ then $2a \equiv 2b \pmod{5}$? I have thought about the solution as follows: $2a \equiv 10k+2r \equiv 5 (2k) +2r$ ......(1) $2b \equiv 10l+2r \equiv 5 (2l) + 2r$ .....(2) both…
Coheen
  • 63
3
votes
5 answers

logics and proofs

This question is given in discrete mathematics by Kenneth Rosen. Each inhabitant of a remote village always tells the truth or always lies. A villager will only give a "yes " or a "No" response to a question a tourist asks. Suppose you are a…
srishti77714
  • 31
3
votes
3 answers

how does $p | (a^2 + b^2)$ force $p | b^2$

I have a question that reads: if $p | a$ and $p|(a^2+b^2)$, then $p | b$. In the solution menu it reads: since $p|a$, $p|a^2$. Now $p|a^2$ and $p|(a^2+b^2)$ forces $p|b^2$. we can conclude that $p|b$. I honestly have no idea how $p|(a^2+b^2)$ can…
夢のの夢
  • 186
3
votes
2 answers

Counterfeit Coin Problem - 8 Coins

How many weighings of a balance are necessary to determine if a coin is counterfeit among eight coins. The counterfeit coin is either heavier or lighter than the other coins. I understand the reasoning behind this problem when you know how the…
blues5938
  • 73
3
votes
3 answers

In how many ways can $25$ identical pens be distributed to four students with restrictions?

Use combinatorics to count how many ways can 25 identical pens be distributed to four students so that each student gets at least three but no more than seven pens. What I have done so far is look like it make sense but it doesn't work out I was…
Wongsakorn
  • 87
3
votes
2 answers

Prove Perfect square of the form 4k or 4k+1

So i want to prove that every perfect square is of the form 4k or 4k+1, can someone tell me how to do this. Really need help with this
Syed Naqi
  • 165
3
votes
4 answers

Number of squarefree positive integers less than $100$

An integer is called squarefree if it is not divisible by the square of a positive integer greater than $1$. Find the number of squarefree positive integers less than $100$. My attempt: I apply the inclusion-exclusion principle…
Nighty
  • 2,152
1 2 3
…
99 100