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

learn more… | top users | synonyms

2
votes
1answer
42 views

Proof Verification for Discrete Math Class

Prove that $n^2$ is even iff $n$ is even. I proved it like this: Case I: $n$ is even 1) $n = 2a$ $(a\in Z)$ 2) $n^2 = 4a^2 = 2(2a^2)$ 3) $2a^2 = K$ $(K \in Z)$ 4) $n^2 = 2K$ Case II: $n$ is ...
1
vote
1answer
43 views

Meaning of the characteristic polynomial of a matroid

From wikipedia The characteristic polynomial of a matroid $M$ (which is sometimes called the chromatic polynomial,[29] although it does not count colorings), is defined to be $$ p_M(\lambda) ...
1
vote
1answer
34 views

Mathematical induction of the harmonics number

My textbook has the steps to prove it, but I can't comprehend the steps that the textbook are showing. Can someone explain the math or logic used going from steps red to yellow and finally green?
9
votes
1answer
88 views

How many Sudoku puzzles are there with at least one solution?

A Sudoku puzzle is a 9 by 9 matrix of blanks(which we can represent as 0), and elements of the set {1,2,3,4,5,6,7,8,9}. How many Sudoku puzzles are there with at least one solution. Yes, I am even ...
0
votes
0answers
61 views

TAUTOLOGIES NP-Complete Condition

The decision problem TAUTOLOGIES is, Given $\forall x_1 \forall x_2 ... \forall x_n$ $\phi(x_1, x_2, ... x_n)$ a set of universally quantified Boolean variables and a Boolean formula ...
2
votes
2answers
41 views

What are a geometric system and a finite geometry?

Wikipedia says A finite geometry is any geometric system that has only a finite number of points. I wonder what a geometric system is? Is it some set system $(E, F)$, where $E$ is a set and $F ...
0
votes
2answers
72 views

prenex normal equivalence challenges in math

consider these two following formula are prenex normal equivalence with the above formula? i think yes, but didn't have any idea to explain it.
0
votes
1answer
44 views

Logic Pure Subset Problem

for example if we define : $$ \$(p,q,r) = (p\to q)\land(\neg p\to r)$$ how we can inference that set $\{\$,\top,\bot\}$ is Full Functional and not any pure subset of this be full functional.
1
vote
1answer
38 views

Initial value of Newton Raphson Method

I am currently studying Newton-Raphson Method. I feel that I understand the concept of it. Somehow, I am facing some question in my head about how to actually apply it. The questions that I have are ...
0
votes
3answers
43 views

How do I finish this summations problem?

I have posted a picture since I don't know how to make the summation symbols with the lower and upper summations on keyboard, sorry about that.. $$\sum_{a=1}^9\sum_{b=0}^9(101a+10b)$$ The answer is ...
0
votes
1answer
122 views

Logic challenge in math

i get stuck in logic problem. suppose $L=\{P,Q\}$ which $P$ and $Q$ are one-place predicate. if $A$ is a set with three element. how many way we can convert $A$ into a Structure for $L$ that ...
0
votes
1answer
38 views

How to test mathematically if a number contains the highest digit of its radix?

Is there a way to test mathematically if a number contains the highest digit of its radix, and if so how? For example, 101 in base 2 contains the digit 1, highest in base 2; but 101 in base 3 does ...
2
votes
6answers
247 views

Discrete math induction problem.

I am stuck at this step in the inductive process and I was wondering if someone can help me out from where I am stuck. Question: if $n$ is a positive integer, prove that, ...
0
votes
3answers
38 views

Giving an equivalence relation that corresponds to set partitions

My question is: Give equivalence relation that corresponds to the partitions A1 = {1,3,5} A2 = {2} A3 = {4,6} of the set A = {1,2,3,4,5,6} I don't know what the format of the relation should be, in ...
7
votes
5answers
171 views

Does $\{1,2,\ldots,3000\}$ contain a subset of $2000$ integers with no member twice another?

Does the set $X=\{1,2,\ldots,3000\}$ contain a subset $A$ of $2000$ integers in which no member of $A$ is twice another member of $A$? I started by putting $P=[1501,3000]$, but twice any integer in ...
1
vote
2answers
55 views

Factor $n=59305397$ given that $ p-q \le 10 $

So what is given is that $n=pq\ ; \ p-q = \sqrt{(p+q)^2 -4n}$ Rearranging the $p-q$ equation, I get $$ p+q = \sqrt{(p-q)^2 +4n}$$ So, $$2p = (p+q) + (p-q) \ \text{and} \ q=\cfrac{n}{p}$$ However ...
2
votes
2answers
77 views

Combination small challenge problem

How many ways can 3 different Scientific Groups be formed using 5 students such that Each student is at least be a member of one committee and each two committee has exactly 2 students in common? I ...
0
votes
3answers
99 views

Proof for Concrete Mathematics 3.24

I'm reading Concrete Mathematics by Graham, Knuth, Patashnik . I found that for every integer $n$, this holds : $$n = \lceil n/m \rceil + \lceil (n-1)/m \rceil + \cdots + \lceil (n-m+1)/m \rceil$$ I ...
1
vote
1answer
28 views

Find how many People Like dancing Only,People Like Movies

A survey was conducted among 402 persons regarding their interest in movies,dancing and games it was found that (i) 100 People Like games. (ii) 142 People Like movies or dancing but not games. (iii) ...
0
votes
1answer
26 views

Define a numeric relation that is reflexive, but not symmetric or transitive.

Define a numeric relation that is reflexive, but not symmetric or transitive. I've googled on this one quite a bit and am stuck.
1
vote
1answer
26 views

chinese remainder theorem constructive proof

I am trying to understand CRT constructive proof from wikipedia [http://en.wikipedia.org/wiki/Chinese_remainder_theorem#A_constructive_algorithm_to_find_the_solution] I am unable to follow it from ...
1
vote
1answer
31 views

Probability of a certain result obtaioned by throwing an octahedron

Assume having a fair octahedron. We throw it $93$ times and get the following results: $\{33;7;8;1;2;0;5;37\}$ The numbers represent how many times the die fell on side $1, 2,...., 8$. What is the ...
0
votes
0answers
42 views

which of the following sets are nonempty?

Problem: $$\left\{x\,|\,x\in\mathbb{N},\,2x+7=3\right\}$$ Steps I took to solve it: $$\begin{array}{c} 2x + 7 = 3 \\ 2x = 3 - 7 \\ x = - 2 \end{array}$$ Hence, it is an empty set (not nonempty), but ...
-3
votes
0answers
49 views

Every polynomial of degree $\geq 1$ in $F[x]$ , $F$ a field, is irreducible or factors into a product of irreducible polynomials.

I am trying to prove the following: Every polynomial of degree $n\geq 1$ in $F[x]$, $F$ a field, is irreducible or factors into a product of irreducible polynomials. I don't understand fields ...
1
vote
2answers
40 views

Equality of two sets written differently

$$A = \{2m+ 1:m \text{ exists in } \mathbb{Z}\}$$ $$B= \{2n + 3:n \text{ exists in } \mathbb{Z}\}$$ For this question, it seems that $A=B$, and we know it's equal because we can just plug in numbers ...
0
votes
2answers
40 views

What is the difference between these empty set questions?

a) Ø ⊂ Ø False b) Ø ⊂ {Ø} True c)Ø ⊆ Ø True d)Ø ⊆ {Ø} True I am particularly confused with the difference of having {} and not having the braces because it seems that the braces make "b" true ...
0
votes
1answer
21 views

Check these recursive definitions for me?

Looking for Give a recursive definition of A) the set of odd positive integers B) the set of positive integer powers of 3 C) the set of polynomials with integer coefficients I have a. Basis: ...
3
votes
1answer
67 views

Determine Units of a Ring $\mathbb{Z}[\alpha]$

I am trying to determine the units of $Z[\alpha]$ where $\alpha$ satisfies the monic polynomial $\alpha^4+\alpha^3+\alpha^2+\alpha+1$. I found $Z[\alpha] := \lbrace a+b\alpha+c\alpha^2+d\alpha^3\;|\; ...
0
votes
2answers
44 views

Induction inequality check

check my proof, I feel like I made a mistake :) so I'm looking to prove that when $p(n)$ is $n!<n^n$, $p(n)$ is true for all $n>1$. Base Case $$ p(2) \iff 2!<2^2 \iff 2<4 $$ Assume p(k) ...
4
votes
1answer
196 views

What is the difference between these two subsets in Discrete Math?

Let $U = \{1, 2, 3, 4, 5, 6, x, y, \{1, 2\}, \{1, 2, 3, 4\}, \{1, 2, 3\}\}$ $A = \{1, 2, 3, 4\}$ Can anyone explain to me the difference between these 2 pairs of things? $$A\subseteq U \text{ and } ...
1
vote
1answer
52 views

Book for learning mathematics [closed]

I want a book that teaches me mathematics,not just problem solving methods.I want to study mathematics.I want different graphs,the movements of different functions in mathematics.the basics of a ...
2
votes
3answers
58 views

Basic induction proof methods

so we're looking to prove $P(n)$ that $$1^2+2^3+\cdots+n^3 = (n(n+1)/2)^2$$ I know the basis step for $p(1)$ holds. We're going to assume $P(k)$ $$1^3+2^3+\cdots+k^3=(k(k+1)/2)^2$$ And we're ...
2
votes
2answers
56 views

Equivalent definitions for a coloop?

From wikipedia, in a matroid, An element that belongs to no circuit is called a coloop. Equivalently, an element is a coloop if it belongs to every basis. I wonder why the equivalence? From ...
2
votes
1answer
23 views

Minimum score for winner and maximum score for loser in a round-robin tournament.

I have just correctly solved this programming problem. The problem is the following: $N$ teams play a round-robin tournament, i.e. each pair of teams plays exactly one game and the winner gets 3 ...
1
vote
1answer
20 views

Get days on basis of Sum of values of

Lets suppose i have list of days : Sun - 1 Mon - 2 Tue - 4 Wed - 8 Thu - 16 Fri - 32 Sat - 64 Now user can select one or more then one from checklist .My database just storing the sum of days ...
0
votes
1answer
17 views

How do the dependent sets of a matroid characterize the matroid?

Wikipedia says: The dependent sets of a matroid characterize the matroid completely. The collection of dependent sets has simple properties that may be taken as axioms for a matroid. So I ...
1
vote
0answers
28 views

Name for variations of elements from several sets

Consider the set $S=\{1,2,3\}$. As is well known, $(1,1), (1,2), (1,3), (2,1), (2,3), \ldots, (3,3)$ are the variations with repetition of elements of $S$ taken two at a time. We can similarly ...
0
votes
0answers
43 views

Verification of a Combinatorial Identity

I was given a question and would like to see if I made any errors in my answer. The Question: My Answer: I noticed the following identity is very useful here: $\dbinom{n+1}{r}$ = $\dbinom{n}{r}$ ...
1
vote
1answer
36 views

Rules of inference: The Rules of Disjunctive Syllogism and Double Negation

I have a question about the use of Double Negation in relation to this problem I found in my textbook examples. Problem: $\;¬(r \land t) \lor u$ $\;r \land t$ Therefore, $u$. In my textbook it ...
0
votes
1answer
24 views

Change of variables in function $T(n)$.

I've been given this recurrence to solve: $T(n) = T(\sqrt n) + \theta(lglgn)$ And I'm told that the way to solve it is to let $m = lgn$, so that the recurrence can be rewritten as follows: $S(m) = ...
0
votes
3answers
98 views

Find the problem with this proof.

The following attempts to prove that if $n^2$ is even, then $n$ is even. Suppose $n^2$ is even. Then $n^2$ = 2$k$ for some integer $k$. Let $n$ = 2$m$ for some integer $m$. This shows that $n$ is ...
1
vote
3answers
28 views

Using set theory to count the possible paths on an XY plane

I'm taking an introductory discrete math course, and we're studying set theory. It's going okay, but I read an example problem which gave me some difficulty. I've included a screenshot of the problem. ...
0
votes
1answer
26 views

Transition probabilities in a finite state machine

Assume I have a finite state machine and a bunch of tokens. Transitions happen every time a token is inserted. Transitions are based on the token (i.e. at state S, inserting a blue token would give a ...
1
vote
1answer
25 views

What kind of set system is defined to have this property?

Let $E$ be a set, and $F \in \mathcal P(E)$ has the following property: For every $x\in E$ and $Y,Z\in F$ with $x\notin Y\cup Z$, there exists $X\in F$ with $(Y\cap Z)\cup\{x\}\subseteq X$. I wonder ...
0
votes
1answer
24 views

Discrete Math sets and equality.

I have a question about sets and subsets. Consider the universe $\mathbb{Z}$ comprising of all integers and with the following sets: $A=\{2m+1\}$ $B=\{2n-3\}$, where $m$ and $n$ are elements of ...
-1
votes
1answer
23 views

Trouble determining planarity of graph

I am practicing for an exam and I can not wrap my head around this exercise. I am supposed to show if the given graph is planar by drawing it or show the subgraph that is homeopathic to K 3,3 or K5. ...
1
vote
2answers
63 views

Proof Verification for Homework

If $n$ is odd, then $n^2$ is odd. $1$) $n = 2k + 1$ (Definition of an odd number) $2$) $n^2 = (2k+1)^2 = (2k+1)(2k+1) = 4k^2 + 4k + 1$ (Distributive Property) $3$) $4k^2 + 4k + 1 = 2(2k^2 + 2k) + ...
1
vote
1answer
21 views

Determining if a graph is planar and if so draw or disprove with Kuratowski's Theorem

This is a practice exercise for in my text that even my professor was having trouble explaining to me. The instructions are in the title. Here is an image of the graph: I believe this graph is not ...
3
votes
2answers
63 views

What am I doing wrong with this derivative? (Calculus)

I've been doing derivatives with the formula: Definition of a Derivative: for every $x$ plugin $(x+h)$, then subtract original from the equation. This means for $x^2$, I get: $$\frac{(x+h)^2 - ...
0
votes
0answers
18 views

$k$ edge-disjoint $r$-arborescences in an acylic digraph

An $r$-arborescence of a digraph $D$ is a rooted spanning tree with root $r\in V(D)$ in which all the edges of $D$ are directed away from $r$. I would like to prove the following: I have thought ...