Tag Info

New answers tagged

1

HINT: I’ll write $F\preceq G$ instead of $F\mathrel{R}G$. You can’t assume that $H$ is the greatest lower bound, because at this point in the argument you don’t know that the set $\{F,G\}$ necessarily even has a greatest lower bound. What you need to do is show that if $H$ is any lower bound for $\{F,G\}$, then $H\preceq F\cdot G$. In order to do this, you ...


2

For part A, for each odd integer $2k+1$ with $k$ a positive integer, consider the integers $(2k+1)2^m$ with $m$ a non-negative integer. The admissible parts in the first case include only $2k+1$ (i.e. $m=0$), whereas the admissible parts in the second case include all these integers for all $m$. In a given partition, we can group all parts with a given $k$ ...


2

HINT: Start with an $X\in F$. Since $F\mathrel{R}G$, there is a $Y\in G$ such that $X\subseteq Y$. Then since $G\mathrel{R}F$, there is an $X'\in F$ such that $Y\subseteq X'$, and it follows that $X\subseteq X'$. But $X$ and $X'$ are both members of the partition $F$, so what does that tell you about them? What can you then infer about $X$ and $Y$?


2

You've described an NP-complete problem. Indeed, this problem is exactly the subset-sum problem with the extra restriction that the desired subset has size $N$; but if this were not NP-complete then the subset-sum problem would not be either, because it would only take $|C|$ iterations of the "change-problem" algorithm to solve subset-sum (where $C$ is the ...


1

So you want to reduce the partition problem to the subset sum problem. Hint: Given an instance of the partition problem, sum the numbers and halve the sum to find out what each side of an equal partition must sum to. Append minus this number to the problem, and feed the resulting multiset to the hypothesized subset-sum solver.


0

Your friend is right....(1): If it were possible it would need a countably infinite family...(2):Proof by contradiction: Suppose $I(n)=[A(n),,B(n)] $ with $A(n) < B(n)$ for $n \in N$ with $ \cup \{ I(n) \} _{n \in N} = [0,1]$ and $I(m) \cap I(n) = \phi$ for $m \not =n$. We may assume $A(0)=0$ and $B(1)=1$.For brevity,say that $I(j)$ is between $I(i)$ ...


1

Concerning the current edition of your question, I can say that both propositions are right, by The Sierpiński Theorem. I recall that a continuum is a compact connected Hausdorff space and remark that the unit segment $[0,1]$ can contain at most a countable family of pairwise disjoint nondegenerate closed intervals. (cited from “General Topology” by ...


1

I don't think there is a name for such a transform, although I could be wrong. It's pretty easy to compute using generating functions. If $a_n$ is your original sequence, let $$f(x) = \prod_{i=1}^\infty (1-x^i)^{-a_n}.$$ Then the coefficients of $f(x)$ are the transform of your sequence. In your example, we we have $a_1 = 2, a_2 = 1$, and then $$f(x) = ...


2

By "almost equal", you mean "almost everywhere equal". Which means that the two functions agree except possibly on a set of measure zero. You can kind of visualize the measure of a subset of the real line as being its "length". And in fact, this is exactly what the measure is for intervals: that is, the measure of $(a,b)$ is $b-a.$ Now, what we call ...



Top 50 recent answers are included