# 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.

Message body

 Emoticons View more Emoticons
 [quote="novice"][quote="Griffin"]*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*[/quote] Solution: [spoiler]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. [/spoiler][/quote]
Options
HTML is OFF
BBCode is ON
Smilies are ON
 Disable BBCode in this post Disable Smilies in this post

 All times are GMT
 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
 Topic review
Author Message
Griffin
Posted: Thu Oct 04, 2012 4:06 pm    Post subject: 1

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.
novice
Posted: Thu Oct 04, 2012 11:53 am    Post subject: 0

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.
Griffin
Posted: Thu Oct 04, 2012 9:10 am    Post subject: -1

*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*
L'lanmal
Posted: Mon Aug 13, 2012 11:15 pm    Post subject: -2

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.)
bonanova
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.
Thok
Posted: Wed Aug 08, 2012 3:58 am    Post subject: -4

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
Posted: Wed Aug 08, 2012 2:16 am    Post subject: -5

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?