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

1
vote
1answer
52 views

Solve Inverse Linear Congruence

I want to solve Linear congrunece : 9x+2 ≡ 6(mod 1453) using inverse of 9 mod 1453. Inverse of 9 mod 1453 is 323. Now to solve it I subtract 2 from left and right side which gives me 9x ≡ 4(mod 1453), ...
0
votes
1answer
25 views

Colouring maximizing the weight of coloured edges

I would like to know if the following problem has been studied in the literature: We are given a edge-weighted undirected graph $G = (V,E)$ together with a set of available colours $C_v$ for each ...
0
votes
0answers
15 views

Autocorrelation Bernoulli process

Considering a process in discrete time $u[k]$, also known as Bernoulli process and defined by this characteristics: 1. The process appear as $0$'s and $1$'s. The random variable $u[k]$ don't take any ...
2
votes
0answers
48 views

Correctness of counting with product of generating functions

In generating functions we can related the coefficients of the generating function with as sequence. $$f(x) = \sum^{\infty}_{n=0}f_nx^n$$ and the sequence that corresponds to it: $$( \ f_0 \ , \ ...
0
votes
3answers
29 views

Is there a theorem or axiom which shows that permutations of step sequences through a lattice graph result in the same destination?

I have been searching for a theorem, lemma, or even an axiom which shows that the permutations of a step sequence in Taxicab Geometry result in the same destination in such a lattice graph. To ...
4
votes
2answers
112 views

How many ways are there for three medals to be awarded if ties are possible?

The Question There are six runners in the 100-yard dash. How many ways are there for three medals to be awarded if ties are possible? (The runner or runners who finish with the fastest time receive ...
1
vote
1answer
88 views

How many bit strings contain exactly eight 0s and 10 1s if every 0 must be immediately followed by a 1?

The Question How many bit strings contain exactly eight 0s and 10 1s if every 0 must be immediately followed by a 1? Note: There is a similar but also very different question on this site. Please do ...
0
votes
2answers
60 views

how to prove that which constants a,b,c,and d it is true that f o g = g o f

im working on a functions unit and Im stuck on this problem: Let $f(x) = ax + b$ and $g(x) = cx^2 + dx$ (a,b,c,d are constant). Compute f o g and g o f. And determine for which constants a, b, c and ...
2
votes
1answer
26 views

Show that n is a perfect square if and only if $k_i$ is even for $ 1 \leq i \leq m$

Suppose that $n = p_{1}^{k_1} p_{2}^{k_2} ... p_{m}^{k_m}$, where $p_1<p_2<...<p_m$ are all prime. Show that n is a perfect square if and only if $k_i$ is even for $1 \leq i \leq m$ I'm not ...
3
votes
1answer
74 views

Variances for K-Means clustering

Can somebody help me understand formulas with an example in the below image? The below image is about K-means clustering. The formulas are about calculations for the variance for within-clusters and ...
0
votes
2answers
53 views

Using inclusion-exclusion principle to count the integers in $\{1, 2, 3, \dots , 100\}$ that are not divisible by $2$, $3$ or $5$

Question: How many integers in $\{1, 2, 3, \dots , 100\}$ are not divisible by $2$, $3$ or $5$? Can anyone give me a full explain of how this applies to the inclusion-exclusin principle? Because I ...
1
vote
1answer
46 views

Conversion from English Language to Logic Symbols

I have a problem in an example of Discrete Mathematics which my teacher worked in his lecture. He gave an argument and proved it that his argument was not valid, but the validity of argument is not ...
1
vote
1answer
14 views

How do you scale a set of number such that they sum to 0.5 after scaling

Suppose I have a set of numbers of various different values (>0.0). I want to scale these numbers so that they all sum to 0.5. The scaling is required so that the relative strength of the numbers with ...
0
votes
0answers
28 views

For any set $A$, prove that $A^{\lbrace1,2,3\rbrace}$ ~$A \times A \times A$

~ just denotes showing two sets have the same cardinality. $A^{\lbrace1,2,3\rbrace }$ is the set of functions, 1,2,3 that go to the set $A$. I am not sure how to do this but I know if I can define ...
3
votes
3answers
79 views

Bijection, and finding the inverse function

I am new to discrete mathematics, and this was one of the question that the prof gave out. I am bit lost in this, since I never encountered discrete mathematics before. What do I need to do to prove ...
0
votes
1answer
116 views

how to solve a question about Fibonacci numbers and lucas numbers using induction..

Im working on practice problems that the instructor gave us yesterday, and I absolutely have no clue of how to solve this problem.. I need to use mathmatical induction to solve this problem.. The ...
1
vote
2answers
50 views

if $f(g(x))$ is 1 to 1, then is g 1 to 1?

Im working on practice problems that the instructor gave us yesterday and Im stuck with this question.. the question is: if $f\circ g $ is one to one, then is $g$ one to one? Im not sure how to ...
2
votes
1answer
45 views

How many ways are there for eight men and five women to stand in a line so that no two women stand next to each other?

How many ways are there for eight men and five women to stand in a line so that no two women stand next to each other? I started off by arranging the men into a line so we have $M_1,M_2,M_3,....,M_8$ ...
2
votes
2answers
48 views

How many bit strings of length n contain exactly r 1s?

This has me confused. Wouldn't we want to use permutations in this case, and not combinations, since order is relevant when forming bit strings?
1
vote
2answers
27 views

Minimum number of students, where 100 students from the same state go to the same university

I was given the following question: I thought of the problem like this. Each of the $50$ states represents a box, and I want $100$ people in the same box. By the pigeon-hole principle, we are ...
0
votes
1answer
43 views

Logarithmn subtraction with unknown bases & Logarithmn Identities

The b is supposed to be lowercase in the log functions but I do not know how to do that yet in this syntax. $1)$ Find $x - y$ where $x = 2^{\log_b(3)}$ and $y = 3^{\log_b(2)}$ $2^{\log_b(3)} = ...
1
vote
0answers
65 views

Proving Reflexivity, Symmetry and Transitivity of a Relation

I'm currently taking an intro discrete math course, and I'm having some trouble understanding the rules of reflexivity, symmetry, and transitivity. The book isn't making a lot of sense to me, and my ...
1
vote
1answer
45 views

Recurrence Fibonacci Sequence Proof

I'm having troubles proving that in a fibonacci sequence if n is divisible by four, then Fn is divisible by three So when Fn is 6, n is 8 and so on. I was thinking maybe I could use mod 3 or mod 4 ...
2
votes
1answer
178 views

Using Induction to prove complete binary trees

Prove a complete binary tree has an odd number of vertices. My attempt at the solution: Basis step: A binary tree with a height of 0 is a single vertex. This would result in the tree having an odd ...
0
votes
1answer
51 views

Finding inverse of $g(x) = \dfrac{3x + 1}{2x + g(x)}$

Find $g^{-1}(3)$ given $g(x) = \dfrac{3x + 1}{2x + g(x)}$ My Approach: \begin{align*} y & = \frac{3x + 1}{2x + y} && \text{(does $g(x)$ become $y$ also?)}\\ x & = \frac{3y + 1}{2y ...
1
vote
3answers
45 views

Set with no elements!?

Consider a set defined on the universe of integers. It contains a large number of subsets. These subsets include the empty set and sets which contain multiple integer elements. However our set does ...
1
vote
5answers
57 views

Remainder when $p$ is divided by $6$

Let $p$ be a prime. If there is a remainder of $1$ on division of $p$ by $3$, then what is the remainder when $p$ is divided by $6$? why? I know the remainder is $1$ in both the cases, but I'm ...
0
votes
2answers
25 views

Proof by induction for a recursive sequence (closed form formula given)

I was given the following: A sequence is defined recursively by a0 = 0, and, for n>=1, an = 5an-1 + 1. Use induction to prove the closed form formula for an is an = (5n - 1) / 4. So far for my ...
1
vote
2answers
51 views

Prove composition of bijections is bijection

Let f : A → B and g : B → C be bijections. Prove that g◦f : A → C is a bijection Can someone show me the steps I should take to solve this problem?
2
votes
0answers
62 views

A Strange Algorithm on Processor [closed]

We have n processes, each with a predetermined start and end time. We want to use the ...
-1
votes
1answer
71 views

Is this question is true? [closed]

The negation of There is an x whose square is equal to 2 is for every x whose square is equal to 2 ???
1
vote
3answers
41 views

Expected number of rolls

A fair m-sided dice is rolled and summed until the sum is at least N. What is the expected number of rolls? In other words what is the number of rolls if we roll a m-sided dice and the sum of rolls ...
2
votes
1answer
34 views

The disease problem

Students are sitting in a n * n grid. There's a disease spreading among them in a particular fashion. At start, there a 'k' students infected(At random). After every time step(equal intervals), the ...
19
votes
2answers
1k views

Understanding this pattern behind the Fibonacci sequence

To be honest, I'm pretty awful at mathematics however, when up till 6AM I do like to do random things throughout the night to keep me occupied. Tonight, I began playing with the Fibonacci sequence in ...
0
votes
2answers
70 views

Explicit Mapping to show that positive even integers and integers divisible by 3 have the same cardinality

So I'm really confused about what this question is asking and how to show it. I've started by trying to map out each set in my head ie. {..-6,-3,0,3,6..} {2,4,6,8..} I've done some research and it ...
1
vote
0answers
24 views

How to prove that a function f(x) is O(g(x)), using the definition (finding C and k)

We say that $f(x)$ is $O(g(x))$ if $$(∃C ∈ \mathbb(R)❘)(∃k ∈ \mathbb(R)❘)(∀x ∈ \mathbb(R)❘)$$ $$(x ≥ k → |f(x)| ≤ C · |g(x)|)$$ In English: We can find $C$ and $k$ so that, once we get past the “small ...
2
votes
1answer
59 views

Prove that the sum of harmonic series 1..n can be expressed as (n+1)H_n -n

Prove by induction that the sum of harmonic series Hn from 1 to n where n is a natural number is as follows. $$ H_n = \sum\limits_{i=1}^n 1/i $$ Prove: $$ \sum\limits_{i=1}^nH_i = (n+1)H_n -n $$ ...
5
votes
3answers
85 views

Arguing the correctness of an alternative, way to count how many bit sequences with exactly n zeroes and k+1 ones are there

I was trying to count how many bit sequences with exactly n zeroes and k+1 ones are there. One obvious reasoning is just by doing $ \binom {k+n+1}{k+1}$, by doing choose. However, I was told that ...
0
votes
0answers
27 views

Simplify iterative logarithm

This is a homework question for my algorithms class and I have no clue how to start simplifying this function. I know log* is the iterative log function. It will equal the number of times you have to ...
1
vote
2answers
18 views

How many strings of five ASCII characters contain the character @ (“at” sign) at least once?

I'm given the question: "How many strings of five ASCII characters contain the character @ (“at” sign) at least once?" Note: There are 128 different ASCII characters. I realized I'd have to use rule ...
1
vote
2answers
49 views

Proving 2 Sets have the same cardinality [duplicate]

Prove (0,1) and [0,1] have the same cardinality. I've seen questions similar to this but I'm still having trouble. I know that for 2 sets to have the same cardinality there must exist a bijection ...
0
votes
0answers
24 views

Number of simple graphs with no vertices of degree 0

Determine the number of graphs with no vertices of degree 0 on a given $n$-element vertex set V. The total number of simple graphs with $n$ vertices is $2^{\binom{n}{2}}$. We want to find the number ...
0
votes
0answers
11 views

Problem with finding max edge weighted subgraph in a complete graph, relative to it's node number

Let's sat that I have a complete, undirected, edge-weighted graph, and that I'm interested in finding the max-weight subgraph with regards to it's vertex set cardinality. Is there a specific name for ...
0
votes
2answers
46 views

Quadratic programming for special equation issues

My problem is how to find $\tau_1$ and $\tau_2$ s.t maximize the objective function is $$E=M-\alpha V$$ subject to $$-0.0062\le\tau_1\le0.499$$ $$-0.479\le\tau_2\le0.0262$$ $$\tau_1+\tau_2\le0.02$$ ...
0
votes
0answers
25 views

Interesting inequality involving sets of points

I have the following result in a paper with no proof provided so I'm trying to construct one and wanted to question the validity of it. Some information in the paper maybe irrelevant to the proof ...
4
votes
3answers
146 views

Prove using a strategy stealing argument that player 1 has a winning strategy in the chomp game

I have no idea what this question is asking or how to prove it mathematically. I realize based on the strategy stealing theory that if player two has a winning stratagy then player one can use the ...
4
votes
1answer
93 views

Discrete math problems

I am a high school student interested in thinking about math. I don't know a lot of high-powered math (I only know up to calculus), instead I focus on discrete topics related to math Olympiads ...
2
votes
2answers
44 views

For all positive real numbers, is $f(x)=\sqrt{x}+x+2$ one to one?

I understand that in order to prove this to be one to one, I need to prove $2$ numbers, $a$ and $b$, in the same set are equal. This is what I did: $$\sqrt{a} + a + 2 = \sqrt{b} + b + 2$$ ...
-3
votes
2answers
47 views

Why when divided by 10 $a^2$ remainder can't equal 2,3 or 7?

Suppose $a \in Z$. Why when $a^2$ is divided by 10, the remainder can't equal 2,3 or 7 ?
-1
votes
1answer
57 views

To prove that an argument is valid with the rules of inference of propositional logic

Use propositional logic to prove that the following argument valid : $$(A→ ¬B) ∧ [D ∨ ¬ (C ∧ ¬B)] ∧ C → (A→D)$$