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
0answers
233 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
0answers
72 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
91 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
165 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
8answers
206 views

Why is $n^2+4$ never divisible by $3$?

Can somebody please explain why $n^2+4$ is never divisible by $3$? I know there is an example with $n^2+1$, however a $4$ can be broken down to $3+1$, and factor out a three, which would be divisible ...
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
664 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
832 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
1k 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
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
5answers
1k views

discrete math book suitable for younger person?

When I took discrete math as an adult I realized that this was a subject I would have enjoyed and done well at much earlier in life, even in my early teens. Does anyone know if there are good books, ...
6
votes
3answers
419 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
3answers
21k 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
2answers
481 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
80 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
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
2answers
343 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
842 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
713 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
560 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
140 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
242 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
778 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
2answers
6k views

Correct way to calculate numeric derivative in discrete time?

Given a set of discrete measurements in time $x_t, t \in \{0,\Delta t, 2\Delta t,\ldots,T-\Delta t,T\}$, what is the correct way to compute the discrete derivative $\dot x_t$. Is it more correct to ...
6
votes
5answers
993 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
117 views

A group acting on colourings of a set

Suppose I have a set $L$ with some permutation group $G$ defined upon it, which I think of as a symmetry group. I want to consider the set $F$ of functions $f: L \to C$, for some set $C$. It seems ...
6
votes
3answers
87 views

Show that $9\mid a^2$ if given that $6\mid a$

Does this prove I made seem correct to show that if $6$ divides $a$ then $9$ divides $a^2$ If $6\mid a$, then $a = 6k$ (k is some integer). Then $a^2 = 36k^2 = 9(4k^2)$. Which means that $9\mid ...
6
votes
1answer
1k views

Concrete Mathematics - Towers of Hanoi Recurrence Relation

I've decided to dive in Concrete Mathematics despite only doing a couple of years of undergraduate maths many years ago. I'm looking to work through all the material whilst plugging gaps in my ...
6
votes
2answers
155 views

Construction of the projective plane over $\mathbb{F}_3$

I have a question about constructing projective plane over $\mathbb{F}_3$. We first establish seven equivalence classes $P= \{ [0,0,1], [0,1,0], [1,0,0], [0,1,1], [1,1,0], [1,0,1], [1,1,1] \}$. ...
6
votes
2answers
528 views

Planar graphs & Spanning trees

Does there exist a planar graph whose edges can be coloured either red, green or blue in such a way that the red edges form a spanning tree, the green edges form a spanning tree, and the blue edges ...
6
votes
1answer
4k views

Find a big-O estimate for $f(n)=2f(\sqrt{n})+\log n$

While self-studying Discrete Mathematics, I found the following question in the book "Discrete Mathematics and Its Applications" from Rosen: Suppose the function $f$ satisfies the recurrence ...
6
votes
3answers
1k views

How many of the 9000 four digit integers have four digits that are increasing?

How to find the number of distinct four digit numbers that are increasing or decreasing? The correct answer is $2{9 \choose 4} + {9 \choose 3} = 343$. How to get there?
6
votes
3answers
114 views

Numbering students inequality problem

Ten students are sitting around a campfire. A teacher randomly assigns each student a different number from 1-10. Another teacher assigns a new number to each student with the requirement that the new ...
6
votes
2answers
111 views

Show by induction that $2!4!6!…(2n)! \geq ((n+1)!)^n$

Show by induction that $2!4!6!...(2n)! \geq ((n+1)!)^n$ I stuck at $((n+1)!)^n (2(n+1))! \geq ((n+1+1)!)^{n+1}$, but cant progress to next step It will be great in someone can demonstrate how to ...
6
votes
1answer
302 views

convoluted recurrence: $f(2n)=f(n)+f(n+1)+n, f(2n+1)=f(n)+f(n-1)+1$

For the recurrence relation: $f(0)=1$ $f(1)=1$ $f(2)=2$ $f(2n)=f(n)+f(n+1)+n\ \ \ (\forall n>1)$ $f(2n+1)=f(n)+f(n-1)+1\ \ \ (\forall n\ge 1)$ (the first numbers of the sequence are: 1, 1, 2, ...
6
votes
1answer
153 views

permutation and f(n) challenge

Suppose $f(n)$ be the number of permutation from set ${1,2,..,n}$ such that for each $ 1 \leq i \leq n$ we have: $ | \pi(i)-i| \leq 1 $. meaning of $ \pi(i)$ is an elements whose in place $i$ of ...
6
votes
3answers
385 views

Recurrence with varying coefficient

Problem 1 $$ {\rm f}\left(n\right) = \frac{1}{n}\, \left[{\rm f}\left(n - 1\right)k_{0} + {\rm f}\left(n-2\right)k_{1}\right]\tag{1} $$ ( This can also be written as ${\rm Q}\left(n\right) = ...
6
votes
2answers
135 views

If $x+\frac{1}{x}$ is a natural number, then $x^{n}+\frac{1}{x^{n}}$ is a natural number for all $n\in \mathbb{N}.$

I am trying to solve the following exercise. If $x+\frac{1}{x}$ is a natural number, then $x^{n}+\frac{1}{x^{n}}$ is a natural number for all $n\in \mathbb{N}.$ Here what I've done. If ...