Tag: prove

Prove: If $T’$ is not a MST one of its edges may be replaced by a lighter edge in order to get a lighter spanning tree

Prove: If $ T’=(V,F’)$ is not a MST of $ G=(V,E)$ , then there are edges $ e’ \in F$ and $ e \in $ $ E$ \ $ F$ such that $ w(e)<w(e’)$ and $ T’$ \ $ \{e’\} \cup \{e\}$ is a spanning tree.

My idea:

Let $ T=(V,F)$ be a MST of $ G$

for all $ e \in T$ , try to insert it into $ T’$ and see if there is an edge in the cycle created that is heavier than $ e$ . If we found such $ e$ we are done.

If not, define $ G’=(V,F \cup F’)$

This graph obviously has a MST.

We didn’t find a suitable $ e$ in the previous part so all edges in $ F$ may be colored in red.

That means there is a MST $ T”=(V,F”)$ such that $ F” \ F’$ but that is impossible because $ T’$ is not a MST of $ G’$ , because $ T$ is lighter.

Does that seem correct?

How to prove $f(n) \in O(h(n))$ and $g(n) \in O(i(n))$, then $f(n)+g(n) \in O(max(h(n),i(n)))$

Prove with formal proof that if $ f(n) \in O(h(n))$ and $ g(n) \in O(i(n))$ , then $ f(n)+g(n) \in O(max(h(n),i(n)))$

What I have so far:

By definition of Big-Oh

$ \exists c_1 \exists n_1 \forall n \geq n_1 ( f(n) \leq c_1 \cdot h(n))$

$ \exists c_2 \exists n_2 \forall n \geq n_2 ( f(n) \leq c_2 \cdot i(n))$

Let $ n_0= max(n_1,n_2)$ .

Then $ f(n)+g(n) ≤ c_1 \cdot h(n) + c_2 \cdot i(n) = (c_1 \cdot h + c_2 \cdot i)(n)$ , for all $ n ≥ n_0$ .

I get what the statement is trying to prove, I don’t know how to get $ f(n)+g(n) ≤ c\cdot max(h(n),i(n)) $ , or equivalent, which implies $ f(n)+g(n) \in O(max(h(n),i(n)))$

Prove simple theorems in Haskell in automated way

I would like to prove in Haskell, whether in vanilla Haskell or using some libraries / tools, some simple theorems such as:

and [n*(n+1)/2 == sum [0..n] | n <- [0..]]

Is there a simple enough (ie. fully automated) way to prove such theorems involving integers in Haskell? I am not really interested in the proof itself, or a counterexample, but merely a yes/no answer.

There’s this publication which doesn’t seem practically usable; other than that most of everything else seems to be rather complex, ie. involving a completely separate language and not concerning Haskell.

Does this artifact from Descent Into Avernus prove that magic weapons resize?

The accepted answer to Are there any guidelines in place governing the extent to which magic items can resize to different-sized users? only shows that “worn” magic items are supposed to resize to fit the wearer – not weapons.

I am interested whether the properties of the following artifact demonstrate that magic weapons also resize to fit the bearer.

Furthermore,

Given these two facts, must it be true that this artifact weapon can resize to best fit its wearer, whether Small/Medium or Large? And if so, does that mean that all magic weapons can do this?

Prove a problem to be in NP-complete

Problem: Given n paths in a directed graph G(V, E) and an integer k, find out k paths among them such that no two of them pass through a common node.

Prove that the given problem is in NP-complete.

I was able to prove that the problem is in NP. Hint is that we need to come up with a polynomial time reduction of the independent set problem to this problem prove that it is in NP-hard.

Prove little o with just the definition

I have been searching for a while now but couldn’t find anything about this exact pair of functions with the little $ \mathcal{o}$ notation.

Given the functions $ f(n) = 2^{n}$ and $ g(n) = n!$ I am supposed to prove, or disprove, the following statement: $ f(n) \in \mathcal{o}(g(n))$ .

I am fairly sure that it’s true but now I need an idea of how to show this. We have just started out with this whole concept and this is the second exercise, the first one being a relatively easy big $ \mathcal{O}$ task. But this exercise is just beyond me right now. The only definition I am allowed to use (meaning: NO LIMITS) is $ \mathcal{o}(g(n)) = \{f(n)|\forall C > 0 \exists n_{0} \forall n\geq n_{0}:f(n) < C * g(n)\}$ . This means other than with big $ \mathcal{O}$ , where it suffices to show that there’s at least one pair $ C$ and a $ n_{0}$ so that $ f(n) \leq C * g(n)$ $ \forall n \geq n_{0}$ , I now have to prove that for every $ C > 0$ , there is such a $ n_{0}$ so that the condition stated in the set is true.

I first have been thinking about the functions, and I would have an answer for $ \mathcal{O}$ , because you can prove with induction that $ 2^{n} < n!, \forall n\geq 4$ . Meaning my C would be 1 here. However, I have no idea how to prove it for every C and would be grateful for any guidance! (It would already help to know how to start. Probably like, let $ C$ be greater 0, and then I have to show that for any Value of this $ C$ , there is… because… My biggest struggle is to find meaningful estimations to get a chain of inequalities.)