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

0
votes
1answer
96 views

Use strong induction to prove that n is congruent.

I need some hints on this question: There are two players, Bill and Steve. Initially there is a pile of $n$ coins placed on a table. The players alternate turns, with Bill playing first. Each player, ...
-1
votes
1answer
45 views

Relations on a set.

State the smallest relation containing the relation $$\{(1,2),(2,1),(2,3),(3,4),(4,1)\}$$ that is: a) reflexive and transitive. b) reflexive, symmetric and transitive. For me reflexive would be ...
1
vote
1answer
42 views

Formula for the terms of the sequence defined by $a_0 = 1$, $a_1 = -2$ and $a_{n}=-4 a_{n-1}-4 a_{n-2}$

Let $a_{n}$ be the sequence recursively defined by $a_{0} = 1$, $a_{1} = -2$, and for $n\geq 2$, $a_{n}=-4 a_{n-1}-4 a_{n-2}$. Use strong induction to show that $a_{n}$ = $(-2)^n$ for all n. ...
1
vote
1answer
73 views

State whether or not the relation on the set of reals is reflexive, symmetric, antisymmetric or transitive

State whether or not the relation on the set of real numbers is reflexive, symmetric, anti-symmetric or transitive. $$R= \{(x,y)\mid x=1\text{ or }y=1\}$$ This is what I have done up to now, not ...
1
vote
5answers
131 views

Prove $13|19^n-6^n$ by congruences

I am trying to prove $13|19^n-6^n$. With induction its not so bad but by congruences its quite difficult to know how to get started. Any hints?
1
vote
1answer
46 views

Determine the equivalence relation on {1, 2, 3, 4}

If the relation is an equivalence relation, list the equivalence classes. $$\{(x, y) : 4 \mid x - y\}$$ I have no clue how to solve this. What I have tried is: To know its an equivalence relation, ...
1
vote
2answers
45 views

Proving recurrence

I'm trying to prove the following recurrence: $g(n) = 3g(n-1) + 2$ $g(0) = 0$ $g(1) = 2$ $g(2) = 8$ ... I know that $g(n)$ in closed form is equal to $n^3 -1$, but I'm having a hard time proving ...
1
vote
2answers
58 views

Strong induction proof with polygon

How can we show that if a simple polygon with at least four sides is triangu-lated, then at least two of the triangles in the triangulation have two sides that border the exterior of the polygon using ...
3
votes
2answers
73 views

Proof related with mathematical induction

I tried to prove this claim using mathematical induction. $ a^2 + 15a + 5 ≤ 21 a^2 $ $\;\; ∀a∈\mathbb Z^+$ The way is as the following: Basis: for a = 1 is true since 21 = 21 Inductive step: If ...
1
vote
3answers
77 views

Find the rest of the division when $23^{84292}$ is divided by $7$, is the procedure and the result correct?

I want to know if the procedure I have followed in order to get the result for the next problem is correct. The problem is this: Find the rest of the division when $23^{84292}$ is divided by $7$. ...
0
votes
2answers
89 views

meaning of the symbol $Z_n^*$ in discrete mathematics

I was reading discrete Mathematics, and i found a symbol $$Z_n^*.$$ I don't know what it means. The text says that the "image" with the multiplication operator is an abelian group. can any one ...
0
votes
3answers
163 views

Show two graphs are not isomorphic

I know this graphs are not isomorphic. However they have the same number of vertex and edges, and the same degree sequence, is not the most easy case. If im correct, the graphs are isomorphic if ...
1
vote
1answer
56 views

floor and ceiling functions.

Determine whether ‘the set of positive integers that are not divisible by 3’ is countable or uncountable. If this set is countable, prove it by proposing a bijection (a oneto- one and onto function) ...
2
votes
1answer
21 views

Restricting the ordering of a given permutation

Let $p_1p_2p_3...p_n$ be a randomly-selected n-permutation. Why is $P(p_1>p_2>p_3)=\frac 16$? (P denotes probability.)
1
vote
1answer
58 views

Why is $ 2\binom nm^2<n^{2m}$?

$\forall n\geq2 \forall m\geq2,$ $$ 2\binom nm^2<n^{2m}.$$ Why is the above inequality, which is equivalent to $ \binom nm<\frac{n^m}{\sqrt 2}$, true?
1
vote
1answer
56 views

Closed-form formula

Show (not by giving a $(c,k)$ pair but in some other way) that the sum of the squares of the first $n$ odd positive integers is of order $n3$. I.e. is that sum $\Theta(n3)$? Hint: Try to find a ...
1
vote
2answers
126 views

How to prove that the smallest asymmetric tree has at least 7 vertices?

Find the smallest possible number of vertices an asymmetric tree can have (i.e. prove that no smaller tree can be asymmetric). I think that the answer is 7, but I don't know how to prove it.
0
votes
1answer
40 views

worst-case algorithm

Suppose you are given a list of positive integers { a1,a2, … an}. Describe an algorithm (write-down its pseudocode) that goes through the elements in the list one by one and finds the index of the ...
2
votes
1answer
87 views

Application of pigeonhole principle

Select $11$ diff erent numbers from $f\{1,2,...,20\}$. Prove that two of your numbers, $a$ and $b$, will diff er by two. Clearly this is an application of the pigeonhole principle. However, I'm not ...
1
vote
3answers
75 views

Why is this binomial coefficient bounded thus?

Source: Miklos Bona, A Walk Through Combinatorics. $$ \forall k\geq 2,\binom{2k-2}{k-1}\leq4^{k-1}.$$ The RHS is the upper bound of the Ramsey number $R(k,k)$. How can I prove the inequality ...
1
vote
0answers
57 views

Understanding the beginning, while, sum, and end of an algorithm

My problem is as follows: \1brace procedure sum (n: positive number) sum:=0 while i < 10 begin sum :=sum + i end output(sum) \rbrace Then, I have the following choices to select from as ...
1
vote
2answers
118 views

Drawing Graph on 5 vertices.

Draw a graph on 5 vertices that contains no clique of size three (that is, no triangle) and no anti-clique of size three (that is, three vertices none of which is connected to any other). Here ...
1
vote
1answer
166 views

Write a grammar that generates the strings over {a,b} starting with a

The answer is: S -> aA, A -> aA, A -> bA, A -> a, A -> b, S -> a Any idea how they got this?
1
vote
4answers
261 views

How many ways are there for 2 teams to win a best of 7 series?

Case 1: 4 games: Team A wins first 4 games, team B wins none = $\binom{4}{4}\binom{4}{0}$ Case 2: 5 games: Team A wins 4 games, team B wins one = $\binom{5}{4}\binom{5}{1}-1$...minus 1 for the ...
1
vote
3answers
171 views

Show that there is exactly one maximal element in a poset with a greatest element?

This is true, any idea how to say it in proof form? I would guess: In a poset with one maximal element, then that element has no other elements above it and has elements below it. If its the only ...
0
votes
1answer
65 views

Proving a set is countably infinite $\left \{q \in \Bbb Q:q=\dfrac{a}{b}\ \text{where $a$ is even and $b$ is odd} \right \}$

Proving a set is countably infinite $$\left \{q \in \Bbb Q:q=\dfrac{a}{b}\ \text{where $a$ is even and $b$ is odd} \right \}$$ I am not sure how to go about solving this problem. I know it has ...
0
votes
1answer
236 views

What is the time complexity (in big O notation) given the following code?

Before asking the question I read through my textbook and the wikipedia page for big O notation and I am still having a hard time understanding how to calculate time complexity in big O notation. How ...
0
votes
1answer
129 views

Given that $k\equiv 2 \mod 4$, determine the remainder when $5k + 13$ is divided by $4$

This is what I've done to solve it: Since $k$ is congruent to $2 \mod 4$, any number in the set $\{...,-10,-6,-2,2,4,18,22,...\}$ will solve the original congruence. By simple algebra, if $5k + 13$ ...
1
vote
1answer
223 views

How to prove that if n and k are integers with 1 ≤ k ≤ n, then k*(n C k)=n(n−1 C k−1) combinatorally?

I am having with combinatorial proofs. My professor says to come up with a scenario so that we can connect both sides by double counting but I am clueless.
0
votes
2answers
406 views

Why are these relations not posets?

I was hoping you guys could help me clarify why these relations are or arent posets. I gave my thought process that resulted in the wrong answer. ...
4
votes
1answer
883 views

Concrete Mathematics - Towers of Hanoi Recurrence Relation

I've decided to dive in Concrete Mathematics despite only doing a couple of years of undergraduate maths many years ago. I'm looking to work through all the material whilst plugging gaps in my ...
2
votes
1answer
78 views

Planar Realization of a Graph in Three-Space

We call a planar graph one that we can draw in two-space such that no two edges intersect. I was told that we're not so interested in drawing graphs in three-space, because it is "intuitively obvious" ...
1
vote
1answer
193 views

Using euclidean algo to find d (RSA encryption)

The questions says "let p = 5, q =11, n = 55 tocient(n) = 40. e=7. Use the Euclidean algo to find the value of d. This is driving me crazy. Here's what I did: ...
3
votes
7answers
329 views

the concept of Mathematical Induction

I am currently taking Discrete Mathematics and while I understand most of the topics covered, the one topic which I still don't quite understand is Mathematical Induction. The way the professor taught ...
0
votes
1answer
291 views

Symmetric and Transitive closures

Given a relation $R$, is the symmetric closure of the transitive closure of $R$ equal to the transitive closure of the symmetric closure of $R$? If yes, prove it. If not, give a counterexample. ...
2
votes
1answer
89 views

Recursive Function - mod 5

How do the recursive function for $\mod 5(x) = 0$ rest of division of $x$ by $5$. $$\begin{align} \mod&5(5) = 0\\ \mod&5(6) = 1\\ \mod&5(7) = 2\\ \mod&5(8) = 3\\ \mod&5(9) = 4\\ ...
2
votes
1answer
53 views

$\max\{\chi(G):G$ embeds on projective plane$\}=6$

My lecture notes in Discrete Mathematics state that $$ \max\{\chi(G) \; : \; G \text{ embeds on projective plane} \}=6, $$ but I have no idea where this comes from. $\chi(G)$ is the chromatic number ...
0
votes
1answer
211 views

How do you solve linear congruences with three variables.

Given \begin{cases} x+y+z &\equiv 1 \pmod{10} \\ x+2y+3z &\equiv 2 \pmod{10} \\ 2x+3y+6z &\equiv 3 \pmod{10} \end{cases} find $x,y,z$. How does one solve such a system of ...
3
votes
2answers
73 views

Graphs with a polynomial number of shortest paths between any pair of vertices

Let $G$ be a simple undirected graph, and let $s$ and $t$ be two arbitrary vertices of $G$. Even for some rather restricted graph classes, the number of shortest paths between $s$ and $t$ can be ...
0
votes
1answer
76 views

Boolean functions with $3$ variables

Is it true or false that the total number of boolean functions with $3$ variables is $255$? ${2^2}^3$ is $256$ so this statement is false.
0
votes
1answer
83 views

Solution Check: Union/intersect complement

This a true/false question. For set operations, we always can replace Union by intersection and complement operation. I think what it is saying is that if A U B, you can swap U with intersect and ...
0
votes
1answer
40 views

Binary relations: transitivity and symmetry

I've been looking at some examples for transitivity and symmetry. Suppose $A=\{0,1,2 \} $ and the relation $R=\{ (0,0),(1,1),(2,2),(1,2),(2,1) \}$ Well for starters this is clearly reflixe since ...
1
vote
3answers
136 views

Existence of uncountable set of uncountable disjoint subsets of uncountable set

"Can you to any uncountably infinite set $M$ find an uncountably infinite family $F$ consisting of pairwise disjoint uncountably infinite subsets of $M$?" Intuitively, I feel like it should be ...
0
votes
1answer
63 views

Which strings belong to the regular set represented by the regular expression (1∗01∗0)?

I know the string should be like 1…101…10, but not sure how to describe it. Can anyone help me?
0
votes
1answer
42 views

Need help with a combinations question

I am just having a lot of trouble identifying this question as a combination question, and knowing exactly what numbers to use. How many bit strings of length 10 contain? a) exactly four 1s. I'm ...
0
votes
1answer
47 views

Path counting discrete

I need help understanding a simple concept. Lets say you're given a problem where you start at (0,0) on a 2D grid and want to count the number of paths to (8,4). Would I be following the combinations ...
2
votes
2answers
196 views

Construction of a triangle-free graph of chromatic number $1526$

I found this exercise in Bollobas: Modern Graph Theory "Construct a triangle-free graph of chromatic number 1526" It is added not to use results from the chapter about Ramsey Theory. Now my ...
0
votes
2answers
20 views

Construction of two graphs

I would like to know if it is possible to construct two graphs $G,H$ such that $|G|=|H|, e(G)=e(H)$ (means that the two graphs have the same number of vertices and edges) and $\chi(G)>\chi(H)$ ...
0
votes
3answers
68 views

Uncountable infinite family of uncountable subsets of an uncountable set [closed]

Find an uncountable family of pairwise disjoint uncountable subsets, on an uncountable set B.
1
vote
2answers
29 views

Why $R=\{(a,b)\mid a=b \mbox{ or } a=-b\}$ is not anti symmetric?

Why $R=\{(a,b)\mid a=b \mbox{ or } a=-b\}$ is not anti symmetric? I read because this is symmetric so it is not anti symmetric, but $R=\{(a,b) \mid a=b \}$ is both symmetric and anti symmetric.