# Tagged Questions

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.

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 ...
37k 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 ...
765 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 ...
890 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. ...
467 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 ...
518 views

686 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?
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 ...
5k views

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

The following has been bugging me, and I can't go to sleep until I resolve it. Here is a summary of the document on page 109 of http://courses.csail.mit.edu/6.042/spring12/mcs.pdf. False ...
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$$
350 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 ...
337 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 ...
1k views

### How many bit strings of length 8 start with “1” or end with “01”?

A bit string is a finite sequence of the numbers $0$ and $1$. Suppose we have a bit string of length $8$ that starts with a $1$ or ends with an $01$, how many total possible bit strings do we have? I ...
481 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,...$ ...
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 whose ...
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 ...
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 ...
725 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. ...
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 ...
267 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 ...
92k 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 once....
154 views

### Maximum value of the smallest number of operations to obtain configuration from original configuration

Let $n$ be a positive integer. There are $n(n+1)/2$ marks, each with a black side and a white side, arranged into an equilateral triangle, with the biggest row containing $n$ marks. Initially, each ...
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: http://gpuzzles.com/...
194 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$ ...
180 views

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 ...
15k 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 ...
667 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 ...
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 ?
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$" ...
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 $... 4answers 21k 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 ... 3answers 191 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 : $$\min(x,y,z)=\min(x,\min(y,z)),\quad\min(x,\max(x,... 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), ... 2answers 778 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) \... 1answer 862 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? 3answers 195 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 ... 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 ... 3answers 191 views ### Is there a closed form or approximation to$\sum_{i=0}^n\binom{\binom{n}{i}}{i}I tried to calculate the sum $$\sum_{i=0}^n\binom{\binom{n}{i}}{i}$$ but it seems that all my known methods are poor for this. Not to mention the intimate recursion, that is $$\sum_{i=0}^n\binom{\... 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 &... 4answers 8k 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 ...