Discrete mathematics is the study of mathematical structures that are fundamentally discrete rather than continuous.

learn more… | top users | synonyms

0
votes
0answers
2 views

perfect square/# divisors problem

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$ ...
0
votes
0answers
17 views

Block design: derived designs

I am now study some theorems of block design. I have a question about the derived designs. Let $B$ be the oringinal design $t-(v,k, \lambda)$. Suppose we omit one of the points, say $P$, then we have ...
2
votes
1answer
41 views

Bijection between $N^3$ and $N$ [on hold]

How can we say that there exists a bijection between $N^3$ and $N$. Kindly give me a detailed solution. How can we say that $N^3$ is countably infinite?
1
vote
1answer
15 views

How many boolean functions $F(x, y, z)$

Question:How many boolean functions $F(x, y, z)$ are there so that $F(\bar{x}, y, z) = F(x, \bar{y}, z) = F(x, y, \bar{z})$ for all values of the Boolean variables $x, y,$ and $z$? I'm at loss on ...
3
votes
2answers
37 views

A sum of difference of floors

I have the sum ( $M$ is any integer $> 1$ ): $$ \sum_{h = 1}^{M}\left(\,\left\lfloor\, 2M + 1 \over h\,\right\rfloor -\left\lfloor\, 2M \over h\,\right\rfloor\,\right) $$ and looking for a way to ...
1
vote
1answer
59 views

prime division problem

$a,b,c \in$ {0,1,2,...,9} with at least one of $a,b,c$ nonzero. Prove that the six-digit integer $abcabc$ is divisible by at least 3 distinct primes. My thinking is not to use induction as there is ...
1
vote
1answer
30 views

Laws of equivalence needed to prove $\;q \leftrightarrow (¬p ∨ ¬q) ≡ (¬p ∧ q)\;?$

I'm not sure which laws should be applied and how I can tell for myself how to discern which laws I should use - any and all help is appreciated.
0
votes
0answers
7 views

Histogram Separation Energy Equation

I am working in level set method, specially Lankton method paper. I try to implement Histogram Separation (HS) Energy problem (Part III.C). It based on Bhattacharyya to control the evolution of ...
0
votes
0answers
48 views

Prove that $f: \Bbb R \setminus \{2 \} \to \Bbb R \setminus \{3 \}$ is bijective

I wanna know how can I have a formal proof for this one $$f: \Bbb R \setminus \{2 \} \to \Bbb R \setminus \{3 \}.$$ I understand that for functions like this $f(x)=2x+1$. I can know if its is ...
3
votes
0answers
30 views

A probability of a monochromatic cycle on a randomly colored lattice graph.

Let $G$ be an undirected $6 \times 6$ lattice graph. The $36$ vertices of $G$ are each randomly colored with one of $5$ colors with equal probability. Such a coloring is called "successful" if and ...
0
votes
0answers
13 views

discrete-time vs. continuous-time energy

Could any one please explain why the energy of a continuous pulse shape is larger than its discrete-time samples by a factor of bit period $T$? Thank you, Elnaz
0
votes
1answer
11 views

How many ways between 2000 and 5000 can be written from the digits 2,3,4,5,7 if: a. no digit is repeated b. digits must be repeated?

How many ways between 2000 and 5000 can be written from the digits 2,3,4,5,7if: a. no digit is repeated b. digits must be repeated?
1
vote
3answers
81 views

Finding the sum of $3+4\cdot 3+4^2\cdot 3+\dots +4^{\log n-1} \cdot 3$

I see this: $$A=3+4\cdot 3+4^2\cdot 3+\dots +4^{\log n-1} \cdot 3=3\cdot ([4^{\log n}-1]/3)=n^2-1$$ The base of logarithm is $2$, and $n$ is $2,4,8,\dots$ Anyone could describe me how this sum was ...
1
vote
3answers
76 views

Number of images from $\mathbb{N}$ to {0, 1}.

Are the number of images from $\mathbb{N}$ to {0, 1} countably infinite or uncountably infinite? I was thinking of counting in base 2 to make a bijection between $\mathbb{N}$ and {0, 1}. So, a ...
0
votes
0answers
50 views

Writing probability as log

I have a question regarding the log probability and I am confused on this. The question is: $$\hat P^{(t)}(x)=\sum_{i=1}^N v_i^{(t)}P_i^{(t)}(x)$$ which is some function of size $N$. The question ...
1
vote
0answers
40 views

Least power of $x$ so that $y$ divides $x$

How do I find the least $z$ to satisfy, $$y \mid x^z$$ I have tried keep dividing $y$ with the GCD($x$,$y$) until $y \mid x$ and adding $z$ by $1$ (starting from $1$), but turns out it's too slow.
0
votes
0answers
22 views

Prove identity involving alternating groups

Prove the following identity: where $I_{A_n}(x_1,...,x_n)$ is a cyclic index the natural action of the alternating group $A_n$ on the set ${1,...,N}$ (assuming that $I_{A_0} = 1$).
0
votes
2answers
30 views

Prove that $G$ is Hamiltonian.

Let $G=(V,E)$ be a connected graph which is not a tree. Prove that if for every cycle $C$ of the graph G and for any $v \in V(G)- V(C)$ there are more than $\frac{|C|}{2}$ edges from $v$ to $V(C)$ ...
1
vote
1answer
26 views

Discretization of an integral

Given $f: [a,b] \to R $ and $K: [a,b]$ x $[a,b]$ $\to R$, we want to find a solution $\varphi:[a,b] \to R $ to the Fredholm integral equation: $$\varphi(x) = f(x)+\int _{ a }^{ b }{ K( x,t)\varphi ...
0
votes
0answers
18 views

Represent this differential equation as a set of n+1 equations w n+1 unknowns

Given the following differential equation: $$s''w'' + 2s'w''' + sw'''' = q$$ We use these approximations: $$w''''(x_i) \approx \frac { { w }_{ i+2 }-4{ w }_{ i+1 }+6{ w }_{ i }-4{ w }_{ i-1 }+{ w ...
1
vote
1answer
42 views

Divisibility problem ($p \leq \sqrt{n}$)

If $n \geq 2$ and $n$ is composite, then there exists a prime $p$ such that that $p \mid n$ and $p \leq \sqrt{n}$ As $n$ is composite, it follows that $n = ab$ for some $a, b \in \Bbb N$, where ...
0
votes
2answers
51 views

What does let $F$ denote the set of all functions from $\{1, 2, 3\}$ to $\{1, 2, 3\}$ mean?

Let $F$ denote the set of all functions from $\{1, 2, 3\}$ to $\{1, 2, 3\}$. I'm supposed to prove that this statement is true or false, $$∀f ∈ F, \;∃g ∈ F\tag i$$ so that $g(f(1)) = 2$ But I'm not ...
-3
votes
0answers
33 views

graph problem homework helps [closed]

1) Prove that if all edge-costs are different, then there is only one cheapest tree. (Hint: Do a proof by contradiction, following the proof of Kruskal’s theorem. Make sure to keep track of the costs ...
-1
votes
1answer
45 views

The union of two connected graphs is connected [closed]

Let $G = (V,E)$ be a graph and let $H_1 = (V_1,E_1)$ and $H_2 = (V_2,E_2)$ be two connected subgraphs of $G$ that have at least one node in common. Prove that the graph $H = H_1\cup H_2 = (V_1\cup ...
2
votes
1answer
26 views

Is this relation symmetric

$R = \{(X, Y) \in \mathscr{P}(A)^2| X \subset Y \text{ and }X \neq Y \}$ I know that $(X,Y) \in R$ holds true since $X \subset Y$. However I'm unsure if $(Y,X) \in R$ since if $Y \subset X$ then ...
1
vote
1answer
52 views

Is the subset relation on the powerset of a set, with qualification, reflexive?

I was wondering if the subset relation is reflexive? $R = \{(X, Y ) \in P(A)^2\mid X\subseteq Y \text{ and } X \neq Y \}$ I assumed they it was reflexive since for all $X \in P(A), X \subseteq X$ is ...
0
votes
1answer
44 views

fundamental theorem of arithmetic problem

Change machine contains n quarters, 2n nickels, 4n dimes, n positive integer. Find all values of n so that these coins total k dollars, k positive integer. My thinking is to reduce coins to prime ...
5
votes
3answers
152 views

How many ways can 5 dice produce a total of 20?

How many ways can $5$ dice produce a total of $20$? I set up the equation $x_1+x_2+x_3+x_4+x_5 = 20$. The total possible number of combinations is $\binom{19}4$. From there I subtracted the ...
0
votes
1answer
31 views

Translating to English: $\forall x ¬(\forall y P(x, y)) \rightarrow \forall x \forall y ¬P(x, y)$

$$\forall x ¬(\forall y P(x, y)) \rightarrow \forall x \forall y ¬P(x, y)$$ I'm trying to intuitively understand this idea by thinking about it in terms of English. The second half is easy. Where P ...
0
votes
0answers
30 views

Properties of R, R^n, R*

I was talking to a friend who mentioned that eventually, R^n and R* are equivalent. This confuses me because I don't see how it's necessarily the case. But it does seem to hold, for instance: R = ...
2
votes
2answers
88 views

ZFC and apples described using only fundamental axioms (complete expanded reasoning)

Let's assume that I'm adding two numbers representing my count of objects I perceive (lets say a green and a blue apple that are consider to be of the same class) and I see them as a set of two apples ...
2
votes
2answers
69 views

Sum of floor of ratios

I need to compute, in a program at work, the sum, for $k = 2$ to $n-1$, of the floors of the ratios: $\frac{n}{k}$. Since n is a large integer in my case I would need a "closed form" formula for this ...
0
votes
0answers
73 views

A new combinatorics identity— similar to Catalan number

I find a combinatorics identity during my study, but fail to prove it.$$\sum_{i=0}^{[M/2]}(-1)^i\frac{(3M-1-2i)!}{(M-2i)!i!(2M-i)!} = \frac{1}{2M}\big(_{M}^{2M}\big)$$ where $M=1,2,3\cdots$. Note than ...
0
votes
2answers
159 views

Help showing that every walk of length $k$ from $x$ to $y$ in a graph is a path.

If I were to suppose $x$ and $y$ are two vertices in the same connected component of a graph, and let $k$ be the distance between them, how would I prove that every walk of length $k$ from $x$ to $y$ ...
1
vote
1answer
29 views

Let R be the relation on ℤ+→ℤ+ defined by (a,b)R(c,d) if and only if a-2d=c-2b. List all the elements of the equivalence class [(3,3)].

I'm confused on how to find all the elements. I know how to find some but not all, wouldn't they be infinite? This is affecting me with the other questions as well. Thanks in advance!
3
votes
0answers
35 views

Is it possible to find plaintext from ciphertext if (n) and (a) are known?

I have a couple of questions pertaining to a RSA problem. I need to decipher some ciphertext and find out what the original plaintext was. n = 2537 and a (or the exponent) = 11. Encrypting function: ...
0
votes
1answer
71 views

Discrete Math Clause Count Question

Ok, I'm completely lost if anyone could hint me through some of the first steps that would be hugely appreciative!! In a CNF formula, a clause contains one or more terms. Each term is either a ...
0
votes
2answers
49 views

Number theory divisibility - simple way to prove this is prime?

Suppose that $y$ is a positive integer, and $z$ is the largest factor of $y$ such that $z<y$, then let $x=y/z$. Prove that $x$ must be a prime number. Is there a simple way to solve this? It ...
0
votes
2answers
50 views

Mathematical Induction - Inequality

Does anyone have any idea on how to complete the inductive step? Thm: For all $n >= 0~~~~ 6^n + 4 > n^3$ Pf: by Induction     Let $P(n)$ be proposition that $~6^n + 4 ...
1
vote
1answer
32 views

Complex automata Rubiks cube question (with picture) help needed

Question 1 A Rubik’s Cube is a puzzle in the shape of a cube. Each face is covered by nine stickers, each of which is coloured with one of six colours: white, red, blue, orange, green, andyellow. An ...
0
votes
1answer
36 views

Width and height of binary tree is $\theta(n)$?

we know this definition: Given a binary tree, Width of a tree is maximum of widths of all levels. Let us consider the below example tree. ...
3
votes
3answers
109 views

How to prove that $4^m + 5^m$ is divisible by 9 when m is an odd number [duplicate]

I am trying to use congruence theorems, specifically Euler's Theorem for a proof.
0
votes
5answers
36 views

Injective function proof involving floor function

Let $f : \Bbb{Z} \to \Bbb{Z}$ and $g : \Bbb{Z} \to \Bbb{Z}$ be functions defined by $f(x)=3x+1$ and $g(x)=\lfloor\frac{x}{2}\rfloor$. Is $g(f(x))$ one-to-one? So, $g(f(x)) = ...
0
votes
1answer
21 views

trouble understanding subsets and well ordered subsets

I need to understand what a subset is and would appreciate examples to develop intuition. I understand that a subset is a mini-set of the members of a container set. I'm working on problems related to ...
3
votes
1answer
33 views

Is there a specific name for a directed graph that is composed of only loops?

Recently I have been doing practice questions for my Final exam tomorrow and this one question appeared that was interesting, but I couldn't seem to find the other half of the answer to it. Q: Given ...
2
votes
2answers
65 views

prove that any integer greater than or equal to 8 can be represented as the sum of nonnegative integer multiples of 3 and 5

This problem asks to use Well Ordering Principle to prove any integer greater than or equal to 8 can be represented as the sum of nonnegative integer multiples of 3 and 5. Here's where I'm at: For ...
3
votes
2answers
70 views

prove/verify prime division

$a_i$ positive integers for $1\le i\le n$ if $p$ prime and $p\mid a_1a_2\cdots a_n$ then $p\mid a_i$ for some $1\le i\le n$: My thinking is to prove it by contraposition. $p$ does not divide ...
2
votes
2answers
39 views

Proof: no fractions that can't be written in lowest term with Well Ordering Principle

My question is the exact same question as the one in this post but I commented on it but it's from a year ago so I just wanted to bump it and see if I could get a response: Prove that there's no ...
2
votes
3answers
99 views

Double summation index problem

I often meet the following situation: $$\sum\limits_{n=0} ^\infty \sum\limits_{k=0} ^n f(k)g(n-k)=\sum\limits_{p=0} ^\infty \sum\limits_{q=0}^\infty f(p)g(q)$$ While intuitively this is very clear ...
1
vote
2answers
67 views

nth convolved Fibonacci numbers of order 6 modulo m

Problem: Find the coefficient of xk in (1−x−x2)-6 modulo m. Constraints: k≤264 m≤105, m can be a composite number. I have 10^5 such queries to process in 2 sec, so O(log k) for each query ...