Questions on discrete mathematics generally: "the study of mathematical structures that are fundamentally discrete rather than continuous"
143
votes
1answer
6k views
How many fours are needed to represent numbers up to $N$?
The goal of the four fours puzzle is to represent each natural number using four copies of the digit $4$ and common mathematical symbols.
For example, $165=(\sqrt{4} + \sqrt{\sqrt{{\sqrt{4^{4!}}}}}) ...
54
votes
11answers
3k views
Zero to the zero power - Is $0^0=1$?
Could someone provide me with good explanation of why $0^0 = 1$?
My train of thought:
$x > 0$
$0^x = 0^{x-0} = 0^x/0^0$, so
$0^0 = 0^x/0^x = ?$
Possible answers:
$0^0 * 0^x = 1 * 0^x$, so ...
39
votes
1answer
570 views
A discrete math riddle
Here's a riddle that I've been struggling with for a while:
Let $A$ be a list of $n$ integers between 1 and $k$. Let $B$ be a list of $k$ integers between 1 and $n$. Prove that there's a non-empty ...
36
votes
4answers
685 views
Partitioning the integers $1$ through $n$ so that the product of the elements in one set is equal to the sum of the elements in the other
It is known that, for $n \geq 5$, it is possible to partition the integers $\{1, 2, \ldots, n\}$ into two disjoint subsets such that the product of the elements in one set equals the sum of the ...
24
votes
2answers
346 views
Can a collection of points be recovered from its multiset of distances?
Consider $n$ distinct points $x_1,\dots,x_n$ on $\mathbb{R}$. Associated to these points is the multiset of all distances $d(x_i,x_j)$ between two points. Suppose one is only handed this multiset (you ...
22
votes
15answers
3k views
Proof that $\sum\limits_{k=1}^nk^2 = \frac{n(n+1)(2n+1)}{6}$?
I am just starting into calculus and I have a question about the following statement I encountered while learning about definite integrals:
$$\sum_{k=1}^n k^2 = \frac{n(n+1)(2n+1)}{6}$$
I really ...
22
votes
1answer
591 views
Always oddly-many ones in the binary expression for $10^{10^{n}}$?
Update: Pending independent verification, the answer to the title question is "no", according to a computation of $q(10) = 11609679812$ (which is even).
Let $q(n)$ be the number of ones in the ...
18
votes
2answers
728 views
A stronger version of discrete “Liouville's theorem”
If a function $f : \mathbb Z\times \mathbb Z \rightarrow \mathbb{R}^{+} $ satisfies the following condition
$$\forall x, y \in \mathbb{Z}, f(x,y) = \dfrac{f(x + 1, y)+f(x, y + 1) + f(x - 1, y) +f(x, ...
16
votes
2answers
666 views
What is the millionth decimal digit of the (10^10^10^10)th prime?
What is the millionth decimal digit of the $10^{10^{10^{10}}}$th prime?
(This prime is, of course, far larger than the largest currently "known" prime, the latter having nearly 13 million ...
15
votes
7answers
2k views
Proof: If n is a perfect square, $\,n+2\,$ is NOT a perfect square
"Prove that if n is a perfect square, $\,n+2\,$ is NOT a perfect square." I'm having trouble picking a method to prove this. Would contraposition be a good option (or even work for that matter)? If ...
15
votes
3answers
398 views
A (probably trivial) Induction Problem: $\sum_2^nk^{-2}\lt1$
So I'm a bit stuck on the following problem I'm attempting. Essentially, I'm required to prove that $\frac{1}{2^2}+\frac{1}{3^2}+\cdots+\frac{1}{n^2} < 1$ for all $n$. I've been toiling with some ...
14
votes
5answers
11k views
What is the best book for studying discrete mathematics?
As a programmer, mathematics is important basic knowledge to study some topics, especially Algorithms. Many websites, and my fellows suggest me to study Discrete Mathematics before going to ...
14
votes
4answers
254 views
Solve recursion $a_{n}=ba_{n-1}+cd^{n-1}$
Let $b,c,d\in\mathbb{R}$ be constants with $b\neq d$. Let
$$\begin{eqnarray}
a_{n} &=& ba_{n-1}+cd^{n-1}
\end{eqnarray}$$
be a sequence for $n \geq 1$ with $a_{0}=0$. I want to find a closed ...
14
votes
1answer
201 views
Showing $(x,y)$ pairs exist for $\sqrt{\quad\mathstrut}$
If we were to show that there exists infinitely many $(x,y)$ pairs in $\mathbb{Q}^2$ for which both $\sqrt{x^2+y^4}$ and $\sqrt{x^4+y^2}$ are rational. If the power root for $x$ and $y$ vary but never ...
13
votes
4answers
753 views
Are these 2 graphs isomorphic?
They meet the requirements of both having an = number of vertices (7)
They both have the same number of edges (9)
They both have 3 vertices of deg(2) and 4 of deg(3)
However, graph two has 2 ...
13
votes
2answers
535 views
Is there a discrete version of de l'Hôpital's rule?
When considering asymptotics of runtime functions, you often have to find limits of quotients of discrete functions, e.g.
$\displaystyle\qquad \lim\limits_{n \to \infty} ...
13
votes
2answers
541 views
Combinatorial interpretation of Binomial Inversion
It is known that if $f_n = \sum_{i=0}^{n} g_i \binom{n}{i}$ for all $0 \le n \le m$, then $g_n = \sum_{i=0}^{n} (-1)^{i+n} f_i \binom{n}{i}$ for $0 \le n \le m$. This sort of inversion is called ...
13
votes
4answers
201 views
Proof of Irrationality of e using Diophantine Equations
I was trying to prove that e is irrational without using the typical series expansion, so starting off $e = a/b $ Take the natural log so $1 = \ln(a/b)$ Then $1 = \ln(a)-\ln(b)$ So unless I did ...
12
votes
5answers
388 views
Notation Question: What does $\vdash$ mean in logic?
In a "math structures" class at the community college I'm attending (uses the book Discrete Math by Epp, and is basically a discrete math "light" edition), we've been covering some basic logic.
I've ...
12
votes
3answers
584 views
Twenty questions against a liar
Here's one that popped into my mind when I was thinking about binary search.
I'm thinking of an integer between 1 and n. You have to guess my number. You win as soon as you guess the correct number. ...
12
votes
2answers
7k views
A comprehensive list of binomial identities?
Is there a comprehensive resource listing binomial identities? I am more interested in combinatorial proofs of such identities, but even a list without proofs will do.
12
votes
4answers
294 views
How to prove $\sum\limits_{k=0}^n{n \choose k}(k-1)^k(n-k+1)^{n-k-1}= n^n$?
How do I prove the following identity directly?
$$\sum_{k=0}^n{n \choose k}(k-1)^k(n-k+1)^{n-k-1}= n^n$$
I thought about using the binomial theorem for $(x+a)^n$, but got stuck, because I realized ...
12
votes
1answer
159 views
Monochromatic squares in a colored plane
Color every point in the real plane using the colors blue,yellow only. It can be shown that there exists a rectangle that has all vertices with the same color. Is it possible to show that there exists ...
11
votes
8answers
1k views
Proof: For all integers $x$ and $y$, if $x^3+x = y^3+y$ then $x = y$
I need help proving the following statement:
For all integers $x$ and $y$, if $x^3+x = y^3+y$ then $x = y$
The statement is true, I just need to know the thought process, or a lead in the right ...
11
votes
3answers
983 views
Gay Speed Dating Problem
Here's an interesting problem that I came up with the other night.
With straight speed dating, (assuming the number of men and women are equal) the number of iterations that need to be made before ...
11
votes
3answers
2k views
Lights out game on hexagonal grid
I greatly enjoyed the Lights Out game described here (I am sorry I had to link to an older page because some wikidiot keeps deleting most of the page).
Its mathematical analysis is here (it's just ...
11
votes
2answers
436 views
A Weaker Version of the ABC Conjecture
The ABC conjecture states that there are a finite number of integer triples (a,b,c) such that $\frac {\log \left( c \right)}{\log \left( \text{rad} \left( abc \right) \right)}>1+\epsilon $, where ...
11
votes
1answer
394 views
Factorial canceling on expansion of binomial coefficients on Concrete Mathematics
On Concrete Mathematics section 5.5, which is teaching the hypergeometric functions, generalized factorials is defined as:
\[
\frac 1 {z!} = \lim_{n \to \infty} \binom{n+z}{n}n^{-z}
\]
where
\[
...
10
votes
4answers
1k views
Proof by contradiction: $r - \frac{1}{r} =5\Longrightarrow r$ is irrational?
Prove that any positive real number $r$ satisfying:
$r - \frac{1}{r} = 5$ must be irrational.
Using the contradiction that the equation must be rational, we set $r= a/b$, where a,b are positive ...
10
votes
3answers
131 views
Combinatorial proof of $\sum^{n}_{i=1}\binom{n}{i}i=n2^{n-1}$.
Prove
$$\sum^{n}_{i=1}\binom{n}{i}i=n2^{n-1}$$
I can't find counting interpretations for either of the sides. A hint of "if $S$ is a subset of $\{1, . . . , n\}$ and $S^\prime$ is its complement ...
10
votes
1answer
218 views
In naive set theory ∅ = {∅} = {{∅}}?
In naive set theory, I believe ∅ = {∅} = {{∅}} is correct, but just wanted to make sure that I understood this correctly.
∅ is an empty set, so having an empty set as an element of a set that ...
10
votes
2answers
633 views
Good upper bound for $\sum\limits_{i=1}^{k}{n \choose i}$?
I want an upper bound on $$\sum_{i=1}^k \binom{n}{i}.$$
$O(n^k)$ seems to be an overkill -- could you suggest a tighter bound ?
10
votes
4answers
245 views
Number of possibilities to cross a hexagonal lattice.
An ant walks along the line segments in the hexagonal lattice shown, from start to finish. The ant must go in the direction shown if there is an arrow, and never goes on the same line segment twice. ...
10
votes
2answers
310 views
Summation by parts of $\sum_{k=0}^{n}k^{2}2^{k}$
I want to evaluate this sum
$$\sum_{k=0}^{n}k^{2}2^{k}$$ by summation by parts (two times) and I need to know, if my approach was right.
I know the formula for summation by parts is $$\sum u\Delta ...
10
votes
2answers
237 views
What is the probability that $\pi(x) + x$ is injective?
Let $S$ be a finite group with operator + and $\pi$ be a permutation on $S$. Then what is the probability that $\pi(x) + x$ is injective over choices of $\pi$?
The concrete instantiation I'm ...
10
votes
2answers
280 views
bijection = bijection + bijection on symmetric integer intervals
Given a bijection $f:\mathbb Z \to \mathbb Z$ where $\mathbb Z$ is the set of all integers, does there always exist two bijections $g:\mathbb Z \to \mathbb Z$ and $h:\mathbb Z \to \mathbb Z$ which ...
9
votes
8answers
839 views
Showing that an equation holds true with a Fibonacci sequence: $F_{n+m} = F_{n-1}F_m + F_n F_{m+1}$
Question: Let $F_n$ the sequence of Fibonacci numbers, given by $F_0 = 0, F_1 = 1$ and $F_n = F_{n-1} + F_{n-2}$ for $n \geq 2$. Show for $n, m \in \mathbb{N}$: $$F_{n+m} = F_{n-1}F_m + F_n F_{m+1}$$
...
9
votes
4answers
262 views
Prove $1+\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}+\dots+\frac{1}{\sqrt{n}} > 2\:(\sqrt{n+1} − 1)$
Basically, I'm trying to prove (by induction) that:
$$1+\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}+\dots+\frac{1}{\sqrt{n}} > 2\:(\sqrt{n+1} − 1)$$
I know to begin, we should use a base case. In this ...
9
votes
2answers
146 views
What is the converse of this statement and is it true?
If $a$ and $b$ are relatively prime, $a\mid c$ and $b\mid c$, then $(ab)\mid c$.
I am lost. Would the converse be "If $(ab)\mid c$, then $a$ and $b$ are relatively prime and $a\mid c$ and $b\mid c$" ...
9
votes
6answers
316 views
Proof that the sum of the cubes of any three consecutive positive integers is divisible by three.
So this question has less to do about the proof itself and more to do about whether my chosen method of proof is evidence enough. It can actually be shown by the Principle of Mathematical Induction ...
9
votes
2answers
370 views
9 pirates have to divide 1000 coins…
A band of 9 pirates have just finished their latest conquest - looting, killing and sinking a ship. The loot amounts to 1000 gold coins.
Arriving on a deserted island, they now have to split up the ...
8
votes
5answers
2k views
Resources/Books for Discrete Mathematics
I am going to a Computer Science Course in University next year. I heard that Discrete Mathematics is whats required for Comp Sci so, I am looking for resources/books that I can read to get started ...
8
votes
2answers
253 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
275 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
6answers
221 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
169 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
2answers
928 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
4answers
1k views
How do I figure out what kind of distribution this is?
i've sampled a real world process, network ping times. The "round-trip-time" is measured in milliseconds. Results are plotted in a histogram:
Ping times have a minimum value, but a long upper tail.
...
8
votes
2answers
259 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.)
...
8
votes
3answers
290 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 ...
