# Questions tagged [discrete-mathematics]

Questions about discrete mathematics, the study of mathematical structures that are fundamentally discrete rather than continuous.

319 questions
Filter by
Sorted by
Tagged with
18 views

### Proving set of finite languages vs all languages over finite alphabet to be countable / uncountable

I came across following facts: Set of finite languages over a finite alphabet is countable. Set of languages over finite alphabet is uncountable. I believe proof of this will be similar to ...
12 views

### Using a PDA, show that ( x * y ) + x is a valid string

Using a PDA, show that ( x * y ) + x is a valid string. im having trouble with part C
23 views

### $O(k)$ Algorithm to find the first $k$ pairs of Magic numbers $a$ and $b$ such that $\sum_{i=1}^{a-1} i = \sum_{k=a+1}^b k$, with restrictions

Provide an $O(k)$ algorithm to find $k$- magic pairs of positive integers a and b of type signed int where a magic pair is defined as $\sum_{i=1}^{a-1} i = \sum_{k=a+1}^b k$. You can't use the ...
13 views

### Recursive definition character counter

This is my definition for part 1 (in latex form) \begin{alignat*}{2} \text{Base Case }& &&\text{ if } \mathtt{ones}(\varepsilon) = 0 \qquad \mbox{ ($\varepsilon$ is the empty ...
54 views

### Fermat's last theorem: How to (partially) solve by programs

No three distinct positive integers $a, b, c$ can satisfy the equation : $a^n + b^n=c^n$, if $n$ is an integer greater than two. The above statement, known as the Fermat's last theorem is proven ...
38 views

### O(n) external intersection points?

I have a doubt. For a given n (axis-parallel) squares in a plane, where there are Ω(n²) intersection points between the edges of the square, is it possible to have O(n) external intersection points? (...
17 views

### Array manipulation and number theory [closed]

How do I rearrange a given array such that the GCD of all the adjacent elements is always 1?
In the partition problem, the task is to partition $n$ given integers into two subsets $A$ and $B$ with equal sum. This problem is known to be NP-hard, but it becomes easy if the "equal sum" ...