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
223 views

What's the most efficient way to put all the stones in one pile?

There are $k$ piles of $n_i$ stones, on every move you can choose two piles with sizes $a$ and $b$ and if $a \ge b$ take from the first pile $b$ stones and put to the second one, on other hand if $a ...
9
votes
2answers
11k 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)$$ ...
9
votes
1answer
148 views

How and what to teach on a first year elementary number theory course?

In the late 80’s and early 90’s there was the idea of ‘calculus reform’ and some emphasis and syllabus changed. The order of doing things in calculus also changed with the advantage of technology. ...
9
votes
1answer
306 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 ...
9
votes
1answer
99 views

$\{1, 2, . . . , 49\}$ is partitioned into $3$ subsets. Prove that at least $1$ of them contains $3$ different numbers $a,b,c$ such that $a+b=c$

As the title says, I'm asked to prove that at least one of the subsets contains three different numbers $a, b$ and c such that $a + b = c$. I tried to prove it but it is more difficult than it ...
9
votes
1answer
746 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
66 views

Show by combinatorial argument that ${2n\choose 2} = 2{n \choose 2} + n^2$

So i was given this question. Show by combinatorial argument that ${2n\choose 2} = 2{n \choose 2} + n^2$ Here is my solution: Given $2n$ objects, split them into $2$ groups of $n$, $A$ and $B$. ...
9
votes
2answers
241 views

Counting sets by their connectedness

Let $U = \{u_1, u_2, \ldots , u_m \}$ where each $u_i$ is an $r$-subset of $[n]$ and $\,\bigcup u_i \!=\! [n]$. Construct the intersection graph of $U$. That is, let node $i$ correspond to $u_i$ and ...
9
votes
1answer
196 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 ...
9
votes
1answer
154 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
113 views

Interesting shapes using probability and discrete view of a problem

Suppose we have a circle of radius $r$, we show the distance between a point and the center of the circle by $d$. We then choose each point inside the circle with probability $\frac{d}{r}$ , and turn ...
9
votes
0answers
162 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
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 ...
8
votes
6answers
1k views

If $xy$ and $x+y$ are both even integers (with $x,y$ integers), then $x$ and $y$ are both even integers

The title statement can be proven using the contrapositive, note that $x$ odd or $y$ odd means that at least one of $x\cdot y,x+y$ is odd. Is there a way to prove the statement directly? To ...
8
votes
4answers
2k 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
9answers
2k views

What do we actually prove using induction theorem?

Here is the picture of the page of the book, I am reading: $$P_k: \qquad 1+3+5+\dots+(2k-1)=k^2$$ Now we want to show that this assumption implies that $P_{k+1}$ is also a true statement: ...
8
votes
3answers
1k 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 ...
8
votes
3answers
4k views

The number of ways 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 ...
8
votes
2answers
275 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
3answers
28k views

Largest prime factor of 600851475143 [duplicate]

I'm trying to use a program to find the largest prime factor of 600851475143. This is for Project Euler here: http://projecteuler.net/problem=3 I first attempted this with the code that goes through ...
8
votes
2answers
524 views

Is the given relation transitive?

Consider the relation: $$R = \{(a,b), (a,c), (c,c), (b,b), (c,b), (b,c)\}$$ on the set $A = \{a,b,c\}$. Is $R$ transitive? I said no because $$[(c, c) \wedge (a, c)] \Longrightarrow (c,a)$$ is a ...
8
votes
2answers
4k views

What is the difference between necessary and sufficient conditions?

If $\quad p \implies q\quad $ ($p$ implies $q$), then $p$ is a sufficient condition for $q$. If $\quad \bar p \implies \bar q \quad$ (not $p$ implies not $q$), then $p$ is a necessary condition for ...
8
votes
4answers
179 views

Generating functions - deriving a formula for the sum $1^2 + 2^2 +\cdots+n^2$

I would like some help with deriving a formula for the sum $1^2 + 2^2 +\cdots+n^2$ using generating functions. I have managed to do this for $1^2 + 2^2 + 3^2 +\cdots$ by putting $$f_0(x) = ...
8
votes
4answers
298 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
221 views

How to distinguish between combination and permutation questions?

How do you distinguish combination and permutation question? An example of a combination question: Example: How many different committees of 4 students can be chosen from a group of 15? ...
8
votes
1answer
849 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
1answer
70 views

How many rectangles are there on an $8 \times 8$ checkerboard?

How many rectangles are there on an $8 \times 8$ checkerboard? \begin{array}{|r|r|r|r|r|r|r|r|} \hline & & & & & & & \\ \hline & & & ...
8
votes
5answers
200 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
6answers
339 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
2answers
10k views

Correct way to calculate numeric derivative in discrete time?

Given a set of discrete measurements in time $x_t, t \in \{0,\Delta t, 2\Delta t,\ldots,T-\Delta t,T\}$, what is the correct way to compute the discrete derivative $\dot x_t$. Is it more correct to ...
8
votes
3answers
5k 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
3answers
908 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
1answer
10k views

What is the prerequisite knowledge for learning discrete math?

To become a better computer programmer I would like to take the time to learn discrete mathematics, but I am positive that I do not have the required existing knowledge to do so. So I would like to ...
8
votes
3answers
4k views

What's the difference between a contrapositive statement and a contradiction? [duplicate]

I keep mixing them up, because they are very similar. Some contrapositives resemble some contradictions.
8
votes
3answers
147 views

Number of $n^2\times n^2$ permutation matrices with a 1 in each $n\times n$ subgrid

I found the following question in a paper I was trying to solve: The following figure shows a $3^2 \times 3^2$ grid divided into $3^2$ subgrids of size $3 \times 3$. This grid has $81$ cells, $9$ in ...
8
votes
1answer
12k views

Converting to Chomsky Normal Form

I am trying to learn how to convert any context free grammar to Chomsky Normal Form. In the example below, I tried to apply Chomsky Normal Form logic, to result in a grammar, where every symbol either ...
8
votes
2answers
1k views

Proof of clockwise towers of Hanoi variant recursive solution

This is from one of the exercises in "Concrete Mathematics", and is something I'm doing privately, not homework. This is a variant on the classic towers of Hanoi, where all moves must be made ...
8
votes
2answers
295 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
359 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 ...
8
votes
5answers
156 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
202 views

What is the right way to define a function?

Most authors define functions this way: Given the sets $A$ and $B$. A relation is a subset of $A\times B$. Then given a relation $R$, we define $Dom_R=\{x|(x,y)\in R\}$ and $Img_R=\{x|(y,x)\in R\}$. ...
8
votes
2answers
333 views

recurrence relation $f(n)=5f(n/2)-6f(n/4) + n$

I've been trying to solve this recurrence relation for a week, but I haven't come up with a solution. $f(n)=5f(n/2)-6f(n/4) + n$ Solve this recurrence relation for $f(1)=2$ and $f(2)=1$ At first ...
8
votes
1answer
83 views

Share the beer fairly in a finite number of pours

A classical problem within measurements is that you have a $8\,\text{dl}$ mug of delicious expensive beer and need to share it evenly with your friend. However you only have two empty glasses of ...
8
votes
2answers
240 views

Counting number of distinct systems

This is an enumeration problem in conjunction with some lottery problems. Given an integer $N \ge 5$. Let a ticket be a set of 5 distinct integers between $1$ and $N$. Given an integer $T$ between ...
8
votes
1answer
432 views

Prove that there's no fractions that can't be written in lowest term with Well Ordering Principle

This is from Class Note from 6.042 ocw courses at MIT: "Well Ordering Principle" section: ( Sorry for not posting latex; I have less than 10 reputations to post images ) You can read the original ...
8
votes
1answer
163 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
142 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
219 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
527 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
1answer
169 views

$(123)!$ divided by $(25!)^x$. What is the maximum possible integral value of $x$?

The answer given is $5$. But I am getting $4$. Here is what I have done. $$25!= 2^{22}\cdot3^{10}\cdot5^6\cdot7^3\cdot11^2\cdot13\cdot17\cdot19\cdot23$$ ...