Tag Info

Hot answers tagged

36

Yes, you can. This method is known as proof by exhaustion. Also, see computer-assisted proof. Edit: As others have noted, this of course works only for finite sets.


12

You need to count in terms of $5^0, 5^1, 5^2, 5^3$ and $5^4$, not in term of $100 ,10$ and $1$. Start by the highest power of $5$ smaller than your number, i.e. $5^4=625$ here, and check how much you can multiply it without exceding (this will be a number in $1,2,3,4$). Take the leftover (base 10, 727-625=102) and repeat until you reach $0$. You should ...


12

Trick: divide consecutively the quotients by $\;5\;$ and keep aside the residues : $$\begin{align*}\frac{727}5=145+\frac25\longrightarrow& \color{red}2\\ \frac{145}5=29\longrightarrow&\color{red}0\\ \frac{29}5=5+\frac45\longrightarrow&\color{red}4\\ \frac55=1\longrightarrow&\color{red}0\\ ...


8

Yes, but some mathematicians think of it as an inferior way of proving things. They think that it's not "pure" and it doesn't really explain(on a deeper level) about what's going on. One of the most famous computer-assisted proofs is the proof for the four color theorem. EDIT: Also note that this technique does not work for infinite sets(I personally ...


5

Using a computer to brute-force can be the first step to a proof. The next step is to prove that the program is correct! A few ways you might do this are: Have the program output a proof for each member of the set. We can then check these proofs without having to trust the program at all. We could even send them all through an automated proof checker, ...


4

This is only true because it is a complete binary tree. There are twice as many nodes in each succeeding level (starting from the root at level $k=0$). Thus, at level $k$, there are $2^k$ nodes and the index of the first node is $2^0 + 2^1 + \dots + 2^{k-1} + 1 = 2^k$. At level $k$, the children of the first node (index $N = 2^k$) will be labeled as soon ...


3

Exhaustive checking is certainly a valid method proof, that is, everyone agrees that it is a proof. It is usually considered a not very satisfying proof, though, because it usually fails to produce any insight why such-and-such is true. It just observes that it is true, but mathematicians are generally interested in understanding rather than mere facts, and ...


3

Consider the partial function which takes as input a Turing machine and returns as output its halting time if it has one. The exact domain of this function, namely the set of Turing machines which have halting times, is in a pretty strong sense impossible to know because the halting problem is undecidable.


3

Yes. Compute the singular value decomposition of the two sets of points (as matrices of vectors of their coordinates). If the singular values do not agree, then there is no orthogonal matrix mapping one to the other. If the singular values do agree, then the singular vectors are an orthogonal coordinate system in which the two sets may be identical, which ...


3

The Myhill-Nerode theorem shows this immediately. The infinitely many prefixes $a^ib^i$ are all pairwise distinguishable. (If $i\ne k$, then $c^i$ is a distinguishing extension: $a^ib^ic^i \in L$ but $a^kb^kc^i\notin L$). Therefore the language cannot be regular.


2

The following procedure should do the trick. It returns false if it is not possible to seat people and true otherwise. It also seats people as a side-effect: While (not all persons seated){ put a standing person p in the queue level(p)=0 While (queue not empty){ remove person p from the queue seat p at table (level(p) mod 2) + 1 for all ...


2

Suppose $L$ is regular. Let $n \in \mathbb{N}$ be the number mentioned in Pumping lemma (PL). Now, let us take $\alpha=a^nb^nc^n$. According to PL, we can choose $u,v,w$ such that $\alpha=uvw$, $|uv| \leq n$ and $|v| \geq 1$. Then, since $|uv| \leq n$, the word $v$ consists of $a$'s only. And so, for example, $uv^2w$ contains $n+|v|$ letters $a$, while the ...


2

Suppose $L$ were regular. According to the Pumping Lemma, every sufficiently long word in $L$ can then be written as $xyz$ with $y \neq \epsilon$ such that $xy^iz \in L$ for all $i$. Now, take a sufficiently long word in $L$ and write it that way. If $y$ consists of two or three different types of letters (e.g., both $a$'s and $b$'s in $y$), then $xy^2z ...


2

Regular Expressions in formal languages and automaton theory are the basis for regular expressions in UNIX. Some of the syntax is a bit different in grep than in the formal theory. For example, in grep, you can use $(a+b)^{2}$, while this is not acceptable syntax theoretically (though it would make sense to have it theoretically). Grep also has a larger set ...


2

The mathematical (theoretical CS) definition of regular is that which is recognized by a NFA or DFA. Equivalently it can be generated by a regular grammar. Regexes are things that have popular implementations in Perl, Python, grep, etc. I won't call them regular expressions because for most (all?) of the modern implementations, they are not regular anymore. ...


2

There is a way to reduce the complexity and make the system solvable in parallel. It is called Diakoptics (a method invented by Gabriel Kron). The methods primary use is for large electrical networks that have few interconnections like power grids. But you should be able to adapt it. The complexity (for the case below) is reduced from $O(n^3)$ to ...


2

The image $f(X) = \{ f(x) : x \in X \}$. So to find the preimage of $3$, you want $\{ x : f(x) = 3 \}$. So set $3 = 2 + x^{2}$. You should be able to take it from here. For part (ii), a one-to-one function is a function such that $f(a) = f(b) \implies a = b$. Here, you have $f(a) = f(b)$, but $a \neq b$. An onto function is one such that $\forall{y} \in E$, ...


2

One method is to, first, transform the grammar into Chomsky Normal Form, after having deleted non-yielding and unreachable symbols (yours is quite close as is now and don't need to change it, but I'm just saying for the general case). Then construct a directed graph as follows: Make a vertex for every non-terminal symbol of the grammar. Put edges $(A,B)$ ...


2

For applications of Differential Geometry in Computer Science, the following link is very useful: http://stat.fsu.edu/~anuj/CVPR_Tutorial/ShortCourse.htm It talks about : "Differential Geometric Methods for Shape Analysis and Activity Recognition" One of the contributors of the above is Dr.Anuj Srivastava (http://stat.fsu.edu/~anuj/index.php). I liked the ...


2

You can build such a function whenever you have a function $f$ whose zeros are unknown. For example, set $$ f(z) = \frac{1}{\zeta(z)} $$ where $\zeta(z)$ is the Riemann zeta function. It is conjectured, but not proven, that for all zeros of $\zeta(z)$, either $z = -2n$, $n \in \mathbb{N}$ (these are called the trivial zeros) or $\textrm{Re} z = ...


2

The Collatz conjecture provides a nice example: $$ f(n) = \begin{cases} 1 & \text{ for } n = 1, \\ f(n/2) & \text{ for } n \text{ even}, \\ f(3n+1) & \text{ for } n \text{ odd}, \end{cases} $$ for any positive $n \in \mathbb{N}$. The conjecture is (equivalent to) that the domain of $f$ is $\mathbb{N}\setminus\{0\}$, but we don't know it. ...


2

If every edge has weight $1$, then every spanning tree of $G$ has the same weight: $\lvert V\rvert-1$. So, all that you actually have to do here is find any $O(\lvert V\rvert+\lvert E\rvert)$-time algorithm for finding ANY spanning tree for $G$. For instance: breadth-first search can be used to do this, with worst-case performance $O(\lvert V\rvert+\lvert ...


2

What is a linear homogeneous recurrence relation? It is an equation of the form: $A_0a_n + A_1a_{n-1} + A_2a_{n-2} + ... + A_ka_{n-k} = 0$ Indeed, the equation above is of order k. For it to be linear, there should be no powers greater than $1$ lying around the recurrence relation terms. It is easy to verify this for your equations. Now, important to ...


2

HINT : Hopefully this will help you solve the question. Otherwise you can just calculate the first 3-4 $G_n$ and see to which of the proposed solutions it corresponds : \begin{eqnarray*} G_0 &=& 0\\ G_1 &=& G_0 + 2\cdot1 - 1 \qquad n = 1 \text{ here}\\ &=& 0 + 2 - 1\\ &=& 1\\ G_2 &=& G_1 + 2\cdot2 - 1 \qquad n = 2 ...


2

When talking about indexing, it provides a structured way of accessing the array elements. It's not so much a mathematical property of a binary tree (at least, that's not how I'd look at it), as more of a way of modeling the data for efficient lookup and storage in an array. An array based solution allows for a compact representation of the tree. You ...


2

After the point, it goes like $16^{-1}$, $16^{-2}$ etc. Therefore, $(15C.38)_{16}$ can be converted by doing the following: $1 \times 16^2 + 5 \times 16^1 + 12 \times 16^0 + 3 \times 16^{-1} + 8 \times 16^{-2}$. Another method is, writing every digit as 4-bit binary string and than converting those to decimal. i.e. $(0001$ $0101$ $1100$ . $0011$ ...


1

Maximal independent sets are not unique. Consider $Q_{3}$, the hypercube on $8$ vertices. I can select two non-adjacent vertices and up to four non-adjacent vertices depending on my selection. Each such selection is a maximal independent set. The Wikipedia page has a really nice graphic demonstrating this: ...


1

Take the words $u:=$"$A$" and $v:=$"$B$". Are the words "$AB"$ and "$BA$" the same? No. Well, indeed, we have a canonical map $L_1\times L_2\to L_1L_2$: $$\langle u,v\rangle\ \mapsto\ uv$$ but this doesn't need to be bijection if $L_1,\ L_2$ can be any subset of words, as in the following example: $L_1:=\{$"$A$","$AA$"$\}$ $L_2:=\{$"", "$A$"$\}$. ...


1

I'm not sure about the policy on posting pictures in answers, but I recently wrote up how to do this as part of a proof of the undecidability of the Wang (domino) tiling problem. It would take considerable time to translate into tex and diagrams, so here goes: (They may need to be viewed in full size to get some of the details) Edit: It's somewhat ...


1

We will show that if T is not a tree, then there is an integer $k>0$ such as $p^{k}(y)=y$ for a $y \in T$. This doesn't agree with your definition. You want to show that there is no periodic point. By definition, a tree is acyclic. So it suffices to show that $p$ will end up traversing a cycle. That's how you should go about contrapositive. ...



Only top voted, non community-wiki answers of a minimum length are eligible