Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [discrete-mathematics]

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.

310
votes
24answers
33k views

Zero to the zero power – is $0^0=1$?

Could someone provide me with a 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\cdot0^x=1\cdot0^0$, so $0^0=1$ $...
215
votes
4answers
9k 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=\left(\sqrt{4} + \sqrt{\sqrt{{\sqrt{4^{4!}}}...
127
votes
6answers
60k views

Using proof by contradiction vs proof of 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 ...
115
votes
31answers
59k views

Sum of First $n$ Squares Equals $\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 ...
114
votes
15answers
11k 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 ...
102
votes
15answers
15k views

What is the smallest unknown natural number?

There are several unknown numbers in mathematics, such as optimal constants in some inequalities. Often it is enough to some estimates for these numbers from above and below, but finding the exact ...
88
votes
10answers
7k views

Would you ever stop rolling the die? [duplicate]

You have a six-sided die. You keep a cumulative total of your dice rolls. (E.g. if you roll a 3, then a 5, then a 2, your cumulative total is 10.) If your cumulative total is ever equal to a perfect ...
78
votes
11answers
102k 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 Algorithms,...
64
votes
8answers
14k 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 ...
62
votes
26answers
8k views

What are some mathematically interesting computations involving matrices?

I am helping designing a course module that teaches basic python programming to applied math undergraduates. As a result, I'm looking for examples of mathematically interesting computations involving ...
60
votes
20answers
13k 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 ...
59
votes
1answer
2k views

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

Question summary The number of gap-free compositions of $n$ can already for quite small $n$ be very well approximated by the total number of compositions of $n$ divided by $2$. This question seeks ...
52
votes
5answers
1k views

Time to reach a final state in a random dynamical system (answer known, proof unknown)

Consider a dynamical system with state space $2^n$ represented as a sequence of $n$ black or white characters, such as $BWBB\ldots WB$. At every step, we choose a random pair $(i,j)$ with $i<j$ ...
51
votes
2answers
3k 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 ...
49
votes
8answers
65k 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).
46
votes
2answers
32k 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.
45
votes
13answers
8k views

Proof of the Hockey-Stick Identity: $\sum\limits_{t=0}^n \binom tk = \binom{n+1}{k+1}$

After reading this question, the most popular answer use the identity $$\sum_{t=0}^n \binom{t}{k} = \binom{n+1}{k+1}.$$ What's the name of this identity? Is it the identity of the Pascal's triangle ...
44
votes
13answers
14k views

If nine coins are tossed, what is the probability that the number of heads is even?

If nine coins are tossed, what is the probability that the number of heads is even? So there can either be 0 heads, 2 heads, 4 heads, 6 heads, or 8 heads. We have $n = 9$ trials, find the ...
44
votes
6answers
3k 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 ...
43
votes
7answers
7k 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 work....
42
votes
5answers
7k views

How do I find a flaw in this false proof that $7n = 0$ for all natural numbers?

This is my last homework problem and I've been looking at it for a while. I cannot nail down what is wrong with this proof even though its obvious it is wrong based on its conclusion. Here it is: ...
41
votes
29answers
8k 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 ...
41
votes
6answers
1k views

You have to estimate $\binom{63}{19}$ in $2$ minutes to save your life.

This is from the lecture notes in this course of discrete mathematics I am following. The professor is writing about how fast binomial coefficients grow. So, suppose you had 2 minutes to save ...
41
votes
6answers
2k views

Why is this combination of nearest-integer functions — surprisingly — continuous?

Alright, I didn't know the best way to formulate my question. Basically, whilst doing some physics research, I naturally came upon the function $$ f(x) = 2x[x] - [x]^2 $$ where I use $[x]$ as ...
41
votes
4answers
868 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 ...
38
votes
13answers
11k views

Function which creates the sequence 1, 2, 3, 1, 2, 3, …

I was wondering how to map the set $\mathbb{Z}^+$ to the sequence $1, 2, 3, 1, 2, 3, \ldots$. I thought it would be easy, but I was only able to obtain an answer through trial and error. For a ...
37
votes
3answers
3k 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, ...
37
votes
9answers
76k 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 ...
34
votes
10answers
12k views

How do I explain the Königsberg Bridge problem to a child?

I am going to demonstrate the Königsberg seven bridge problem in a science exhibition. I am also going to use a model for a more visual representation of the problem. Now, how do I explain this (the ...
34
votes
10answers
14k 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 ...
34
votes
2answers
771 views

$n$ people sitting on a circular table without repeating neighbour-sets

I made this problem up and it's been bothering me ever since. We're organising team activities in our company for the next few days. Our team consists of $n$ people seated on a circular table. To ...
33
votes
12answers
39k views

Is $[p \land (p \to q)] \to q$ a tautology?

I am new to discrete mathematics, and I am trying to simplify this statement. I'm using a chart of logical equivalences, but I can't seem to find anything that really helps reduce this. Which of ...
32
votes
6answers
18k views

Questions on “All Horse are the Same Color” Proof by Complete Induction

I'm bugged by the following that's summarized on p. 109 of this PDF. False theorem: All horses are the same color. Proof by induction: $\fbox{$P(n)$ is the statement: In every set of ...
31
votes
2answers
3k 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} \frac{4^n}{\binom{2n}{n}\sqrt{...
31
votes
4answers
31k 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?
30
votes
5answers
3k views

Can $\sqrt{n} + \sqrt{m}$ be rational if neither $n,m$ are perfect squares?

Can the expression $\sqrt{n} + \sqrt{m}$ be rational if neither $n,m \in \mathbb{N}$ are perfect squares? It doesn't seem likely, the only way that could happen is if for example $\sqrt{m} = a-\sqrt{n}...
30
votes
2answers
2k 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, with more than $10^{10^{10}}$ decimal digits, is far larger than the largest "known" prime.) The answer should ...
29
votes
7answers
3k views

How do you correctly reason that this directed graph is acyclic?

How can you correctly reason that this directed graph is acyclic? I can only visually say that this graph is acyclic because there is not a single path in the graph where the starting vertex is ...
29
votes
4answers
33k views

Why a complete graph has $\frac{n(n-1)}{2}$ edges?

I'm studying graphs in algorithm and complexity, (but I'm not very good at math) as in title: Why a complete graph has $\frac{n(n-1)}{2}$ edges? And how this is related with combinatorics?
29
votes
3answers
579 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 ...
29
votes
4answers
3k views

Is there a branch of Mathematics which connects Calculus and Discrete Math / Number Theory?

I am asking this question out of both curiosity and frustration. There are many problems in computer science which require you to perform operations on a finite set of numbers. It always bothers me ...
29
votes
2answers
3k 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 ...
28
votes
4answers
16k 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, ...
28
votes
2answers
2k 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. ...
27
votes
4answers
91k views

How many distinct functions can be defined from set A to B?

In my discrete mathematics class our notes say that between set $A$ (having $6$ elements) and set $B$ (having $8$ elements), there are $8^6$ distinct functions that can be formed, in other words: $|b|^...
27
votes
4answers
2k views

Is a proof using modular arithmetic in a question like this valid?

It's been two years or so since I've finished my math undergrad (and I'm doing something non-math related now, unfortunately), so I apologize if what is to follow isn't a very good question! Prove ...
27
votes
5answers
67k 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 I'm having hard time conceptualizing ...
26
votes
3answers
48k views

Simple Double Summation

I've seen how nesting works with a simple $(i+j)$ but this problem below is tripping me up. It's either because of the multipliers or because they each start at zero but I get 60, and the answer I ...
25
votes
6answers
9k views

Why is mathematical induction a valid proof technique? [duplicate]

Context: I'm studying for my discrete mathematics exam and I keep running into this question that I've failed to solve. The question is as follows. Problem: The main form for normal induction over ...
25
votes
2answers
2k 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, ...