Discrete mathematics is the study of mathematical structures that are fundamentally discrete rather than continuous.

learn more… | top users | synonyms

8
votes
1answer
4k views

How to convert formula to disjunctive normal form?

Formula is: $((p \wedge q) → r) \wedge (¬(p \wedge q) → r)$ This is what I've already done: $$((p \wedge q) → r) \wedge (¬(p \wedge q) → r)$$ $$(¬(p \wedge q) \vee r) \wedge ((p \wedge q) \vee r)$$ ...
8
votes
2answers
238 views

A modified NIM game

Let's play a game of NIM, but with a catch! We have exactly three piles of stones with sizes $a$, $b$ and $c$, all of which are different. We move in turns. In every move, we can select a pile and ...
8
votes
1answer
200 views

Function mapping challange

For a given set $A=\{1, 2, 3, 4, \ldots, n\}$, find the number of non-constant mappings (associations ) $f$ from $A$ to $A$ such that $f(k) \leq f(k + 1)$ and $f(k) = f(f(k + 1))$. This is ...
8
votes
1answer
150 views

$n \times n$ lattice graph with partial derivatives bounded by $1$ has $n$ equal values.

I once proved this question many years ago but now I have completely forgotten how I did it. I remember it being a fun problem and wouldn't mind seeing a proof again, with the likelihood of it being ...
8
votes
1answer
137 views

For how many $n \in \mathbb{N}$ is $\sqrt{n^2+2379}$ natural?

Here's my attempt at a solution: the expression $\sqrt{n^2+2379}$ is natural iff $$n^2 + 2379 = x^2, \quad \mbox{ for some } x \in \mathbb{N}.$$ Therefore $$(x+n)(x-n)=2379=3 \cdot 13 \cdot 61.$$ I ...
8
votes
1answer
208 views

Error correction code handling deletions and insertions

I have data which is expressed in form of fixed-length sequence of decimal digits, typically 10 digits in length. I'm looking for error correction code that would allow me to append one or more ...
8
votes
1answer
444 views

Into how many parts do $n$ ellipsoids divide $\mathbb{R}^{3}$?

What is the maximum number of regions into which $\mathbb{R}^{3}$ can be divided by $n$ ellipsoids? (Each ellipsoid has the same size). Let´s denote this number by $r_{n}$. Clearly $r_{1}=2$. But ...
8
votes
1answer
380 views

Throwing balls into $b$ buckets: when does some bucket overflow size $s$?

Suppose you throw balls one-by-one into $b$ buckets, uniformly at random. At what time does the size of some (any) bucket exceed size $s$? That is, consider the following random process. At each of ...
8
votes
2answers
161 views

Given $N$, count $\{(m,n) \mid 0\leq m<N, 0\leq n<N, m\text{ and } n \text{ relatively prime}\}$

I'm confused at exercise 4.49 on page 149 from the book "Concrete Mathematics: A Foundation for Computer Science": Let $R(N)$ be the number of pairs of integers $(m,n)$ such that $0\leq m < N$, ...
8
votes
0answers
75 views

A group acting on functions of functions of functions

Given a group acting on a set $X$, there is a standard way to define an action of the group on the set of functions of $X$. This can be extended to the set of functions of functions of $X$ as I show ...
8
votes
0answers
494 views

A constrained topological sort?

Suppose that one has a directed, acyclic graph G, and each vertex $v$ contains a (positive) value $a_v$. Additionally, let $r$ be a constant. For my purposes, $r>1$, but this might not matter. ...
7
votes
9answers
1k views

prove for all $n\geq 0$ that $3 \mid n^3+6n^2+11n+6$

I'm having some trouble with this question and can't really get how to prove this.. I have to prove $n^3+6n^2+11n+6$ is divisible by $3$ for all $n \geq 0$. I have tried doing $\dfrac{m}{3}=n$ and ...
7
votes
6answers
1k views

Number of 6-digit passwords, starting with even or ending with odd digit

My problem is A password consists of six digits, each in $\{0,\ldots,9\}$ How many passwords start with an even digit or end with an odd digit? the answer is $750,000.$ I would like to know ...
7
votes
3answers
5k views

What is a null set?

I am very confused with null sets. I get that a set which has no elements will be called a null set but I am not getting the examples given below. Please help me by explaining how $P,Q,R$ are all ...
7
votes
10answers
2k views

Prove by induction that $5^n - 1$ is divisible by $4$.

Prove by induction that $5^n - 1$ is divisible by $4$. How should I use induction in this problem. Do you have any hints for solving this problem? Thank you so much.
7
votes
3answers
1k views

Counting zero-digits between 1 and 1 million

I just remembered a problem I read years ago but never found an answer: Find how many 0-digits exist in natural numbers between 1 and 1 million. I am a programmer, so a quick brute-force would ...
7
votes
2answers
957 views

How many bins do random numbers fill?

Given is a sequence $\langle a_1,a_2,\ldots,a_n\rangle$ over the alphabet $\{1,2,\ldots,m\}$ chosen uniformly at random among the $m^n$ possibilities. What is the expected size of the set ...
7
votes
5answers
454 views

How does one find a formula for the recurrence relation $a_{1}=1,a_{2}=3, a_{n+2}=a_{n+1}+a_{n}?$

I am self-studying Discrete Mathematics, and I have two exercises to solve. Find a formula for the following recurrence relation: (translated from Portuguese) a) $a_{1}=3,a_{2}=5, ...
7
votes
4answers
266 views

Not understanding the concept of equivalence class

Let $U$ be a set defined: $U=\{(x,y)\in \Bbb R^2\mid x^2+y^2=1; xy\neq 0\}$, and let $R$ be relation defined: $(x_1,y_1)R(x_2,y_2) \iff (x_1 \cdot x_2>0∧y_1\cdot y_2>0)$. I was to prove it's ...
7
votes
4answers
563 views

Closed-form expressions for sums

I've got a problem with deducing closed-form expressions for sums: $1) \ \sum_{k=0}^{m}(-1)^k {n \choose k} {n \choose m-k}$ $2) \ \sum_{A,B\subseteq X} |A\cup B|$ where $|X|=n$ Can anyone help me? ...
7
votes
5answers
174 views

Does $\{1,2,\ldots,3000\}$ contain a subset of $2000$ integers with no member twice another?

Does the set $X=\{1,2,\ldots,3000\}$ contain a subset $A$ of $2000$ integers in which no member of $A$ is twice another member of $A$? I started by putting $P=[1501,3000]$, but twice any integer in ...
7
votes
2answers
454 views

Visualizing Concepts in Mathematical Logic

If you were forced to speculate or offer anecdotal evidence, how would you say excellent practicioners of mathematical logic coneptually grasp statements like: $$ \vdash ((P \rightarrow Q) ...
7
votes
2answers
336 views

Given three integers in $\{0,\ldots,100\}$ which sum up to $100$. What is the probabilty that two of them are the same?

We pick $3$ numbers (one by one) from set $\{0,1,...,100\}$. What is probabilty that two numbers are the same if sum of those $3$ numbers is $100$? My solution: Which two are the same we can pick in ...
7
votes
2answers
393 views

Fibonacci numbers divisible by $9$

The $n$th Fibonacci number $F_n$ is defined as follows,$$F_1=F_2=1\mbox{ and } F_{n+2}=F_{n+1}+F_{n}\mbox{ for } n\geq 1$$ I want to know how many of the first $1000$ Fibonacci numbers are divisible ...
7
votes
1answer
257 views

Spectrum of a real number

Whilst reading Concrete Mathematics, the authors mention something which they refer to as the "spectrum" of a real number (pg. 77): We define the spectrum of a real number $\alpha$ to be an ...
7
votes
4answers
268 views

How many sequence of integers ($j_1 , j_2 , . . . , j_k$) are there such that $0 ≤ j_1 ≤ j_2 ≤ . . . ≤ j_k ≤ n$?

I need to solve the problem, How many sequence of integers ($j_1 , j_2 , . . . , j_k$) are there such that $0 ≤ j_1 ≤ j_2 ≤ . . . ≤ j_k ≤ n$? I've been given a hint, (Hint: Reduce the ...
7
votes
3answers
2k views

Prove that if $2^n - 1$ is prime, then $n$ is prime for $n$ being a natural number

Prove that if $2^n - 1$ is prime, then $n$ is prime for $n$ being a natural number I've looked at http://math.stackexchange.com/a/19998 It is known that $2^n-1$ can only be prime if $n$ is ...
7
votes
2answers
136 views

Every 33-length subsequence of $1,2,\dotsc,122$ contains a three term arithmetic progression

Is it possible to prove that every 33-length subsequence of the sequence $1,2,3,\dotsc,122$ contains a three term arithmetic progression? Maybe I should post it on mathoverflow
7
votes
2answers
299 views

Existence of infinitely many integers $n$ such that $2^n$ ends with $n$

Can anyone please help me on the following proof: Prove that there exist infinitely many positive integers $n$ such that $2^n$ ends with $n$ in decimal notation, i.e. $2n = \ldots n$.
7
votes
4answers
1k views

Proof by Induction: Alternating Sum of Fibonacci Numbers [duplicate]

Possible Duplicate: Show that $f_0 - f_1 + f_2 - \cdots - f_{2n-1} + f_{2n} = f_{2n-1} - 1$ when $n$ is a positive integer This is a homework question so I'm looking to just be nudged in ...
7
votes
3answers
4k views

Inclusion-exclusion principle: Number of integer solutions to equations

The problem is: Find the number of integer solutions to the equation $$ x_1 + x_2 + x_3 + x_4 = 15 $$ satisfying $$ \begin{align} 2 \leq &x_1 \leq 4, \\ -2 \leq &x_2 \leq 1, \\ 0 \leq ...
7
votes
2answers
215 views

maximum number of edges to be removed to possess a property

I am working on a problem. We know that on squaring a cycle, degree of every vertex is 4. For squares of cycles, we know if we delete any arbitrary edge then still eccentricity is same for all ...
7
votes
4answers
176 views

Let $a_n$ be the $nth$ term of the sequence $1, 2, 2, 3, 3, 3, 4, 4, 4, 4, \dots$

Question:Let $a_n$ be the $nth$ term of the sequence $1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6\dots$, constructed by including the integer $k$ exactly $k$ times. Show that $a_n = ...
7
votes
3answers
625 views

Decomposing a discrete signal into a sum of rectangle functions

Hello math@stackexchange community ! I have a simple question that seems to have a non trivial answer. Given a discrete one dimensional signal $w(x)$ defined in a finite range, and the boxcar ...
7
votes
2answers
476 views

If we have $m$ indistinguishable objects how many ways is it possible to put them in $n$ indistinguihable positions?

if we have $m$ indistinguishable objects, how many ways is it possible to put them in $n$ indistinguishable positions? (for 2 cases 1: without empty position allowed 2: empty positions are allowed.) ...
7
votes
2answers
329 views

For all $n>2$: there exists $p$ prime: $n<p<n!$

The question is: For all $n>2$, where $n \in \mathbb Z$: there exists $p$ prime such that $n<p<n!$ Here is my Proof: $\forall$ $p<n: p|n!$, or $p$ divides $n!$ Since $n!$ and $n!-1$ ...
7
votes
4answers
9k views

What five odd integers have a sum of $30$?

I've been asked the following question: What five odd integers from the set $\{1, 3, 5, 7, 9, 11, 13, 15\}$ that when summed together equals to $30$? Note that any integer can be used more than ...
7
votes
1answer
125 views

A finite sum involving the binomial coefficients and the harmonic numbers

Wikipedia has a proof of the identity $$ H_{n} =\sum_{k=1}^{n} (-1)^{k-1} \binom{n}{k} \frac{1}{k}$$ http://en.wikipedia.org/wiki/Harmonic_number#Calculation Curiously, there is also the identity ...
7
votes
1answer
92 views

Number of permutations $\langle a_1,\ldots,a_n\rangle$ of $\{ 1,\ldots ,n \}$ with $a_{i+1} - a_i \ne 1$

Prove that for $n>0$, the number of permutations $\langle a_1,\ldots,a_n\rangle$ of the set $\{ 1,\ldots ,n \}$, where $a_{i+1} - a_i \ne 1$ for $ i = 1, \ldots, n-1$ is equal to: $$D_n + ...
7
votes
1answer
140 views

Graph, two colors, no path length 3

I've just begun studying graph theory and I have some difficulty with this problem. Could you tell me how to go about solving it? In a graph $G$ all vertices have degrees $\le 3$. Show that we can ...
7
votes
3answers
216 views

Changing Summation Index Question

I'm sorry if this seems like a very novice question, but I am still relatively new to the world of discrete math ( still in 9th grade). I've been reviewing some of the concepts I learned in a ...
7
votes
2answers
411 views

A magic trick with synchronizing words

See the following magic trick. http://www.speedyadverts.com/SAEntertainment/html/realmagic4.html Spoiler Alert Believe it or not, the lady didn't really read your mind; she is not even a real lady ...
7
votes
2answers
211 views

Combinatorial proof for identity $\left(\!\!\binom{n\vphantom{1}}{k}\!\!\right)=\left(\!\!\binom{k+1}{n-1}\!\!\right)$ (multiset coefficients)

In class we have recently started using combinatorial proofs. I have tried this problem that our teacher has assigned as a "challenge". I understand how to receive the left hand side, but am ...
7
votes
1answer
140 views

Equation $\displaystyle\sum_{k=0}^{n-1}(-1)^{n-k-1}\dfrac{(n+k)!}{(k!)^2(n-k-1)!}=n^2$

I think this equality is very inters prove that: $\displaystyle\sum_{k=0}^{n-1}(-1)^{n-k-1}\dfrac{(n+k)!}{(k!)^2(n-k-1)!}=n^2$
7
votes
1answer
152 views

Connecting cells by line and column permutations in a finite grid

I'd like to know whether the following simple problem has been studied before and if any solution is known. Let G be a finite (MxN) grid, S a subset of G's cells (the "crumbs"). Two crumbs are said ...
7
votes
1answer
88 views

Prove this is an equivalence relation.

Define a relation of $\mathbb{Q} -$ {$0$} as follows: $x$ ~ $y$ $\Leftrightarrow$ $\dfrac {x} {y} = 2^k $ for some $k \in \mathbb{Z}$ Prove this is an equivalence relation. ATTEMPT: Reflexive: ...
7
votes
0answers
188 views

Citation for subset complement result

Let $S = \{s_1, \ldots, s_n\} \subset \{1, \ldots, 2n\}$. Consider two operations on $S$, unfortunately both called complement in different setting: let $A(S) = \{1, \ldots, 2n\} \setminus S$ (set ...
7
votes
0answers
155 views

A variation on the Look and Say Sequence and some questions about it.

For information on the sequence mentioned in the title, see http://en.wikipedia.org/wiki/Look-and-say_sequence. This is an original problem. Suppose instead of "describing" the numbers in a string in ...
6
votes
3answers
895 views

Is it possible to have a rule which generates: 2, 4, 6, 8, 10, 12, 14, 16, -23?

This is on Lagrange Interpolations . . . Is it possible to have a rule which generates the sequence: 2, 4, 6, 8, 10, 12, 14, 16, -23? The hint that he gave us is to use Summation Products, the only ...
6
votes
1answer
618 views

In a group of 26 people, is it possible for each person to shake hands with exactly 3 other people?

In a group of 26 people, is it possible for each person to shake hands with exactly 3 other people? Does anybody know how to solve this?