Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [discrete-mathematics]

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.

16
votes
0answers
1k 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 ...
8
votes
0answers
216 views

Counting the labellings of paths in perfect binary trees

Suppose that we have a set of $n$ labels $L = \{\ell_1, \ell_2, \ldots, \ell_n\}$ and a perfect rooted binary tree $T$ of height $r \leq n$. For my purpose, the tree containing a single node will be ...
8
votes
0answers
123 views

Minimum number of terms of strictly increasing minimal sequence whose product is square.

Ron Graham's sequence is a neat bijection from the positive integers to the non-primes, defined as following: $a(n)$ = smallest $m$ for which there is a sequence $n = b_1 < b_2 < \dotsc < ...
8
votes
0answers
265 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 bounds:$$|C|\...
7
votes
0answers
64 views

Partitioning a graph in cycles of four

I have the following question: Suppose that in a simple undirected graph with $4n$ vertices, each vertex has degree at least $2n$. Is it true that we can always partition the set of vertices ...
7
votes
0answers
141 views

Broken stick game

Two players Alice and Bob play the following game consisting of $n-1$ turns. Initially the segment $[0,1]$ is given. Alice and Bob then alternate breaking one segment into two pieces. After all turns ...
7
votes
0answers
145 views

Approximating intervals and squares by increasingly dense disjoint finite sets with special properties

Apologies for the length of the question. Consider interval $I=[0,1]$. For any $n \in \mathbb{N}$ we can always find two finite sets $S_{1n} \subset I$ and $S_{2n} \subset I$ such that: a) $S_{1n}\...
7
votes
0answers
104 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 $\text{supp}(...
7
votes
0answers
84 views

Number of circuits that surround the square.

Consider a grid $G$ in the $\mathbb{R}^2$ plane formed by the points $(x,y)$ with integer coordinates i.e. $G=\{(x,y)\in\mathbb{R}^2: x\in\mathbb{Z},\;y\in\mathbb{Z} \}$. For $n>0$ let $B_n$ square ...
7
votes
0answers
209 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
247 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
0answers
139 views

Almost a prime number recurrence relation

For the number of partitions of n into prime parts $a(n)$ it holds $$a(n)=\frac{1}{n}\sum_{k=1}^n q(k)a(n-k)\tag 1$$ where $q(n)$ the sum of all different prime factors of $n$. Due to https://oeis....
6
votes
0answers
76 views

The number of Hamiltonian paths in a tournament is always odd?

A tournament is defined as an orientation of a complete graph. Prove or disprove the following statement: In a tournament, there are exactly an odd number of Hamiltonian paths. In all cases I’ve ...
6
votes
0answers
83 views

Number of phone locking patterns

LG android cell phones have locking screens with $9$ points to be traced in any pre-specified fashion (drawing pattern) so as to join $\geq 4$ points without including any points more than once. ...
6
votes
0answers
105 views

Central limit theorem for perfect matching counts

Set $N_G$ the number of copies of graph $G$ in the Erdős–Rényi random graph model $G(n,p)$. We have the law of large number for the number of copies of of graph $G$ i.e. $N_G$ is very close to the ...
6
votes
0answers
131 views

Is there a relationship between local prime gaps and cyclical graphs?

By defining the following algorithm I was able to generate some interesting graphs using the values of the gaps between consecutive primes: Start in any prime $p_i$, this will be the initial ...
6
votes
0answers
977 views

Recursive and Primitive recursive functions

According to the book that I'm reading, we can define the $\mu-$recursive functions inductively, as follows: The constant, projection, and successor functions are all $\mu-$recursive. If $g_1, \...
6
votes
0answers
275 views

Worst case in decanting puzzles (pouring water from one jug to others).

A classic puzzle is to start with $3$ jugs of nonzero integer capacity ($A \ge B \ge C$) and have some water (integer) in each jug (the initial position). The goal is to get to some final (integer) ...
6
votes
0answers
191 views

Decrease of entropy when iterating a random discrete function

Let $m$ be a positive integer. Let $S$ be the set of non-negative integers $x$ less than $m$, with $|S|=m$. Let $X_0$ be the discrete uniform distribution over $S$, with $P(x)=\begin{cases} 1/m & \...
5
votes
0answers
71 views

Two players placing coins on a table- Extension

The origin of my question comes from a common job interview question where two players take turns placing coins on a round table. The coins cannot overlap and can't be moved once they've been placed. ...
5
votes
0answers
103 views

Properties of the “eeny, meeny, miny, moe function”

N.B.: there's another question about "eeny, meeny, miny, moe" in mathstackexchange but it is different to what it is presented here. Consider the function $f(p,s)$ defined as follows: There are $p&...
5
votes
0answers
92 views

Generating functions - coefficient of $x^{27}$

What is the coefficient of $x^{27}$ for $f(x) = \Big(\dfrac{1+x^{10}}{(1-x)^5}\Big)^{2}$ ? So i can work the math a little bit to get - $f(x) = \Big(\dfrac{1+2x^{10} + x^{20}}{(1-x)^{10}}\Big)$ $...
5
votes
0answers
137 views

Is $63\times63$ the largest matrix with no rectangles that have an even number of each $0-9$ digit?

I'm working on an algorithm that finds the largest rectangle with an even number of all 10 digits within a square matrix, e.g. for the 4×4 square on the left that would be this 3×2 ...
5
votes
0answers
9k views

Proof that the sum of all degrees is equal to twice the number of edges

We want to proof $2|E| = \sum \limits_{v \in V} deg(v)$ for a simple graph (no loops). For our proof we assume $n$ to be the number of edges in a simple graph $G(E, V)$. We proceed our proof by ...
5
votes
0answers
97 views

How to formally represent a function whose elements are sets?

Let us suppose that I have two sets: A and B. $A = \{0,2,4,6,8\}$ $B = \{1,3,5,7,9\}$ Let us suppose that I have a function f that maps elements of A and elements of B to the natural numbers ($\...
5
votes
0answers
191 views

Binomial Coefficient Identity, Double Series, Floor Function

Show that for any natural numbers $m$ and $n$ such that $ m \le n $ that: $$ \sum_{i=0}^{n}{ \sum_{j=0}^{m}{ \left(-1 \right)^{\lfloor \frac{i}{2} \rfloor+j}2^{n-i}\binom{n-\lfloor \frac{i+1}{2} \...
5
votes
0answers
107 views

Proving $f$ cannot be onto

If $f$ maps finite sets $A$ to $B$ and $n(A) < n(B)$, prove that $f$ cannot be onto. Proof by contradiction: If $f: A→B$ and $n(A) < n(B)$, $f$ is onto. Since, by definition of a function, $a∈...
5
votes
0answers
201 views

Maximal Hamming distance

Here is a combinatorial problem: let $\Sigma=\{\alpha_1,\ldots,\alpha_n\}$ be an alphabet and we consider any words over $\Sigma$ of length $n$. We also define over the set of such words the Hamming ...
5
votes
0answers
152 views

Using discrete calculus to study convergence of series and sequences

From some personal investigation, I've noticed that all convergence tests for infinite series (at least, the real kind) can be rephrased in terms of the discrete derivative $∆f(x)$ of a function $f(x)$...
5
votes
0answers
148 views

Upper bounds on rate of q-ary codes

Among the many upper bounds for families of codes in $\mathbb F _2 ^n$, the best known bound is the one by McEliece, Rodemich, Rumsey and Welch (MRRW) which states that the rate $R(\delta)$ ...
4
votes
0answers
40 views

Prove that $(A\setminus B)\cup (B \setminus A)\subseteq (A\cup B)\setminus(A\cap B)$

I am asked to prove that $$ (A\setminus B)\cup (B\setminus A)\subseteq (A\cup B)\setminus(A\cap B) $$ where $A$ and $B$ are sets. Could someone please check my solution and see if it is correct? I ...
4
votes
0answers
57 views

Longest path through chessboard of arbitrary size

The original problem: You have a $8\times 6$ board. Your task is to color some tiles white and some black. There must be a unique beginning and end of the white trail and only one way to get from one ...
4
votes
0answers
64 views

Small & Balanced family of sets

I have the following problem: Let $\epsilon >0$, and $[n] = \{ 1,2,...,n\}$ the set of positive integers up to $n$. There exists a family of subsets $\mathcal{F} \subseteq 2^{[n]}$, such that ...
4
votes
0answers
49 views

Proving $(A \cup B) \backslash (A \cap B) = (A \cup C) \backslash (A \cap C) \implies B = C$

Indirect proof. Assume that $B \neq C$. Therefore I assume without loss of generality that $\exists x (x \in B \land x \notin C)$. This leaves us with two possible cases: $x \in A$. But then $x \...
4
votes
0answers
40 views

Prove that a $d$-regular, $d$-edge-connected graph $G$ is tough when $d\geq3$.

Isn't something like shown below can happen where $d=3$ and $k=1$? If no, then how do we prove it. Here v is a vertex with degree $3$, and $C_1$, $C_2$, and $C_3$ are $3$ different components, then ...
4
votes
0answers
112 views

On the Catalan Numbers

I have been able to prove the following using the snake oil method: $$\sum_{k \ge 0} C_k {{n-2k} \choose {l-k}} = {{n+1} \choose {l}}$$ where $l,n$ are positive integers and $C_k$ is the $k$-th ...
4
votes
0answers
173 views

What is the sum of the even (resp. odd) terms only of the Hockey-stick identity?

The Hockey-stick identity is $$\sum^n_{i=r}{i\choose r}={n+1\choose r+1} \qquad \text{ for } n,r\in\mathbb{N}, \quad n>r$$ I am trying to determine the values of the following $$\sum_{\...
4
votes
0answers
63 views

Proof that every polygon has at least 2 ears

I had this question asked a few weeks ago and gave an argument that involved finding an ear and clipping it, professor said it was not quite the correct answer and that I lacked some insights. How ...
4
votes
0answers
145 views

Bipartite graph $G=(A,B)$ with $\delta(A)=3n/2$ and no $C_4$ has a matching which saturate each vertex in $A$.

Say $G$ is a bipartite graph with bipartition $(A,B)$ and $G$ is $C_4$-free. Prove that if every vertex in $A$ has degree at least $\frac32 n$ and $|A|\leq n^2$, then $G$ has a matching which uses ...
4
votes
0answers
74 views

Periodic sequences resulting from a summation over the Thue–Morse sequence

Let $s_2(n)$ denote the sum of digits of $n$ in base-2 (OEIS sequence A000120), and $t_n=(-1)^{s_2(n)}$. Note that $t_n$ is the signed Thue–Morse sequence (OEIS sequence A106400), satisfying the ...
4
votes
0answers
49 views

Counting all $9 \times 8$ matrices with two restrictions (checking if I'm right)

I stumbled upon this problem today and I'm not 100% confident my approach is correct. The problem states: Count all $9 \times 8$ matrices that fulfill all three restrictions: 1) Every element in the ...
4
votes
0answers
211 views

Graph Envelope Constraint puzzles from The Witness game.

The computer game "The Witness" contains various puzzles based on a finite square grid graph arranged in the usual way. A path must be found from a given point on the edge to another. Each square can ...
4
votes
0answers
247 views

Probability with random intersecting lines

Suppose we have $n$ random lines that intersect the coordinates $[0,1]^2$. To choose a line randomly, we must first randomly choose a point on a side, choose any point on either of the other three ...
4
votes
0answers
158 views

Prove or disprove that a graph made by $n$ straight lines is Hamiltonian.

Given $n$ lines, no two of which are parallel and no more than two intersect at the same point. Construct a graph with the intersection of lines as vertices and the line segments as edges. Prove or ...
4
votes
0answers
375 views

Bride and groom for photo

In how many ways can a photographer at a wedding arrange seven people in arow, including the bride and the groom, if the bride must be next to the groom? Here is my attempt at solving this problem. ...
4
votes
0answers
107 views

Seemingly difficult probabilistic method question

Hello I was asked the following question and I really am not sure how to show such results. I believe it could maybe be done using the probabilistic method. Consider a graph on $ m$ vertices, for ...
4
votes
0answers
132 views

How to discretize a certain integral

I would like to discretize the following integral operator: $$\frac{1}{s^2}\sum_{j=1}^N\mu_j\int d\mathbf{x}d\mathbf{x}'f(\mathbf{x})f(\mathbf{x'}) \left(x_j + x'_j - 2\mu_j\right)\hat{a}^\dagger(\...
4
votes
0answers
65 views

A question on a proof of the existence of non-measurable sets

This is an excerpt of Rosenthal's book: "A First look at Rigorous Probability Theory" and contains an important theorem in the development of measure theory. While I generally understand the proof ...
4
votes
0answers
164 views

Find the number of simple labeled graphs which have no isolated vertices

Find the number of simple labeled graphs on n vertices which have no isolated vertices? Compute the result for n=13 Total number of simple labeled graphs = $2^{n \choose 2}$. How to remove vertices ...
3
votes
0answers
144 views

How to generate a Penrose tessellation around a given tile?

Given a starting Penrose tile, I need to build a "spiraling" tessellation around it. The following picture illustrates the request: In this example, the starting tile is a "thin rhombus" (the pink ...