# The Grey Labyrinth is a collection of puzzles, riddles, mind games, paradoxes and other intellectually challenging diversions. Related topics: puzzle games, logic puzzles, lateral thinking puzzles, philosophy, mind benders, brain teasers, word problems, conundrums, 3d puzzles, spatial reasoning, intelligence tests, mathematical diversions, paradoxes, physics problems, reasoning, math, science.

Author Message
bonanova
Daedalian Member

 Posted: Wed Aug 08, 2012 2:16 am    Post subject: 1 I was reading about processes that have an unbounded number of steps but a certain conclusion. It interested me because I had associated unboundedness with for example the counting numbers. Give me an integer as large as you like and there is an integer that is one higher. More dramatically, for every integer N, no matter how large, it can be dwarfed by the integer N raised to the Nth power. I intuitively took this to be a description, informal perhaps, of Aleph null. The process that was being discussed can be described as follows. You are given a bucket that contains an arbitrarily large number of balls, numbered 1-N, and you are to empty it by a series of steps described below.. For each ball number there is supplied another bucket with an infinite number of balls with the same number. That is, if the original bucket contains a ball that is numbered 3, there is another bucket with an infinite number of balls also numbered 3. You then proceed as follows. A ball of your choosing, say its number is p, is removed from the original bucket and discarded. The second part of the step is that an arbitrarily large number of balls numbered p-1 are taken from the infinite bucket of p-1 balls and put into the original bucket. Each replacement could entail adding to the bucket a set of new balls of size equal to the number of electrons in the universe. Nevertheless, the process ultimately terminates because when you remove a ball that has the number 1 on it, you don't replace it with any other balls. The interesting fact about this procedure is that at no point, at least until only balls that are numbered with a 1 remain in the bucket, is it possible to give an upper bound for the number of steps remaining to completion. Yet completion is guaranteed. The number is steps is unbounded - give me a number of steps and I will ensure the process goes longer - yet finite. So my thought was, is it a sufficient argument, to prove the integers are infinite, simply to say that no matter how large an integer you choose I will give you one that is larger?_________________ Vidi, vici, veni.
Thok
Oh, foe, the cursed teeth!

Posted: Wed Aug 08, 2012 3:58 am    Post subject: 2

 bonanova wrote: So my thought was, is it a sufficient argument, to prove the integers are infinite, simply to say that no matter how large an integer you choose I will give you one that is larger?

Yes (if you think the integers are finite, then the largest one is well-defined by doing a finite number of comparisons and then your statement gives a contradiction.) But such an argument does not imply any individual element of the integers is infinite.
bonanova
Daedalian Member

 Posted: Sun Aug 12, 2012 1:20 am    Post subject: 3 I agree. I was intrigued with an unbounded process that would always come to completion. But it's the fact that at every point it stays finite that matters._________________ Vidi, vici, veni.
L'lanmal
Daedalian Member

 Posted: Mon Aug 13, 2012 11:15 pm    Post subject: 4 Here is a twist which, in a different context, blew my mind once. Let's add a second option... after drawing a ball, you can put it back, leaving the bucket's state unchanged. Then the process is no longer guaranteed to terminate, and the number of balls the bucket can contain is unbounded. And you can go an arbitrary amount of time with the same number of balls in the bucket only to jump up by a few million later. Yet the number of balls in the bucket will converge. *Edit: to make the statement make sense, I guess I also need to say that if you have an empty bucket you must leave it unchanged. (In short, either you get in an infinite loop of replacing the last ball you drew, or you don't. If you do, you have converged to the number at that point. If you don't, it eventually terminates with 0.)
Griffin
Daedalian Member

 Posted: Thu Oct 04, 2012 9:10 am    Post subject: 5 *wanders in* bonanova, your unbounded process reminds me of a Putnam problem: Show that every rational number can be written as the quotient of products of factorials of (not necessarily distinct) primes. For example, 10/9 = (5! 2!)/(3! 3! 3!) *wanders out*
novice
No harm. Pun intended!

Posted: Thu Oct 04, 2012 11:53 am    Post subject: 6

 Griffin wrote: *wanders in* bonanova, your unbounded process reminds me of a Putnam problem: Show that every rational number can be written as the quotient of products of factorials of (not necessarily distinct) primes. For example, 10/9 = (5! 2!)/(3! 3! 3!) *wanders out*

Solution:

Assume without loss of generality that the rational number is positive.

First show by induction that (assumption 1) : any positive integer X can be expressed as the quotient of products of factorials of primes.
Lets call such an expression Z(x) for readability.

This is true for X = 1 since 1 = 2! / 2!, and it is true for X = 2 since 2 = 2!*2!/2!.

Assume this is true for X = n. Then, for X = (n+1), we have
a) X is nonprime. In that case, express X as the product of the Z functions of the factors of X, which is in itself a Z function.
b) X is prime. In that case, express X as X = (n+1) * n! / n! = (n+1)!/n!. Since n! can be expressed as a Z function, and (n+1) is prime, (n+1)!/n! = (n+1)!/Z(n!) is a Z function for (n+1).

Hence, our assumption 1 is correct.

Since any positive rational number can be expressed as a ratio Q/R where Q and R are positive integers, it follows immediately that any rational number can be expressed as a Z function by expressing it as Z(Q)/Z(R).

For negative rational numbers X, simply express Z(X) as -Z(-X).

QED.

Last edited by novice on Thu Oct 04, 2012 4:27 pm; edited 2 times in total
Griffin
Daedalian Member

 Posted: Thu Oct 04, 2012 4:06 pm    Post subject: 7 Nice novice! And I suppose I meant positive rational number, but if we allow a negative sign all is well. bonanova's post reminded me of this problem since in step b) when showing X = (n+1) can be written in this way, we need that n! can be written in this way. To get that, we need to apply the induction hypothesis for a whole lot of different values, but since each time is for a smaller value than X, the process eventually terminates.
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year by All usersbonanovaGriffinL'lanmalnoviceThok Oldest FirstNewest First
 All times are GMT Page 1 of 1

 Jump to: Select a forum Puzzles and Games----------------Grey Labyrinth PuzzlesVisitor Submitted PuzzlesVisitor GamesMafia Games Miscellaneous----------------Off-TopicVisitor Submitted NewsScience, Art, and CulturePoll Tournaments Administration----------------Grey Labyrinth NewsFeature Requests / Site Problems
You cannot post new topics in this forum
You can reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum