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
24 views

Prove a relation is transitive

I've stumbled upon this question in my discrete math book: Prove $$ R = \{(x,y) \in N \times N \ | \ 2x \mid y^2 \} $$ is transitive. I tried thinking about it having to do something with division ...
0
votes
2answers
45 views

threshold for random 2-sat

I'm looking at notes on the threshold for random 2-sat which is given as $r_{2}^{*}=1$. In the first part of proving the threshold they claim that a 2-sat formula is satisfiable if and only if the ...
0
votes
1answer
36 views

Prove that $|A| \geq |B|$ implies $|B| \leq |A|$ [duplicate]

If $|A| \geq |B|$, then there exists an onto function $f: A \rightarrow B$. If $|B| \leq |A|$, then there exists a one-to-one function $f: B \rightarrow A$. My issue is that I don't think that $|A| ...
0
votes
0answers
14 views

The problem of finding a smallest spanning 2-edge-connected subgraph of a graph G is NP-hard

For a given graph G = (V, E) with weights c(e), e ∈ E, the problem of finding a smallest spanning 2-edge-connected subgraph means that one has to find a subset F ⊆ E of smallest weight c(F) ...
0
votes
1answer
24 views

Proof of equivalence theorem using equational calculus

I have to show the following theorem: $p\vee \neg p \equiv ((p \vee q)\wedge \neg (\neg p \wedge (\neg q \vee \neg r)))\vee (\neg p \wedge \neg q) \vee (\neg p \wedge\neg r)$ I have proved $((p ...
0
votes
0answers
16 views

Recursion $T(m) = c_0 m + \sum\limits_{i=0}^{k}T(\lceil c_i m \rceil)$,$\sum\limits_{i=1}^{k}c_i < 1$ is linear

Let $L: \mathbb N_0 \to \mathbb N_0$ satisfy the recursion $T(m) = c_0 m + \sum\limits_{i=0}^{k}T(\lceil c_i m \rceil)$ with $c_i \geq 0$ for $i=0,\ldots, k$ and $\sum\limits_{i=1}^{k}c_i < ...
0
votes
4answers
58 views

Prove that if $n$ is odd, then $-n$ is odd.

Here is my work so far, I am missing something quite obvious but I can't seem to link it together: Proof. Let $n$ be an integer. Suppose $n$ is odd. This means that there is an integer $k$ such that ...
0
votes
1answer
33 views

Consider a general arithmetic sequence,$\{x_n\}^{\infty}_ {n=1}$, defined by $x_n = a+nb$

Consider a general arithmetic sequence,$\{x_n\}^{\infty}_ {n=1}$, defined by $x_n = a+nb$, ($n ≥ 1$).Prove that if $c$ is any integer such that gcd$(b,c) = 1$ then there is some element of the ...
0
votes
0answers
33 views

Consider the sequence of positive integers An, for n ≥ 1, defined by $A_n = 10^{2^n} + 1$.

Consider the sequence of positive integers $A_n$, for $n \geq1$, defined by $A_n = 10^{2^n} + 1$. 1) Prove that the elements of this sequence are pairwise coprime, i.e. prove that if $m \neq n$ then ...
0
votes
0answers
23 views

Master Theorem for common recurrence

I have the following recurrence: $$T(n) = T\bigg(\frac{n}{2}\bigg) + O(n)$$ And I am trying to find the time complexity using the master theorem. So I have: $a = 1, b = 2$ $f(n) = O(n) = c(n)$ ...
1
vote
2answers
30 views

Show that ¬p ∨ (r →¬q) and ¬p ∨¬q ∨¬r are equivalent.

I am new in Discrete Math so that I am still not familiar with Logical Equivalent rules. 1) Show that ¬p ∨ (r →¬q) and ¬p ∨¬q ∨¬r are equivalent. My Try: ¬p ∨ (r →¬q) $\equiv$ ¬p ∨ (¬r∨ q) ...
1
vote
2answers
53 views

What is the remainder produced when the integer 2099^(2017^13164589) is divided by $99$? [closed]

I'am looking for the remainder produced when the integer $2099^{2017^{13164589}}$ is divided by $99$ ? The goal reached is to avoid large integers.
2
votes
1answer
12 views

Nested Quantification of exactly one.

Suppose my domain is "All students in the class" and P(x, y):= x has emailed y. So, how do i define: Every student has emailed exactly one student. Exactly one student has emailed every one. A ...
2
votes
3answers
49 views

Given $3$ types of coins, how many ways can one select $20$ coins so that no coin is selected more than $8$ times.

So I was given this question. Given $3$ types of coins, how many ways can one select $20$ coins so that no coin is selected more than $8$ times. First I make $x_1 + x_2 + x_3 = 20$ Then $ 0 \leq x_i ...
0
votes
2answers
57 views

Big-Oh Analysis of For Loop

I have the following for loop: sum = 0 for i = 1 to n do for j = 1 to i^3 do for k = 1 to j do sum++ What is the strategy to determine ...
0
votes
2answers
31 views

Floor and ceiling opposite property

For $x\in \mathbb{R}$ let's define $[x]$ as: $$ [x] = max \{ k\in \mathbb{Z}: k\leq x \} $$ and $[x]^{*}$ as: $$ [x]^{*} = min \{ k\in \mathbb{Z}: k\geq x \}. $$ Show that: $$ [x]^{*} = -[-x]. $$ So ...
1
vote
2answers
29 views

Is the relation $P$, for all real numbers $x$ and $y$ that satisfy $xPy $ iff $x^3 - y \ge y^3 - x$, a reflexive, symmetric and transitive relation?

Image of an exam question I am revising link: [1] For (i) I have stated the relation is reflexive as $\forall x ∈ \Bbb R, xPx$ is reflexive as $x^3 \ge x $ For (ii) I have stated that the relation ...
1
vote
0answers
17 views

What are the different ways of performing Triangular matrix-vector multiplication?

Suppose we have $$\left[\begin{array}{cccc} x_1 & 0 & 0 & 0 \\ x_2 & x_1 & 0 & 0 \\ x_3 & x_2 & x_1 & 0 \\ x_4 & x_3 & x_2 & x_1 \end{array}\right] ...
0
votes
1answer
36 views

Discrete math: Simplified the following english sentence?

Simplified the following english sentence? It is not the case that overnight lows are not in the 60s or the furnace is running. What I tried is ignore the exactly meaning in the real life. So I took ...
0
votes
0answers
26 views

The minimum of two big-O functions

Suppose we have the following lower and upper bounds for an invariant $\chi(G_N)$, where $G_N$ is a graph on $N$ vertices, $N=f(k,n,m) $ and $N,k,n,m\in \mathbb{N}$: $$ ...
0
votes
1answer
34 views

combinatorial Proof

I need to check if the following is true for all $k$. Can anyone help me? $$k{n\choose r} ={kn\choose kr} $$ I know that using the formula, I will obtain: $$ k\left(\frac{n!}{r!(n-k)!}\right) = ...
1
vote
2answers
41 views

Deductive Proof - Justify each step with law or inference rule

My Professor gave me the following: a) If $P \to Q, \neg R \to \neg Q$, and $P$ then prove $R$. b) If $P \to (Q\wedge R)$ and $\neg R\wedge Q$ then prove $\neg P$. I understand how to do ...
0
votes
2answers
20 views

$A = \{{1, … , n\}}$ - How many $(B,C) \in P(A) \times P(A)$ are there such that $B \cap \overline{C} = \emptyset$?

$A = \{{1, ... , n\}}$ How many $(B,C) \in P(A) \times P(A)$ are there such that $B \cap \overline{C} = \emptyset$ ? I got to the conclusion that it must be $\sum\limits_{k=0}^{n}2^k$ because for ...
-1
votes
1answer
22 views

Calculate the number of equivalence classes [closed]

Let $A = \{1,2,3,4,5,6\}$ and let $B = \{1,2,3\}$ Let $R$ be a relation such that $R=\{(x,y) \in P(A) \times P(A): x \cap B = y\cap B\}$ How many equivalence classes are possible? I'm kinda stuck ...
1
vote
2answers
20 views

Show that, in all bases $n$ greater than $3$, the number written as $1331$ is a perfect cube. [duplicate]

Show that, in all bases $n$ greater than $3$, the number written as $1331$ is a perfect cube. I was given this question to do and sadly I have no idea where to even begin. Any help will be ...
0
votes
2answers
42 views

Let A ={x ∈ Z | x =18a − 2 for some integer a } and B ={y ∈ Z | y = 18b + 16 for some integer b} Prove A ⊆ B

I'm fairly certain that this proposition is true, but I have no idea how to approach a proof for it. I'm not looking for someone to do the work for me, I'm just trying to find out what type of proof ...
2
votes
2answers
27 views

If $B= \{1, 2\}$ and $C = \{\{1,2\}\}$ what is $B \times C$?

I understand the basics of Cartesian products, but I'm not sure how to handle a set inside of a set like $C = \{\{1,2\}\}$. Do I simply include the set as an element, or do I break it down? If I use ...
3
votes
2answers
30 views

How many pairs are in $(B,C) \in P(A) \times P(A)$ such that $B \subseteq C$

I'm trying to solve this problem: Let $A = \{1,2,3,\ldots,n \}$ How many pairs are in $(B,C) \in P(A) \times P(A)$ such that $B \subseteq C$ I want to solve this using combinatorics, Basically what ...
0
votes
0answers
7 views

Count options for sitting people om a bench [duplicate]

I have this combinatoric question which I can't figure out. In how many ways can we sit 12 men and 12 women on a bench where no 2 women sit next to each other. The answer is : $ 13! \cdot 12! $ but my ...
0
votes
1answer
29 views

Lattice Reduction in Mathematica

I have some trouble understanding the concept of lattice reduction. As I understand, an integer lattice $$\{ A k : k \in \mathbb{Z}^n \} \subset \mathbb{Z}^n $$ is defined by a regular matrix $A \in ...
1
vote
2answers
37 views

Counting problem (students assigned to a tutor)

Four new students have to be assigned to a tutor. There are seven possible tutors, and none of them will accept more than one new student. In how many ways can the assignment be carried out? The ...
0
votes
1answer
37 views

In how many ways can 40 identical carrots be distributed among 8 different rabbits?

In how many ways can 40 identical carrots be distributed among 8 different rabbits, while every rabbit needs to get a carrot, and no rabbit get more then 16 carrots. Thank you for the help!
2
votes
1answer
47 views

Chromatic Index in Graph

There is a graph $G$ with maximum degree that is greater than $0$. Suppose that $G$ contains a perfect matching $P$ and that $G-P$ (graph after removing all edges of $P$ in $G$) is bipartite. What is ...
1
vote
1answer
49 views

Prove that $L_n = \alpha^n +\beta^n$ for all integers $n\geq 0$

Let $\alpha =\left(\frac{1+\sqrt{5}}{2}\right)$ and $\beta = \left(\frac{1-\sqrt{5}}{2}\right)$. Prove that $L_n = \alpha^n +\beta^n$ for all integers $n\geq 0$ where $L_n$ denotes the Lucas numbers. ...
1
vote
2answers
41 views

If $p$ is a prime other than 2 or 5, prove that $p$ must be one of the forms $10k + 1$, $10k + 3$, $10k + 7$, or $10k + 9$

If $p$ is a prime other than 2 or 5, prove that $p$ must be one of the forms $10k + 1$, $10k + 3$, $10k + 7$, or $10k + 9$ -The section we are covering is on the division algorithm, although I am ...
0
votes
2answers
30 views

Let $F_n$ denote the nth Fibonacci number and prove that the following re true for every possible integer $n$

$$\sum_{i = 1}^n F_{i}^2 = F_n F_{n+1}$$ -I solved a similar Fibonacci sequence that was the following: $$\sum_{i = 1}^n F_i = F_{n + 2} - 1$$ But, I am having trouble with this one, any help is ...
1
vote
4answers
60 views

Prove that $f(n) = 3n^5 + 5n^3 + 7n$ is divisible by 15 for every integer $n$

So far I have only been able to complete the base case for which I got the following: $$f(n) = 3n^5 + 5n^3 + 7n$$ $$f(n) = 3(1)^5 = 5(1)^3 + 7(1)$$ $$f(n) = 3 + 5 + 7$$ $$15/15 = 1$$ From here ...
0
votes
0answers
15 views

Compute the linear relationship between the random variables from its singular covariance matrix

As an example, say (x3) = 2(x1) - 3(x2) has the following covariance matrix [25, 0, 50] [ 0, 16, -48] [50, -48, 244] Is it correct to solve the equation ...
0
votes
1answer
17 views

Existence of hypergraphs with large parameter values

By a result of Erdös, proved using the probabilistic method, there exist graphs of arbitrarily large chromatic number and girth. What are the corresponding results for hypergraphs (given some ...
1
vote
2answers
41 views

Guide to solving Harary's exercises

Most of Harary's harder exercises are research problems (although solved), that need almost always a single key idea as a breakthrough. Often it so happens that even after thinking for a long time no ...
6
votes
2answers
179 views

summation of a binomial expression that doesn't start from 0

I have the following expression: $$ \sum_{k=9}^{17}\binom{17}{k} $$ and I need to show that it's equal to: $$ 2^{16} $$ now I know that if 'k' was starting from zero and not from 9 , like this: $$ ...
0
votes
1answer
17 views

Given a set $A$ of size $n$, is there a formula for the number of anti-reflexive relations on $A$?

By anti reflexive I mean: $\forall (a \in A)$, $\neg (aRa)$ Given a set $A$ of size $n$, is there a formula for the number of anti-reflexive relations on $A$?
0
votes
0answers
12 views

universal quantifiers in predicate logic [duplicate]

can anyone tell me if I'm doing this right? Any pet either loves itself(a) or some person(b). my answer: ∀ x Pet(x) --> (Love(x,a) V Love(x, b)) Dogs will eat anything my answer: ∀ x (Dog(x) --> ...
0
votes
1answer
72 views

translate sentences using predicate logic and universal quantifiers

ok so I think I understand of them, but correct my answers if I am wrong.. Any pet either loves itself(a) or some person(b). my answer: ∀ x Pet(x) --> (Love(x,a) V Love(x, b)) Dogs will eat ...
0
votes
1answer
59 views

Evaluate truth value of formula

I am not sure about this question? Domain = {1, 2} Assignment of constants: a = 1 and b = 2 Assignment of functions: f(1) = 2 and f(2) = 1 Assignment for predicate P: P(1, 1) = T; P(1, 2) = T; ...
2
votes
0answers
29 views

Simplify binomial coefficients sum [duplicate]

Exercise requires to simplify this sum: $$\sum_{k=0}^{20} \binom{50}{k}\binom{50}{20-k}$$ Tried to figure this out with no success. I have only final answer, which is $\binom{100}{20}$. Please help ...
0
votes
2answers
42 views

Simplify the sum of binomial coefficients

The exercise requires to simplify the following expression: $$\sum_{k=0}^{25} \binom{50}{2k}$$ By finally looking at someone's answer, I know that the result should be $2^{49}$, but the following ...
1
vote
1answer
45 views

Stable Matching Problem Worst Preference?

Suppose we have one hundred pairs of women and men, and there is a man M that is ranked the second highest on every woman's preference rankings. Would it be possible that he ends up with the woman he ...
0
votes
2answers
77 views

How many ways to arrange people on a bench so that no woman sits next to another woman? [closed]

There are $12$ women and $12$ men. How many ways are there to sit them all on a bench where no woman can sit next to another woman? Thank you.
-4
votes
1answer
30 views

Prove that the shortest path between two vertices in a weighted graph does not change if we multiply weights with the same number [closed]

I need help to prove that if we multiply weights with the same positive number , in a weighted graph, the shortest path between two vertices does not change.