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

7
votes
3answers
355 views

Changing Summation Index Question

I'm sorry if this seems like a very novice question, but I am still relatively new to the world of discrete math ( still in 9th grade). I've been reviewing some of the concepts I learned in a ...
7
votes
2answers
782 views

Looking for a bijective, discrete function that behaves as chaotically as possible

I need to write a coupon code system but I do not want to save each coupon code in the database. (For performance and design reasons.) Rather I would like to generate codes subsequent that are ...
7
votes
2answers
62 views

How do I solve for P in this equation? (involving floor functions) edited

I have the following equation: $$ A=\frac{\left \lfloor (n+1)^{P} \right \rfloor}{\left \lfloor n^{P} \right \rfloor} $$ How to solve for P using A and n? *n is a non negative integer *A and P are ...
7
votes
2answers
151 views

Prove $ \frac{\sqrt{2}}{2} + \frac{\sqrt{3}}{4} + \frac{\sqrt{4}}{6} + \cdots + \frac{\sqrt{n+1}}{2n} > \frac{\sqrt{n}}{2} $ by induction

Prove by induction that for all $n > 0$, $$ \frac{\sqrt{2}}{2} + \frac{\sqrt{3}}{4} + \frac{\sqrt{4}}{6} + \cdots + \frac{\sqrt{n+1}}{2n} > \frac{\sqrt{n}}{2} $$ I have done the basis ...
7
votes
2answers
450 views

A magic trick with synchronizing words

See the following magic trick. http://www.speedyadverts.com/SAEntertainment/html/realmagic4.html Spoiler Alert Believe it or not, the lady didn't really read your mind; she is not even a real lady ...
7
votes
2answers
371 views

Combinatorial proof for identity $\left(\!\!\binom{n\vphantom{1}}{k}\!\!\right)=\left(\!\!\binom{k+1}{n-1}\!\!\right)$ (multiset coefficients)

In class we have recently started using combinatorial proofs. I have tried this problem that our teacher has assigned as a "challenge". I understand how to receive the left hand side, but am ...
7
votes
1answer
143 views

Equation $\displaystyle\sum_{k=0}^{n-1}(-1)^{n-k-1}\dfrac{(n+k)!}{(k!)^2(n-k-1)!}=n^2$

I think this equality is very inters prove that: $\displaystyle\sum_{k=0}^{n-1}(-1)^{n-k-1}\dfrac{(n+k)!}{(k!)^2(n-k-1)!}=n^2$
7
votes
1answer
162 views

Connecting cells by line and column permutations in a finite grid

I'd like to know whether the following simple problem has been studied before and if any solution is known. Let G be a finite (MxN) grid, S a subset of G's cells (the "crumbs"). Two crumbs are said ...
7
votes
0answers
68 views

Share the beer fairly in a finite number of pours

A classical problem within measurements is that you have a $8\,\text{dl}$ mug of delicious expensive beer and need to share it evenly with your friend. However you only have two empty glasses of ...
7
votes
1answer
118 views

$n$ points in the plane: show there are at least $\lceil \frac{n}{3} \rceil $ different distances between pairs of points

How can I prove that in each group of $n$ points in the plane, such that there are not $3$ points on the same line, there are at least $\left\lceil \frac{n}{3} \right\rceil $ different distances ...
7
votes
0answers
75 views

Showing that poset of set of supports of a vector space is semimodular

Let $W$ be a subspace of the vector space $\mathbb{K}^n$, where $\mathbb{K}$ is a field of characteristic $0$. The support of a vector $v = (v_1,\ldots, v_n) \in \mathbb{K}^n$ is given by ...
7
votes
0answers
234 views

Minimal “sumset basis” in the discrete linear space $F_2^n$

Let's $$ C\subseteq F^n_2, $$ $$ 2C=C+C=\{\bar\alpha+\bar\beta\ | \bar\alpha,\bar\beta\in C\}. $$ I need to find $C$ such that $2C=F_2^n$ and $|C|$ is minimal. I have found the following ...
7
votes
1answer
91 views

For what numbers is $a_{b}= b_{a}$? (Reference?)

A student recently asked me about solutions to the equation $$a_{b} = b_{a},$$ where the subscript notation $a_{b}$ denotes interpreting the digits of $a$ in base $b$. It turns out there are tons of ...
7
votes
1answer
95 views

Prove this is an equivalence relation.

Define a relation of $\mathbb{Q} -$ {$0$} as follows: $x$ ~ $y$ $\Leftrightarrow$ $\dfrac {x} {y} = 2^k $ for some $k \in \mathbb{Z}$ Prove this is an equivalence relation. ATTEMPT: Reflexive: ...
7
votes
0answers
194 views

Citation for subset complement result

Let $S = \{s_1, \ldots, s_n\} \subset \{1, \ldots, 2n\}$. Consider two operations on $S$, unfortunately both called complement in different setting: let $A(S) = \{1, \ldots, 2n\} \setminus S$ (set ...
7
votes
0answers
168 views

A variation on the Look and Say Sequence and some questions about it.

For information on the sequence mentioned in the title, see http://en.wikipedia.org/wiki/Look-and-say_sequence. This is an original problem. Suppose instead of "describing" the numbers in a string in ...
6
votes
3answers
1k views

Is it possible to have a rule which generates: 2, 4, 6, 8, 10, 12, 14, 16, -23?

This is on Lagrange Interpolations . . . Is it possible to have a rule which generates the sequence: 2, 4, 6, 8, 10, 12, 14, 16, -23? The hint that he gave us is to use Summation Products, the only ...
6
votes
7answers
1k views

What is an example of function $f: \Bbb{N} \to \Bbb{Z}$ that is a bijection?

Could you give me an example of function $ f \colon \mathbb N \to \mathbb Z$ that is both one-to-one and onto? Does this work: $f(n) := n \times (-1)^n$? N starts with zero.
6
votes
9answers
666 views

How to prove $\left \lceil \frac{n}{m} \right \rceil = \left \lfloor \frac{n+m-1}{m} \right \rfloor$?

everybody, how can I prove that, for natural $m$ and $n$, $$ \left \lceil \frac{n}{m} \right \rceil = \left \lfloor \frac{n+m-1}{m} \right \rfloor \; ? $$ Thanks a lot.
6
votes
4answers
3k views

Prove the cuberoot of 2 is irrational

I need to prove the cube root is irrational. I followed the proof for the square root of $2$ but I ran into a problem I wasn't sure of. Here are my steps: By contradiction, say $ \sqrt[3]{2}$ is ...
6
votes
3answers
2k 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 ...
6
votes
1answer
858 views

In a group of 26 people, is it possible for each person to shake hands with exactly 3 other people?

In a group of 26 people, is it possible for each person to shake hands with exactly 3 other people? Does anybody know how to solve this?
6
votes
3answers
7k views

How many options are there for 15 student to divide into 3 equal sized groups?

How many options are there for 15 student to divide into 3 equal sized groups? Now i know the soultion is $\;\dfrac {15!}{5!5!5!3!}\;$ but i can't understand why. Can anyone please enlighten me?
6
votes
2answers
2k views

A number is a perfect square if and only if it has odd number of positive divisors

I believe I have the solution to this problem but post it anyway to get feedback and alternate solutions/angles for it. For all $n \in \mathrm {Z_+}$ prove $n$ is a perfect square if and only if $n$ ...
6
votes
5answers
1k views

Proving prime $p$ divides $\binom{p}{k}$ for $k\in\{1,\ldots,p-1\}$.

Prove if $p$ is a prime then $p \,| \binom{p}{k}$ for $k\in\{1,\ldots,p-1\}$ I don't really know where to begin with this one.
6
votes
3answers
153 views

Does $a\mid(bc)$ imply that $a\mid b$ or $a\mid c$?

Does $a\mid(bc)$ imply that $a\mid b$ or $a\mid c$? Can someone elaborate on this a bit?
6
votes
1answer
217 views

Show the distance does not exceed $\sqrt{2}$.

Choose any ten points from the interior of a square with side length $3$. Show that the distance of some pair of these points does not exceed $\sqrt{2}$. Can someone help me?
6
votes
5answers
8k views

Number of relations that are both symmetric and reflexive

Consider a non-empty set A containing n objects. How many relations on A are both symmetric and reflexive? The answer to this is $2^p$ where $p=$ $n \choose 2$. However, I dont understand why this is ...
6
votes
6answers
168 views

What's the result? $1/i=?$, where $i=\sqrt{-1}$ [duplicate]

I just had my first math class in the university, and I understood everything pretty well, but I think I have misread this one because I read that the result is $-1$. Thanks for your answers!
6
votes
6answers
1k views

Quantifiers, predicates, logical equivalence

I am asked if $(\exists x) (P(x) \rightarrow Q(x))$ and $\forall x P(x) \rightarrow \exists xQ(x)$ are logically equivalent. I don't think they are but how will I prove it? Am I supposed to use ...
6
votes
3answers
212 views

Closed form for a binomial series

I am wondering if any knows how to compute a closed form for the following two series. $$\sum_{m=1}^{n}\frac{(-1)^m}{m^2}\binom{2n}{n+m}$$ $$\sum_{m=1}^{n}\frac{(-1)^m}{m^4}\binom{2n}{n+m}$$ ...
6
votes
3answers
23k views

Largest prime factor of 600851475143 [duplicate]

I'm trying to use a program to find the largest prime factor of 600851475143. This is for Project Euler here: http://projecteuler.net/problem=3 I first attempted this with the code that goes through ...
6
votes
3answers
424 views

What does the notation $\binom{n}{i}$ mean?

What do the parentheses next to the summation involving the binomial coefficients mean? Like this: $$\sum _{i=0}^{n} \binom{n}{i}a^{(n-i)}b^i=\left(a+b\right)^n $$
6
votes
2answers
502 views

Distribution of points on a rectangle

Let $R$ be a rectangular region with sides $3$ and $4$. It is easy to show that for any $7$ points on $R$, there exists at least $2$ of them, namely $\{A,B\}$, with $d(A,B)\leq \sqrt{5}$. Just divide ...
6
votes
3answers
133 views

Help with math induction

Prove that $n(n+1)(n+2)$ is divisible by $6$ for all integers. I'm not sure if I'm suppose to use division into cases or not. Our teacher ran out of time to go over this in class, and this is on ...
6
votes
4answers
85 views

How many solutions for equation $x_1+x_2+x_3+x_4+x_5 = 15$ have two variables equal to 1?

How many solutions for equation $x_1+x_2+x_3+x_4+x_5=15$ have exactly two variables equal to 1? ($x_i \ge 1 $) Hint: think about splitting 15 beans among 5 children, considering the restrictions.
6
votes
2answers
348 views

Is this expression even a function?

This is from Discrete Mathematics and its Applications My question is on 22c. From the book, I inferred from the question that all of the listed mathematical expressions are functions. Is the ...
6
votes
2answers
918 views

Proof that no polynomial with integer coefficients can only produce primes [duplicate]

Doing a discrete math review and am trying to solve problem 1.6 in the text found here: http://courses.csail.mit.edu/6.042/fall13/ch1-to-3.pdf - I believe I've gotten parts (a) and (b) correctly, but ...
6
votes
3answers
745 views

How many 3-subsets of $\{1,2,\ldots,10\}$ contain at least two consecutive integers?

Let A = {1, 2,..., 10}. How many three-element subsets of A contain at least two consecutive integers? I believe there are $\displaystyle \tbinom{10}{3}$ total 3-subsets of A. To find the subsets ...
6
votes
3answers
1k views

Looking for induction problems that are not formula-based

I am looking for problems that use induction in their proofs such as this one: Given a checker board with one square removed you can cover it with L-shaped pieces made out of three squares. This ...
6
votes
5answers
575 views

trivial but non-trivial equivalence relations

Define a binary relation $R$ on a set $A$ by saying $xRy$ iff $x$ and $y$ have the same whatever. "Whatever" is of course some specified function on $A$. This is a "trivial" equivalence relation: ...
6
votes
4answers
442 views

“If A then B” in Venn (or Euler) Diagrams

How can I represent "If A then B" in a diagram? I thought it would be a simple subset like $A ⊂ B$. However this material says that If $A$ then $B$ $=$ $A^c ∪ B$. Now I am confused.
6
votes
2answers
338 views

What exactly is the difference between weak and strong induction?

I am having trouble seeing the difference between weak and strong induction. There are a few examples in which we can see the difference, such as reaching the $k^{th}$ rung of a ladder and ...
6
votes
4answers
141 views

Pigeon Hole. 80 numbered balls

We have $80$ numbered balls(From $1$ to 80).Among which are $45$ blue and $35$ orange. Prove that at least two blue balls differ by $9$. For example $13$ and $22$ or $69$ and $78$. So they can differ ...
6
votes
1answer
243 views

Recurrence relation satisfied by $\lfloor(1+\sqrt{3})^n\rfloor$

This is a follow up to a question I had asked earlier about a linear recurrence relationship satsified by $\lfloor(1+\sqrt{5})^n\rfloor$. I messed up there, and I actually meant to ask about ...
6
votes
2answers
827 views

Is there a relation that is irreflexive, anti-symmetric and not transitive?

from the set $\{a, b, c, d\}$? Of the one's I have tried, it at best is two of the three, but never all.
6
votes
5answers
7k views

Big-O Notation - Prove that $n^2 + 2n + 3$ is $\mathcal O(n^2)$

I'm taking a course in Discrete Mathematics this summer, and my book doesn't offer a very good explanation of Big-O notation. I understand that if $f(x)$ is $\mathcal O(g(x))$ it means that there ...
6
votes
3answers
152 views

Why is the function $f(x)=x^3 \pmod{10}$ periodic with this strange property?

I've noticed that the function $f(x)=x^3 \pmod{10}$ is periodic. For example, listing mod(x^3,10) we get: ...
6
votes
5answers
1k views

Inherently discrete concepts

Are there any concepts which are naturally defined only for the integers and so far has resisted any attempts at extension to other fields such as rationals or reals? Does not meet criteria: ...
6
votes
1answer
8k views

What is the prerequisite knowledge for learning discrete math?

To become a better computer programmer I would like to take the time to learn discrete mathematics, but I am positive that I do not have the required existing knowledge to do so. So I would like to ...