# 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.

22,046 questions
33k views

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 ...
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 ...
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 ...
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 ...
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 ...
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,...
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 ...
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 ...
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 ...
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 ...
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$ ...
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 ...
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).
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.
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 ...
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 ...
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 ...
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....
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: ...
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 ...
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 ...
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 ...
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 ...
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 ...
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, ...
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 ...
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 ...
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 ...
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 ...
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 ...
18k views

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?
3k views

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 ...
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 ...
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 ...
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, ...