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

14
votes
1answer
776 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
363 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
259 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
1answer
262 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 ...
14
votes
2answers
503 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
4k 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 + ...
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
3answers
1k 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 ...
13
votes
3answers
718 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
2answers
990 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 ...
13
votes
4answers
390 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
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.
12
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}$$ ...
12
votes
5answers
7k 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 ...
12
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 ...
12
votes
1answer
857 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 ...
12
votes
5answers
435 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
3answers
420 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
3answers
790 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
2answers
353 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
1answer
1k views

Interview Question Asked In yahoo

Can you find the smallest positive number such that if you shuffle the digits of the number in a particular order, the shuffled number becomes twice the original number. Source: ...
12
votes
1answer
460 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 ...
11
votes
4answers
2k views

Proof by contradiction: $r - \frac{1}{r} =5\Longrightarrow r$ is irrational?

Prove that any positive real number $r$ satisfying: $r - \frac{1}{r} = 5$ must be irrational. Using the contradiction that the equation must be rational, we set $r= a/b$, where a,b are positive ...
11
votes
2answers
893 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 ...
11
votes
4answers
2k views

How many three digit numbers are not divisible by 3, 5 or 11?

How many three digit numbers are not divisible by 3, 5, or 11? How can I solve this? Should I look to the divisibility rule or should I use, for instance, $$ \frac{999-102}{3}+1 $$
11
votes
4answers
339 views

Prove $1+\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}+\dots+\frac{1}{\sqrt{n}} > 2\:(\sqrt{n+1} − 1)$

Basically, I'm trying to prove (by induction) that: $$1+\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}+\dots+\frac{1}{\sqrt{n}} > 2\:(\sqrt{n+1} − 1)$$ I know to begin, we should use a base case. In this ...
11
votes
8answers
3k views

Proof that the sum of the cubes of any three consecutive positive integers is divisible by three.

So this question has less to do about the proof itself and more to do about whether my chosen method of proof is evidence enough. It can actually be shown by the Principle of Mathematical Induction ...
11
votes
4answers
584 views

Number of possibilities to cross a hexagonal lattice.

An ant walks along the line segments in the hexagonal lattice shown, from start to finish. The ant must go in the direction shown if there is an arrow, and never goes on the same line segment twice. ...
11
votes
3answers
3k views

Lights out game on hexagonal grid

I greatly enjoyed the Lights Out game described here (I am sorry I had to link to an older page because some wikidiot keeps deleting most of the page). Its mathematical analysis is here (it's just ...
11
votes
2answers
1k views

Number of ways to put $n$ unlabeled balls in $k$ bins with a max of $m$ balls in each bin

The number of ways to put $n$ unlabeled balls in $k$ distinct bins is $$\binom{n+k-1}{k-1} .$$ Which makes sense to me, but what I can't figure out is how to modify this formula if each bucket has a ...
11
votes
2answers
260 views

What is the probability that $\pi(x) + x$ is injective?

Let $S$ be a finite group with operator + and $\pi$ be a permutation on $S$. Then what is the probability that $\pi(x) + x$ is injective over choices of $\pi$? The concrete instantiation I'm ...
11
votes
1answer
184 views

Proving that $(3n)!$ is divisible by $n! \times (n + 1)! \times (n + 2)!$ if $n$ is greater than 2

Prove that: If $n$ is greater than 2, then $(3n)!$ is divisible by $n! \times (n + 1)! \times (n + 2)!$ From Barnard & Child's "Higher Algebra". I know that the highest power of a prime $p$ ...
11
votes
1answer
695 views

Factorial canceling on expansion of binomial coefficients on Concrete Mathematics

On Concrete Mathematics section 5.5, which is teaching the hypergeometric functions, generalized factorials is defined as: \[ \frac 1 {z!} = \lim_{n \to \infty} \binom{n+z}{n}n^{-z} \] where \[ ...
10
votes
1answer
293 views

In naive set theory ∅ = {∅} = {{∅}}?

In naive set theory, I believe ∅ = {∅} = {{∅}} is correct, but just wanted to make sure that I understood this correctly. ∅ is an empty set, so having an empty set as an element of a set that ...
10
votes
3answers
388 views

Help with combinatorial proof of identity: $\sum_{k=1}^{n} \frac{(-1)^{k+1}}{k} \binom{n}{k} = \sum_{k=1}^{n} \frac{1}{k}$

How to prove this identity? Can someone please give me some insight ? $$\sum_{k=1}^{n} \frac{(-1)^{k+1}}{k} \binom{n}{k} = \sum_{k=1}^{n} \frac{1}{k}$$
10
votes
2answers
441 views

What is the converse of this statement and is it true?

If $a$ and $b$ are relatively prime, $a\mid c$ and $b\mid c$, then $(ab)\mid c$. I am lost. Would the converse be "If $(ab)\mid c$, then $a$ and $b$ are relatively prime and $a\mid c$ and $b\mid c$" ...
10
votes
3answers
667 views

Find the highest power of two in the expression.

What would be the highest power of two in the given expression? $32!+33!+34!+35!+...+87!+88!+89!+90!\ ?$ I know there are 59 terms involved. I also know the powers of two in each term. I found that ...
10
votes
2answers
1k views

Good upper bound for $\sum\limits_{i=1}^{k}{n \choose i}$?

I want an upper bound on $$\sum_{i=1}^k \binom{n}{i}.$$ $O(n^k)$ seems to be an overkill -- could you suggest a tighter bound ?
10
votes
3answers
736 views

A question related to Pigeonhole Principle

In a room there are 10 people, none of whom are older than 60, but each of whom is at least 1 year old. Prove that one can always find two groups of people (with no common person) the sum of ...
10
votes
1answer
751 views

Arrangement of Numbers

How can we prove that it is posible to arrange numbers $1,2,3,4,\ldots, n$ in a row so that the average of any two of these numbers never appears between them?
10
votes
4answers
543 views

How can I complete this proof by contradiction?

This problem is from Discrete Mathematics and its Applications: Prove that there are no solutions in integers $x$ and $y$ to the equation $2x^2 + 5y^2 = 14$. I am trying to use proof by ...
10
votes
3answers
188 views

Show that $2^n(\cos^n(\frac{2\pi}{9})+\cos^n(\frac{4\pi}{9})+\cos^n(\frac{8\pi}{9}))\in\mathbb{Z}$

$a_n=2^n\left[\cos^n\left(\dfrac{2\pi}{9}\right)+\cos^n\left(\dfrac{4\pi}{9}\right)+\cos^n\left(\dfrac{8\pi}{9}\right)\right]$. Show that $a_n\in\mathbb{Z}$ for all $n\in\mathbb{Z}$. Find the last ...
10
votes
7answers
16k views

Are there any good Discrete Mathematics video online?

I want to learn discrete mathematics by reading book by myself but I find sometime it's very hard to understand what author trying to say. I want to know, are there any good online video that teach ...
10
votes
2answers
432 views

Summation by parts of $\sum_{k=0}^{n}k^{2}2^{k}$

I want to evaluate this sum $$\sum_{k=0}^{n}k^{2}2^{k}$$ by summation by parts (two times) and I need to know, if my approach was right. I know the formula for summation by parts is $$\sum u\Delta ...
10
votes
3answers
381 views

bijection = bijection + bijection on symmetric integer intervals

Given a bijection $f:\mathbb Z \to \mathbb Z$ where $\mathbb Z$ is the set of all integers, does there always exist two bijections $g:\mathbb Z \to \mathbb Z$ and $h:\mathbb Z \to \mathbb Z$ which ...
10
votes
1answer
120 views

Blocking lines of length $5$ in a $7 \times 8$ matrix; how can we know the solutions have a specific form?

A friend shared with me the following puzzle he encountered in a Chinese math competition: In a $7 \times 8$ matrix, we place tokens so that any straight line of length $5$ (horizontal, vertical, ...
10
votes
4answers
76k views

What five odd integers have a sum of $30$?

I've been asked the following question: What five odd integers from the set $\{1, 3, 5, 7, 9, 11, 13, 15\}$ that when summed together equals to $30$? Note that any integer can be used more than ...
10
votes
1answer
156 views

Which graphs can be drawn using straight lines with no disjoint edges?

What is the class of graphs that can be drawn using only straight lines with no two edges disjoint? Edges are disjoint when they don't cross and they don't share a vertex. Vertices should be in ...
9
votes
14answers
2k views

Using set notation, define the set of even natural numbers between 100 and 500.

Using set notation, define the set of even natural numbers between 100 and 500. This is what I have so far: $P$ is even numbers so the set of natural numbers between 100 and 500 would be $$P = ...