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

2
votes
5answers
68 views

How many $3$ integer subsets have no consecutive integers, where integers are less than $20$?

I have to determine how many integers between $1$ and $20$ are possible if no two consecutive integers are in a set. I've thought it has something to do with a combination of an element $(a,a+2,a+4)$ ...
1
vote
3answers
35 views

Discrete Math logically equivalent?

Show that $$(p \land q) \lor (\lnot p \land \lnot q) \equiv p\leftrightarrow q$$ How would I go about doing this? Do I use a truth table or a more "algebraic" process?
1
vote
0answers
11 views

What to do about Missing values for Multivariate regression analysis

I am required to perform multivariate analysis on all countries in the World bank database regarding digital divide. I am confused becasue when I look at factors such as School enrollment, there are ...
-1
votes
0answers
36 views

State why the following assertions are valid? [on hold]

Please give me some hints how to prove that the following assertions are valid! a) $(\forall x)(\forall y)P(x, y) \Leftrightarrow (\forall y)(\forall x)P(x, y)$ b) $(\exists x)(\forall y)P(x, y) ...
0
votes
1answer
16 views

First order logic expression of “Each finite state automaton has an equivalent push-down automaton”?

Problem is Let fsa and pda be two predicates such that fsa(x) means x is a finite state automaton and pda(y) means that y is a pushdown automaton. Let equivalent be another predicate such ...
3
votes
3answers
935 views

Confusion related to curse of dimensionality in k nearest neighbor

I have this confusion related to curse of dimensionality in k nearest neighbor search. It says that as the number of dimensions are higher I need to cover more space to get the same number of ...
0
votes
2answers
25 views

Switching the order of summations.

Why is the below statement true? $$\sum_{j=0}^{n}\left(-\sum_{t=0}^{k}{{k+1}\choose {t}}j^t(-1)^{k+1-t}\right) = -\sum_{t=0}^{k}{{k+1}\choose {t}}(-1)^{k+1-t}\left(\sum_{j=0}^{n}j^t\right)$$ More ...
0
votes
1answer
473 views

Size K subset sum problem?

I am trying to solve the following problem - I have a set of $n$ elements consisting of objects say from $O_1$ to $O_n$ ($\{O1_,O_2,O_3,........,O_n$}). Each of those elements are mapped to an integer ...
2
votes
1answer
551 views

Find an inverse of $a$ modulo $m$ for each of these pairs of relatively prime integers

How would I find the inverse of a given number $a$ modulo $m$, given that $\gcd(a,m)=1$? a) $a = 2$, $m = 17$ $17 = 2 \cdot 8 + 1$ $2 = 1 \cdot 2 + 0$ $1 = 17 - 8 \cdot 2$ <-How do I know ...
3
votes
1answer
39 views

Let $p \neq \pm 1, 0$ be an integer. Prove that $p$ is prime iff for all $a \in \mathbb Z$, either $p \mid a$ or $(a, p) = 1$.

I'll try in $\to$ direction; Nothing divides the prime $p$ but $\pm1, \pm p$. If $a = \pm p$ or $a = \pm 1$ then $p \mid a$. Assume $p = 2$ . If $a$ is even, then $p \mid a$ and if $a$ is odd, then ...
3
votes
1answer
46 views

Picking K counters out of K buckets containing NK counters, N of each different colour, up to N in each

This is a generalisation of a question that recently came up while solving a TopCoder problem. Suppose we have N blue counters, N red counters, N white counters, and so forth, K colours in total. We ...
-2
votes
1answer
26 views

discrete finite summation of non-linear functions

Does anyone have idea for dealing with the two following series summations $$ \sum_{i=1}^n \dfrac{1}{a+b x_i}=c $$ $$ \sum_{i=1}^n \dfrac{x_i}{a+b x_i}=d $$ I need to find the values of 'a' and ...
1
vote
1answer
28 views

Find a recursive definition for inorder: binary Tree(T) → list(T ) where inorder(T ) is the list of nodes from an inorder traversal of T .

Find a recursive definition for inorder: binary Tree(T) → list(T ) where inorder(T ) is the list of nodes from an inorder traversal of T . I have no idea what this question is even asking me. What ...
4
votes
1answer
267 views

$n$ players of paper scissor rock

Suppose there are $n$ players $(3\leq{n})$ showing Paper, Scissor or Rock simultaneously. If there is no winner then there is no payoff to any player. If there are winners and losers (e.g. $k$ ...
0
votes
1answer
21 views

Say we have a double-decker Lazy Susan with two levels that can be turned independently. If we have n + k dishes in total, how many ways

Say we have a double-decker Lazy Susan with two levels that can be turned independently. If we have n + k dishes in total, how many ways is that solution is correct ???
-1
votes
2answers
37 views
-2
votes
0answers
37 views

In Z_437, calculate 30 circled division 29 [on hold]

I am having trouble with modular division, especially finding inverses. I know the answer is 212, but I was hoping someone could show me how to reach this answer. Other practice problems include (all ...
2
votes
1answer
25 views

Finding the recurrence relation(with square roots) [on hold]

I came across a very peculiar recurrence relation : $\sqrt {T(n)} = \sqrt {T(n-1)} + 2 \sqrt {T(n-2)} $ And Initial Condition $T(0) = T(1)= 1$ Any helps on how to find it
-2
votes
1answer
30 views

basic statistic [on hold]

1) In a class of 32 children, 16 have a skateboard, 12 have a bicycle and 17 have a scooter. 5 of them have a skateboard and a bicycle. 7 of them have a skateboard and a scooter. 4 of them have a ...
0
votes
0answers
26 views

Hanging a painting with nails so that removing any subset of nails from a given collection makes painting fall, and subsets are minimal

So I'm aware of the result that for positive integers $k \leq n$ it's possible to hang a painting with $n$ nails, such that if any $k$ nails are removed then the painting falls, but never when $k-1$ ...
1
vote
4answers
35 views

X and Y be finite sets and f: X->Y be a function.

The option D is the correct option. But, I have a doubt since the inverse of function can exist or cannot exist, how can this option be true. How to approach these questions? Should we assume ...
1
vote
2answers
27 views

Proof - Uniqueness part of unique factorization theorem

The uniqueness part of the unique factorization theorem for integers says that given any integer $n$, if $n=p_1p_2 \ldots p_r=q_1q_2 \ldots q_s$ for some positive integers $r$ and $s$ and prime ...
2
votes
1answer
37 views

Must the number of people at a party who do not know an odd number of other people be even

I have a homework question in my discrete mathematics class as the title shows, I feel the answer is no, but googling this question seem's to contradict my answer. Let me explain: So if they are ...
0
votes
1answer
26 views

Is p|(q|r) is it equivalent to (q and r)

Using De Morgan's laws can I turn $p|(q|r)$ into: $(q \ and \ r)$ or does the and become an or, such as $(q \ or \ r)$ ?
1
vote
0answers
47 views

How to find the eigenvalues numerically

How to find the eigenvalue numerically for this ode $$u''-ku'-\lambda u=0$$ with BCs $u(\pm c)=u(0)$ ? I tried to discretize in space like so: $$x_j=jh$$ $$u''=\frac{u_{j+1}-2u_j+u_{j-1}}{h^2}$$ ...
2
votes
2answers
36 views

How many zero-sum $n$-tuples are there?

The question is extremely short and concise. How many $n$-tuples $X \in \{\, -1,0,1 \,\}^n$ have the zero-sum property $\sum_{x \in X} x = 0$ ? At the moment I have nothing to share of my own since ...
1
vote
2answers
34 views

Statements with multiple quantifiers

Suppose $P(x,y)$ is a predicate whose truth depends on $x$ ($x\in D$) and $y$ ($y\in E$). In the following statement,does the order of assigning values to $x$ and $y$ matter? For example, assign some ...
1
vote
0answers
20 views

Obtain cycles with $a < $ nr. of edges $< b$

I have a chemistry/mathematical problem and I would like to get your opinion. Imagine you are generating a planar, cyclic molecule, with a total $N$ is the number of atoms. By Euler graph theory, the ...
4
votes
4answers
53 views

Prove by contradiction $a,b,c>0$?

Suppose $a,b,c$ are real numbers such that $a+b+c>0$, $ab+bc+ca>0$, and $abc>0$. Prove by contradiction that $a,b,c>0$. I have tried to solving it case by case like: case $1$: ...
2
votes
1answer
25 views

Count the number of strings of length 8 over A = {w, x, y, z} that begins with either w or y and have at least one x

Count the number of strings of length $8$ over $A = \{w, x, y, z\}$ that begins with either $w$ or $y$ and have at least one $x$ So here is what I came up with..Can someone check my work? $A = ...
-1
votes
1answer
35 views

Use induction to prove the following equation: $2 + 6 + 10 + \cdots + (4n − 2) = 2n^2$ where $n \ge 1$ [on hold]

Use induction to prove the following equation: $2 + 6 + 10 + \cdots + (4n − 2) = 2n^2$ where $n \ge 1$
0
votes
2answers
32 views

Let f : N9 → N9 be defined by f(x) = (5x + 3) mod 9. Find f −1 if it exists. [on hold]

Let $f : N/9 → N/9$ be defined by $f(x) = (5x + 3) \bmod 9$. Find $f^{−1}$ if it exists.
0
votes
1answer
11 views

DNF or CNF functions

The problem tells us to find the full DNF and CNF of the logic function $f(P, Q, R)$ = True if and only if either Q is True or R is False. I feel fine with converting to get the full DNF or CNF form, ...
14
votes
13answers
3k views

Show that from a group of seven people whose (integer) ages add up to 332 one can select three people with the total age at least 142. [closed]

I need help with this problem, and I was thinking in this way: $$ x_{1} + x_{2} + x_{3} + x_{4} + x_{5} + x_{6} + x_{7} = 332 $$ and I need to find three of these which sum is at least 142. But I ...
13
votes
5answers
2k views

How is an empty set truly “empty”?

In a related question, an answerer says: an empty bag is a bag with nothing inside it. Makes sense, but I'm reading a textbook right now that says: The empty set has only one subset (namely, ...
7
votes
4answers
12k views

How many distinct functions can be defined from set A to B?

In my discrete mathematics class our notes say that between set A (having 6 elements) and set b (having 8 elements), there are $8^6$ distinct functions that can be formed, in other words: $|b|^{|a|}$ ...
-1
votes
0answers
21 views

Discrete mathematics combinations with repetition?? [on hold]

A bagel shop has onion bagels, poppy seed bagels, egg bagels, salty bagels, pumpernickel bagels, sesame seed bagels, raisin bagels, and plain bagels. How many ways are there to choose a) six bagels? ...
-1
votes
1answer
25 views

Adding two variables with subscripts [on hold]

What is the explanation to why $x_{3k} + x_{3k+1}$, is equal to $x_{3k+2}$. Isn't that incorrect because there is no value 1 in the subscript $x_{3k}$? I saw this in a prove in ...
1
vote
2answers
43 views

Find $a_i, b_i$ such that they are all distinct

Very tough, I spent at least an hour, not solving this! From the set of integers $ \{1,2,3,\ldots,2009\}$, choose $ k$ pairs $ \{a_i,b_i\}$ with $ a_i<b_i$ so that no two pairs have a common ...
2
votes
2answers
53 views

Prove or disprove: If the positive integer m divides the positive integer n, then the Fibonacci number $f_{m}$ divides $f_{n}$

I have $f_{n}=f_{n-1}+f_{n-2}; f_{n}= [0,1,1,2,3,5,8,13,21,34,55,89,144,233,...]$ for which I note that indeed, 2 divides 4, and $f_{2}$ divides $f_{4}$. I am wondering if a proof by induction is ...
15
votes
1answer
1k views

True or false: {{∅}} ⊂ {∅,{∅}}

Note: Actually there's no error in the book and the manual. I actually misread it. The answer is of a different question : True or False: {0} ⊂ {0} This question is from Discrete Math Book by Rosen. ...
-2
votes
2answers
29 views

What are good techniques for creating a DFA state diagram given a set of accepted/rejected strings?

I am in a Discrete Structures class and my teacher is pretty big on proving his intellect to the class and getting an average of about 60% for his test questions. Right now we are working with ...
0
votes
2answers
28 views

5-Card Poker Two-Pair Probability Calculation

Question: What is the probability that 5 cards dealt from a deck of 52 (without replacement) contain exactly two distinct pairs (meaning no full house)? Solution: ...
0
votes
1answer
40 views

Writing regular expressions

So here's the problem: Let $Σ =\{a, b, c\}$. Write a regular expression for the set of all strings in $Σ^∗$ such that the sum of the number of $a$’s and $b$’s in the string is at most two. Thus the ...
2
votes
3answers
54 views

Mathematical induction: using 3 cent and 7 cent stamps

Use mathematical induction (and proof by division into cases) to show that any postage of at least 12 cents can be obtained using 3 cent and 7 cent stamps. I thought this was the simple kind of ...
0
votes
1answer
25 views

Name for $f(a,b) = c/d$

What is the a name for functions of the form $f(a_1/b_1,\ldots,a_n/b_n) = c/d$ where $a_1,\ldots,a_n,b_1,\ldots,b_n,c,d \in Z$ and all the denominators are not zero. I was thinking about calling ...
1
vote
2answers
41 views

How to find the amount of binary digits in a decimal number?

This seems like such a simple question but I can't seem to come up with an answer. I know the formula for the number of digits of $2^n$ is $1+[nlog(2)]$. So the amount of decimal digits of $2^{100}$ ...
2
votes
3answers
94 views

If $\gcd(ab,c)=d$ and $c|ab$ then $c=d$

For all positive integers $a$, $b$, $c$ and $d$, if $\gcd(ab, c) = d$ and $c | ab$, then $c = d$. Need help proving this question, I know that $abx + cy = d$ for integers $x,y$ and that $c|ab$ can be ...
1
vote
2answers
44 views

Subset vs. Proper subset

I'm a bit confused on the wording here.. For example: $$A = \{c, d, f, g\}$$ $$C = \{d, g\}$$ Is $C$ "subset" of $A$? Obviously, yes. But.. the proper subset states that: If $C$ and $A$ are any ...
1
vote
1answer
28 views

interpreting words as if-then statements

In my book it is stated the $P \rightarrow Q$ is used to interpret $P$ only if $Q$. So, in the statement "$x$ divides 4 only if $x$ divides 8" should the symbolic form not be $P: x \text{ divides ...