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

Prove that if both $a$ and $b$ divided by $n$ give remainder 1, then $ab$ divided by $n$ gives remainder 1.

Here's is my approach: $a=q_1n+1$ $b=q_2n+1$ $ab = q_1q_2n^2+q_1n+q_2n+1=(q_1q_2n+q_1+q_2)n+1$ I'm not sure if this is sufficient, and if so, whether there's a better proof.
Mel
  • 87
6
votes
3 answers

Discrete Mathematics (Prove or Find a Counterexample of a Proposition)

Let f : X → Y be a function. For each of the following propositions, prove or find a counterexample. (In constructing a counterexample, please specify what your domain and codomain are as well as the function itself.) If S,T ⊆ X then f(S ∩ T) =…
I'm Hungry
  • 181
6
votes
1 answer

Show the distance does not exceed $\sqrt{2}$.

Choose any ten points from the interior of a square with side length $3$. Show that the distance of some pair of these points does not exceed $\sqrt{2}$. Can someone help me?
CSQ
  • 71
6
votes
5 answers

How can I show that $4^{1536} - 9^{4824}$ can be divided by $35$ without remainder?

How can I show that $4^{1536} - 9^{4824}$ can be divided by $35$ without remainder? I'm not even sure how to begin solving this, any hints are welcomed! $$(4^{1536} - 9^{4824}) \pmod{35} = 0$$
Ilan Aizelman WS
  • 4,128
6
votes
1 answer

Recurrence relation satisfied by $\lfloor(1+\sqrt{5})^n\rfloor$

Let $L(n)=\lfloor(1+\sqrt{5})^n\rfloor$. What kind of a linear recurrence is satisfied by $L(n)$? I have no idea how to go about this, because of the presence of the greatest integer function. Please feel free to retag it as I kept getting an error…
Derek Scavo
  • 1,983
6
votes
1 answer

Prove parity of binomial coefficient

The task is to find the parity of ${2n\choose 2k+1}$ where $n,k\in\mathbb{N}$. How can I do that?
xan
  • 1,443
  • 1
  • 21
  • 28
6
votes
4 answers

Compute $ \sum\limits_{k=0}^{m}(-1)^k {n \choose k} {n \choose m-k}$ and $\sum\limits_{A,B\subseteq X} |A\cup B|$ for some given finite set $X$

I've got a problem with deducing closed-form expressions for sums: $1) \ \sum_{k=0}^{m}(-1)^k {n \choose k} {n \choose m-k}$ $2) \ \sum_{A,B\subseteq X} |A\cup B|$ where $|X|=n$ Can anyone help me? In 1) I have no idea. I can use identity…
xan
  • 1,443
  • 1
  • 21
  • 28
6
votes
4 answers

Prove that every amount of postage of 12 cents or more can be formed using just 4-cent and 5-cent stamps.

I know this question has been posted before, there is a solution in my text-book for this question and also this is posted on so many websites with full solution but I still don't understand. So can someone please help me? BASIS STEP: We can form…
Diana
  • 61
5
votes
1 answer

How many natural numbers less than 1,000,000,000 are multiples of 5 or 7?

I used the Inclusion-Exclusion Principle and I got $200,000,000$ (multiples of $5$ less than $10^9$, obtained by $10^9 / 5$) + $124,857,142$ ( multiples of $7$ less than $10^9$, obtained by $10^9 / 7$ and round it down) - $28,571,428$ ( multiples of…
bodygued
  • 297
5
votes
4 answers

When numbers of $1$ to $1000$ are written out in decimal notation. How many digits are $1$?

Question: When numbers of $1$ to $1000$ are written out in decimal notation. How many digits are $1$? Attempt: $$1XX\\ X1X\\ XX1$$ The count of $1$ for the types above are, $${{3}\choose{1}}*9*9$$ $$1000$$ Which is just one $1$. $$1X\\11\\X1$$ Which…
JoeyAndres
  • 1,269
5
votes
3 answers

How many of the 9000 four digit integers have four digits that are increasing?

How to find the number of distinct four digit numbers that are increasing or decreasing? The correct answer is $2{9 \choose 4} + {9 \choose 3} = 343$. How to get there?
Belphegor
  • 1,268
  • 6
  • 27
  • 51
5
votes
3 answers

Find all integer solution

Find all integer solutions such that $$a+1|2a^2+9$$ Solution. I could solve this by writing $$\frac{2a^2+9}{a+1}=2a-2+\frac{11}{a+1}.$$ So, the only integer solution for the last equation are $a=10, a=-12.$ But, i want to get a solution using…
Jeybe
  • 1,222
5
votes
3 answers

Is it true, that every prime (except 2) can be found as a divisor of enough long series of 1-s?

I suspect, that the prime divisors of the series of 1, 11, 111, 1111, ... 1...1 will contain every primes. But this is an intuitive hypothesis only. Somebody knows, if it is so? How could it be proven/disproven?
peterh
  • 2,683
5
votes
1 answer

discrete math- picking points inside an equilateral

Suppose 5 points are chosen at random inside an equilateral triangle with sides of length 1. Show that there is at least one pair of these points that are separated by a distance of at most 1/2. I can't figure this out, this applies to pigeon hole…
Roy Kesserwani
  • 383
5
votes
2 answers

prove that one of the digits $1,2,\dots,9$ occurs infinitely often in the decimal expansion of $\pi$

prove that one of the digits $1,2,\ldots,9$ occurs infinitely often in the decimal expansion of $\pi$. you may use without proof the fact that $\pi$ is irrational. It is recommended using proof by contradiction. My attempt: Supppose that $1$ does…
user2510809
  • 535
1 2 3
…
99 100