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

17
votes
1answer
2k views

True or false: {{∅}} ⊂ {∅,{∅}}

Note: Actually there's no error in the book and the manual. I actually misread it. The answer is of a different question : True or False: {0} ⊂ {0} This question is from Discrete Math Book by Rosen. ...
17
votes
4answers
403 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
2k 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 ...
17
votes
1answer
92 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 ...
17
votes
1answer
1k 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: ...
16
votes
3answers
2k views

Counting numbers in a sequence - explain “Add 1 before you're done” rule

I'm studying for the GRE, and my study book uses a rule that it never justifies for counting numbers in a sequence: "Add 1 before you're done." For example, how many multiples of 3 are between 250 ...
16
votes
9answers
10k 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 ...
16
votes
6answers
8k 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 ...
16
votes
2answers
3k 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 ...
16
votes
4answers
659 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
3answers
256 views

Count permutations of $\{1,2,…,7\}$ without 4 consecutive numbers - is there a smart, elegant way to do this?

Here's a problem I've solved: Count permutations of $\{1,2,...,7\}$ without 4 consecutive numbers (e.g. 1,2,3,4). So I did it kinda brute-force way - let $A_i$ be the set of permutations of $[7]$, ...
16
votes
2answers
339 views

Do any of these sequences have infinitely-many distinct iterates under run-length substitution?

Let $$S = \{x \in \{1,2\}^\mathbb{N}: \ \text{every run in }x\text{ has finite length}\}$$ and define $$T: S\to \mathbb{N}^\mathbb{N} $$ such that for any $x\in S$, ${T}x$ is the sequence of ...
16
votes
1answer
287 views

$1^2+2^2+\cdots+24^2=70^2$ and squarily squaring the torus

The unique nontrivial solution to $1^2+2^2+\cdots+n^2=m^2$ is $(n,m)=(24,70)$. (This fact has connections to modular forms, special functions, lattices and string theory.) Martin Gardner, in the ...
16
votes
1answer
200 views

Is there a closed-form expression for $\sum_{k=1}^{n}\lfloor k^{q} \rfloor$ for $q \in \mathbb{Q}_{> 0}$?

There are well-known closed-form expressions for summations such as $\sum_{k=1}^{n}\lfloor k^{\frac{1}{2}} \rfloor$, $\sum_{k=1}^{n}\lfloor k^{\frac{1}{3}} \rfloor$, $\sum_{k=1}^{n}\lfloor ...
15
votes
13answers
3k views

Show that from a group of seven people whose (integer) ages add up to 332 one can select three people with the total age at least 142. [closed]

I need help with this problem, and I was thinking in this way: $$ x_{1} + x_{2} + x_{3} + x_{4} + x_{5} + x_{6} + x_{7} = 332 $$ and I need to find three of these which sum is at least 142. But I ...
15
votes
6answers
3k views

Is an arbitrary number of the form xyzxyz divisible by 7, 11, 13?

So I was given this question Choose any 3-digit number xyz and write it after itself as follows: xyzxyz. Check whether it is divisible by 7,11, 13. Is an arbitrary number of the form xyzxyz ...
15
votes
11answers
6k views

Prove that $1 + 4 + 7 + · · · + 3n − 2 = \frac {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 + ...
15
votes
12answers
2k 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: ...
15
votes
4answers
6k 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?
15
votes
5answers
258 views

How to prove that $\frac{(12!)!}{12!^{11!}}$ is integer?

So far I have used that a combination is an integer so $\frac{n!}{m!(n-m)!}$ is integer. Now let $n=mb$ so $\frac{mb!}{m!(mb-m)!}$. What is left is to prove that $\frac{(mb)!}{m!^b}$ is integer so ...
15
votes
3answers
1k views

Use this sequence to prove that there are infinitely many prime numbers. [duplicate]

Problem: By considering this sequence of numbers $$2^1 + 1,\:\: 2^2 + 1,\:\: 2^4 + 1,\:\: 2^8 +1,\:\: 2^{16} +1,\:\: 2^{32}+1,\ldots$$ prove that there are infinitely many prime ...
15
votes
3answers
893 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 ...
15
votes
4answers
340 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
3answers
2k 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 ...
15
votes
2answers
416 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. ...
15
votes
1answer
273 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 ...
15
votes
2answers
1k 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 ...
14
votes
8answers
3k 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 ...
14
votes
7answers
2k 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 ...
14
votes
6answers
2k views

Prove $1+2\sqrt3$ is not a rational number

How would I go about proving $1+2\sqrt 3$ is not a rational number assuming $\sqrt 3$ is not a rational? Would direct proof be the easiest? Total beginner here, any insight would be appreciated.
14
votes
3answers
2k views

Combinatorial proof of $\sum^{n}_{i=1}\binom{n}{i}i=n2^{n-1}$.

Prove that $$\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 ...
14
votes
2answers
558 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
3answers
13k views

Maximization with xor operator

Few days ago i found task : with given N numbers only one of those numbers doesn't have pair, which one is it? After hours of surfing the net i found that XOR operator is good for that, because ...
14
votes
1answer
817 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
5answers
504 views

A set contains $0$, $1$, and all averages of any subset of its element, prove it contains all rational number between 0 and 1

Assume we have a set $S$ $\subseteq \mathbb{R}$, we know $0,1 \in S$. Also, $S$ has the property that if $A \subseteq S$ is finite, the average of elements in $A$ is in $S$. We want to prove that any ...
14
votes
4answers
434 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 ...
14
votes
1answer
661 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 ...
13
votes
7answers
4k views

Roll two dice. What is the probability that one die shows exactly two more than the other die? [closed]

Two fair six-sided dice are rolled. What is the probability that one die shows exactly two more than the other die (for example, rolling a $1$ and $3$, or rolling a $6$ and a $4$)? I know how to ...
13
votes
4answers
994 views

Set builder notation: Colon or Vertical Line

I remember once hearing offhandedly that in set builder notation, there was a difference between using a colon versus a vertical line, e.g. $\{x: x \in A\}$ as opposed to $\{x\mid x \in A\}$. I've ...
13
votes
8answers
2k 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}$$ ...
13
votes
2answers
986 views

Discrete math. Finding a perfect square.

The problem is: Find all natural numbers $n$ for which $2^n + 1$ is a perfect square? I am having a bit of trouble finding a generic way of finding these numbers. Of course the first obvious solution ...
13
votes
4answers
1k views

Is Cantor's diagonal argument dependent on the base used?

Applying Cantor's diagonal argument to irrational numbers represented in binary, one and only one irrational number can be generated that is not on the list. Wikipedia image: But if you change ...
13
votes
4answers
19k 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 im having hard time conceptualizing ...
13
votes
1answer
964 views

Do Cantor's Theorem and the Schroder-Bernstein Theorem Contradict?

I am confused as to how Cantor's Theorem and the Schroder-Bernstein Theorem interact. I think I understand the proofs for both theorems, and I agree with both of them. My problem is that I think you ...
13
votes
3answers
34k views

Is my understanding of antisymmetric and symmetric relations correct?

So I'm having a hard time grasping how a relation can be both antisymmetric and symmetric, or neither. Are my examples correct? symmetric & antisymmetric ...
13
votes
5answers
535 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$ ...
13
votes
3answers
532 views

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}$, then $n-4m$?

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 ...
13
votes
0answers
902 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. ...
12
votes
5answers
2k views

Finding how many 8-bit bytes contain an even number of zeros . . .

I believe I'm overthinking this or otherwise confused but I believe that the method to solve this would be $2^n$ where n is the length of the bytes? So in this particular case it would be $2^8$ equal ...
12
votes
7answers
3k views

Show that (p ∧ q) → (p ∨ q) is a tautology?

I am having a little trouble understanding proofs without truth tables particularly when it comes to → Here is a problem I am confused with: Show that (p ∧ q) → (p ∨ q) is a tautology The first ...