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
1
vote
1 answer

The squares of an $8 × 8$ chessboard are colored black or white.

Prove that no matter how we color the chess board, there must be two L-regions that are colored identically. Explanation: An L-region is a collection of $5$ squares in the shape of a capital L. Such a region includes a square (the corner of the L)…
UH1
  • 343
1
vote
2 answers

What is the value of $\sum_{i=1}^n(-1)^{i+1}i(i+1)$?

$$\sum_{i=1}^n(-1)^{i+1}i(i+1)$$ I know $$\sum_{i=1}^ni(i+1)=\frac{n(n+1)(n+2)}3$$ but not for the first expression. Thank you in advance and I'm not a mathematician or math student so just ask me if any information is needed.
Dharmik Gadhiya
  • 49
1
vote
2 answers

cantor diagonalization method for proving infinity of real numbers

Cantor Diagonalization method for proving that real numbers are strictly uncountable suggests to disprove that there is a one to one correspondence between a natural number and a real number. However, The natural number and the real numbers both…
mathmaniage
  • 596
1
vote
1 answer

Highest power of a prime which divides an integer

The question is the following: "Which is the highest power of 18 that divides 190! ?" I seem to be under the impression that I don't know the "formula" correctly as this is my solution (which is so far wrong). $18=3^22$ So I thought we'd look at…
Linus Jensen
  • 35
1
vote
3 answers

Proving if $d_0$ is the smallest positive integer in $S$ then $d_0 = \gcd(a,b)$

I would appreciate hints to this. I've done part (a) but am unconfident. Wondering how I could approach part (b) Question's comment -- The aim of this question is to use the Division Algorithm and the definition of greatest common divisor (gcd) to…
Twenty-six colours
  • 1,881
1
vote
1 answer

Are there any methods to represent integers in forms like $2^k$*(odd number)?

I recently encountered this form of representation of integer numbers: $a_j=2^{k_j}q_j$, where $k_j$ is a non negative integer and $q_j$ is odd. My question is from where one can get idea of representing integers in this kind of forms?
user146551
  • 103
  • 5
1
vote
2 answers

Strong mathematical induction to prove $n=4x+5y$

Use the principle of strong mathematical induction to prove that if $n\in\mathbb N, n\geq12$ , then there exist non-negative integers $x$ and $y$ such that $n=4x+5y$.
pppp
  • 11
1
vote
1 answer

Proof By Contradiction Question

I have a question where I have to prove that $x + y$ is not a multiple of $9$, assuming that $x$ is a multiple of $9$ and $y$ is not a multiple of $3$. I know I can just substitute values to prove this, but I'm trying to do it algebraically. I was…
Broadsword93
  • 567
  • 6
  • 21
1
vote
0 answers

Simplify Operations on a List

Assume we have a list of objects: (A B C D) Also, that we can perform operations on this list. There could be any number defined (insert, delete, move, swap, etc), but only insert and delete are required to transform any list into any other. For…
Phil Kulak
  • 111
  • 1
1
vote
1 answer

Prove that $P(K)$ is the disjoint union of $P(S)$ and $X=\{T \subset K : x \in T\}$

EDIT:Let $S$ be any finite set and suppose $x \notin S$. Let $K=S \cup \{x\}$. 1.Prove that $P(K)$ is the disjoint union of $P(S)$ and $X=\{T \subset K : x \in T\}$. That is, show that $P(K) = P(S) \cup X$. 2.Prove that every element of $X$ is the…
user7478
  • 21
1
vote
1 answer

How to prove this expression?

It's from a programming language. "%' here is a modulo operation. (a * 2^32 + b) % c = (((a % c) * (2^32 % c)) + b) % c
accme
  • 111
1
vote
2 answers

Partial Order least and greatest elements

Prove that the following relation on the set of all nonempty subsets of $\{a,b,c,d\}$ is an order, draw its diagram, find all the maximal, minimal, least and greatest elements: $(x,y)\in R$ if and only if $x$ is a subset of $y$ How do I determine…
Aaron
  • 551
1
vote
1 answer

Extended Euclidean theorem

Let $a$ and $b$ be two numbers whose $\gcd{(a,b)}=ax+by$. How do I find $x$ and $y$? I did it like this. There is a $c$ which is a multiple of $\gcd{(a,b)}$ . Then $c=d \gcd{(a,b)}=d(ax+by)$ . Then I used this equation and the above most equation to…
User14229754
  • 11
1
vote
2 answers

Working Rates Problem 2

The boat hit something, which caused a hole in the boat. Water is leaking in at a consistent rate and some has already gathered when the hole is detected. At this stage, twelve men of the same skill can make the boat dry in 3 hours, while five men…
Valerie
  • 95
1
vote
2 answers

What is the minimum value of $\frac{a_1}{a_2} + \frac{a_2}{a_3} +\cdots + \frac{a_n}{a_1} $

Let $a_1,a_2,\cdots,a_n$ are positive real numbers. Question: what is the minimum value of $$\frac{a_1}{a_2} + \frac{a_2}{a_3} +\cdots + \frac{a_n}{a_1} $$ Thought: I have no clue how to proceed. Tried some standard inequalities but in vain.
Akash Banerjee
  • 371
1 2 3
…
99 100