Discrete mathematics is the study of mathematical structures that are fundamentally discrete rather than continuous.

learn more… | top users | synonyms

6
votes
3answers
149 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
206 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
890 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
3answers
131 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
330 views

Watchdog Problem

I just came up with this problem yesterday. Problem: Assume there is an important segment of straight line AB that needs to be watched at all time. A watchdog can ...
6
votes
3answers
270 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
5answers
451 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
5answers
2k views

If a plane is divided by $n$ lines, then it is possible to color the regions formed with only two colors.

I am self-studying Discrete Mathematics, and there is the following exercise. (in Portuguese) A plane is divided by many lines. Show that it is possible to color the regions formed with only two ...
6
votes
3answers
730 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
3answers
6k views

Transitive Relations

For example, $$R = \{ (1,1),(1,2),(2,1),(2,2) \} \quad\text{for}\quad A = \{1,2,3\}.$$ This relation is symmetric and transitive. I understand that the relation is symmetric, but my brain does not ...
6
votes
1answer
234 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
290 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
147 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
1answer
107 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
81 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
2answers
94 views

Find a formula for $\sum\limits_{k=1}^n \lfloor \sqrt{k} \rfloor$

I need to find a clear formula (without summation) for the following sum: $$\sum\limits_{k=1}^n \lfloor \sqrt{k} \rfloor$$ Well, the first few elements look like this: $1,1,1,2,2,2,2,2,3,3,3,...$ ...
6
votes
2answers
141 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
378 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
3answers
2k views

Prove that if $2^n - 1$ is prime, then $n$ is prime for $n$ being a natural number

Prove that if $2^n - 1$ is prime, then $n$ is prime for $n$ being a natural number I've looked at http://math.stackexchange.com/a/19998 It is known that $2^n-1$ can only be prime if $n$ is ...
6
votes
1answer
3k 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
113 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
830 views

Proof of clockwise towers of Hanoi variant recursive solution

This is from one of the exercises in "Concrete Mathematics", and is something I'm doing privately, not homework. This is a variant on the classic towers of Hanoi, where all moves must be made ...
6
votes
4answers
105 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
3answers
2k views

What's the difference between a contrapositive statement and a contradiction? [duplicate]

I keep mixing them up, because they are very similar. Some contrapositives resemble some contradictions.
6
votes
2answers
124 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
2answers
833 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
102 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
1answer
317 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
6answers
942 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
311 views

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. ...
6
votes
4answers
2k views

Big-O notation Basics, is it related to derivatives?

I am having the hardest time with Big-O notation (I am using this Rosen book for the class I am in). On the surface, Big-O reminds me of derivatives, rate of change and what not; is this proper ...
6
votes
2answers
405 views

Elementary bound of binomial coefficient

I'm working my way through an Erdős paper from the sixties and some of the elementary bounds he claims seem to be just beyond my reach. The expression looks horrendous but maybe there is a clever ...
6
votes
1answer
155 views

eHarmony combinatoric question, probability that I should get at least 1 compatible match. [closed]

Ok.. (as I type this with a smirk on my face) - in all seriousness I am trying to figure out, given 29 degrees of compatibility and 40 million members if I should be getting at least 1 match a day. ...
6
votes
1answer
364 views

Find all permutations that commute with $\omega$=(1 9 7 10 12 2 5)(4 11)(3 6 8) in $S_{12}$

I'm asked in this exercise to find all permutations that commute with $\omega$=(1 9 7 10 12 2 5)(4 11)(3 6 8) in $S_{12}$. What I have so far: We could write $x$(1 9 7 10 12 2 5)(3 6 8)=(1 9 7 10 12 ...
6
votes
2answers
609 views

Looking for a bijective, discrete function that behaves as chaotically as possible

I need to write a coupon code system but I do not want to save each coupon code in the database. (For performance and design reasons.) Rather I would like to generate codes subsequent that are ...
6
votes
1answer
47 views

Does $K_{15,15}$ decompose into $K_{5,5}-C_{10}$ and $K_{5,5}-(C_6 \cup C_4)$ subgraphs?

Following on from this question: Q: Does $K_{15,15}$ decompose into $K_{5,5}-C_{10}$ and $K_{5,5}-(C_6 \cup C_4)$ subgraphs? or equivalently Q: Does there exist a $15 \times 15$ matrix ...
6
votes
1answer
317 views

A little fun with tournaments (graphs).

Assume $G$ is a tournament, i.e. a (finite) directed graph such that between any two vertices, $a$ and $b$, there is at least one edge in one of the two directions, $a\rightarrow b$ or $b\rightarrow ...
6
votes
1answer
205 views

Solve $\sum_{i=0}^k \binom{n}{i} = u$.

I would like to get as tight bounds as possible for $k$ from $\sum_{i=0}^k \binom{n}{i} =u $. In other words, the number of terms in the sum neeeded to get to $u$. We can assume that both $n$ and $u$ ...
6
votes
2answers
154 views

A function over the integers and its fixed points

Define $f:\mathbb{N}\rightarrow\mathbb{N}$ as follows, $f(n)$ is the number of times the digit "1" is needed if we were to write all integers between 1 and $n$ (inclusive) in base 10. So for example ...
6
votes
1answer
381 views

In any set of n different natural numbers, exists subset of more than n/3 numbers, such as there are no three numbers in it : a+b=c

I need to prove, that in any set of n different natural numbers, exists subset of more than n/3 numbers, such as there are no three numbers in it, one of which is the sum of two others. Can anyone ...
6
votes
1answer
389 views

What is the expression for putting $n$ indistinguishable balls into $k$ indistinguishable cells?

I'm looking for the expressions for the number of ways in which $n$ indistinguishable balls can be placed into $k$ indistinguishable cells, with No cell being empty Some cells being empty I knew ...
6
votes
1answer
794 views

Relation between different ways of accessing bernoulli numbers with matrices

First Variant: Bernoulli numbers can easily be expressed by linear algebra equations. For example just using the recursion formula $$\sum_{k=0}^{n-1}{n\choose k}B_k=0$$ which is equation (34) from ...
5
votes
9answers
622 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.
5
votes
3answers
245 views

Given 50 holes, what's the chance 2 balls fall into same hole

In a game, a ball can fall any of $50$ holes evenly spaced around a wheel. The chance that a ball falls into any particular hole is $\dfrac 1{50}.$ What is the chance $2$ balls circling the wheel at ...
5
votes
2answers
325 views

Predicate logic: “Everybody knows somebody who knows Alice”

I'm stuck on an undergraduate CS exercise: I am to translate "Everybody knows somebody who knows Alice" into predicate logic. I'm having trouble bending my head around it (being a complete beginner), ...
5
votes
4answers
204 views

Prove $\binom{n}{a}\binom{n-a}{b-a} = \binom{n}{b}\binom{b}{a}$

I want to prove this equation, $$ \binom{n}{a}\binom{n-a}{b-a} = \binom{n}{b}\binom{b}{a} $$ I thought of proving this equation by prove that you are using different ways to count the same set of ...
5
votes
3answers
749 views

How is “Some computer science majors take discrete math” not an implication?

"Some computer science majors take discrete math" S is the domain of all college students C(x) means "x is a computer science major" D(x) means "x takes discrete math" Can someone please explain why ...
5
votes
6answers
616 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 ...
5
votes
2answers
5k views

Strong Mathematical Induction: Why More than One Base Case?

I am trying to understand this example of strong induction. I know normal induction. In normal induction, if base case is true then we assume some number $n$ to be true. Afterwards, we prove $n+1$ is ...
5
votes
3answers
1k views

Domain, codomain, and range

This question isn't typically associated with the level of math that I'm about to talk about, but I'm asking it because I'm also doing a separate math class where these terms are relevant. I just want ...