Questions on discrete mathematics generally: "the study of mathematical structures that are fundamentally discrete rather than continuous"
-1
votes
1answer
48 views
Convert $435_{10}$ and $220_{10}$ to both their hexadecimal and octal expansions
I need to convert 435 and 220 from their decimal form, to their hexadecimal and octal expansions.
1
vote
2answers
49 views
What is the set containing only integers congruent to 89 modulo 17?
What is the set containing only integers congruent to 89 modulo 17
1
vote
1answer
17 views
Even weighted codewords and puncturing
My question is below:
Prove that if a binary $(n,M,d)$-code exists for which $d$ is even, then a binary $(n,M,d)$-code exists for which each codeword has even weight.
(Hint: Do some puncturing ...
3
votes
2answers
49 views
A property of a prime divisor of a number consisting of 1s
For $n>0$ let $A(n) = \underbrace{111 \ldots 11}_{n}$. Prove that if $A(n)$ is divisible by a prime number $p>3$, then $\gcd(n, p-1) > 1$.
It is no huge discovery that if $n$ is even, ...
1
vote
2answers
25 views
solving linear recurrence - general solution confusion
I've been trying to get my head around this for days. I understand what is going on with the calculation of a linear recurrence and I also understand how the characteristic is obtained.
What is ...
1
vote
4answers
73 views
Writing an expression using logic
Write an expression using letters $\land, \lor, and$ $\neg$ which has the following truth table:
$$\begin{array}{ccc|c}
P&Q&R&???\\ \hline
T&T&T&F\\
T&T&F&T\\
...
10
votes
3answers
133 views
Combinatorial proof of $\sum^{n}_{i=1}\binom{n}{i}i=n2^{n-1}$.
Prove
$$\sum^{n}_{i=1}\binom{n}{i}i=n2^{n-1}$$
I can't find counting interpretations for either of the sides. A hint of "if $S$ is a subset of $\{1, . . . , n\}$ and $S^\prime$ is its complement ...
2
votes
3answers
58 views
How many numbers between 1 and 10,000,000 don't have the sequence 12? Inclusion-exclusion problem
I got the following question:
How many numbers between 1 and 10,000,000 don't have the sequence 12? This is an inclusion-exclusion problem. Sadly I didn't fully understand its concept, so I tried ...
0
votes
1answer
14 views
Clues to prove average in T is minor or equal than average in a smaller inner interval.
Suppose I want to prove (or disprove) this assertion
Let $f$ be a discrete function, $T,h,k$ are constants
So these terms are averages over $T$ and over $h$
$\sum\limits_{i=0}^{T}\frac {f(i)}{T}$ ...
1
vote
2answers
34 views
Proper way to define this multiset operator that does a pseudo-intersection?
it's been a while since I've done anything with set theory and I'm trying to find a way to describe a certain operator.
Let's say I have two multisets:
$A = \{1,1,2,3,4\}$
$B = \{1,5,6,7\}$
How ...
2
votes
2answers
28 views
Probability question about distinguishable and non distinguishable objects
so for part a I got the answer as m choose 1 times (1/m)^b
but for part B I am having different approaches and dont know which one is correct
approach 1:
m choose 2 times (2/m)^m
approach 2:
m ...
2
votes
2answers
49 views
Polynomial discrete mathematics
I ran into this question:
Let $p$ be a prime number. We will work on $\mathbb{Z}_{p}$.
Let $d$ be a divisor of $p-1$, $(p-1)/d=r$.
Show that the equation $x^{d}=1$ has exactly $d$ solutions on ...
0
votes
3answers
51 views
Solutions over $\mathbb{Z}_p$
What does this fact mean:
"the polynomial $\sum_{i=0}^{n}a_{i}x^{i}$ has at most $n$ solutions over $\mathbb{Z}_{p}$"
?
Thanks in advance,
Yaron.
0
votes
0answers
41 views
What computer program can calculate Kemeny-Snell's median?
Unfortunately, I didn't find any computer realization for computing Kemeny-Snell's median.
1
vote
1answer
141 views
No of labeled trees with n nodes such that certain pairs of labels are not adjacent.
Moderator Note: This is a current contest question on codechef.com.
What is the number of trees possible with $n$ nodes where the $i$th and $(i+1)$th node are not adjacent to each other for $i ...
-1
votes
0answers
20 views
Estimate the number of lattice points inside a hyperbox
How can I estimate the number of lattice points inside a $d$-dimensional hyperbox?
1
vote
3answers
129 views
Prove that connected graph G, with 11 vertices and and 52 edges, is Hamiltonian
Is this graph always, sometimes, or never Eulerian? Give a proof or a pair of examples to justify your answer
Could G contain an Euler trail? Must G contain an Euler trail? Fully justify your answer
2
votes
2answers
57 views
Are these propositions equivalent?
Statement 1: Maria will find job if she learns mathematics.
Statement 2: Maria will find a job unless she does not learn
mathematics.
I know the answer is probably that these are same, but ...
1
vote
1answer
44 views
binary circle - difficult question
I ran into this question and I'm not really sure how to start.
we are looking at 100 0/1's that are written arround a circle. for a binary sequence $w$,
we'll define $n_{w}$ as the number of times ...
1
vote
1answer
28 views
Combinatorial Techniques: Putting two and two together
This is a $3$-part question. I got the first two parts, but could not get the third part (which uses the first two parts):
Pick sequence of $8$ coins from sack of $40$ coins, containing $10$ pennies, ...
0
votes
1answer
53 views
Probability 2 people have a birthday in the same month out of 7
What is the probability that 2 people in the group have a birthday in the same month out of 7 people?
I know the answers 88.85% however I want to know how to work it out using factorials instead of ...
1
vote
1answer
38 views
Placing beads on a necklace, 7 colours. How many can be made
Dude wants to make a necklace with 7 beads, each a diffrent color.
(red, orange, yellow, blue, green, indigo, violet) placed on a chain that is then closed
to form a circle. How many different ...
0
votes
1answer
21 views
Recursive Definitions with Converse
I think I know how to solve i. and ii., but not iii:
Base Case: $(0,0) \in S$
Recursive Step: If $(a,b)\in S$, then $(a+1,b+2)\in S$ and $(a+2, b+1)\in S$.
(For i and ii): Prove that if $(a,b) \in ...
2
votes
2answers
43 views
Graph Theory adjacency matrix
Is it possible for a graph to exist that meets these conditions.
For Graph G the adjacency martix has all 1's in the first row and all 0's in the second row.
What I think: it cant exist because if ...
0
votes
0answers
37 views
Random Walk, Coin flip game [closed]
Consider the coin flipping game, where player $A$ pays $B$ \$1 for each Heads, and vice versa for each Tails. (The coin is unbiased here.) Let $X_1$ be the random variable recording the first time ...
1
vote
1answer
16 views
Is there an explicit solution to: $\arg \min mn : mn \geq k, l_0 \leq n \leq l_1$?
Is there an explicit solution or a fast algorithm to compute:
$$\underset{(m, \ n) \in \mathbb{N}_{+}^2}{\arg \min} \ mn \ : \ mn \geq k,\ l_0 \leq n \leq l_1$$
for given constants $k, l_0, l_1 \in ...
1
vote
0answers
41 views
Which cut does the “minimum cut” refer to?
My course notes give the following definitions; could someone please verify that the last definition is non-standard? (I've spent all evening googling, and isn't "minimum cut" a concept related to cut ...
3
votes
2answers
46 views
Symmetric Groups and Commutativity
I just finished my homework which involved, among many things, the following question:
Let $S_{3}$ be the symmetric group $\{1,2,3\}$. Determine the number of elements that commute with (23).
Now, ...
2
votes
2answers
36 views
Let $A$ be a set, $R$ an empty relation on $A$, what is $A/R$?
Let $A=\{0,1,2\}$ be a set and $R=\{\}$. I know that $R$ is not an equivalence relation, but does it have to be? What is $A/R$ if $R$ is empty?
Examples:
$R_1=\{(0,0),(1,1),(2,2)\}$, $A/R_1=\{[0], ...
2
votes
0answers
33 views
Are edge cuts, vertex cuts, and cut sets all variously called “cuts”?
I've seen "cut" being used to refer to all three, in different places, and sometimes in the same book.
Which does "cut" most commonly refer to?
p.s. I am aware that "cut" itself can be defined to ...
0
votes
1answer
29 views
Do “cut set” and “edge cut” mean the same thing?
The definitions I have are:
A cut set of a graph $G$ induced by a partition of $G$'s vertices
into sets $X$ and $Y$ is the set of all edges with one endpoint in $X$
and another endpoint in ...
1
vote
1answer
16 views
Convergence of Discrete Poisson equation
Are there any sources that show the convergence of the discrete poisson equation?
To be clear, by convergence I mean: given the poisson equation in a domain $ M \subset R^2 $, $\Delta \psi = f $, one ...
0
votes
0answers
44 views
Map-Coloring Problem
When we are faced with map-coloring problem, why do we allow countries that meet at only one point to receive the same color? Is it because they do not share the same boundaries or common boundaries? ...
2
votes
2answers
56 views
How do I prove the arithmetic-geometric mean inequality?
I am following along with this bare-bones proof of the arithmetic-geometric mean inequality with two real numbers. I'm having difficulty understanding the logic behind this step:
$$
...
4
votes
1answer
40 views
Finding maximum score in a “bubble pop” game
Consider the following game: there is a n×n field, where each cell is randomly coloured in one of m colours. Let a group of cells be a set of same-coloured cells s.t. every cell in a group has at ...
0
votes
1answer
34 views
Do these two expressions mean the same?
So for a given database we have the sets Persons, Married, Women, Men and Children.
I want to express all Women who are not Children and not Married:
$$Women\setminus \left ( married \cup children ...
1
vote
1answer
11 views
Prove the existence of a row and a column in the Boolean matrix which satisfy the conditions
"Let A be an 8x8 Boolean matrix. If the sum of A = 51, prove that there is a row and a column such that when the total entries of the row and column are added, the sum is greater than 13."
I have ...
2
votes
5answers
88 views
Solving the recurrence relation [closed]
I'm interested in learning how can we solve this linear non-homogeneous recurrence relation?
$$a_z = 2a_{n-1} - 1a{n-2} + (s^2 + 1)$$
0
votes
1answer
36 views
Finding a reccurence relation for the following problem
A circular disk is cut into n distint sectors, each shaped liek a piece of pie and all meeting at the center point of the disk. Each sector is to be painted red, green, yellow, or blue in such a way ...
-2
votes
1answer
50 views
Given the following recurrence relation, prove using mathematical induction
How can we prove this using mathematical induction?
$m_1 = 0$
$m_k = m_{\lfloor (k/2) \rfloor} + m_{\lceil (k/2) \rceil} + k-1$ for all integers $k \geq 1$
Prove using mathematical induction that ...
0
votes
6answers
110 views
Finding the number of subsets of S
How can we find the number of subsets of $S=\{1,2,3,...,10\}$ that contain neither 5 nor 6?
Thanks!
0
votes
2answers
49 views
Use the binomial theorem to expand
How can we expand this using the binomial theorem?
$(x^2 + 1/x)^7$
3
votes
3answers
67 views
Why all odd numbers not ending with 5 divide exactly into a number comprising only 9's?
Help me!!It's really frustrating I can't understand this simple thing.The maths instructor in my video,the renowned Arthur Benjamin,states (clip linked below) the following:
...
1
vote
1answer
50 views
to find disconnected graphs
We know that if in a graph $G$, $e$ < $(n -1)$, then the graph is disconnected, where $e$ and $n$ are number of edges and number of vertices resp. Is there any other criteria to find out the ...
1
vote
1answer
45 views
Proof involving functions.
Consider two functions $f\colon A \to B$ and $g\colon B \to C$. How can I prove the following?
If $f$ and $g$ are one-to-one, then the composition function $g \circ
f$ is one-to-one.
If $f$ and ...
1
vote
1answer
30 views
Relations. Check whether symmetric,reflexive or transitive .?
Q6. Let R and S be relations on a set A. Assuming A has at least three elements, state whether each of the following statements is true or false. If it is false, give a counterexample on the set A = ...
0
votes
3answers
47 views
Set Theory: General Intersection
How to properly prove the following:
For all integers positive integers n, if A1, A2,... and B are sets, then
9
votes
2answers
371 views
9 pirates have to divide 1000 coins…
A band of 9 pirates have just finished their latest conquest - looting, killing and sinking a ship. The loot amounts to 1000 gold coins.
Arriving on a deserted island, they now have to split up the ...
0
votes
1answer
57 views
Discrete math problem confusion.
:
But I'm still confused how we are are going to write the final answer.
Your help will be appreciated. thanks.
0
votes
2answers
30 views
Prove that if $A\triangle B = C\triangle B$, then $A = C$
I am working with proofs in discrete math.
Help to prove:
For the sets $A$ and $B$, we define the symmetric difference of $A$ and $B$ to be $A \triangle B = (A-B)\cup(B-A).$
Prove that if $A ...
