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

learn more… | top users | synonyms

157
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!}}}}}) ...
100
votes
14answers
7k 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 ...
70
votes
14answers
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 ...
53
votes
15answers
7k 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 ...
48
votes
19answers
10k 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 ...
44
votes
3answers
7k 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 ...
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 ...
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 ...
37
votes
4answers
735 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 ...
36
votes
26answers
3k 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 ...
33
votes
5answers
954 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 ...
32
votes
20answers
6k 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 ...
30
votes
0answers
689 views

On the number of complete and gap-free compositions

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 ...
27
votes
2answers
409 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
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 ...
23
votes
7answers
24k 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 ...
23
votes
4answers
1k 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
951 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, ...
22
votes
8answers
48k 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 ...
22
votes
1answer
614 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
4answers
3k 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, ...
18
votes
4answers
1k views

Is the number $333, 333, 333, 333, 333, 333, 333, 333, 334$ a perfect square?

I know that if the number is a perfect square then it will be congruent to 0 or 1 (mod 4). Now since the number is even, I know that it is either 0 or 2 (mod 4). How would I go about answering this? ...
18
votes
2answers
809 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 ...
17
votes
4answers
369 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 ...
17
votes
2answers
859 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} ...
17
votes
6answers
497 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 ...
16
votes
3answers
505 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 ...
16
votes
1answer
544 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
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 ...
15
votes
7answers
5k 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
602 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 ...
15
votes
2answers
924 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
2answers
10k 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.
14
votes
12answers
849 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
4answers
303 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
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 ...
14
votes
2answers
270 views

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

Post-Bounty Edit: Still no answer; will gladly accept if someone can provide a reference. Earlier Edit: It appears that the answer is "yes," either by an already existent publication or by ...
14
votes
1answer
249 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
246 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
7answers
962 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
638 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 ...
13
votes
3answers
508 views

Prove that if 33 rooks are placed on a chessboard, at least five don't attack one another

The question asks to prove that when 33 rooks are placed on an $8 \times 8$ chessboard that there are a total of 5 rooks that aren't attacking each other. What I know: 64 squares Rooks attack in ...
13
votes
4answers
317 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
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 ...
12
votes
2answers
454 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.
12
votes
3answers
686 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
3answers
292 views

$\frac{1}{7} + \frac{1\cdot 3}{7\cdot 9} + \frac{1\cdot 3\cdot 5}{7\cdot 9\cdot 11} + …$

If the sum $\frac{1}{7} + \frac{1\cdot 3}{7\cdot 9} + \frac{1\cdot 3\cdot 5}{7\cdot 9\cdot 11} + ...$ to 20 terms is $\frac{m}{n}$, reduced fraction, then what is $n-4m$? This is a question I dug ...
12
votes
5answers
300 views

How many prime numbers are there in between $1000!+1$ and $1000!+1000$, inclusive?

I know $1000!$ is not a prime number as any number $1000$ or less is a divisor, but how would I know if $1000!+1$ is prime? Any hints? Also, use the above question to prove that you can find $n$ ...
12
votes
2answers
305 views

What problems are easier to solve in a higher dimension, i.e. 3D vs 2D?

I'd be interested in knowing if there are any problems that are easier to solve in a higher dimension, i.e. using solutions in a higher dimension that don't have an equally optimal counterpart in a ...
12
votes
2answers
569 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 ...