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

-3
votes
0answers
22 views

Mathematical induction to prove a loop invariant [on hold]

Consider the following program segment, where $n$ is assumed to be a non-negative integer: ...
-1
votes
0answers
11 views

Discrete probability distribution question [on hold]

A player throws an ordinary unbiased die, and if it is not a 6, his score X is the number on the face showing uppermost; if he throws a 6, he has a second throw and his score X is then the total ...
1
vote
1answer
15 views

Numbers written into a square grid

I was working on a problem from The Art and Craft of Problem Solving by Zietz, in the chapter called 'The extreme principle.' Here is the problem: "The integers from 1 to $n^2$ are written into a ...
-1
votes
1answer
20 views

prove ceiling(x) - x = fp(1-x)

prove ceiling(x) - x = fp(1-x) using the facts: -> 0 <= fp(x) < 1, and fp(x) = x - ⌊x⌋ -> fp(1-x) = 1 - χℤ (x) - fp(x) -> the real interval [x,x+1) or (x,x+1] has an integer Here is my ...
-4
votes
0answers
41 views

Recall structures made from legos [on hold]

Recall structures made from legos. We do not see these as just one lego brick after another, we see substructure. Try to find some substructure in the following lines of proof. Assume r is in Q. ...
0
votes
1answer
19 views

prove that $fp(1 - x) = 1 - \chi_{\Bbb Z}(x) - fp(x)$

prove that $fp(1 - x) = 1 - \chi_{\Bbb Z}(x) - fp(x)$, where $fp(x) = x - \lfloor x\rfloor$, and $0 \le fp(x) < 1$, and $\chi_{\Bbb Z}$ is the characteristic function of the integers By the way of ...
-1
votes
1answer
28 views

Prove that, in a simple graph G with n vertices and a edges, $2a \le n^2-n$ [on hold]

Prove that, in a simple graph G with $n$ vertices and $a$ edges, $2a \le n^2-n$.
0
votes
0answers
26 views

deconvolution of exp($x^2$)

I would like to know whether we can get the function of type exp($x^2$) by convoluting any functions. That is which function convolution gives exp($x^2$). Thanks in advance
5
votes
3answers
153 views

Closed form for a binomial series

I am wondering if any knows how to compute a closed form for the following two series. $$\sum_{m=1}^{n}\frac{(-1)^m}{m^2}\binom{2n}{n+m}$$ $$\sum_{m=1}^{n}\frac{(-1)^m}{m^4}\binom{2n}{n+m}$$ ...
0
votes
0answers
21 views

For a real number x, define the fractional part of x as fp (x) := x − floor(x)

For a real number x, define the fractional part of x as fp (x) := x − floor(x). Prove that 0 ≤ fp (x) < 1. Here is my proof By the way of contradiction assume 0 > fp(x) >= 1. Suppose x is an ...
2
votes
1answer
26 views

How does one go from this step: $(\neg p \lor \neg q) \lor (p \lor q)$ to this one: $(\neg p \lor p) \lor (\neg q \lor q)$

I'm reviewing discrete math a second time (after it being over a decade since I took the course in college). How does one go from this step: $(\neg p \lor \neg q) \lor (p \lor q)$ to this one: $(\neg ...
1
vote
5answers
81 views

Proof that intervals of the form $[x, x+1)$ or $(x, x+1]$ must contain a integer.

Show that any real interval of the form $[x, x+1)$ or $(x, x+1]$ must contain a integer. Here is my proof (by contradiction) We start by saying, assume the interval of the form $[x, x+1)$ or $(x, ...
0
votes
2answers
36 views

Proving a Recursive Formula

I know there are some questions on this site about how to find a recursive formula, but I've already found the formula. I'm doing an assignment (http://mathstat.dal.ca/~svenjah/math2112/Assign6.pdf) ...
0
votes
1answer
29 views

How to convert 3 SAT Problem to a Graph using some kind of reduction ~? [on hold]

How to convert 3 SAT Problem to a Graph using some kind of reduction ~? Here is my example and I would like to transform it to a graph $( V_4 \lor V_2 \lor \lnot V_3) $ $\land (\lnot V_2 \lor V_1 ...
0
votes
1answer
58 views

Prove that two non-bald residents of NYC have exactly the same number of hairs.

In New York City there are two non-bald people who have the same number of hairs ( the human head can contain up to several hundred thousands with maximum of about 500,000) How can I prove the ...
0
votes
2answers
62 views

At least $500$ of the $25,000$ students in a school come from the same state

Imagine, in the school there are 25,000 students, at least one from each of 50 states. Than must be a group of 500 students coming from same state. I don't know what to count the 25,000 students or ...
0
votes
1answer
35 views

One to One Correspondence versus One to One Function

I'm doing some discrete math reading and I am confused by the question "if A and B are infinite sets, is it possible for there to be a 1-1 function from A to B and a 1-1 function from B to A without ...
3
votes
2answers
63 views

Closed form for solution of $t_{n+1}=t_n(t_n-2)$

As in the title I am interested in finding closed form for sequence satysfing $$t_{n+1}=t_n(t_n-2)$$ with $t_1=4$. I have tried many guesses, because I don't know if there is a metod to solve that, ...
1
vote
2answers
23 views

Proof that if a simple Graph contains at most two nodes with odd degree then it has a Euler walk

My proof would be start as the following : In general if there are two node at most, then one node used to start walking and the other to end. A) If we start from odd one, this means we have two ...
0
votes
2answers
21 views

compositions of n with k even summands and compositions of n-k with k odd summands

A composition of the number n with k summands is the representation n=a1+⋯+ak with integers ai≥1,1≤i≤k. The order of the summands is important. Show that: There are as many compositions of n ...
0
votes
2answers
25 views

Show that the sum of (outdeg(v)-indeg(v))=0

Let $G = (V,E,\Phi)$ a directed graph. Let $outdeg(v)=\#\{e \in E| source(e) = v\}$ and $indeg(v)=\#\{e \in E| sink(e) = v\}$. Show that $$\sum \limits_{v \in V}(outdeg(v)-indeg(v)) = 0$$ Can you ...
1
vote
3answers
42 views

Show that the coefficient of $x^i$ in $(1+x+\dots+x^i)^j$ is $\binom{i+j-1}{j-1}$

Show that $$\text{ The coefficient of } x^i \text{ in } (1+x+\dots+x^i)^j \text{ is } \binom{i+j-1}{j-1}$$ I know that we have: $\underbrace{(1+x+\dots+x^i) \cdots (1+x+\dots+x^i)}_{j\text{ times}}$ ...
5
votes
2answers
323 views

proof by contradiction puzzle

Consider the following game between two players: • There is an initially rectangular grid of cookies. • The cookie in the upper left corner is poisoned. • The players take turns. On a player’s ...
0
votes
1answer
48 views

Show that $c_n=\frac{n!}{4(n-4)!}$ [on hold]

Let $c_n, n\geq1$ be the number of pair $(\sigma,\tau)$ of permutations $\sigma , \tau \in S_n$ of Type $(1^{n-2},2)$ with the product $\sigma \tau$ of Type $(1^{n-4},2^2)$. Show that ...
1
vote
2answers
38 views

Prove that in a simple graph with $\geq 2$ nodes at least one node can be removed without disconnecting the graph

Prove that in any simple graph $G$ with number of nodes $\geq 2$ there is at least one node $v$ that can be removed with its all edges, and keep the graph connected? From my point of view I can say ...
0
votes
1answer
35 views

Confused by one-to-one question, I think it's order incorrectly

I have this question and it seems a tad redundant If $A$ and $B$ are infinite sets, is it possible for there to be a 1-1 function from $A$ to $B$ and a 1-1 function from $B$ to $A$ without there ...
-4
votes
2answers
39 views

I need to prove the following property of the binomial coefficient…please Help! [on hold]

$$\binom rk = \frac rk \binom{r-1}{k-1}$$ Any help is immensely appreciated!
4
votes
0answers
56 views

How do i find formula for the recurrence relation :$x_{n+1}= x^2_{n}-x^2_{n-1}$ with :$x_{-1}=0,x_{0}=\frac{3}{4}$?

How do i find formula for the recurrence relation according to the below initial conditions: $x_{n+1}= x^2_{n}-x^2_{n-1}$ with :=$x_{-1}=0,x_{0}=\frac{3}{4}$ ? Note:$n=0,1,2\cdots$ Thank you for ...
0
votes
0answers
64 views

Number of graphs with 5 vertices

Let $v_i$ where $i=1,2,3,4,5$ be vertices of a graph. Each vertex makes only one directed edge to any other vertex. For instance $v_1 \to v_2 \to v_3 \to v_4 \to v_5 \to v_1$ and $v_1 \to v_3 \to v_4 ...
0
votes
2answers
16 views

Invalid function or invalid domain

Let $ f : A \rightarrow B $ What happens if $\exists\ a\in A $ which doesn't map to any element in B ?
-2
votes
2answers
47 views

An injection from R × {0, 1} to R [on hold]

What would be an example of this An injection from R × {0, 1} to R i think it is all real numbers f(x) = x Can some one help me on this. Thanks in advance
1
vote
1answer
22 views

Proof by contradiction - Predicates and quantifiers

Consider statement, For all integers, b,c,d, if x is a rational number such that $x^2+bx+c=d$, than x is an integer. a) express above statment in the form, $Q_1 b,c,d\in U_1 ( Q_2 x\in ...
1
vote
0answers
22 views

Maximum number of edges in a subgraph of hypercube

Let $H_n$ is an $n$-dimensional hypercube, $|V(H_n)|=2^n, |E(H_n)|=n2^{n-1}$. Let $M\subset V(H_n), |M|=2^k, 1\le k<n$, and $G_M$ is a subgraph of $H_n$ induced by $M$, $V(G_M)=2^k$. Prove that ...
1
vote
1answer
27 views

Lines in the plane from Concrete Mathematics. How many bounded regions are there?

I'm studying Concrete Mathematics by Donald Knuth. While doing the warmup questions, from the recurrence chapter, I stumbled upon an interesting problem. I have an intuition about the solution but I ...
0
votes
5answers
69 views

How can I prove that $4^{2012} \mod 8$ is $0$

Prove that $4^{2012} \mod 8 = 0$ I'm not really sure what rule I should use to prove this.
1
vote
0answers
100 views

Maths puzzle 1: smart play with sets

Let $$X=\{ a, b, c, d, e, f, {ab}, {ac}, {ad}, {ae}, {af}, {bc}, {bd}, {be}, {bf}, {cd}, {ce}, {cf}, {de}, {df}, {ef}, {abc}, {abd}, {abe}, {abf}, {acd}, {ace}, {acf}, {ade}, {adf}, {aef}, {bcd}, ...
5
votes
3answers
695 views

Number of 11-digit length number with all 10 digits and no consecutive same digits

Here is the question: In how many ways we can construct a 11-digit long string that contains all 10 digits without 2 consecutive same digits. Initially, I came up with $10!9$. I thought that there ...
0
votes
2answers
35 views

Solve it by using logical proposition

Show that given logical proposition is tautology $((A \implies C) \land (B \implies C) \land \lnot C) \implies \lnot (A \lor B) $ I can apply the implication rule first and got $\lnot((A \implies ...
-2
votes
1answer
31 views

What is the best answer from choices for 15:220 :: 100:? [closed]

This question is from "DEO General Intelligence Exam" Held on 31 August 2008 by Staff selection commission of India. So, please help me solve this, which of the option best suits for this question. ...
-2
votes
1answer
46 views

How many elements are in the set $S^S$, where $S=\{a,b\}$? [on hold]

If set $S =\{a,b\}$, then how many elements will be in set $S^S$? Here $S^S$ is {Set S is Exponent of S}. Do we need to do cross product like $S*S$ when it says $(S^S)$. Please advise.
0
votes
2answers
39 views

Big-O Question 1

We have to find the least integer such that $f(x)$ is $O(x^n)$ for the given function. We also have to find the smallest corresponding witnesses $C$ and $K$. Here is what I have, let me know where I ...
0
votes
1answer
31 views

What are the composite functions

f : $\mathbb{R} \to \mathbb{R}$ $$g(x)=\begin{cases} \frac1n,&x\in\Bbb Q\text{ and }x=\frac{1}n\text{ in lowest terms}\\ \sqrt{2},&x=0\ \end{cases}$$ g(x) is the inverse of f(x) determine ...
0
votes
1answer
35 views

Is the function invertible?

$$f(x)=\begin{cases} \frac1q,&x\in\Bbb Q\text{ and }x=\frac{p}q\text{ in lowest terms}\\ 0,&x\notin\Bbb Q\;. \end{cases}$$ Is the function $f|_D$ invertible? If so, describe its inverse ...
0
votes
2answers
38 views

What is the domain of the function

I think the subset D is 1/n where n is an element of natural numbers. Can someone help me with this, thanks in advance
0
votes
3answers
28 views

Double modular exponent with Euler-Fermat

$$7^{3^{18}} \pmod{9}$$ Using this formula : $a^{\phi(m)} \equiv 1 \pmod m$ I got $7^6 \equiv 1 \pmod{9}$ and I can write $3^{18}$ as $3^6 \cdot 3^3$ And what are next steps? I got stuck here.
0
votes
0answers
19 views

RSA number sequence encryption

Encrypt the following number sequence $3,9,27$ with key $m=33$ and $r=7$ It's about RSA encryption. How should I encrypt this? Should I find the key $s$ (inverse key) and what then? $r \cdot s + ...
1
vote
1answer
30 views

Graph and tree computation

A graph is given with set of nodes $[x_1,x_2,x_3,\ldots,x_6]$ and with set of edges: $$\{[x_1,x_2], [x_1,x_3], [x_1,x_4], [x_1,x_5], [x_1,x_6], [x_2,x_3], [x_2,x_6], [x_3,x_4], [x_4,x_5], ...
0
votes
1answer
14 views

Solve the relation with congruence

On $\Bbb Z$ consider the relation $xRy \Leftrightarrow x-y \not\equiv 0 \mod 3$. Prove (with explanation), whether the relation reflexive, symmetric, antisymmetric transitive is and prove if they are ...
-1
votes
2answers
24 views

What is the adjacency matrix and number of paths of length $4$ between vertex $2$ and vertex $5$ in the null graph on $\{1,2,3,4,5\}$? [closed]

Given the following graph 1) Compute adjacency matrix 2) Compute the number of paths of length 4 from knot Nr.2 to knot Nr.5 Can anyone provide a solution how to do it?
0
votes
1answer
20 views

Bridge hands (13) Discrete Mathematics [closed]

How many bridge hands contain four cards of the three suits and one card of the fourth suit?