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

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 ...
12
votes
1answer
760 views

What is a sharp constant?

I've been reading some papers and found this term "Sharp constant" being used in inequalities frequently. Can anyone provide me a detailed meaning of this term ? I couldn't find proper resources to ...
12
votes
3answers
874 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
459 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
509 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 ...
12
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 ...
12
votes
4answers
505 views

How do I prove this combinatorial identity using inclusion and exclusion principle?

$$\binom{n}{m}-\binom{n}{m+1}+\binom{n}{m+2}-\cdots+(-1)^{n-m}\binom{n}{n}=\binom{n-1}{m-1}$$ Note that we can show this with out using inclusion and exclusion principle by using Pascal's Identity ...
11
votes
14answers
3k 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 = ...
11
votes
2answers
682 views

when is $n!+10$ a perfect square?

When is $n!+10$ is a perfect square ? I have tried and found that only for $n=3$ is $n!+10$ a perfect square. Is there any other solution to this?
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
7answers
1k views

Proof of the Hockey-Stick Identity: $\sum_{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 ...
11
votes
4answers
4k 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
349 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
1answer
331 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 ...
11
votes
5answers
449 views

Find a formula for $\sum\limits_{k=1}^n \lfloor \sqrt{k} \rfloor$

I need to find a clear formula (without summation) for the following sum: $$\sum\limits_{k=1}^n \lfloor \sqrt{k} \rfloor$$ Well, the first few elements look like this: $1,1,1,2,2,2,2,2,3,3,3,...$ ...
11
votes
3answers
1k 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 ...
11
votes
8answers
4k 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
2k 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 ...
11
votes
4answers
714 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
2answers
2k 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
266 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
2k 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: ...
11
votes
1answer
193 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
178 views

Curious combinatorial summation

Let $\gamma$ denote a grid walk from the upper left corner $(1,k)$ to the lower right corner $(\ell,1)$ of the $k\times\ell$ rectangle $\{1,..,k\}\times\{1,..,\ell\}$. There are ...
11
votes
1answer
782 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 \[ ...
11
votes
0answers
614 views

Minimal time gossip problem

The gossip problem (telephone problem) is an information dissemination problem where each of $n$ nodes of a communication network has a unique piece of information that must be transmitted to all the ...
10
votes
6answers
3k views

Using generating functions find the sum $1^3 + 2^3 + 3^3 +\dotsb+ n^3$

I am quite new to generating functions concept and I am really finding it difficult to know how to approach problems like this. I need to find the sum of $1^3 + 2^3 + 3^3 +\dotsb+ n^3$ using ...
10
votes
4answers
2k views

Is any relation which contains only one ordered pair transitive?

I need clarification. Let $A=\{1,2,3\}$ be a set and $R=\{(1,2)\}$ be a relation on $A$. Is it a Transitive relation? I am confused because some text books say $R$ is transitive if it contains only ...
10
votes
2answers
1k views

Pigeonhole principle: Five points on an orange

Five points are drawn on the surface of an orange. Prove that it is possible to cut the orange in half in such a way that at least four of the points are on the same hemisphere. (Any points lying ...
10
votes
5answers
14k views

How many bananas can a camel deliver without eating them all?

This is a fun puzzle I was assigned on the first day of highschool (over a decade ago). I just dug it up randomly from under my bed and thought I'd share it with the SE community. At the time, I ...
10
votes
3answers
650 views

Sets of Prime and Composite Numbers

We know that all primes are of the form $ 6k ± 1 $ with the exception of 2 and 3. We also know that not all numbers of the form $ 6k ± 1 $ are prime. This leads to four distinct sets of pairs ...
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
2answers
511 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
784 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
4answers
20k views

Transitive Relations

For example, $$R = \{ (1,1),(1,2),(2,1),(2,2) \} \quad\text{for}\quad A = \{1,2,3\}.$$ This relation is symmetric and transitive. I understand that the relation is symmetric, but my brain does not ...
10
votes
3answers
190 views

How many different functions we have by only use of $\min$ and $\max$?

We can making many functions of three variable by only use and combining of $\min$ and $\max$ functions. But many of them are not different , like : ...
10
votes
2answers
4k views

Prove that $\mathcal{P}(A)⊆ \mathcal{P}(B)$ if and only if $A⊆B$. [duplicate]

Here is my proof, I would appreciate it if someone could critique it for me: To prove this statement true, we must proof that the two conditional statements ("If $\mathcal{P}(A)⊆ \mathcal{P}(B)$, ...
10
votes
2answers
767 views

Visualizing Concepts in Mathematical Logic

If you were forced to speculate or offer anecdotal evidence, how would you say excellent practicioners of mathematical logic coneptually grasp statements like: $$ \vdash ((P \rightarrow Q) ...
10
votes
1answer
847 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
292 views

How many sequence of integers ($j_1 , j_2 , . . . , j_k$) are there such that $0 ≤ j_1 ≤ j_2 ≤ . . . ≤ j_k ≤ n$?

I need to solve the problem, How many sequence of integers ($j_1 , j_2 , . . . , j_k$) are there such that $0 ≤ j_1 ≤ j_2 ≤ . . . ≤ j_k ≤ n$? I've been given a hint, (Hint: Reduce the ...
10
votes
3answers
5k views

Inclusion-exclusion principle: Number of integer solutions to equations

The problem is: Find the number of integer solutions to the equation $$ x_1 + x_2 + x_3 + x_4 = 15 $$ satisfying $$ \begin{align} 2 \leq &x_1 \leq 4, \\ -2 \leq &x_2 \leq 1, \\ 0 \leq ...
10
votes
4answers
7k views

What is the solution to the following recurrence relation with square root: $T(n)=T (\sqrt{n}) + 1$?

This looks like a question asked earlier, but it isn't. $$T(n)=\begin{cases} T (\sqrt{n}) + 1 \quad & \text{ if } n>1 \\ 1 & \text{ if }n=1\end{cases}$$ My professor gave this to me in ...
10
votes
3answers
91k 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
3answers
428 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
126 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
1answer
506 views

outer automorphisms of $S_6$

$$ \begin{array}{|l|c|c|} \hline \text{cycle structure} & \text{number of permutations} & \text{order} \\ \hline 6 & 120 & 6 \\ 5+1 & 144 & 5 \\ 4+2 & 90 & 4 \\ ...
10
votes
2answers
165 views

Determine Fastest 3 horses out of 125 when only 5 racing track are given without using stopwatch?

We have 125 horses, and we want to pick the fastest 3 horses out of those 125. In each race, only 5 horses can run at the same time because there are only 5 tracks. What is the minimum number of races ...
10
votes
1answer
101 views

Examples of classes $\mathcal{C}$ of structures such that every finite group is isomorphic to the automorphism group of a structure in $\mathcal{C}$

Since it is not the case that every group is the automorphism group of a group (see Is every group the automorphism group of a group?), it is natural to ask: what are some examples of classes ...
10
votes
2answers
245 views

Counting sets by their connectedness

Let $U = \{u_1, u_2, \ldots , u_m \}$ where each $u_i$ is an $r$-subset of $[n]$ and $\,\bigcup u_i \!=\! [n]$. Construct the intersection graph of $U$. That is, let node $i$ correspond to $u_i$ and ...
10
votes
1answer
177 views

$(123)!$ divided by $(25!)^x$. What is the maximum possible integral value of $x$?

The answer given is $5$. But I am getting $4$. Here is what I have done. $$25!= 2^{22}\cdot3^{10}\cdot5^6\cdot7^3\cdot11^2\cdot13\cdot17\cdot19\cdot23$$ ...