Tagged Questions

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
0answers
5 views

Convert form English to logical symbols.

I have a logical argument in English which says. All Humans are Mortal. Zeus is not Mortal. therefore Zeus is not Human. And I tried to convert it from English to logic. and did this h = is ...
3
votes
2answers
31 views

GCD Direct Proof

I need to show that if $a,b,c$ are ints such that $\gcd(a,b) = 1$ and $c|(a+b)$, then $\gcd(c,a) = \gcd(c,b) = 1$ I want to try and prove this directly because I think it will be more straightforward ...
1
vote
1answer
15 views

Proving n is not divisble by m using Division Algorithm

When $n$ and $m$ are integers, how could I write a statement equivalent to the statement "$n$ is not divisible by $m$" using ideas from the Division Algorithm?
1
vote
0answers
24 views

Solve the recurrence $T(n)=aT(n-1)+bn$

I have to solve the following recurrence, given $T(1)=1$, $$T(n)=aT(n-1)+bn$$ I have done the following: $$T(n)=aT(n-1)+bn \\ =a^2T(n-2)+ab(n-1)+bn \\ =a^3T(n-3)+a^2b(n-2)+ab(n-1)+bn \\ = \dots \\ ...
0
votes
2answers
14 views

Modulo congruence

I have a problem here that I have no idea how to go about solving. It states: Let $n∈Z$ with $n>1$. (a) If $n=2k$ for some odd integer $k$, prove that $k^3≡k \pmod{2n}$. (b) If $n=2k$ for ...
2
votes
1answer
17 views

Preorder traversal, inorder traversal, postorder traversal

a) preorder traversal b) inorder traversal c) postorder traversal Ok, a) r,j,h,g,e,d,b,a,c,f,i,k,m,p,s,n,q,t,v,w,u b) a,b,d,c,e,g,f,h,j,i,r,s,p,m,k,n,v,t,w,q,u c) ...
-1
votes
0answers
17 views

Combinatorics problem - sitting at $n$ tables [on hold]

I've got the following problem: Given $3n$ people, $n$ tables, each table is for $3$ people. In how many ways can these people sit at the tables so each two people meet only once? Thanks in advance ...
0
votes
0answers
7 views

Number of solutions of a diophantine inequality

In my problem i am looking for the number of the nonnegative integer pairs $(x,y)$ which satisfy the inqueality $x+my\leq n$, where $m$ and $n$ are coprime integers. The answer in the book is given ...
-4
votes
1answer
53 views

Which if the following three propositions are logically equivalent? [on hold]

Which if the following three propositions are logically equivalent? $(p \wedge q) \Rightarrow (p \wedge r)$ $p \wedge (q \Rightarrow (p \wedge r)) $ $(\lnot p) \vee (\neg q) \vee (r \wedge p)$ ...
-3
votes
0answers
51 views

Determine the truth value of the following proposition: “If it is sunny, then it is raining if and only if it is snowing.” [on hold]

Determine the truth value of the following proposition: "If it is sunny, then it is raining if and only if it is snowing."
1
vote
2answers
15 views

Proof of connectedness in a simple graph

Let G be a simple graph with n vertices. Prove that if the degree of every vertex is at least $\frac{n-1}2$, then G is connected. I've tried the degree sum formula, but it doesn't seem to get me ...
0
votes
1answer
65 views

how can I publish my log approximation formula

I've successfully found out a formula which can give log value of any base till 4-5 places after decimal I want to know whether it can get published because I've seen some journals which have ...
0
votes
1answer
13 views

decidability and countability

The diagonolisation technique is utilized to prove that the halting problem is undecidable. However, I kind of sense that it is making the assumption that decidable sets should be countable. Is this ...
-1
votes
1answer
20 views

Prove $|A| \le|C|$ for injection and surjective functions

$A$, $B$ and $C$ are finite sets with $F: A \to B$ a surjection and $G: B \to C$ an injection. Prove $|A| \le |C|$ I could prove it using examples, but not sure how to generally.
1
vote
1answer
49 views

True or False Time complexity questions

Here is my go at them and any help is appreciated: If $f(n) = \Theta(n^2)$ and $g(n) = \Theta(n^2)$ then $(f - g)(n) = \Theta(n^2)$ where we define $(f-g)(n) = f(n) - g(n) \forall n$ TRUE? If $f(n) ...
0
votes
2answers
47 views

How to find the generating function and the closed form for the generating form

I'm trying to find the generating function and the closed form for the generating form for this sequence: $0,1,-2,4,-8,16,-32,64...$ I've tried the following: I think it's an index shift so that's ...
1
vote
1answer
39 views

Time complexity of algorithms

I am having some trouble figuring out the time complexity in big theta notation of the following algorithms. Any help is appreciated. ...
0
votes
1answer
24 views

How many function A to B satisfied from f(1)=x

What does it mean to satisfy a function A to B from $f(1)=x$ ? Where $$ A=\{1,2,3,4\}\ \ \text{and}\ \ B=\{x,y,z\}$$ The answer should be $3^3$, but why?
1
vote
3answers
53 views

Using mathematical induction to show that for any $n\ge$ 2 then $\prod_{i=2}^n\left(1-\frac{1}{i^2}\right)=\binom{n+1}{2 \cdot n}$

I'm trying to work through some practice problems but I've been stuck on this for god knows how long now and I've no idea where to even start. Just wondering if it would be possible for someone to ...
1
vote
2answers
23 views

Cardinality of a set of matrices

Consider the set $S$ of $3\times3$ matrices with binary coefficients, that is the coefficients are integers modulo 2. Compute $|S|$ I am not sure what is this question trying to ask. Am I right to ...
0
votes
0answers
11 views

diffusion equation

Kindly give me suggestions on my following assignment of Simulations in Fluid Flow: Solve the following differential equation for transport of f(x,y,z,t) by MS Excel ∂f/∂t+Ux ∂f/∂x+Uy ∂f/∂z+Uz ...
0
votes
0answers
18 views

Proofs with algebraic structures (rings)

If one is given a ring $R$ with a unity $u$, what are the steps one would have to take to prove that some element of $R$ named $s$ has a multiplicative inverse, where $-s$ also has a multiplicative ...
0
votes
1answer
21 views

Probability with Loaded Dice.

The Question Suppose that a die is biased (or loaded) so that 3 appears twice as often as each other number but that the other five outcomes are equally likely. What is the probability that an odd ...
0
votes
0answers
40 views

Finding spanning trees using Depth-First Search

I am wondering if root in spanning trees using Depth-First Search can have more than $2$ children? I know this is a silly question, but there is an example in the book which involves only $2$ ...
1
vote
1answer
56 views

Induction Proof with Combinations?

Show that for all $n\geq0$ $$\binom{n}{0}3^n+\binom{n}{1}3^{n-1}+\dotsc+ \binom{n}{n-1}3^{1}+\binom{n}{n} $$ $$= \binom{n}{0}5^n-\binom{n}{1}5^{n-1}+\binom{n}{2}5^{n-2}-\binom{n}{3}5^{n-3}+\dotsc ...
1
vote
3answers
39 views

Combinatorial Argument with Natural Numbers

Give a combinatorial argument to show that all natural numbers n ≥ k ≥ m c(n,k) * c(k,m) = c(n,m) * c((n-m),(k-m)) where c stands for combination.
1
vote
0answers
22 views

Finding Equivalence Classes for Infinite Sets

Let R be the relation on the set of rational numbers Q defined as follows: for all q, r ∈ Q, qRr iff q − r ∈ Z, where Z is the set of integers. R is an equivalence relation on Q. What is the ...
0
votes
1answer
21 views

Changing exponent sign

Sorry for the bad title, I am not sure how do I name it. Find all the roots that satisfy $z^4$ $$z^4 =\frac 12 e^{-i{\frac π7}} $$ $$z^4 = \frac 12 e^{i{\frac {13\pi}7}} $$ Therefore, the roots are. ...
26
votes
9answers
2k views

Monty Hall Problem with Five Doors

My math class went over the original Monty Hall problem a few days ago, then looked at a related question where the number of doors was increased to five. There was a struggle to figure out what the ...
0
votes
2answers
15 views

Function bijective proving.

Let $\mathbb{C}$ be the set of all complex number. $z\in \mathbb{C}$ Given a function $$ f : \mathbb{C} \to \mathbb{C} $$ $$f(z) = (1+2i)z+5i$$ Prove that it is bijective. First, prove ...
2
votes
1answer
28 views

Euler characteristic of closed surface

Assume that you have a closed surface that can be covered by finitely many triangles. Then $K(p)= 6-val(P)$ where P is a vertex and $val(P)$ the number of edges that lead to this vertex. Now, I am ...
-1
votes
0answers
22 views

Is it true that a tree on n vertices has n-1 edges and graph has 2n edges? [on hold]

I'm a bit confused how can these two theorems exist at the same time. A tree on n vertices has n-1 edges but graph has 2n edges [Hand-Shaking Lemma]. I know Induction Proof for the first part but the ...
1
vote
1answer
18 views

Size of an interval

Can someone explain to me how I can prove how many elements are there in a given interval? For example, in semi-open interval $[n,m)$, the number of elements in it is equal to $m-n$, and for a closed ...
-1
votes
1answer
27 views

Probability standard deck of 52 cards [on hold]

What is the probability that five cards selected at random from a standard deck of 52 cards contain an ace? 52 cards 4 aces in a deck of 52cards So the answer is: 4/52 = 1/13?
0
votes
2answers
46 views

Help to write the generating function

How do I write the generating function and the closed for form the generating function The sequence is 0 0 0 1 1 1 1 1 1 Is this correct? $$A(x) = 0+0x+0x^2+1x^3+1x^4+1x^5+1x^6+1x^7+1x^8$$ This is ...
-1
votes
1answer
26 views

Prove that the sieve of Eratosthenes crosses off all composite numbers on the list but retains all the primes. [on hold]

Prove that the Sieve of Eratosthenes crosses off all composite numbers on the list but retains all the primes. I don't know where to start and how to strictly prove this statement.
2
votes
1answer
47 views

Let n and r be positive integers with n ≥ r. [duplicate]

Let n and r be positive integers with n ≥ r. Prove that ($\tfrac{r}{r}$) + ($\tfrac{r + 1}{r}$) + • • • + ($\frac{n}{r}$) = ($\tfrac{n + 1}{r + 1}$) I was trying to do this, but I'm keep over ...
0
votes
0answers
28 views

A mathematical statement is logically equivalent to a related statement

I have to finish the statement: A mathematical statement and its ____________ are logically equivalent. My guess is contrapositive but I do not think that's right. Any help will be appreciated. ...
0
votes
2answers
15 views

Prime Factorizations that divide each other

Let n have prime factorization n = p^s1 · p^s2 · · · p^sk and let m have prime factorization m = q^t1 · q^t2 · · · q^tl If n|m, what must be true about the corresponding lists of primes and the ...
0
votes
1answer
26 views

Probability of Rolling 3 dice versus 2 dice

The Question Which is more likely: rolling a total of 9 when two dice are rolled or rolling a total of 9 when three dice are rolled? My Work First we have to determine the probability of two die ...
0
votes
0answers
14 views

Predicate logic truth value same?

Consider the predicate $$P(x,y,z) = xyz = 1",$$ for $$ x,y, z \in R,$$ $$x; y; z > 0.$$ $1 - \forall x; \forall y; \exists z; P(x; y; z). $ $2 - \exists x; \forall y; \forall z; P(x; y; z). $ ...
1
vote
3answers
23 views

Show that $7\mid 2^{3n} -1 \,\,\,\forall n\in \mathbb N^+$

Show that $7\mid 2^{3n} -1 \,\,\,\forall n\in \mathbb N^+$ Should I prove this by induction? If so, how should I go about it?
0
votes
1answer
27 views

How to define open and closed functions whose domain or range is a discrete metric space?

I encountered that a function is open or closed in my analysis book [Herbert Amann, 2005], and it illustrates it in this way: A function $f: X \xrightarrow{} Y$ between metric spaces $(X,d)$ and ...
0
votes
4answers
28 views

Probability of winning first, second or third in a contest with 100 contestants

The Question Suppose that 100 people enter a contest and that different winners are selected at random for first, second, and third prizes. What is the probability that Michelle wins one of these ...
-1
votes
1answer
27 views

Discrete: Boolean Function 1 [on hold]

Let $X = \{x_1, x_2,\dots,x_n\}$ be a set of $n$ real numbers. Let $A$ be the average of the numbers in $X$. Prove that at least one of the $x_i ∈ X$ is greater than or equal to $A$.
0
votes
2answers
18 views

Probability of a five-card poker hand contains cards of five different kinds and does not contain a flush or a straight?

Important Information There are 13 kinds of card in poker and 4 distinct suits for each kind of card. A Flush is 5 cards of the same suit in one hand A straight is a hand with 5 cards of ...
0
votes
2answers
113 views

Arranging books on the shelf.

There are five distinct computer science books, three distinct mathematics books, and two distinct art books. In how many ways can these books be arranged on a shelf if no two of the three mathematics ...
-1
votes
0answers
44 views

Injective and Surjective Proofs

Suppose that $f:N\to A$ and $g:N\to B$ are bijective functions, and define a new function $h : N \to A \cup B$ by $$h(x)=\begin{cases}f(x/2)&\text{ if $x$ is even},\\g((x+1)/2)&\text{ if $x$ ...
0
votes
1answer
98 views

prove that the board contains a nontrivial rectangle whose 4 corner squares are all black or all red??

the question is, A 3 x 7 rectangle is divided into 21 squares each of which is coloured red or black. prove that the board contains a nontrivial rectangle (not 1 x k or k) whose 4 corner squares are ...
0
votes
1answer
123 views

Prove that the board contains a nontrivial rectangle.

A 3 × 7 rectangle is divided into 21 squares each of which is colored red or black. Prove that the board contains a nontrivial rectangle (not 1 × k or ...