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

8
votes
2answers
408 views

A modified NIM game

Let's play a game of NIM, but with a catch! We have exactly three piles of stones with sizes $a$, $b$ and $c$, all of which are different. We move in turns. In every move, we can select a pile and ...
8
votes
2answers
220 views

Counting number of distinct systems

This is an enumeration problem in conjunction with some lottery problems. Given an integer $N \ge 5$. Let a ticket be a set of 5 distinct integers between $1$ and $N$. Given an integer $T$ between ...
8
votes
1answer
161 views

$n \times n$ lattice graph with partial derivatives bounded by $1$ has $n$ equal values.

I once proved this question many years ago but now I have completely forgotten how I did it. I remember it being a fun problem and wouldn't mind seeing a proof again, with the likelihood of it being ...
8
votes
1answer
141 views

For how many $n \in \mathbb{N}$ is $\sqrt{n^2+2379}$ natural?

Here's my attempt at a solution: the expression $\sqrt{n^2+2379}$ is natural iff $$n^2 + 2379 = x^2, \quad \mbox{ for some } x \in \mathbb{N}.$$ Therefore $$(x+n)(x-n)=2379=3 \cdot 13 \cdot 61.$$ I ...
8
votes
1answer
217 views

Function mapping challange

For a given set $A=\{1, 2, 3, 4, \ldots, n\}$, find the number of non-constant mappings (associations ) $f$ from $A$ to $A$ such that $f(k) \leq f(k + 1)$ and $f(k) = f(f(k + 1))$. This is ...
8
votes
1answer
492 views

Throwing balls into $b$ buckets: when does some bucket overflow size $s$?

Suppose you throw balls one-by-one into $b$ buckets, uniformly at random. At what time does the size of some (any) bucket exceed size $s$? That is, consider the following random process. At each of ...
8
votes
1answer
156 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$$ ...
8
votes
1answer
514 views

Into how many parts do $n$ ellipsoids divide $\mathbb{R}^{3}$?

What is the maximum number of regions into which $\mathbb{R}^{3}$ can be divided by $n$ ellipsoids? (Each ellipsoid has the same size). Let´s denote this number by $r_{n}$. Clearly $r_{1}=2$. But ...
8
votes
2answers
167 views

Given $N$, count $\{(m,n) \mid 0\leq m<N, 0\leq n<N, m\text{ and } n \text{ relatively prime}\}$

I'm confused at exercise 4.49 on page 149 from the book "Concrete Mathematics: A Foundation for Computer Science": Let $R(N)$ be the number of pairs of integers $(m,n)$ such that $0\leq m < N$, ...
8
votes
0answers
130 views

Algorithm to compute fastest method of collecting $k$ re-spawning items which spawn at $n$ specified points

Let $V = v_1, \dots, v_n$ be the locations the items can spawn at, and let $U = u_1, \dots, u_k$ be the current positions of the items. We will assume a new items spawns instantly every time we ...
7
votes
8answers
1k views

Show that from a group of seven people whose (integer) ages add up to 332 one can select three people with the total age at least 142.

I need help with this problem, and I was thinking in this way: $\ x_{1} + x_{2} + x_{3} + x_{4} + x_{5} + x_{6} + x_{7} = 332 $ and i need to find three of these which sum is 142. But I don't know ...
7
votes
6answers
2k views

Number of 6-digit passwords, starting with even or ending with odd digit

My problem is A password consists of six digits, each in $\{0,\ldots,9\}$ How many passwords start with an even digit or end with an odd digit? the answer is $750,000.$ I would like to know ...
7
votes
3answers
6k views

What is a null set?

I am very confused with null sets. I get that a set which has no elements will be called a null set but I am not getting the examples given below. Please help me by explaining how $P,Q,R$ are all ...
7
votes
6answers
125 views

How am I supposed to know that $\frac{1}{(1-x)^2} = \sum_{n=0}^{\infty } \binom{n+1}{n}x^n$?

I'm currently reading through the solution to a problem that involves finding generating functions. In some of the intermediary steps, it is written that $$\frac{1}{(1-x)^2} = \sum_{n=0}^{\infty } ...
7
votes
10answers
4k views

Prove by induction that $5^n - 1$ is divisible by $4$.

Prove by induction that $5^n - 1$ is divisible by $4$. How should I use induction in this problem. Do you have any hints for solving this problem? Thank you so much.
7
votes
3answers
3k views

Counting zero-digits between 1 and 1 million

I just remembered a problem I read years ago but never found an answer: Find how many 0-digits exist in natural numbers between 1 and 1 million. I am a programmer, so a quick brute-force would ...
7
votes
5answers
10k 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 ...
7
votes
5answers
92 views

Show that if $g \circ f$ is injective, then so is $f$.

The Problem: Let $X, Y, Z$ be sets and $f: X \to Y, g:Y \to Z$ be functions. (a) Show that if $g \circ f$ is injective, then so is $f$. (b) If $g \circ f$ is surjective, must $g$ be surjective? ...
7
votes
5answers
556 views

How does one find a formula for the recurrence relation $a_{1}=1,a_{2}=3, a_{n+2}=a_{n+1}+a_{n}?$

I am self-studying Discrete Mathematics, and I have two exercises to solve. Find a formula for the following recurrence relation: (translated from Portuguese) a) $a_{1}=3,a_{2}=5, ...
7
votes
4answers
276 views

Not understanding the concept of equivalence class

Let $U$ be a set defined: $U=\{(x,y)\in \Bbb R^2\mid x^2+y^2=1; xy\neq 0\}$, and let $R$ be relation defined: $(x_1,y_1)R(x_2,y_2) \iff (x_1 \cdot x_2>0∧y_1\cdot y_2>0)$. I was to prove it's ...
7
votes
2answers
2k views

What is the difference between necessary and sufficient conditions?

If $\quad p \implies q\quad $ ($p$ implies $q$), then $p$ is a sufficient condition for $q$. If $\quad \bar p \implies \bar q \quad$ (not $p$ implies not $q$), then $p$ is a necessary condition for ...
7
votes
3answers
743 views

Getting exactly one pair in a poker hand

I am not understanding this problem: In a deck of 52 cards, of 13 ranks, and 4 suits, how many different 5 card hand can we get such that, there is always exactly one pair. There is a similar ...
7
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, ...
7
votes
3answers
600 views

Fibonacci numbers divisible by $9$

The $n$th Fibonacci number $F_n$ is defined as follows,$$F_1=F_2=1\mbox{ and } F_{n+2}=F_{n+1}+F_{n}\mbox{ for } n\geq 1$$ I want to know how many of the first $1000$ Fibonacci numbers are divisible ...
7
votes
4answers
676 views

Closed-form expressions for sums

I've got a problem with deducing closed-form expressions for sums: $1) \ \sum_{k=0}^{m}(-1)^k {n \choose k} {n \choose m-k}$ $2) \ \sum_{A,B\subseteq X} |A\cup B|$ where $|X|=n$ Can anyone help me? ...
7
votes
2answers
381 views

Given three integers in $\{0,\ldots,100\}$ which sum up to $100$. What is the probabilty that two of them are the same?

We pick $3$ numbers (one by one) from set $\{0,1,...,100\}$. What is probabilty that two numbers are the same if sum of those $3$ numbers is $100$? My solution: Which two are the same we can pick in ...
7
votes
2answers
646 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) ...
7
votes
1answer
315 views

Spectrum of a real number

Whilst reading Concrete Mathematics, the authors mention something which they refer to as the "spectrum" of a real number (pg. 77): We define the spectrum of a real number $\alpha$ to be an ...
7
votes
2answers
359 views

Watchdog Problem

I just came up with this problem yesterday. Problem: Assume there is an important segment of straight line AB that needs to be watched at all time. A watchdog can ...
7
votes
5answers
3k views

If a plane is divided by $n$ lines, then it is possible to color the regions formed with only two colors.

I am self-studying Discrete Mathematics, and there is the following exercise. (in Portuguese) A plane is divided by many lines. Show that it is possible to color the regions formed with only two ...
7
votes
2answers
146 views

Every 33-length subsequence of $1,2,\dotsc,122$ contains a three term arithmetic progression

Is it possible to prove that every 33-length subsequence of the sequence $1,2,3,\dotsc,122$ contains a three term arithmetic progression? Maybe I should post it on mathoverflow
7
votes
2answers
309 views

Existence of infinitely many integers $n$ such that $2^n$ ends with $n$

Can anyone please help me on the following proof: Prove that there exist infinitely many positive integers $n$ such that $2^n$ ends with $n$ in decimal notation, i.e. $2n = \ldots n$.
7
votes
2answers
7k 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 ...
7
votes
2answers
223 views

maximum number of edges to be removed to possess a property

I am working on a problem. We know that on squaring a cycle, degree of every vertex is 4. For squares of cycles, we know if we delete any arbitrary edge then still eccentricity is same for all ...
7
votes
3answers
3k views

What's the difference between a contrapositive statement and a contradiction? [duplicate]

I keep mixing them up, because they are very similar. Some contrapositives resemble some contradictions.
7
votes
6answers
119 views

Solve $\lfloor \sqrt x \rfloor = \lfloor x/2 \rfloor$ for real $x$

I'm trying to solve $$\lfloor \sqrt x \rfloor = \left\lfloor \frac{x}{2} \right\rfloor$$ for real $x$. Obviously this can't be true for any negative reals, since the root isn't defined for such. My ...
7
votes
4answers
209 views

Let $a_n$ be the $nth$ term of the sequence $1, 2, 2, 3, 3, 3, 4, 4, 4, 4, \dots$

Question:Let $a_n$ be the $nth$ term of the sequence $1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6\dots$, constructed by including the integer $k$ exactly $k$ times. Show that $a_n = ...
7
votes
2answers
584 views

If we have $m$ indistinguishable objects how many ways is it possible to put them in $n$ indistinguihable positions?

if we have $m$ indistinguishable objects, how many ways is it possible to put them in $n$ indistinguishable positions? (for 2 cases 1: without empty position allowed 2: empty positions are allowed.) ...
7
votes
4answers
2k views

Big-O notation Basics, is it related to derivatives?

I am having the hardest time with Big-O notation (I am using this Rosen book for the class I am in). On the surface, Big-O reminds me of derivatives, rate of change and what not; is this proper ...
7
votes
3answers
778 views

Decomposing a discrete signal into a sum of rectangle functions

Hello math@stackexchange community ! I have a simple question that seems to have a non trivial answer. Given a discrete one dimensional signal $w(x)$ defined in a finite range, and the boxcar ...
7
votes
2answers
1k views

Proof of clockwise towers of Hanoi variant recursive solution

This is from one of the exercises in "Concrete Mathematics", and is something I'm doing privately, not homework. This is a variant on the classic towers of Hanoi, where all moves must be made ...
7
votes
2answers
448 views

Symbolic coordinates for a hyperbolic grid?

Rephrasing     (one year later)    (original question is below) Apparently the original question wasn't clear, or nobody knows an answer (or both). So I will try to rephrase it. Look at your ...
7
votes
2answers
493 views

For all $n>2$: there exists $p$ prime: $n<p<n!$

The question is: For all $n>2$, where $n \in \mathbb Z$: there exists $p$ prime such that $n<p<n!$ Here is my Proof: $\forall$ $p<n: p|n!$, or $p$ divides $n!$ Since $n!$ and $n!-1$ ...
7
votes
1answer
54 views

Partitioning $n$ naturals summing $2N$ into two sets summing $N$

I'm trying to solve this problem: Let $a_1, \ldots , a_n$ be natural numbers such that $a_k \le k$ for every $k = 1,\ldots,n$, and $\sum_{k=1}^{n} a_k=2N$. Show that there exists a partition of ...
7
votes
1answer
169 views

Occupying seats in a classroom

Here's a nice probability puzzle I have thought about for a class I'm TAing, I'm curious to see different solutions :) It goes like this: We have a classroom with $n$ seats available and $m \leq n$ ...
7
votes
1answer
266 views

A finite sum involving the binomial coefficients and the harmonic numbers

Wikipedia has a proof of the identity $$ H_{n} =\sum_{k=1}^{n} (-1)^{k-1} \binom{n}{k} \frac{1}{k}$$ http://en.wikipedia.org/wiki/Harmonic_number#Calculation Curiously, there is also the identity ...
7
votes
1answer
98 views

Number of permutations $\langle a_1,\ldots,a_n\rangle$ of $\{ 1,\ldots ,n \}$ with $a_{i+1} - a_i \ne 1$

Prove that for $n>0$, the number of permutations $\langle a_1,\ldots,a_n\rangle$ of the set $\{ 1,\ldots ,n \}$, where $a_{i+1} - a_i \ne 1$ for $ i = 1, \ldots, n-1$ is equal to: $$D_n + ...
7
votes
1answer
164 views

Graph, two colors, no path length 3

I've just begun studying graph theory and I have some difficulty with this problem. Could you tell me how to go about solving it? In a graph $G$ all vertices have degrees $\le 3$. Show that we can ...
7
votes
3answers
696 views

Proving statements by its contrapositive

Prove the following statement by proving its contrapositive: “If $n^3 + 2n + 1$ is odd then n is even” Therefore: $\lnot q \rightarrow \lnot p =$ "if $n^3 + 2n + 1$ is even then $n$ is odd. So ...
7
votes
1answer
326 views

Prove that there's no fractions that can't be written in lowest term with Well Ordering Principle

This is from Class Note from 6.042 ocw courses at MIT: "Well Ordering Principle" section: ( Sorry for not posting latex; I have less than 10 reputations to post images ) You can read the original ...