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

165
votes
3answers
7k 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!}}}}}) ...
114
votes
17answers
9k 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 ...
77
votes
15answers
7k views

Infiniteness of non-twin primes.

Well, we all know the twin prime conjecture. There are infinitely many primes $p$, such that $p+2$ is also prime. Well, I actually got asked in a discrete mathematics course, to prove that there are ...
56
votes
15answers
8k views

Prove if $n^2$ is even, then $n$ is even.

I am just learning maths, and would like someone to verify my proof. Suppose $n$ is an integer, and that $n^2$ is even. If we add $n$ to $n^2$, we have $n^2 + n = n(n+1)$, and it follows that ...
53
votes
20answers
11k views

Coin flipping probability game ; 7 flips vs 8 flips

Your friend flips a coin 7 times and you flip a coin 8 times; the person who got the most tails wins. If you get an equal amount, your friend wins. There is a 50% chance of you winning the game and a ...
49
votes
3answers
10k views

Proof by contradiction vs Prove the contrapositive

What is the difference between a "proof by contradiction" and "proving the contrapositive"? Intuitive, it feels like doing the exact same thing. And when I compare an exercise, one person proves by ...
46
votes
0answers
1k views

Why are asymptotically one half of the integer compositions gap-free?

This is a longish post about something that has been haunting me for a while about a kind of restricted composition, namely gap-free and complete compositions. First, I will define the terms that are ...
42
votes
1answer
1k 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 ...
38
votes
4answers
750 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 ...
37
votes
20answers
8k 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 ...
37
votes
6answers
4k views

Of any 52 integers, two can be found whose difference of squares is divisible by 100

Prove that of any 52 integers, two can always be found such that the difference of their squares is divisible by 100. I was thinking about using recurrence, but it seems like pigeonhole may also ...
36
votes
26answers
4k views

How to teach mathematical induction?

Some students are not convinced that a proof by mathematical induction is a proof. I have given the analogy of dominoes toppling but still some remain unconvinced. Is there very convincing way of ...
34
votes
7answers
30k 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 ...
33
votes
5answers
1k views

How much weight is on each person in a human pyramid?

After participating in a human pyramid and learning that it's very uncomfortable to have a lot of weight on your back, I figured I'd try to write out a recurrence relation for the total amount of ...
31
votes
9answers
3k views

Monty Hall Problem with Five Doors

My math class went over the original Monty Hall problem a few days ago, then looked at a related question where the number of doors was increased to five. There was a struggle to figure out what the ...
30
votes
9answers
64k views

Maximum board position in 2048 game

A game called 2048 is making rounds on social media. I am trying to determine the maximum score attainable for this game. Let's assume WLOG that only 2s are returned (if 4s are possible the max score ...
28
votes
8answers
2k views

What is $\gcd(0,0)$?

What is the greatest common divisor of $0$ and $0$? On the one hand, Wolfram Alpha says that it is $0$; on the other hand, it also claims that $100$ divides $0$, so $100$ should be a greater common ...
28
votes
2answers
422 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 ...
26
votes
4answers
2k 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, ...
23
votes
2answers
1k views

A fascinating number chain.

Take a two digit number $10x+y$ of which both digits are different. now add $y-x$ to this number. By repeating this process you will get a chain of numbers $45,46,48,52,49,54,53,51,47,50.$ after $50, ...
23
votes
1answer
621 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 ...
20
votes
2answers
907 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 ...
20
votes
2answers
992 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} ...
19
votes
4answers
4k 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 degree $2$ and $4$ of degree $3$. However, ...
19
votes
2answers
1k views

Understanding this pattern behind the Fibonacci sequence

To be honest, I'm pretty awful at mathematics however, when up till 6AM I do like to do random things throughout the night to keep me occupied. Tonight, I began playing with the Fibonacci sequence in ...
18
votes
6answers
540 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 ...
17
votes
9answers
1k views

What is the purpose of the first test in an inductive proof?

Learning about proof by induction, I take it that the first step is always something like "test if the proposition holds for $n = \textrm{[the minimum value]}$" Like this: Prove that ...
17
votes
3answers
517 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 ...
17
votes
4answers
376 views

Prove that $\dfrac{(n^2)!}{(n!)^n}$ is an integer for every $n \in \mathbb{N}$

Prove that $\dfrac{(n^2)!}{(n!)^n}$ is an integer for every $n \in \mathbb{N}$ I know that there are tools in Number theory to proves the required but I want to use the tool that says that if you ...
16
votes
4answers
623 views

Decreasing integers on the blackboard

There are $n\geq 2$ copies of an integer $k>0$ written on the blackboard. A move consists of choosing an integer $m>0$ on the blackboard, and replacing it as well as one other integer on the ...
16
votes
2answers
11k 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.
16
votes
1answer
653 views

How many different shapes can I make with this toy?

I have the following toy, perhaps some of you have seen it before. It consists of a bunch of cubes with an elastic string in the middle. You can bend it into different shapes like this: Or this: ...
15
votes
7answers
6k 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
4answers
319 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 ...
15
votes
2answers
1k views

Combinatorial interpretation of Binomial Inversion

It is known that if $f_n = \sum\limits_{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 ...
15
votes
3answers
2k 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 ...
15
votes
1answer
54 views

Find all $A\subseteq\mathbb{N}$ such that $A=\{|a-b|:a,b\in A\}$.

For a set $A$ of real numbers, denote $$A^\ast:=\{|a-b|:a,b\in A\}.$$ Question: Find all finite subsets $A\subseteq\mathbb{N}$ of the natural numbers such that $$A^*=A.$$ Attempt: The empty ...
14
votes
12answers
1k views

What does it mean for a number to be in a set?

Frustratingly my book gives me several examples of a number in a set but offers no explanation at all. Anyways what is going on here? According to the book $2$ is not an element of these sets: ...
14
votes
7answers
5k views

What is the proof that the total number of subsets of a set is $2^n$?

What is the proof that given a set of $n$ elements there are $2^n$ possible subsets (including the empty-set and the original set).
14
votes
2answers
483 views

Prove $\sqrt{2\sqrt{3\sqrt{\cdots\sqrt{n}}}}<3$ by induction.

Problem: prove $\sqrt{2\sqrt{3\sqrt{\cdots\sqrt{n}}}}<3$ by induction. I tried some, but stopped in $\sqrt[2^n]{n+1}$. Also tried with $2\sqrt{3\cdots}<3^2$ and so on.
14
votes
2answers
10k views

What books do you recommend before 'Concrete Mathematics'?

What book(s) do you recommend before Concrete Mathematics? Is something like "Introduction to discrete Mathematics" enough?
14
votes
2answers
2k views

There are 10 men, 10 women, and 10 rooms. Each person randomly goes into a room.

What is the expected number of rooms with at least one man and woman? Our prof. gave us the following solution however, I'm confused about the probability portion of the answer (especially the ...
14
votes
1answer
743 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+\varepsilon $, ...
14
votes
2answers
317 views

Does every “balloon” (dragon, tadpole, canoe paddle) admit a graceful labeling?

8/18/14 Edit: If anyone has a copy of a related reference, then I would be happy to see it. For now, I am accepting the answer below and considering the question answered in the affirmative: Yes. ...
14
votes
1answer
256 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 ...
14
votes
2answers
344 views

Minimum number of operations (divide by 2/3 or subtract 1) to reduce $n$ to $1$

This question is inspired by a Stack Overflow question which involves the task to find an algorithm to solve the following problem: Given a natural number $n$, what is the least number of moves ...
13
votes
8answers
2k 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 ...
13
votes
11answers
3k views

Prove that 1 + 4 + 7 + · · · + 3n − 2 = n(3n − 1)/ 2

Prove that $$1 + 4 + 7 + · · · + 3n − 2 = \frac{n(3n − 1)} 2$$ for all positive integers $n$. Proof: $$1+4+7+\ldots +3(k+1)-2= \frac{(k + 1)[3(k+1)+1]}2$$ $$\frac{(k + 1)[3(k+1)+1]}2 + ...
13
votes
7answers
1k views

Prove that the additive inverse of an odd integer is an odd integer

This is a homework problem, but I don't want the answer, just a little guidance: Prove that the additive inverse of an odd integer is an odd integer. When approaching a problem like this, how ...
13
votes
5answers
746 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 ...