# 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.

28,655 questions
Filter by
Sorted by
Tagged with
0answers
14 views

### Use the index calculus with factor base {2, 3} to solve $3^x \equiv 11 \pmod{37}$

I know the answer is x = 15 but I don't know how to reach that conclusion using index calculus. Please any help is greatly appreciated.
0answers
19 views

### Finding the set of all equivalence classes for $\mathbb Z\times \mathbb Z$ on a relation

Consider the following relation $R$ on $\mathbb Z\times \mathbb Z$, $(x,y)R(z,w)$ if $2\mid (x-z)$ and $2|(y-w)$. Prove $R$ is an equivalence class and find $(\mathbb Z\times \mathbb Z)/R$. I am so ...
0answers
14 views

### Maximal number of edges

Given a simple graph on 15 vertices consists of several (more than one) isomorphic connected components. What is the maximal possible number of edges in this graph? I tried by using the bipartite ...
1answer
10 views

### Logarithmic functions complex

Are logarithmic functions not defined for negative real numbers? Since either part of a complex number (real and imaginary) can be 0 then isn't the above statement false and hence they are defined for ...
0answers
21 views

1answer
29 views

### If $B \subsetneq A$ and $f : A \rightarrow B$ is injective, then $f[B] \subsetneq B$

Problem: Let $A,B$ be sets such that if $B \subsetneq A$ and $f : A \rightarrow B$ is injective, then $f[B] \subsetneq B$. Attempt: Suppose $B \subsetneq A$ and $f \in A \rightarrow B$ is ...
2answers
50 views

3answers
51 views

1answer
38 views

### Sets having the same cardinality

I am asked to think of an example of cardinality being the same between two sets X and Y such that the function from X to Y is one to one but it is not onto. I am so confused about this one because I ...
3answers
56 views

### If $w$, $x$, $y$, and $z$ are real numbers with $w < x$ and $y < z$, is the cardinality of the closed interval $[w,x]$ the same as that of $[y,z]$? [duplicate]

My reasoning is yes. I tried to draw a few example functions and based on my workings, think that the answer should be yes but I couldn't figure out how exactly I should mathematically prove the fact. ...
0answers
29 views

### Probability of choosing the same letter

Suppose you are choosing a letter at random from the word DISCRETE and your friend chooses a letter at random from the word ALGEBRA. What is the probability that you choose the same letter? This is my ...
1answer
39 views

### How to prove that for all odd $n \in \mathbb{N}$ can be displayed as the difference of two square numbers?

I need guidance / correction for my proof. It's a little bit longer, but we really have to consider everything. If you find some issues / mistakes or have suggestions to improve it, please let me know!...
1answer
79 views

### What does $[n=1]$ mean?

Studying recurrence relations I stumbled upon this expression in a solution to the problem of finding a closed formula to this: $a_n = 5a_{n-1} - 6a_{n-2}; a_0 = 0, a_1 = 1$ To start the solution, the ...
1answer
33 views

### In an $8\times 8$ square, what's the min number of dots to be placed so that there's always a pair with distance apart at most $\sqrt8$?

By the Pigeon Hole Principle (PHP), we know that when we are to place $17$ dots in an $8 \times 8$ square, then there will always be a pair with distance $< \sqrt8$. However, does PHP actually ...
1answer
21 views

### count equivalence relations on a set with 6 members including and excluding certain pairs

I want to count the equivalence relations on the set ${\{1,2,3,4,5,6}\}$ with the conditions that the relation includes the tuples ${(1,2)}$ and ${(2,3)}$ but it does not include the tuple ${(3,4)}$ I ...
0answers
5 views

### Define several atomic formulas to determine whether a graph is a Hamiltonian graph

how to define several atomic formulas to determine whether a graph is a Hamiltonian graph? It seems that Hamiltonian graph is a very hard problem. I know that a graph is a Hamiltonian graph if the sum ...