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

2
votes
1answer
43 views

The disease problem

Students are sitting in a n * n grid. There's a disease spreading among them in a particular fashion. At start, there a 'k' students infected(At random). After every time step(equal intervals), the ...
19
votes
2answers
1k views

Understanding this pattern behind the Fibonacci sequence

To be honest, I'm pretty awful at mathematics however, when up till 6AM I do like to do random things throughout the night to keep me occupied. Tonight, I began playing with the Fibonacci sequence in ...
0
votes
2answers
74 views

Explicit Mapping to show that positive even integers and integers divisible by 3 have the same cardinality

So I'm really confused about what this question is asking and how to show it. I've started by trying to map out each set in my head ie. {..-6,-3,0,3,6..} {2,4,6,8..} I've done some research and it ...
1
vote
0answers
33 views

How to prove that a function f(x) is O(g(x)), using the definition (finding C and k)

We say that $f(x)$ is $O(g(x))$ if $$(∃C ∈ \mathbb(R)❘)(∃k ∈ \mathbb(R)❘)(∀x ∈ \mathbb(R)❘)$$ $$(x ≥ k → |f(x)| ≤ C · |g(x)|)$$ In English: We can find $C$ and $k$ so that, once we get past the “small ...
2
votes
1answer
90 views

Prove that the sum of harmonic series 1..n can be expressed as (n+1)H_n -n

Prove by induction that the sum of harmonic series Hn from 1 to n where n is a natural number is as follows. $$ H_n = \sum\limits_{i=1}^n 1/i $$ Prove: $$ \sum\limits_{i=1}^nH_i = (n+1)H_n -n $$ ...
5
votes
3answers
113 views

Arguing the correctness of an alternative, way to count how many bit sequences with exactly n zeroes and k+1 ones are there

I was trying to count how many bit sequences with exactly n zeroes and k+1 ones are there. One obvious reasoning is just by doing $ \binom {k+n+1}{k+1}$, by doing choose. However, I was told that ...
1
vote
2answers
86 views

How many strings of five ASCII characters contain the character @ (“at” sign) at least once?

I'm given the question: "How many strings of five ASCII characters contain the character @ (“at” sign) at least once?" Note: There are 128 different ASCII characters. I realized I'd have to use rule ...
1
vote
2answers
57 views

Proving 2 Sets have the same cardinality [duplicate]

Prove (0,1) and [0,1] have the same cardinality. I've seen questions similar to this but I'm still having trouble. I know that for 2 sets to have the same cardinality there must exist a bijection ...
0
votes
0answers
38 views

Number of simple graphs with no vertices of degree 0

Determine the number of graphs with no vertices of degree 0 on a given $n$-element vertex set V. The total number of simple graphs with $n$ vertices is $2^{\binom{n}{2}}$. We want to find the number ...
0
votes
0answers
13 views

Problem with finding max edge weighted subgraph in a complete graph, relative to it's node number

Let's sat that I have a complete, undirected, edge-weighted graph, and that I'm interested in finding the max-weight subgraph with regards to it's vertex set cardinality. Is there a specific name for ...
1
vote
2answers
56 views

Quadratic programming for special equation issues

My problem is how to find $\tau_1$ and $\tau_2$ s.t maximize the objective function is $$E=M-\alpha V$$ subject to $$-0.0062\le\tau_1\le0.499$$ $$-0.479\le\tau_2\le0.0262$$ $$\tau_1+\tau_2\le0.02$$ ...
0
votes
0answers
27 views

Interesting inequality involving sets of points

I have the following result in a paper with no proof provided so I'm trying to construct one and wanted to question the validity of it. Some information in the paper maybe irrelevant to the proof ...
4
votes
3answers
232 views

Prove using a strategy stealing argument that player 1 has a winning strategy in the chomp game

I have no idea what this question is asking or how to prove it mathematically. I realize based on the strategy stealing theory that if player two has a winning stratagy then player one can use the ...
5
votes
1answer
116 views

Discrete math problems

I am a high school student interested in thinking about math. I don't know a lot of high-powered math (I only know up to calculus), instead I focus on discrete topics related to math Olympiads ...
2
votes
2answers
45 views

For all positive real numbers, is $f(x)=\sqrt{x}+x+2$ one to one?

I understand that in order to prove this to be one to one, I need to prove $2$ numbers, $a$ and $b$, in the same set are equal. This is what I did: $$\sqrt{a} + a + 2 = \sqrt{b} + b + 2$$ ...
-2
votes
1answer
69 views

To prove that an argument is valid with the rules of inference of propositional logic

Use propositional logic to prove that the following argument valid : $$(A→ ¬B) ∧ [D ∨ ¬ (C ∧ ¬B)] ∧ C → (A→D)$$
1
vote
1answer
82 views

Tricky Negative Binomial example

Let $Y$ count the number of widgets succesfully produced before $r$th failure. We are told that machine shuts down when $30$th failure has occured, that is $r=30$. Then probability of producing $y$ ...
2
votes
4answers
44 views

Solving equations with mod

So, I'm trying to solve the following equation using regular algebra, and I don't think I'm doing it right: $3x+5 = \pmod {11}$ I know the result is $x = 6$, but when I do regular algebra like the ...
1
vote
1answer
33 views

Expressing given statements using quantifiers examples

I'm new on this subject and I have answered some questions which I found. Since there are no answers for them; I couldn't be sure that my answers are true. Could you help me verify the answers or ...
0
votes
0answers
22 views

Find the optimal solution using sequential quadratic programming

could you help me resolve my problem. My problem is how to find $\tau_1$ and $\tau_2$ s.t maximize the objective function is $$E=M-\alpha V$$ where $M=R(\rho,\tau1,\tau2)$,$V=R(\rho,\tau1,\tau2)$, ...
0
votes
1answer
48 views

Prove $f_{n}^{2} = f_{n-2}f_{n+2}+(-1)^{n}$ $n\ge 3$

Prove $f_{n}^{2} = f_{n-2}f_{n+2}+(-1)^{n}, n\ge 3$ (For the sake of space, I'm going to skip the basis step and move straight to the inductive step.) Inductive Step: Assume P(n) is true, prove ...
2
votes
2answers
112 views

How can this English sentence be translated into a logical expression?

You cannot ride the roller coaster if you are under 4 feet tall unless you are older than 16 years old. Let: $P$ stands for "you can ride the roller coaster" $Q$ stands for "you are under 4 ...
0
votes
3answers
112 views

What are various advanced counting techniques?

I need to give a presentation/seminar in my class of discrete mathematics. I want to present some advanced counting techniques that have not been discussed in classed and are not usually a part of ...
0
votes
4answers
104 views

$3$ and $5 $cent coins

Prove that any amount of more that $7$ cents can be represented by $3$ and $5$ cent coins. (Assume $3$ cent coins exist.) Let P(n) be true if we can find $n$ cents with $3$ and $5$ cent coins. My ...
2
votes
1answer
61 views

How many relations are there between the set A and B?

$A =\{1,2,3\}$ and $B=\{a,b\}$ Based on the text, the number of relations between sets can be calculated using $2^{mn}$ where $m$ and $n$ represent the number of members in each set. Given this, I ...
1
vote
1answer
29 views

Extended Euclidean Question

The question is as follows: $3157x + 656y = 2173$. I found so far $3157 = 4 \cdot 656 + 533$ $656 = 1 \cdot 533 + 123$ $533 = 4 \cdot 123 + 41$ $123 = 3 \cdot 41 + 0$. Now we do the reverse ...
0
votes
1answer
43 views

Proof of: $f_{n}^{2} = f_{n-1}f_{n+1}+(-1)^{n+1}$

So I'm going over some examples of recursion and Fibonacci Sequences for my quiz tomorrow and I'm a bit lost after a certain point. Prove $f_{n}^{2} = f_{n-1}f_{n+1}+(-1)^{n+1}$ $n\geq 2$ Basis ...
2
votes
1answer
17 views

Equivalence classes with respect to congruence modulo

If $A$ and $B$ are subsets of $\mathbb{Z}$, define $AB = \{ab : a ∈ A \wedge b ∈ B\}$. For each integer $x$, let $[x]$ be the equivalence class of $x$ in $\mathbb{Z}$ with respect to congruence ...
2
votes
1answer
39 views

Finding an upperbound on $f(n)$

I am stumped trying to prove that there exists a real number $c$, such that $f(n)\leq cn^4$ for most natural numbers $n$. $$f(n) = \left\{ \begin{array}{ll} 10, &n=10\\ ...
1
vote
1answer
26 views

Find the set of a given equivalence relation

What is the set $[4]$ but I haven't seen any examples in the text that describe how to approach a question such as this one. ...
1
vote
1answer
108 views

Given the partition list the ordered pairs in the corresponding equivalence relation.

Given the partition $\{a,b,c\}$ and $\{d,e\}$ of the set $S=\{a,b,c,d,e\}$, list the ordered pairs in the corresponding equivalence relation. I'm not really sure how to get started on this and would ...
3
votes
4answers
88 views

How to compute $3^{2003}\pmod {99}$ by hand? [duplicate]

Compute $3^{2003}\pmod {99}$ by hand? It can be computed easily by evaluating $3^{2003}$, but it sounds stupid. Is there a way to compute it by hand?
0
votes
1answer
48 views

Expressing sum using simple formula (without summation)

Express by a simple formula not containing a sum: $$\sum\limits^{n}_{k=1} \binom{k}{m}\frac{1}{k}$$ I figured that $$\sum\limits^{n}_{k=1} \binom{k}{m}\frac{1}{k} = ...
0
votes
1answer
39 views

Showing two “infinite ” sets have the same cardinality

Define $X:=\lbrace \frac{1}{n} | n \in \mathbb{N} \rbrace$ and $Y:=\lbrace \frac{1}{n} | n \in \mathbb{N} \rbrace \cup \mathbb{N}$ So writing this in interval notation I have some function $f$ that ...
2
votes
0answers
46 views

Combinatorial formulas for k-tuples

We have $n$ kinds of objects, and we want to determine the number of ways in which a $k$-tuple of objects can be selected. We consider variants: we may be interested in selecting ordered or unordered ...
1
vote
1answer
34 views

Number of linear extensions

Let $le(X, \preceq)$ denote the number of linear extensions of a partially ordered set $(X, \preceq)$. Prove $le(X, \preceq) = 1$ iff $\preceq$ is a linear ordering $le(X,\preceq) = n!$ where $n = ...
0
votes
2answers
50 views

English sentences to first order logic

I'm pretty new to first order logic and I'm attempting to translate some english sentences to first order logic. Am I doing these correctly and if not can someone show me a correct way to represent ...
2
votes
1answer
46 views

Composition of permutations is an equivalence relation

For a permutation $p : X \rightarrow X$, let $p_k$ denote the permutation arising by a $k$-fold composition of $p$, i.e. $p^1 = p$ and $p^k = p \circ p^{k−1}$ . Define a relation $\approx$ on the set ...
0
votes
0answers
25 views

Solving this equation involving a floor

I'm trying to prove that the following recurrence is in $\mathcal{O}(n^4)$: $$f(x) = \left\{ \begin{array}{lr} 10 & ; n=10\\ 3f\Big(\Big\lfloor \frac{2n}{5} \Big\rfloor \Big) ...
0
votes
1answer
41 views

Prove that if a relation $R$ on $X$ is not symmetric, but transitive, the collection of pseudoequivalence classes does not partition $X$.

I'm trying to work through this problem for the class I'm teaching, but am getting stuck. I think the key is that there exists some $(x,y)\in R$ such that $(y,x) \notin R$, so $x$ won't be in a ...
-1
votes
2answers
47 views

F(A ∩ B) ⊆ F(A) ∩ F(B) laymen translation?

I am suppose to prove the above statement but i have got diffculty understanding it in the first place. Could anyone help me translate it into laymen language?
1
vote
1answer
60 views

Don't really understand the absorption law

I don't really get the absorption law, specifically in this case: $$ (\lnot p \lor q) \land (\lnot r \lor q) \equiv (\lnot p \land \lnot r) \lor (\lnot p \land q) \lor (q\land \lnot r) \lor (q \land ...
0
votes
1answer
838 views

How many reflexive relation are there on a set with n elements? [duplicate]

How many reflexive relation are there on a set with n elements ?
11
votes
1answer
181 views

Proving that $(3n)!$ is divisible by $n! \times (n + 1)! \times (n + 2)!$ if $n$ is greater than 2

Prove that: If $n$ is greater than 2, then $(3n)!$ is divisible by $n! \times (n + 1)! \times (n + 2)!$ From Barnard & Child's "Higher Algebra". I know that the highest power of a prime $p$ ...
0
votes
3answers
59 views

Test the binary relation on the set for reflexivity, symmetry, antisymmetry, and transitivity.

$S = \{0,1,2,3,4,5\}$ $xRy, x+y = 5$ I'm not entirely sure on how to test this for reflexivity, symmetry, antisymmetry, and transitivity, though I understand the rules for each. I guess I'm ...
1
vote
1answer
66 views

is f: Z x Z → Z onto, where f(m,n)=m^2+n

I have a good understanding of onto functions, one-to-one functions. However the problem here as I am having is the how would one graph this function. For ex. if f(x)=x then we know its onto since for ...
0
votes
1answer
70 views

Solve this puzzle by gpuzzles

you and Me are playing bets. I take $10 from you and that begins our game. I shuffle the deck of cards (52 cards normal deck) and take out four random cards out of it. Now I place the cards in front ...
0
votes
1answer
20 views

What is the complexity of halving the size of an $n$-bit number every time.

I was discussing this question with my fiend the other day and was hoping to get some confirmation from someone if the logic I used is correct. Suppose that we have a number $N$ in base 2 ie ...
-1
votes
2answers
118 views

How to express other logical operations via Pierce's arrow?

x↑y, x⇒y, and x⇔y. So I have really given my best, but all I could do is express the conjunction, disjunction, negation, and impilcation.
1
vote
3answers
118 views

Set of palindromes with induction

Let $A = \{a_1, a_2, ..., a_k\}$ be a finite alphabet. a. Define, using structural induction, set of all palindromes of A. b. Find the recurrent pattern which represents the number of all ...