CTK Exchange Front Page Movie shortcuts Personal info Awards Reciprocal links Terms of use Privacy Policy Cut The Knot! MSET99 Talk Games & Puzzles Arithmetic/Algebra Geometry Probability Eye Opener Analog Gadgets Inventor's Paradox Did you know?... Proofs Math as Language Things Impossible My Logo Math Poll Other Math sit's Guest book News sit's Recommend this site        CTK Exchange

 Subject: "Stones in Cups" Previous Topic | Next Topic
 Conferences The CTK Exchange This and that Topic #719 Printer-friendly copy Email this topic to a friend Reading Topic #719
sfwc
Member since Jun-19-03
Jun-18-06, 01:51 PM (EST)    "Stones in Cups"

 I believe there is a flaw in the counterargument on this page.You say 'The solution, as it is presented in the magazine, appears to go through for the generalized problem with empty cups verbatim without any change.', but this is not quite true. In fact, everything but the final line goes through unchanged. Indeed, you have shown that in the specific case you consider, 'the repeated sequence of configurations will include the original configuration.'The final line states that 'This inverse move applied to the original configuration puts all the stones in the original cup, and will therefore be reached', but in the similar case you consider, applying the inverse move to the original configuration does not put all the stones in the original cup.I like the proof.Thankyousfwc<><

alexb Charter Member
1858 posts
Jun-29-06, 02:10 PM (EST)    1. "RE: Stones in Cups"
In response to message #0

 Something happened to my mail and I was not receiving notifications of posted messages. Took me time to notice that.You are right. I've been thinking of the problem of collecting all the stones into 1 cup and not necessarily the original one.So what I've been thinking of is this replacement for the last sentence"This inverse move applied to the original configuration puts all the stones in a single cup (which happens to be the original one), and will therefore be reached."But this, too, is only true when k = 1. For k > 1, the empty space is reached too soon. A pity.

sfwc
Member since Jun-19-03
Jul-07-06, 07:15 PM (EST)    2. "Short cycles."
In response to message #0

 It'seems that if k=1, the number of moves before returning to the original configuration is much smaller than the proof suggests. First I need to set up some notation. For simplicity, I shall initially work with an infinite collection of cups, one for each integer, and finitely many stones. Evidently, for any initial configuration, a situation will eventually be reached in which your hand is to the right of all but one of the stones, and all remaining moves consist of picking up that stone and moving it to the next cup along. I shall use the term 'arrangement' to refer to a specification of the number of stones in each cup, independently of the position of the hand. So an arrangement may be thought of as a function from the integers to the natural numbers. For an arrangement u define s_n(u) by s_n(u)(k) = u(k-n); s_n has the effect of shifting all stones k places to the right.To simulate the fact that the real problem refers to a loop, I shall consider the effect on an arrangement of having the hand approach from infinity on the left moving a single stone in the manner described above, and change the arrangement of the stones by following the rules until it leaves all but one stone to its left and goes to infinity on the right with the remaining stone; I shall call the effect that this has on an arrangement a rearrangement. Obviously a rearrangement does not change the total number of stones.I shall say an arrangement u is confined by {a, b} if u(c) > 0 => a <= c <= b. Define u(n, 0) to be the arrangement with n stones in cup 0 and none elsewhere. Define u(n, i) inductively by letting u(n, i + 1) be the rearrangement of u(n, i).Lemma: Let n <= 2^t. Then u(n, i) is confined by {i, i + n - 1} and u(n, 2^t) is the arrangement with all n stones in cup 2^t (That is, it is s_{2^t}(u(n, 0))Proof: Induction on t.There are 2 cases:Case 1: n < 2^(t-1).Then u(n, 2^(t-1)) = s_{2^(t-1)}(u(n, 0)), so for any i u(n, 2^(t-1) + i) = s_{2^(t-1)}(u(n, 0)). In particular, u(n, 2^t) = s_{2^(t-1)}(u(n, 2^(t-1))) = s_{2^(t-1)}(s_{2^(t-1)}(u(n, 0))) = s_{2^t}(u(n, 0)).u(n, i) is confined by {i, i + n - 1} by the induction hypothesis.Case 2: n > 2^(t-1). Let k = n - 2^(t-1).Then u(n, 1) = u(2^(t-1), 1) + s_{2^(t-1)}(u(k, 1)) Now, as u(2^(t-1), 2^(t-1)) = s_{2^(t-1)}(u(2^(t-1), 0)), for i <= 2^(t-1) + 1, u(2^(t-1), i) is confined by {i, 2^(t-1)} and s_{2^(t-1)}(u(k, i)) is confined by {2^(t-1) + i, n + i - 1} so that u(n, i) = u(2^(t-1), i) + s_{2^t-1}(u(k, i)).Therefore by the induction hypothesis u(n, 2^(t-1)) = s_{2^(t-1)}(u(2^(t-1), 0)) + s_{2^t}(u(k, 0)).Now the first 2^(t-1) rearrangements from u(2^(t-1), 0)) each add one stone to cup 2^(t-1). Thus for 0<= i <= 2^(t-1) we have u(n, i + 2^(t-1)) = s_{2^(t-1)}(u(2^(t-1), i)) + s_{2^t}(u(k, 0)).In particular, u(n, 2^t) = s_{2^t}(u(2^(t-10, 0)) + s_{2^t}(u(k, 0)) = s_{2^t}(u(n, 0)).The confinement condition is similar, but simpler.Now consider the original problem. The starting configuration is just like u(n-1, 1) with the blank spaces erased, the ends joined, and the hand just about to reach the arrangement from the left hand side. The confinement conditions ensure that the evolution is exactly as in the lemma: For 2^t > n-1, the stones will all be in a single cup after 2^t - 1 rearrangements. Each rearrangement involves at most n moves, and the whole cycle need be repeated at most n times to bring all the stones into the original cup. So as 2^t < 2n - 2, the total number of moves in the cycle is O(n^3), which is much shorter than would be expected from the given proof.This argument does not appear to generalise for k>1,Thankyousfwc<>< alexb Charter Member
1858 posts
Jul-07-06, 07:26 PM (EST)    3. "RE: Short cycles."
In response to message #2

 Nathan, I am on vacation right now with intermittent access to the web and a schedule unsuitable for focused reading.It looks very intersting what you wrote. I'll look at this upon my return.

 Conferences | Forums | Topics | Previous Topic | Next Topic
 Select another forum or conference Lobby The CTK Exchange (Conference)   |--Early math (Public)   |--Middle school (Public)   |--High school (Public)   |--College math (Public)   |--This and that (Public)   |--Guest book (Public) Educational Press (Conference)   |--No Child Left Behind (Public)   |--Math Wars (Public)   |--Mathematics and general education (Public) You may be curious to have a look at the old CTK Exchange archive.  