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.

learn more… | top users | synonyms

6
votes
9answers
655 views

How to prove $\left \lceil \frac{n}{m} \right \rceil = \left \lfloor \frac{n+m-1}{m} \right \rfloor$?

everybody, how can I prove that, for natural $m$ and $n$, $$ \left \lceil \frac{n}{m} \right \rceil = \left \lfloor \frac{n+m-1}{m} \right \rfloor \; ? $$ Thanks a lot.
6
votes
4answers
2k views

Prove the cuberoot of 2 is irrational

I need to prove the cube root is irrational. I followed the proof for the square root of $2$ but I ran into a problem I wasn't sure of. Here are my steps: By contradiction, say $ \sqrt[3]{2}$ is ...
6
votes
1answer
824 views

In a group of 26 people, is it possible for each person to shake hands with exactly 3 other people?

In a group of 26 people, is it possible for each person to shake hands with exactly 3 other people? Does anybody know how to solve this?
6
votes
3answers
6k views

How many options are there for 15 student to divide into 3 equal sized groups?

How many options are there for 15 student to divide into 3 equal sized groups? Now i know the soultion is $\;\dfrac {15!}{5!5!5!3!}\;$ but i can't understand why. Can anyone please enlighten me?
6
votes
2answers
1k views

A number is a perfect square if and only if it has odd number of positive divisors

I believe I have the solution to this problem but post it anyway to get feedback and alternate solutions/angles for it. For all $n \in \mathrm {Z_+}$ prove $n$ is a perfect square if and only if $n$ ...
6
votes
3answers
153 views

Does $a\mid(bc)$ imply that $a\mid b$ or $a\mid c$?

Does $a\mid(bc)$ imply that $a\mid b$ or $a\mid c$? Can someone elaborate on this a bit?
6
votes
1answer
216 views

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?
6
votes
5answers
7k views

Number of relations that are both symmetric and reflexive

Consider a non-empty set A containing n objects. How many relations on A are both symmetric and reflexive? The answer to this is $2^p$ where $p=$ $n \choose 2$. However, I dont understand why this is ...
6
votes
6answers
168 views

What's the result? $1/i=?$, where $i=\sqrt{-1}$ [duplicate]

I just had my first math class in the university, and I understood everything pretty well, but I think I have misread this one because I read that the result is $-1$. Thanks for your answers!
6
votes
6answers
1k views

Quantifiers, predicates, logical equivalence

I am asked if $(\exists x) (P(x) \rightarrow Q(x))$ and $\forall x P(x) \rightarrow \exists xQ(x)$ are logically equivalent. I don't think they are but how will I prove it? Am I supposed to use ...
6
votes
5answers
1k views

discrete math book suitable for younger person?

When I took discrete math as an adult I realized that this was a subject I would have enjoyed and done well at much earlier in life, even in my early teens. Does anyone know if there are good books, ...
6
votes
2answers
2k views

What is the difference between necessary and sufficient conditions?

If $\quad p \implies q\quad $ ($p$ implies $q$), then $p$ is a sufficient condition for $q$. If $\quad \bar p \implies \bar q \quad$ (not $p$ implies not $q$), then $p$ is a necessary condition for ...
6
votes
3answers
411 views

What does the notation $\binom{n}{i}$ mean?

What do the parentheses next to the summation involving the binomial coefficients mean? Like this: $$\sum _{i=0}^{n} \binom{n}{i}a^{(n-i)}b^i=\left(a+b\right)^n $$
6
votes
3answers
19k views

Largest prime factor of 600851475143 [duplicate]

I'm trying to use a program to find the largest prime factor of 600851475143. This is for Project Euler here: http://projecteuler.net/problem=3 I first attempted this with the code that goes through ...
6
votes
2answers
461 views

Distribution of points on a rectangle

Let $R$ be a rectangular region with sides $3$ and $4$. It is easy to show that for any $7$ points on $R$, there exists at least $2$ of them, namely $\{A,B\}$, with $d(A,B)\leq \sqrt{5}$. Just divide ...
6
votes
3answers
133 views

Help with math induction

Prove that $n(n+1)(n+2)$ is divisible by $6$ for all integers. I'm not sure if I'm suppose to use division into cases or not. Our teacher ran out of time to go over this in class, and this is on ...
6
votes
2answers
341 views

Is this expression even a function?

This is from Discrete Mathematics and its Applications My question is on 22c. From the book, I inferred from the question that all of the listed mathematical expressions are functions. Is the ...
6
votes
2answers
772 views

Proof that no polynomial with integer coefficients can only produce primes [duplicate]

Doing a discrete math review and am trying to solve problem 1.6 in the text found here: http://courses.csail.mit.edu/6.042/fall13/ch1-to-3.pdf - I believe I've gotten parts (a) and (b) correctly, but ...
6
votes
3answers
664 views

How many 3-subsets of $\{1,2,\ldots,10\}$ contain at least two consecutive integers?

Let A = {1, 2,..., 10}. How many three-element subsets of A contain at least two consecutive integers? I believe there are $\displaystyle \tbinom{10}{3}$ total 3-subsets of A. To find the subsets ...
6
votes
3answers
1k views

Looking for induction problems that are not formula-based

I am looking for problems that use induction in their proofs such as this one: Given a checker board with one square removed you can cover it with L-shaped pieces made out of three squares. This ...
6
votes
5answers
545 views

trivial but non-trivial equivalence relations

Define a binary relation $R$ on a set $A$ by saying $xRy$ iff $x$ and $y$ have the same whatever. "Whatever" is of course some specified function on $A$. This is a "trivial" equivalence relation: ...
6
votes
2answers
80 views

${n}\choose {r}$ =$ 8$ Is there any way to find such $n$ and $r$?

Let ${n} \choose {r}$ = $8$. Is there any other choice of $n$ and $r$ except $8$ and $1$, $8$ and $7$ ? In general how to check that existence is guaranteed or not?
6
votes
4answers
136 views

Pigeon Hole. 80 numbered balls

We have $80$ numbered balls(From $1$ to 80).Among which are $45$ blue and $35$ orange. Prove that at least two blue balls differ by $9$. For example $13$ and $22$ or $69$ and $78$. So they can differ ...
6
votes
1answer
240 views

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

This is a follow up to a question I had asked earlier about a linear recurrence relationship satsified by $\lfloor(1+\sqrt{5})^n\rfloor$. I messed up there, and I actually meant to ask about ...
6
votes
2answers
749 views

Is there a relation that is irreflexive, anti-symmetric and not transitive?

from the set $\{a, b, c, d\}$? Of the one's I have tried, it at best is two of the three, but never all.
6
votes
3answers
151 views

Why is the function $f(x)=x^3 \pmod{10}$ periodic with this strange property?

I've noticed that the function $f(x)=x^3 \pmod{10}$ is periodic. For example, listing mod(x^3,10) we get: ...
6
votes
2answers
5k views

Correct way to calculate numeric derivative in discrete time?

Given a set of discrete measurements in time $x_t, t \in \{0,\Delta t, 2\Delta t,\ldots,T-\Delta t,T\}$, what is the correct way to compute the discrete derivative $\dot x_t$. Is it more correct to ...
6
votes
5answers
988 views

Inherently discrete concepts

Are there any concepts which are naturally defined only for the integers and so far has resisted any attempts at extension to other fields such as rationals or reals? Does not meet criteria: ...
6
votes
1answer
115 views

A group acting on colourings of a set

Suppose I have a set $L$ with some permutation group $G$ defined upon it, which I think of as a symmetry group. I want to consider the set $F$ of functions $f: L \to C$, for some set $C$. It seems ...
6
votes
3answers
87 views

Show that $9\mid a^2$ if given that $6\mid a$

Does this prove I made seem correct to show that if $6$ divides $a$ then $9$ divides $a^2$ If $6\mid a$, then $a = 6k$ (k is some integer). Then $a^2 = 36k^2 = 9(4k^2)$. Which means that $9\mid ...
6
votes
5answers
6k views

Big-O Notation - Prove that $n^2 + 2n + 3$ is $\mathcal O(n^2)$

I'm taking a course in Discrete Mathematics this summer, and my book doesn't offer a very good explanation of Big-O notation. I understand that if $f(x)$ is $\mathcal O(g(x))$ it means that there ...
6
votes
2answers
155 views

Construction of the projective plane over $\mathbb{F}_3$

I have a question about constructing projective plane over $\mathbb{F}_3$. We first establish seven equivalence classes $P= \{ [0,0,1], [0,1,0], [1,0,0], [0,1,1], [1,1,0], [1,0,1], [1,1,1] \}$. ...
6
votes
2answers
519 views

Planar graphs & Spanning trees

Does there exist a planar graph whose edges can be coloured either red, green or blue in such a way that the red edges form a spanning tree, the green edges form a spanning tree, and the blue edges ...
6
votes
1answer
4k views

Find a big-O estimate for $f(n)=2f(\sqrt{n})+\log n$

While self-studying Discrete Mathematics, I found the following question in the book "Discrete Mathematics and Its Applications" from Rosen: Suppose the function $f$ satisfies the recurrence ...
6
votes
3answers
1k views

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?
6
votes
3answers
114 views

Numbering students inequality problem

Ten students are sitting around a campfire. A teacher randomly assigns each student a different number from 1-10. Another teacher assigns a new number to each student with the requirement that the new ...
6
votes
2answers
111 views

Show by induction that $2!4!6!…(2n)! \geq ((n+1)!)^n$

Show by induction that $2!4!6!...(2n)! \geq ((n+1)!)^n$ I stuck at $((n+1)!)^n (2(n+1))! \geq ((n+1+1)!)^{n+1}$, but cant progress to next step It will be great in someone can demonstrate how to ...
6
votes
1answer
297 views

convoluted recurrence: $f(2n)=f(n)+f(n+1)+n, f(2n+1)=f(n)+f(n-1)+1$

For the recurrence relation: $f(0)=1$ $f(1)=1$ $f(2)=2$ $f(2n)=f(n)+f(n+1)+n\ \ \ (\forall n>1)$ $f(2n+1)=f(n)+f(n-1)+1\ \ \ (\forall n\ge 1)$ (the first numbers of the sequence are: 1, 1, 2, ...
6
votes
1answer
153 views

permutation and f(n) challenge

Suppose $f(n)$ be the number of permutation from set ${1,2,..,n}$ such that for each $ 1 \leq i \leq n$ we have: $ | \pi(i)-i| \leq 1 $. meaning of $ \pi(i)$ is an elements whose in place $i$ of ...
6
votes
3answers
385 views

Recurrence with varying coefficient

Problem 1 $$ {\rm f}\left(n\right) = \frac{1}{n}\, \left[{\rm f}\left(n - 1\right)k_{0} + {\rm f}\left(n-2\right)k_{1}\right]\tag{1} $$ ( This can also be written as ${\rm Q}\left(n\right) = ...
6
votes
2answers
135 views

If $x+\frac{1}{x}$ is a natural number, then $x^{n}+\frac{1}{x^{n}}$ is a natural number for all $n\in \mathbb{N}.$

I am trying to solve the following exercise. If $x+\frac{1}{x}$ is a natural number, then $x^{n}+\frac{1}{x^{n}}$ is a natural number for all $n\in \mathbb{N}.$ Here what I've done. If ...
6
votes
1answer
403 views

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

For all integers b, c, and d, if x is rational such that x^2+bx+c=d, then x is an integer

Prove or disprove the following statment: For all integers b, c,and d, if x is a rational number such that $x^2+bx+c=d$, then x is an integer. This is a homework question from the book Discrete ...
6
votes
3answers
111 views

Solve recursive equation $ f_n = \frac{2n-1}{n}f_{n-1}-\frac{n-1}{n}f_{n-2} + 1$

Solve recursive equation: $$ f_n = \frac{2n-1}{n}f_{n-1}-\frac{n-1}{n}f_{n-2} + 1$$ $f_0 = 0, f_1 = 1$ What I have done so far: $$ f_n = \frac{2n-1}{n}f_{n-1}-\frac{n-1}{n}f_{n-2} + 1- [n=0]$$ I ...
6
votes
2answers
222 views

Sipser Pumping Lemma Clarification

In a Theory of Computation book I am using, the explanation of Pumping Lemma is not bad, but some parts of it are not clear to me. Here is the Definition of Pumping Lemma: If A is a regular ...
6
votes
1answer
858 views

How many possible arrangements for a round robin tournament?

How many arrangements are possible for a round robin tournament over an even number of players $n$? A round robin tournament is a competition where $n = 2k$ players play each other once in a heads-up ...
6
votes
1answer
367 views

Backwards induction to show that $x_1\cdots x_n \leq ((x_1+\cdots+x_n)/n )^n$

This question is from "Concrete Mathematics", by Knuth. Sometimes it's possible to use induction backwards, proving things from $n$ to $n-1$ instead of vice versa! For example, consider the ...
6
votes
1answer
892 views

Adapted Towers of Hanoi from Concrete Mathematics - number of arrangements

I have a doubt concerning an exercise from Chapter 1 of "Concrete Mathematics". Actually, my doubt is in one exercise (exercise 3), but, since it depends on the previous exercise (2), I'm including it ...
6
votes
1answer
398 views

Expressing Powers in Terms of Falling Powers

The falling power $n^\underline{k}$ (read $n$ to the falling $k$) is defined as follows: $$n^\underline{k}=n(n-1)(n-2)\cdots(n-k+1)$$ These are important in discrete calculus because their finite ...
6
votes
2answers
4k views

How many ways are there to choose 10 objects from 6 distinct types when…

(a) the objects are ordered and repetition is not allowed? (b) the objects are ordered and repetition is allowed? (c) the objects are unordered and repetition is not allowed? (d) the objects are ...