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

learn more… | top users | synonyms

4
votes
3answers
565 views

Questions on “All Horse are the Same Color” Proof by Complete Induction

The following has been bugging me, and I can't go to sleep until I resolve it. Here is a summary of the document on page 109 of http://courses.csail.mit.edu/6.042/spring12/mcs.pdf. False ...
4
votes
4answers
209 views

Determine whether $F(x)= 5x+10$ is $O(x^2)$

Please, can someone here help me to understand the Big-O notation in discrete mathematics? Determine whether $F(x)= 5x+10$ is $O(x^2)$
3
votes
1answer
79 views

Basis reduction and continued fractions

While reading several articles about lattice basis reduction I am left with a few questions. For one, I came across this piece of text Let $\alpha$ and $\beta \in \mathbb{R}$. Then there are two ...
3
votes
3answers
172 views

Any good books on Mathematics and Programming?

I've been on google for a while now searching for a good book on mathematics combined with programming, but either the level of math they're starting at is too high or the level of programming is too ...
0
votes
1answer
83 views

distinguishable and indistinguishable people and ticket offices

In how many ways we can arrange p people in the queue to the 5 ticet offices a) people are distinguishable ticket offices are distinguishable b) people are distinguishable ticket offices are ...
1
vote
1answer
92 views

Can someone help me finish this relations problem?

I have tried to work with this but this is all I have so far Are the following relations (integer sets) Reflexive, Symmetric, Asymmetric, or Transitive? $$R_1= \{(a, b) \mid a*b<1\}$$ Solution: ...
1
vote
0answers
48 views

Extension theorem on acyclic relations

By Sziplrajn's Theorem, we know that every partial order $\succsim$ (i.e. reflexive, transitive and asymmetric relation) on a nonempty set $X$ can be extended to a linear order (i.e. a complete ...
9
votes
1answer
209 views

What's the most efficient way to put all the stones in one pile?

There are $k$ piles of $n_i$ stones, on every move you can choose two piles with sizes $a$ and $b$ and if $a \ge b$ take from the first pile $b$ stones and put to the second one, on other hand if $a ...
2
votes
0answers
88 views

Simplify the square of a sum of cosine functions

I have a square sum of exponantials as below: $$\left|\sum_{l=0}^{M-1}\exp\left(jl^2a\right)\,\exp\left(\frac{-j2\pi l}{M}b\right)\right|^2 $$ where $a$ is constant and $b$ is an integer . and I have ...
0
votes
1answer
202 views

Matrix of a relation on a set

If I have a Matrix $A=\begin{bmatrix} 0&0&0\\ 0 & 0 & 0 \\0&0&0\end{bmatrix}$ why is this both symmetric and anti-symmetric? If I had a Matrix $B=\begin{bmatrix} ...
2
votes
1answer
610 views

Relation Matrix

Is my set of related pairs correct for this problem? $$\{(2,1), (2,2), (3,1), (3,2), (3,3), (4,1), (4,2), (4,3), (4,4)\}$$ Suppose that $\,A = \{1,2,3,4\}\,$ and $\,B = \{1, 2, 3\}.$ Let ...
13
votes
7answers
897 views

Prove that the additive inverse of an odd integer is an odd integer

This is a homework problem, but I don't want the answer, just a little guidance: Prove that the additive inverse of an odd integer is an odd integer. When approaching a problem like this, how ...
2
votes
1answer
516 views

Number of distinct path in a graph with $n$ vertices

Let $T = (V , E)$ be a tree with $|V | = n\geqslant 2$. How many distinct paths are there (as sub graphs) in $T$? I already have the answer to this question as $(n/2)$. The problem that I'm having is ...
1
vote
1answer
105 views

Finding how many isomorphic graphs are there

How many different graphs on the vertex set $V = \{1,2,...,n\}$ are isomorphic to: Answer for all $k,n \in \mathbb{N}$ while $2 \leq k \leq n-3$. Separate the cases when $n = 2k + 2$ and $n \neq ...
1
vote
1answer
55 views

Find a recursive formula for the following problem

Let $a_n$ be the number of bricks in a path that is $n \geq 1$ long. We have 3 types of bricks: Blue: $2$ cm long Red: $3$ cm long Green: $1$ cm long When a blue brick can't be placed next to a ...
2
votes
2answers
192 views

Set Relations Question

I understand these laws when applied to certain situations but can't seem to understand how to apply it to these problems. I know that if Jon is Mike's cousin, then Mike is Jon's cousin and that is a ...
1
vote
0answers
190 views

Understanding Sum of product and complete sum of product

I have a pair of problems, the first two of my homework, and I'm already unclear on how finding SOP and CSOP for them work. The first: E=xy(1+z)y' It seems like this just reduces to 0, since 1+z ...
17
votes
4answers
361 views

Prove that $\dfrac{(n^2)!}{(n!)^n}$ is an integer for every $n \in \mathbb{N}$

Prove that $\dfrac{(n^2)!}{(n!)^n}$ is an integer for every $n \in \mathbb{N}$ I know that there are tools in Number theory to proves the required but I want to use the tool that says that if you ...
0
votes
1answer
94 views

Gambling expected value riddle [duplicate]

A friend of mine gave me this probability riddle i couldn't solve, Maybe you could help me. Say i go to a casino playing roulette. I always gamble that a black number would pop (probability is: ...
1
vote
2answers
180 views

Does this system of congruences have a solution even if they are not relatively prime at first?

$$x \equiv 4\ (\textrm{mod}\ 15) \ \ \ \ \land\ \ \ \ \ x\ \equiv 6\ (\textrm{mod}\ 33)$$ Does this system of congruences have a solution even if they are not relatively prime at first? If I try to ...
0
votes
0answers
89 views

Count the number of transitive functions over set of size n

What is the most efficient way to compute the number of transitive functions over a set of n variables. I cant think of anything but brute force.
1
vote
2answers
59 views

Recursion problem help

The following are the teachers example problems. The issue is that I don't understand the exact steps they took to go from $f(0)$ to $f(1)$ to $f(2)$ to $f(3)$. What I'm asking here is if someone ...
1
vote
1answer
1k views

Solving non homogeneous recurrence relation

I am having a hard time understanding these questions. I know I need to find the associated homogeneous recurrence relation first, then its characteristic equation. I cant figure out how to find the ...
2
votes
2answers
104 views

How can I definitively determine whether a universal/existential statement is true or false?

How can one look at a universal/existential statement and determine with absolute certainty whether it is true or false? For example, is $$∀x\in\mathbb R\,∀y\in \mathbb R\,∃z\in \mathbb R\,\left(z = ...
0
votes
1answer
42 views

A $20$-degenerate graph on $1000$ vertices has to have at least $501$ vertices whose degree is at most $80$.

I'm seriously at a loss here... I'm asked to prove or disprove the following statement: A $20$-degenerate graph on $1000$ vertices has to have at least $501$ vertices whose degree is at most $80$. I'd ...
1
vote
2answers
42 views

Finding a formula to a given $\sum$ using generating functions

Find a close formula to the sum $\sum_{k=0}^{n}k\cdot 5^k$ I tried using generating functions using the differences sequences with no luck.
3
votes
1answer
166 views

Showing that a root $x_0$ of a polynomial is bounded by $|x_0|<(n+1)\cdot c_{\rm max}/c_1$

I have doubts about the following problem (Problem 3.21 from Sipser's "Introduction to the Theory of Computation"): Let $c_1 x^n + c_2 x^{n-1} + \cdots + c_n x + c_{n+1}$ be a polynomial with a ...
1
vote
1answer
93 views

Aquaintance problem in discrete math. induction proof.

I'm supposed to prove this by induction. I already proved it by contradiction, but I am lost on how to set it up for induction. Prove that if at least two people are at a party, at least two of ...
1
vote
1answer
136 views

Handshake problem. discrete math.

at a party, 25 guests mingle and shake hands. prove that at least one guest must have shaken hands with an even number of guests.
2
votes
1answer
144 views

Prove “casting out nines” of an integer is equivalent to that integer modulo 9

Let $s(x)$ be an abstraction for casting out nines of integer $x$. For all integers $x$, prove $s(x) \equiv x$ mod $9$ I'm not asking for an answer more of a way to attack this problem. Can't think ...
1
vote
1answer
22 views

Discrete dynamic models

We have the equation $$x_{n+1} = ax_n(1-x_n) - v_n$$ Why are there only fixed points for $(a-1)^2 - 4av_0 \geq 0$? Show that if $ 1<a<4$, there are 2 fixed points with $0<p_1 < p_2 ...
3
votes
2answers
75 views

$ k x^2 +4x = n $, Algorithm or any other method needed

I want to find any $n < 10^{18} $ so that the equation below has at least two pairs of solutions $(k, x)$ $ k x^2 +4 x = n $ constraints: $x > 10^6; \; x > k ; \; k, x \in \mathbb{N}$ I ...
35
votes
26answers
3k views

How to teach mathematical induction?

Some students are not convinced that a proof by mathematical induction is a proof. I have given the analogy of dominoes toppling but still some remain unconvinced. Is there very convincing way of ...
0
votes
1answer
276 views

Principle of Inclusion and Exclusion

Annually, the 65 members of the maintenance staff sponsor a “Christmas in July” picnic for the 400 summer employees at their company. For these 65 people, 21 bring hot dogs, 35 bring fried chicken, 28 ...
1
vote
4answers
79 views

congruence proof: Prove that there is no integer such that $x≡2 \pmod 6$ and $x≡3 \pmod 9$ are both true.

Prove that there is no Integer such that $x≡2 \pmod 6$ and $x≡3 \pmod 9$ are both true. How should I approach this question? I attempted using contra-positive proof, so $x=6p+2$ and $x=9q+3$ ...
4
votes
3answers
370 views

17! mod 13, How do I do this without a calculator

So I know $$17! = 17 \times16\times15...\times1$$ So I was thinking maybe go $$17mod(13)\equiv4 \space \space and \space 16mod(13)\equiv3 ...$$ add all that together but that is too much work so I ...
0
votes
1answer
52 views

how to work out $14^{293}-12^{26}\pmod{13}$

How can I work this out without a calculator? $$14^{293}-12^{26} \pmod{13}$$ I just couldn't figure out a way to do this.
1
vote
1answer
76 views

Probability, making a selection of 5 people from 10, with two married couples with restrictions

10 people. must make a committee of 5 people So the restrictions are 1) Mr and Mrs Q can't be separated 2) Mr and Mrs P can't be in the same committee. So how many possible committees ...
2
votes
2answers
83 views

Why does the Tower of Hanoi problem take $2^n - 1$ transfers to solve?

According to http://en.wikipedia.org/wiki/Tower_of_Hanoi, the Tower of Hanoi requires $2^n-1$ transfers, where $n$ is the number of disks in the original tower, to solve based on recurrence relations. ...
0
votes
2answers
106 views

discrete math counting problem

I am majoring in philosophy and currently im taking a logic course. I am having trouble with this question and I think you all mathematicians could help me out. There are five philosophy majors, four ...
2
votes
1answer
58 views

Finding a generating function of a series

So say if you have a sequence defined as, for $a\in\mathbb{Z}$, $$ c_n = \binom{a}{0} \binom{a}{n} - \binom{a}{1} \binom{a}{n-1} + \cdots+ (-1)^n \binom{a}{n} \binom{a}{0} = \sum_{i=0}^n (-1)^i ...
1
vote
0answers
58 views

counting more problem continue [duplicate]

i have asked but no one was able to help so i am re-posting, hoping someone can help me. i did the computation and i could be wrong but i have provided my answer. Given problem: How many ways can 5 ...
3
votes
2answers
51 views

counting another problem

I am trying to do my homework and it seems really hard. i would like to get checked here and make sure that im on the right track. can anyone help me?? Question: A group of hundred students want to ...
1
vote
1answer
47 views

Proof convex polyhedron with line does not contain a corner if closed

The excercise I am struggling with is the following: Given a convex closed polyhedron that contains a line, the question is, whether this polyhedron can also contain a corner. My idea was to make a ...
4
votes
1answer
83 views

Evaluate complicated sum

Evaluate following sum: $$\sum_{1\leqslant i< j \leqslant m}\sum_{\substack{1\leqslant k,l \leqslant n\\ k+l\leqslant n}} {n \choose k}{n-k \choose l}(j-i-1)^{n-k-l}.$$ Hint: use combinatorial ...
1
vote
3answers
85 views

$3^{3n+1} < 2^{5n+6} $ for all non-negative integers $n$. Is my induction solution correct?

Show using mathematical induction that $3^{3n+1} < 2^{5n+6} $ for all non-negative integers $n$. I'm not sure whether what I did at the last is valid? Basis step: for all non-negative integers ...
1
vote
3answers
55 views

What do you use for your basis step when its domain is all integers?

Example: *For all integers $ n , 4( n ^2 + n + 1) – 3 n ^2$ is a perfect square what should i use? negative infinity? I know you can use a direct proof but what if theres an induction question with ...
1
vote
0answers
41 views

Edge in a convex polytope

I want to show that a convex polytope $A$ that is an intersection of half-spaces contains an edge if $ A=\{x \in \mathbb{R}^n|Ax=0 \wedge x \ge 0\}$, where x greater equal 0 means, that all components ...
0
votes
3answers
2k views

Venn diagram problem solving question

In a class of $63$ students, $22$ study biology, $26$ study chemistry and $25$ study physics. $18$ study both physics and chemistry, $4$ study both biology and chemistry and $3$ study both physics and ...
3
votes
2answers
149 views

Counting donut problems

By using the permutation and combination techniques, i have attempt to solve this problem and i would like to know if where i did it wrong how many ways to choose $12$ donuts from a store that offers ...