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

9
votes
1answer
562 views

How to justify the solution of this problem?

Assume $\mathbf{x} \in \mathbb R_+^N$ with support $P=\{p_1,p_2,\cdots,p_K\}$ ($P$ is unknown). We already know that $$f_1(\mathbf{x}) = f_2(\mathbf{x}) = \cdots = f_{N-1}(\mathbf{x})$$ where ...
9
votes
1answer
142 views

Binomial formula for $(x+1)^{1/3}$ (related to Newton's binomial theorem)

I know that $$\displaystyle \sqrt{1+x} = \sum_{j=0}^{\infty}\left( \frac{(-1)^{(j-1)}}{2^{2j-1}\cdot(2j-1)}\binom{2j-1}{j}x^j\right). $$ Now, I want to evaluate $\sqrt[3]{1+x}$ but stuck at some ...
9
votes
0answers
102 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 ...
9
votes
0answers
374 views

Minimal time gossip problem

The gossip problem (telephone problem) is an information dissemination problem where each of $n$ nodes of a communication network has a unique piece of information that must be transmitted to all the ...
9
votes
0answers
590 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. ...
8
votes
4answers
1k views

Coin problem with 6 and 10

I am doing a coin problem where: In a city where you only have denominations in 6 and 10. What is the largest value that this city cannot pay? In another problem that my teacher showed me, where ...
8
votes
4answers
1k views

Is any relation which contains only one ordered pair transitive?

I need clarification. Let $A=\{1,2,3\}$ be a set and $R=\{(1,2)\}$ be a relation on $A$. Is it a Transitive relation? I am confused because some text books say $R$ is transitive if it contains only ...
8
votes
2answers
270 views

How does $2^{k+1} = 2 \times 2^k$?

I ask only because my textbook infers this in an example. Where should I go to learn more about this? I'm trying to learn mathematics by Induction but my knowledge of simplifying algebraic equations ...
8
votes
4answers
293 views

“How many different integers does this give us?”

How many unique integers can you get from $\lceil2012/n\rceil$ where $n$ is a positive integer? I don't know at all where to begin to approach this problem. I thought it maybe had something to do ...
8
votes
5answers
181 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 ...
8
votes
1answer
360 views

Puzzle: Give an algorithm for finding a frog that jumps along the number line

You are playing a game, your goal in this game is to catch a frog that's leaping between natural numbers. At first, the frog is found at the number $a \in \mathbb N$ which is not known to you. Each ...
8
votes
6answers
301 views

Can we always draw $n/3$ disjoint triangles from $n$ points in the plane in general position?

Suppose we are given $n$ points in the plane, where $n$ is a multiple of $3$ and no three of these points lie on a line. Is it possible to group all of these points into sets of three, so that if we ...
8
votes
4answers
276 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 ...
8
votes
2answers
2k views

Prove that $\mathcal{P}(A)⊆ \mathcal{P}(B)$ if and only if $A⊆B$. [duplicate]

Here is my proof, I would appreciate it if someone could critique it for me: To prove this statement true, we must proof that the two conditional statements ("If $\mathcal{P}(A)⊆ \mathcal{P}(B)$, ...
8
votes
3answers
3k 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 ...
8
votes
2answers
204 views

How find that $\left(\frac{x}{1-x^2}+\frac{3x^3}{1-x^6}+\frac{5x^5}{1-x^{10}}+\frac{7x^7}{1-x^{14}}+\cdots\right)^2=\sum_{i=0}^{\infty}a_{i}x^i$

let $$\left(\dfrac{x}{1-x^2}+\dfrac{3x^3}{1-x^6}+\dfrac{5x^5}{1-x^{10}}+\dfrac{7x^7}{1-x^{14}}+\cdots\right)^2=\sum_{i=0}^{\infty}a_{i}x^i$$ How find the $a_{2^n}=?$ my idea:let ...
8
votes
3answers
714 views

Cardinality of a discrete subset

If I am correct, a discrete subset of a topological space is defined to be a subset consisting of isolated points only. This is actually equivalent to that the subspace topology on the subset is ...
8
votes
4answers
2k 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 ...
8
votes
2answers
2k views

Minimum degree of a graph and existence of perfect matching

I was reading a result where the following proposition appears as a preliminary step (and left as exercise): Claim: Suppose $G$ is a graph on $n$ vertices ($n$ even and $n \geqslant 3$) with ...
8
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 ...
8
votes
3answers
4k views

How would I figure out how many anagrams of mississippi don't contain the word psi?

I'm really confused how I'd calculate this. I know it's the number of permutations of mississippi minus the number of permutations that contain psi, but considering there's repetitions of those ...
8
votes
3answers
273 views

Prime numbers divide an element from a set

Show that if $p$ is a prime number different from 2 and 5, then it divides at least one of the elements of the set $\left \{ 1,11,111,1111,...\right \}$.
8
votes
5answers
139 views

convert ceil to floor

Mathematically, why is this true? $$\left\lceil\frac{a}{b}\right\rceil= \left\lfloor\frac{a+b-1}{b}\right\rfloor$$ Assume $a$ and $b$ are positive integers. Is this also true if $a$ and $b$ are ...
8
votes
2answers
278 views

Solve a summation

Hi guys I have an exercise I don't know how to approach, would be cool if you could give me a tip or two! A sequence $a_{n}$ is defined by a dependency : $$ \sum_{i, j, k \geq 0}^{i+j+k = n } ...
8
votes
1answer
6k 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
334 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
207 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
157 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
139 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
227 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
476 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
419 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
163 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
100 views

Algorithm to compute fastest method of collecting $k$ re-spawning items which spawn at $n$ specified points

Let $V = v_1, \dots, v_n$ be the locations the items can spawn at, and let $U = u_1, \dots, u_k$ be the current positions of the items. We will assume a new items spawns instantly every time we ...
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
3answers
2k views

Shortest solution to order 26 alphabet letters, no two vowels occurring consecutively

What is the shortest solution to the following problem? What is the number of ways to order the 26 letters of alphabet so that no two of the vowels a,e,i,o,u occur consecutively? What I ...
7
votes
10answers
3k 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
2k 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
1k 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
485 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
5answers
8k views

How many bananas can a camel deliver without eating them all?

This is a fun puzzle I was assigned on the first day of highschool (over a decade ago). I just dug it up randomly from under my bed and thought I'd share it with the SE community. At the time, I ...
7
votes
4answers
269 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
3answers
661 views

Getting exactly one pair in a poker hand

I am not understanding this problem: In a deck of 52 cards, of 13 ranks, and 4 suits, how many different 5 card hand can we get such that, there is always exactly one pair. There is a similar ...
7
votes
3answers
477 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
4answers
604 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
2answers
361 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
577 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
4answers
7k views

Odd/Even Permutations

How do you classify a permutation as odd or even (composition of an odd or even number of transpositions)? I somewhat understand the textbook definition of it but im having hard time conceptualizing ...