Banned User, Former player
Joined: 3/10/2004
Posts: 7698
Location: Finland
Suppose we have, for example: A=4, B=5 and C=1. We can write: C = B - A C(B - A) = (B - A)2 CB - CA = B2 - 2AB + A2 CB - CA - A2 = B2 - 2AB AB + CB - CA - A2 = B2 - 2AB + AB AB + CB - CA - A2 = B2 - AB AB - CA - A2 = B2 - CB - AB A(B - C - A) = B(B - C - A) A = B Where did C disappear? We end up with 4 = 5.
Joined: 10/20/2006
Posts: 1248
These almost always boil down to finding where a division by zero occurs.
Tub
Joined: 6/25/2005
Posts: 1377
Kuwaga wrote:
These almost always boil down to finding where a division by zero occurs.
I'm not sure the word "almost" is necessary in this statement.
Warp wrote:
A(B - C - A) = B(B - C - A) A = B
and there it is, B - C - A = 0.
m00
Joined: 10/11/2009
Posts: 52
Location: Sydney, Australia
Tub wrote:
Kuwaga wrote:
These almost always boil down to finding where a division by zero occurs.
I'm not sure the word "almost" is necessary in this statement.
Actually I've seen a few tricky ones where they square root a negative number to get 1=2 or some other number so almost is necassary :P
Skilled player (1533)
Joined: 7/25/2007
Posts: 299
Location: UK
An 8x8 board has 2 diagonally opposite corners removed. Try to cover the remaining board with 1x2 rectangles, or prove impossible.
Patashu
He/Him
Joined: 10/2/2005
Posts: 4016
I have a 'proof', but I'm not sure how robust it is. Imagine tiling this board with only vertical dominos, leaving holes in opposite corners. By the manhattan metric, the distance from hole A to hole B is even - for them to be adjacent, and thus place a domino there - it needs to be odd and 1. We can imagine shifting or rotating a rectangle into the hole. But this changes the distance by 2! No operation we can perform will change it by 1. Therefore it seems impossible to fully tile. But I might be missing a different starting point.
My Chiptune music, made in Famitracker: http://soundcloud.com/patashu My twitch. I stream mostly shmups & rhythm games http://twitch.tv/patashu My youtube, again shmups and rhythm games and misc stuff: http://youtube.com/user/patashu
Player (42)
Joined: 12/27/2008
Posts: 873
Location: Germany
Flip wrote:
An 8x8 board has 2 diagonally opposite corners removed. Try to cover the remaining board with 1x2 rectangles, or prove impossible.
Simple. Color it like a chessboard. Whenever you place a 1x2 domino, you cover a light square and a dark square. However, to fully cover the board, you need to cover 32 light + 30 dark, or 32 dark + 30 light. Since the number of squares of the two colors is different, it's impossible.
Tub
Joined: 6/25/2005
Posts: 1377
Using the chess board is the most intuitive proof. The one I came up with is a bit more complicated: The first row has 7 squares left, thus it must contain an uneven amount of vertical tiles spanning row1 and row2, let's call it v1. The second row has thus (8-v1) squares remaining, which is uneven, so the amount of vertical tiles between row2 and row3 is uneven, called v3 .... v1, v2, v3, v4, v5, v6 and v7 are uneven (and with an uneven v7, we could fill the last row, so it might work out). Adding them yields an uneven number, so any solution will contain an uneven amount of vertical tiles. Similarly, we can conclude that we need an uneven amount of horizontal tiles. So the total amount of tiles we'll use must be even. But the board requires exactly (8x8 - 2)/2 = 31 tiles. /edit: hmm.. if you randomly remove one black and one white field from a chess board, it will always be possible to fill the remaining board with 2x1-pieces. There's a simple constructive proof which I'm too lazy to write down.
m00
Player (42)
Joined: 12/27/2008
Posts: 873
Location: Germany
This problem is actually a simple case of a well known computer science problem, which is determining if a perfect matching exists in a bipartite graph. You can look at Wikipedia for the terms. If you treat the squares as dots and consider an edge as a line linking connecting each square to its neighbors, you have a bipartite graph, and a perfect matching problem. The proof of impossibility relies on the fact that there can be no perfect matching in a graph if the number of elements in the two independent sets is different. Intuitively, if you color an edge as black when it's matched, and as white if it's unmatched, you can visualize the matching, or better, the domino cover. So, if you want to cover a board with two squares of different colors removed, you first take any matching in the complete board, probably the one where all dominos are in vertical position, because it's easier to see. Then, if you pick two squares of different colors, you can always find a path from the first to the second that consists of black edge -> white edge -> black edge -> white edge -> ... -> black edge. Then you exchange the colors of all edges in this path and remove the two original vertices, and you have covered the board without them.
Joined: 5/30/2007
Posts: 324
There's actually a whole class of problems similar to the one that Flip asked. Sometimes larger dominoes, sometimes you have to color the board more than 2 colors, etc. (Tripartite instead of bipartite, for instance) However, the general method of solving them is always the same. In most of these problems, without using this method, proving that it cannot be done is extremely difficult.
Player (42)
Joined: 12/27/2008
Posts: 873
Location: Germany
Player (79)
Joined: 8/5/2007
Posts: 865
Here's one while I'm thoroughly bored and putting off important work. Consider an arbitrary sequence {an} for which its associated series, {sn} = sum(ak, k, 1, n), is dvergent (I think every mathematician should be comfortable so far). The question is as follows: Is it possible for {an} to be "minimally divergent"? I define "minimally divergent" to mean that if we take any infinite subset of {an}, call it {ank}, then either sum({ank}) or its "complementary series", sum({an}/{ank}), must necessarily converge. For example, take the harmonic series 1 + 1/2 + 1/3 + 1/4 + ... It is clearly not minimally divergent because both 1 + 1/3 + 1/5 + 1/7 + ... and 1/2 + 1/4 + 1/6 + 1/8 + ... are divergent. On the other hand, the sum of the reciprocals of the primes is known to diverge, but extremely slowly (I believe it takes about 520 million terms for the sum to exceed 3). Is it possible that this sum is minimally divergent? If minimal divergence can occur, provide an example and a proof. If not, disprove it. If anyone wants to know the proof but I don't respond for a while, PM me and it'll get my attention. Edit: I've edited this post a few times in the past hour, so if the question didn't make sense before, be sure to reread it. The concept behind what I'm trying to say is actually fairly simple, but it's difficult to put into words. Perhaps someone else can help me?
Joined: 12/10/2006
Posts: 118
I don't think a minimally divergent sequence exists. "any" subsequence seems a too strong argument.
Banned User, Former player
Joined: 3/10/2004
Posts: 7698
Location: Finland
thommy3 wrote:
I don't think a minimally divergent sequence exists. "any" subsequence seems a too strong argument.
Now you'll have to prove that. (I guess that the proof might go in a somewhat similar way as proving that there's no smallest real number larger than zero.)
Player (42)
Joined: 12/27/2008
Posts: 873
Location: Germany
Easy to understand, but not completely correct argument: First consider only series of positive terms that diverge to infinity. Given any divergent series of this type an, we are asked to partition it into two other series ani and anj such that both diverge. The series will diverge if, for every real number K, there's a partial sum of it that will be larger than K. Obviously, if the series diverges, if we remove a finite number of terms from it, it'll continue diverging. Now we have to partition it into two divergent series. First, you have an, and pick the number 1, keep summing the series until you exceed 1 (this will always happen because it diverges), put all these values in the sub-sequence ani. After that, you removed a finite number of terms of the series, it still diverges. So, starting from the first one you didn't remove, you keep summing the series until you exceed 1 again, and put all these values in anj. Keep repeating this process with the remaining sequence. We now see that our method of construction can divide each subsequence we created in infinitely many intervals, each whose sum exceeds 1. So, given any real number K, we know there's a natural number n > K, and picking n of such intervals, we know that the sum of all of them will exceed n, and since n > K, will exceed K also. So, they both diverge. Obviously, that doesn't solve the problem, because in order to diverge, a series doesn't need to be positive for every term or even its sum go to infinity ( (-1,1,-1,1,...) for example). So, we need to generalize this argument to account for the general case. Proof: By definition, a series diverges if and only if the sequence of its partial sums also diverges. Since the set of real numbers is complete, a sequence diverges if and only if it's not a Cauchy sequence. So, with a divergent series an, there's an epsilon>0 such that for any choice of N>0, there are n,m>=N, with |a_n+a_(n+1)+...+a_m| >= epsilon. We then partition the series like in the previous method. For a divergent series, we find any epsilon, N, n, m that satisfy the inequality and put all terms from a_1 to a_m in ani. After removing the finite number of terms, the inequality can still be satisfied with the same epsilon, since it must hold for all N>0. So, we find another n,m that satisfy the inequality and put all remaining terms up to am in anj. After repeating this process indefinitely, we see that the two series have an infinite amount of intervals whose sum exceeds a given epsilon in absolute value, so the partial sums of both do not form a Cauchy sequence, and so they diverge. This method is able to partition any divergent series in two diverging ones, so no series can "diverge minimally".
Joined: 12/10/2006
Posts: 118
You constructed one subsequence that satisfies the condition. But question is, does "any" subsequence do so.
Player (42)
Joined: 12/27/2008
Posts: 873
Location: Germany
I define "minimally divergent" to mean that if we take any infinite subset of {an}, call it {ank}, then either sum({ank}) or its "complementary series", sum({an}/{ank}), must necessarily converge.
This says, for a given series, "every partition has property X", I want to disprove this, so I prove the opposite of this statement, namely "there's at least one partition that doesn't have property X". I only need to construct one example in order to do so. I didn't construct a subsequence that satisfies the condition, I constructed one that doesn't, i.e, both subsequences diverge. EDIT: In case I still wasn't clear: (S is "minimally divergent") iff (S diverges and every partition of S has property X) The proof is: (S divergent) implies (S has a partition that doesn't have property X) Thus, (S diverges) and (every partition of S has property X) can't both be true at the same time. So, no minimally divergent series exists.
Joined: 5/30/2007
Posts: 324
Yeah, p4wner is correct. At first, I was a bit uncertain on what the "complementary series", sum({an}/{ank}), was supposed to mean. However, looking at the example and seeing that it just means all the ones left over, it's a "one mover" in terms of the proof. Props to p4wner for writing it up formally, though.
Player (79)
Joined: 8/5/2007
Posts: 865
Yep, p4wn3r is correct, as usual. He even proved it formally-- I would have just offered his first argument as a proof. (I could/should have specified that an is strictly positive for all n, but it looks like I didn't need to.) I kind of like this problem because it's directly analogous to the proof that conditionally convergent series sum to any value that you want.
Joined: 12/10/2006
Posts: 118
Aftre reading though it i now get your argument. ;)
arflech
He/Him
Joined: 5/3/2008
Posts: 1120
Today while shopping for cereal, I noticed that there were three sizes of cornflakes (12oz, 18oz, and 24oz), and as typically, the unit prices went down (and total prices went up) as the sizes went up, so that the price of a small and a large box together was close to the price of two of the medium boxes. Then I began to wonder whether there was a well-defined algorithm for determining the unit price of a box of a product so that the unit price decreases (and total price increases) as size increases, what all such algorithms looked like, and whether there was also one that had a certain "additive property" that if the sizes of certain sets of boxes had the same total, so would their prices. This last condition turned out to be untenable even in the case that started off my mental wanderings, because it turned out that any such algorithm, starting with an arbitrary choice of unit price for a particular size, would not be well-defined, in particular the one obtained as the arithmetic mean of the unit prices obtained under the extremes of constant unit price and constant total price. Why is this? Next I thought of relaxing that last condition and using what came naturally, the geometric mean of those extreme values, and it turned out to be well-defined. Why? Are there any other such algorithms that are well-defined? The extreme limiting examples of constant unit price and constant total price are well-defined, but they are untenable respectively because the cost of packaging per unit decreases with size and because only the largest package would sell if all had the same price. I'm looking for any other attempts at a "happy medium" that are well-defined. N.B.: The term "well-defined" is key here, although it is not of concern to typical vendors and impossible to implement in practice, much as actual cartographers never seriously tried to use only four colors for their maps and were more concerned with balancing the distribution of the colors.
i imgur com/QiCaaH8 png
Player (42)
Joined: 12/27/2008
Posts: 873
Location: Germany
If I understand correctly your statement, that problem can be abstracted in the following way: (an) is a sequence of real positive numbers that designates the price of a box of n oz, this sequence needs to be strictly increasing. (bn) = (an/n) is the sequence of the unit prices, this one needs to be strictly decreasing. The "additive property" would imply that this has to hold: bn+1 = (bn + bn+2)/2. This sequence has to be an arithmetic progression, but you require it to be bounded, so, it actually must be constant, and unfortunately that breaks it being decreasing, so no solution exists. Ignoring the "additive property", we just need to satisfy these: an < an+1 and an/n > an+1/(n+1) Or better: 1 < an+1/an < (n+1)/n The geometric mean of the two extremes gives an/a1 = sqrt(n). That means an+1/an = sqrt(n+1)/sqrt(n), which does satisfy the inequality. The harmonic mean also seems to be valid. an/a1 = 2n/(n+1). an+1/an = ((2n+2)*(n+1))/((n+2)*2n) = (n+1/n+2)*(n+1/n). n+1/n+2 < 1 and (n+1/n+2)*(n+1/n) > 1 implies n² + 2n + 1 > n² + 2n, which is true. (Also, I've been assuming that you wanted a function whose domain is the entire set of the natural numbers, if your domain is actually a finite subset of them, e.g., 1 <= n <= 10^2011, it might be possible to satisfy your additive property) P.S.: That's some unusual stuff to think while shopping for cereal...
arflech
He/Him
Joined: 5/3/2008
Posts: 1120
Now what about well-definition? Also I wasn't referring to a sequence of package sizes and unit prices but rather to an ideal algorithm for generating the unit price for any package size once the unit price for a particular size is known. I'll expand on my example of using the arithmetic mean, to show where well-definition comes in. Let f denote our desired function (strictly decreasing and smooth on its natural domain), X>0 denote a particular size, and A>0 a particular unit price, and set f(X)=A. Then the price of a package of size X is AX. What should f(x) be for any other value of x? Setting the variable a=f(x), it is clear that one extreme for the unit price is a constant, a=A, while the other is that which would render the package price constant, so that ax=AX, or a=AX/x; notice that when x=X, the extremes are equal. Whatever algorithm generates f(x) must be well-defined (or self-consistent), so that if the algorithm is used upon (x,a) to generate f(X), it must show that f(X)=A. It is evident that the limiting case f(x)=A is well-defined, while to show that the other limiting case, f(x)=AX/x, is well-defined, simultaneously replace X with x, x with X, and A with AX/x to obtain f(X)=AX/x*x/X, and upon cancelling, f(X)=A. There is also an essential symmetry to be seen from the earlier statement of this extreme, ax=AX, but the method I have used will be easier to understand when dealing with the other proposed algorithms. Additionally, if we set the variable r=X-x then I would like whatever algorithm generates f(x) to satisfy the functional equation (X-r)f(X-r)+(X+r)f(X+r)=2AX; at the limiting extreme f(x)=A, or if X=x, this equation is easily satisfied, while at the other limiting extreme f(x)=AX/x, the functional equation becomes (X-r)AX/(X-r)+(X+r)AX/(X+r)=2AX, which simplifies to the true statement AX+AX=2AX. A change of variable may make this easier to work with even though less symmetric-looking...in terms of x, the functional equation is xf(x)+(2X-x)f(2X-x)=2AX. This implies that f(x) should become infinite in the limit as x&rarr;0, because if f(0) were finite, then the equation would yield 2Xf(2X)=2AX, from which f(2X)=A, and f is supposed to be strictly decreasing (f(x)=A is a limiting case but not an actually acceptable solution). An algorithm that should work here is the arithmetic mean of the extremes, f(x)=(1+X/x)A/2, which means xf(x)=(x+X)A/2, so that (2X-x)f(2X-x)=(3X-x)A/2, so their sum is (x+X+3X-x)A/2, which is 4XA/2, which is indeed 2AX; more generally, consider the mean weighted by P>0, given by f(x)=(P+X/x)A/(1+P), which means xf(x)=(Px+X)A/(1+P), so that (2X-x)f(2X-x)=((2P+1)X-Px)A/(1+P), so their sum is (Px+(2P+2)X-Px)A/(1+P), which is 2(1+P)XA/(1+P), which is indeed 2AX. I believe that any algorithm satisfying that functional equation must be such a weighted arithmetic mean, and I suspect any proof of that statement would rely on the smoothness of f. However, there is a problem: It is not well-defined, essentially because the roles of f(x) and A are not symmetric. To see why, in f(x)=(P+X/x)A/(1+P), simultaneously replace x with X, X with x, and A with (P+X/x)A/(1+P), yielding f(X)=(P+x/X)(P+X/x)A/(1+P)2, which, remembering that f(X) is supposed to equal A, expands out to A=(P2+(x/X+X/x)P+1)A/(P2+2P+1) and simplifies to P2+2P+1=P2+(x/X+X/x)P+1 and further to 2=x/X+X/x, or 2Xx=x2+X2, or x2-2Xx+X2=0, or (x-X)2=0, so that x=X...which means that using the algorithm to derive f(x) from f(X), and then using it again to derive f(X) from f(x), will result in two different values for f(X)! Because the values of f(x) under this algorithm depend on which initial choice is made, it is not well-defined; a similar argument shows the essence of well-definition, that once a particular f(x) is derived from f(X), the attempts to derive some f(y) will give different results if f(x) is used as the new base-point or the original base-point f(X) is used. However, another simple algorithm for deriving f(x) from a specified f(X) is well-defined: the geometric mean of the extremes, f(x)=A*sqrt(X/x). A symmetry argument works well here, but let's use another line of argument intimated in the previous paragraph: From this algorithm, if x and y are fixed then, f(y)=A*sqrt(X/y), but if the base-point were f(x) instead of f(X), then X would be replaced with x and A would be replaced with A*sqrt(X/x), so that f(y)=A*sqrt(X/x)*sqrt(x/y), which simplifies to f(y)=A*sqrt(X/y), same as before; this is a sort of "transitivity" of the algorithm. This algorithm does not satisfy the desired functional equation, however: xf(x)=A*sqrt(Xx), so (X-r)f(X-r)=A*sqrt(X)*sqrt(X-r), (X+r)f(X+r)=A*sqrt(X)*sqrt(X+r), and substitution and simplification yield sqrt(X-r)+sqrt(X+r)=2sqrt(X); then squaring and simplification yield 2X+2sqrt(X2-r2)=4X, from which sqrt(X2-r2)=X, and squaring yields X2-r2=X2, so r=0, which means the functional equation is only satisfied in the trivial case x=X. Maybe such an "additivity principle" isn't so important after all...indeed, it is likely inconsistent with well-definition! If we started with the functional equation expressed as xf(x)+(2X-x)f(2X-x)=2Xf(X) and swapped the positions of x and X, this becomes Xf(X)+(2x-X)f(2x-X)=2xf(x), and solved for "2Xf(X)", this becomes 4xf(x)-2(2x-X)f(2x-X)=2Xf(X), which is very different... Now let's look at another candidate algorithm ventured forth in this thread: the harmonic mean of the extremes, which simplifies to f(x)=2AX/(x+X). Simultaneously substituting x with X, X with x, and A with 2AX/(x+X) yields f(X)=4AXx/(x+X)2, and because f(X) is supposed to be A, simplification yields (x+X)2=4Xx, so x2+2Xx+X2=4Xx, so x2-2Xx+X2=0, so (x-X)2=0, so x=X; therefore this one is not well-defined. Note that if A is substituted with f(X) initially, it is evident that the algorithm is not symmetric with respect to the base-point. Similarly, there's a problem with the quadratic mean of the extremes, f(x)=A/x*sqrt((x2+X2)/2), because it too is not symmetric with respect to the base-point. However, much as with the idea I came up with for generalizing to a weighted arithmetic mean, perhaps a weighted geometric mean would allow me to find more well-defined algorithms; let the geometric mean of the extremes, weighted by P>0, of two numbers Y and B be (YPB)1/(1+P), leading to f(x)=(A1+PX/x)1/(1+P), which simplifies to f(x)=A*(X/x)1/(1+P). Indeed this is symmetric with respect to the base-point, for substitution of f(x) with a, and simplification, yield a1+Px=A1+PX. Note that as P approaches 0, f(x) approaches AX/x, and as P approaches infinity, f(x) approaches A. An interesting exercise is to determine and then test criteria for which value of P is "best" (I tried maximizing the curvature of the graph of the expression for f(x), but as a function of P instead; note that none of the derivatives in P is zero when P>0); also, are there any well-defined algorithms for f(x) other than the infinite family I just mentioned?
i imgur com/QiCaaH8 png
Player (42)
Joined: 12/27/2008
Posts: 873
Location: Germany
arflech wrote:
Now what about well-definition?
It's because the well-definition of my example is based on the well-definition of a1, or in what you originally intended, it only works if the information you have is always f(1) = A. This might seem a strong assumption at first glance, but it's not. Solving the problem for an information at f(X)=A is not very different from solving it for f(1)=A. It's basically: having observed f(X)=A, which value A' for f(1)=A' would give a curve consistent with f(X)=A? For example, f(x) = A(X+1)/(x+1) for the harmonic mean and f(x) = A*sqrt(1+x-2)/sqrt(1+X-2) for the quadratic mean. EDIT: The arithmetic mean will work for the additive property, I didn't see before because I switched letters here, it should be an's: xD
bn+1 = (bn + bn+2)/2
You can satisfy the functional equation with (x f(x))'' = 0 and f(X)=A This should be f(x) = A(k/x + 1 - k)/(k/X + 1 - k), for k between 0 and 1. It looks like anything that's f(x) = A g(x)/g(X) within the appropriate bounds works. It may be that, since the geometric mean makes f(x) a constant times a power of x, the division causes a shift in the function and the method you used ends up generating the same function.
arflech
He/Him
Joined: 5/3/2008
Posts: 1120
The "appropriate bounds" end up simplifying, when X>x, to 1<g(X)/g(x)<X/x, and when x>X, to X/x<g(X)/g(x)<1; some rearrangement yields, respectively, x*g(X)/X<g(x)<g(X) and g(X)<g(x)<x*g(X)/X; basically, the graph of g(x) lies between two lines. I wonder whether lg(1+x/X) would work...if x>X, then because lg(2)=1, the inequality to be satisfied becomes 1<lg(1+x/X)<x/X, which does seem to work; of X>x, then the inequality becomes x/X<lg(1+x/X)<1, which also works as long as x>0. Now I wonder whether there is any parsimonious combination of A with AX/x that yields the resulting function, A*lg(1+x/X), and whether there is anything interesting to be gained by scaling the function so that a logarithm of arbitrary base greater than 1 is used. Also, for my musing on the "weighted geometric mean" I was so tired while composing that post that I neglected to notice that it was just A*(X/x)^z, where z=1/(1+P) and 0<z<1; taking the curvature of this with respect to z didn't help either, and neither did seeing where the graph curves out most from the line segment through its endpoints. Also, although I can satisfy that functional equation with x*f(x) equal to a linear function, so that f(x) is of the form P+Q/x, this just brings us back, in the best case, to some weighted arithmetic mean of A and AX/x, which I have already shown to have a problem of lack of well-definition. I'm not sure you quite understand well-definition here: The idea is that there's a set of values, and the easiest way to describe how to get them is to state the value at one point and use some algorithm to get the rest, and this algorithm is well-defined if and only if you get the same set of values regardless of the initial point. If you say that the unit price is A when the size is X, and your algorithm then says that the unit price is B when the size is Y and C when the size is Z (any distinct fixed values of Y and Z within range will do), and then I start that algorithm all over again by starting out with "unit price is B when size is Y," and I don't end up getting A with X and C with Z, then the algorithm is not well-defined, because the set of values you generate depends on the point at which you started generating them.
i imgur com/QiCaaH8 png