Putnam 2009 B1

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Kent Merryfield

18574 posts

Kent Merryfield

#1 h Dec 7, 2009, 12:38 AM • 4 Y

Y by centslordm, ZHEKSHEN, Adventure10, Mango247

Show that every positive rational number can be written as a quotient of products of factorials of (not necessarily distinct) primes. For example, $\frac{10}9=\frac{2!\cdot 5!}{3!\cdot 3!\cdot 3!}.$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Nawahd Werdna

294 posts

Nawahd Werdna

#2 h Dec 7, 2009, 12:47 AM • 2 Y

Y by Adventure10, Mango247

I used strong induction on the prime numbers to show that every prime number could be written this way, so every natural number can be written this way, and then so can every quotient of natural numbers, as desired...

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

themandotcom

1 post

themandotcom

#3 h Dec 7, 2009, 12:54 AM • 2 Y

Y by Adventure10, Mango247

I used a similar method:
It suffices to prove that each integer can be represented this way.
Induction
Base case: n=2=2!

Assume numbers <= n have a representation of a quotient of products of primes

Prove n+1:

Case 1: n+1 is prime
n+1 = (n+1)!/n! but the bottom is n x n-1 x n-2....2 x 1. By induction hypothesis, each term in the product has a representation.

Case 2: n+1 is composte
n+1=p_1xp_2...p_n=(p_1)!/(p_1-1)! x (p_2)!/(p_2-1)! ... (p_n1)!/(p_n-1)!, and we can replace the bottom numbers in the same way as in case 1.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Kierhammer

4 posts

Kierhammer

#4 h Dec 7, 2009, 12:56 AM • 2 Y

Y by Adventure10, Mango247

Although I'm not sure what strong induction is (as opposed to induction in general), I think I solved this one the same way. All primes can be written like this, therefore you can obtain all the natural numbers, therefore you can get all positive rationals (since rationals are just a quotient a/b of integers, b not equal to zero).

First time I've taken the Putnam exam. It was fun.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

mathking123

406 posts

mathking123

#5 h Dec 7, 2009, 1:11 AM • 1 Y

Y by Adventure10

Kierhammer wrote:

...I'm not sure what strong induction is (as opposed to induction in general...

In strong induction, the induction hypothesis is different. In normal induction, you assume it is true for some k and show that it must be true for k+1. In strong induction you assume it is true for 1,2,3,...,k, and then show that it must be true for k+1. The induction hypothesis is "stronger".

Going back to the topic, did anyone think that this problem was too straightforward to be a putnam problem (considering that you could just do the standard sort of induction)?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

jdposkin

3 posts

jdposkin

#6 h Dec 7, 2009, 1:17 AM • 2 Y

Y by Adventure10, Mango247

I think the difficulty of the problem was realizing that all you needed to do was prove it true for any prime p. After you saw through that it was straightforward. It was my first time taking the putnam though so I have no idea how difficult the A1, B1s are supposed to be.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

sundiata82

5 posts

sundiata82

#7 h Dec 7, 2009, 2:32 AM • 2 Y

Y by Adventure10, Mango247

themandotcom wrote:

Case 2: n+1 is composte
n+1=p_1xp_2...p_n=(p_1)!/(p_1-1)! x (p_2)!/(p_2-1)! ... (p_n1)!/(p_n-1)!, and we can replace the bottom numbers in the same way as in case 1.

Question...

If n+1 is composite, shouldn't it be a product of POWERS of primes?

Edit: Well, I guess it doesn't affect your argument....

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

t0rajir0u

12167 posts

t0rajir0u

#8 h Dec 7, 2009, 3:53 AM • 1 Y

Y by Adventure10

Here's a high-concept view. One can regard the positive rational numbers under multiplication as a $\mathbb{Z}$ -module in the obvious way using prime factorizations (in fact they are the countable direct sum of copies of $\mathbb{Z}$ ). The factorials of the primes form the rows of a lower-triangular linear transformation on this module, and lower-triangular linear transformations are always invertible in the obvious way, especially if they have $1$ s on the diagonal.

This post has been edited 1 time. Last edited by t0rajir0u, Dec 7, 2009, 4:51 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

jmerry

12096 posts

jmerry

#9 h Dec 7, 2009, 3:56 AM • 1 Y

Y by Adventure10

Yes, that's how I saw it. The bit I wrote down featured a vector and an upper triangular matrix. (with factorials as the columns, of course).

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

t0rajir0u

12167 posts

t0rajir0u

#10 h Dec 7, 2009, 4:01 AM • 2 Y

Y by Adventure10 and 1 other user

For what it's worth, here's how I actually wrote down the argument:

Let $p_1, p_2, ...$ denote the primes, and strong induct on the largest index $i$ such that $p_i$ appears in the prime factorization. (This seems to me much more natural than inducting on the size of the integers themselves.) $i = 1$ is trivial, since any rational number with only $2$ in its prime factorization is of the form $(2!)^k, k \in \mathbb{Z}$ . If you know the result for $i \le k$ , then suppose that $v_{p_{k + 1}}(q) = r$ and consider $q (p_{k + 1}!)^{ - r}$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

bugake

9 posts

bugake

#11 h Dec 7, 2009, 4:28 AM • 2 Y

Y by Adventure10, Mango247

Is it OK to show that (using induction) since every prime can be written in terms of the quotient of products of factorials of primes, every rational can too?

I mean, for every rational number, both its numerator and its denominator can each be re-written as the product of primes.....

please help

thanks

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

jmerry

12096 posts

jmerry

#12 h Dec 7, 2009, 4:31 AM • 2 Y

Y by Adventure10, Mango247

Yes, that's OK.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

bugake

9 posts

bugake

#13 h Dec 7, 2009, 4:49 AM • 1 Y

Y by Adventure10

my argument is simply saying that every prime can be written as the quotient of products of factorials of primes.

By standard induction, the base case is the smallest prime number, 2 = 2!.

Suppose the argument is true for the kth smallest prime, prove it's true for the (k+1)th smallest prime.

Suppose the (k+1)th prime = p.

p! = p*(p-1)*(p-2)*...*1 = p*(q1^e1)*(q2^e2)....
where the qn's are just prime numbers, each less than p, and en's are just some exponents.

By the inductive hypothesis, all the qn's can be written as quotient of products of factorials of primes.

So, p = p!/[(q1^e1)*(q2^e2)...]

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Roosta

45 posts

Roosta

#14 h Dec 7, 2009, 5:46 AM • 1 Y

Y by Adventure10

I actually did strong induction on the naturals, not the primes. I first showed that the set $S$ of all numbers that can be written as the products of... etc. is closed under addition and inversion, so $\mathbb{N}\in S$ $\Rightarrow$ $\mathbb{Q}\in S$ . Then induction: $1=\frac{2!}{2!}$ , and two cases for $n+1$ :

$n+1$ is prime: $\frac{(n+1)!}{n!}\in S$ since $n!\in S$ .

$n+1$ is composite: $n+1 = ab$ , where $a,b \in S\Rightarrow ab = n+1\in S$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Mgccl

50 posts

Mgccl

#15 h Dec 7, 2009, 8:47 AM • 2 Y

Y by Adventure10, Mango247

For integers a and b, I took the log of all the prime from 2 to the mth prime, where m is the largest prime divisor of a or b. which is a vector space of $\log p_k$ , where $p_k$ is the kth prime number, and all the $\log p_k!$ forms a basis of the vector space. then we can prove $\log \frac{a}{b}$ is in this space. then prove we can write $\log \frac{a}{b}$ as linear combination of $\log p_k!$ , where all coefficient are integers. then it imples $\frac{a}{b}$ can be written as a product of $p_k!$ and $\frac{1}{p_k!}$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Lulze

210 posts

Lulze

#16 h Dec 7, 2009, 3:32 PM • 1 Y

Y by Adventure10

Do you think it's trivial that if $a$ and $b$ follow the form, then so do $ab$ and $\frac{a}{b}$ ? Will I lose points if I state that these properties are true but don't actually show them? During the test I thought they were fairly obvious.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

mathbuzz

803 posts

mathbuzz

#17 h Aug 27, 2013, 2:00 PM • 2 Y

Y by Adventure10, Mango247

We shall prove that every natural number can be written as a quotient of product of factorials of primes [not necessarily distinct] by induction.
we have $1=\frac{2!}{2!}$ , $2=\frac{2!.2!}{2!}$ , $3=\frac{3!}{2!}$ , $4=\frac{2!.3!.2!}{3!}$
now , we assume that , the result is true for $n=1,2,....,m$ .
now , if $(m+1)$ is composite , then , we can write , $m+1=uv$ with math=inline]$u,v>1$[/math .so , $u,v \le m$
so , both $u$ and $v$ can be written as quotients of product of factorials of primes.
so , $m+1$ can be written as a quotient of product of factorials of primes.
And if $m+1$ is a prime , then , $m+1=\frac{(m+1)!}{m!} =\frac{(m+1)!}{1.2....m}$ .
now , all of $1,2,....,m$ can be expressed as the quotients of product of factorials of primes.
so , $m+1$ can also be expressed as a quotient of product of factorials of primes .
hence , by PMI , we conclude that , we can write all positive integers in the 'required form'.
so , clearly , all rational numbers can be written in the 'required form' .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

NWskier

98 posts

NWskier

#18 h Feb 22, 2014, 8:42 AM • 1 Y

Y by Adventure10

I thought I had a correct solution to this, but it doesn't involve induction. Here is what I did, if someone could look it over and tell me if it works that would be greatly appreciated.

Consider any rational number, and WLOG write it as $p/q$ , where $p$ and $q$ are relatively prime positive integers. Next notice that there is some prime factorization (possibly just itself) of both $p$ and $q$ . Hence we can write

$p = p_1^{e_1}p_2^{e_2}p_3^{e_3} \cdots$ where all $p_i$ are prime

and

$q = q_1^{f_1}q_2^{f_2}q_3^{f_3} \cdots$ where all $q_i$ are prime.

Next notice that it is an algebraic fact that $q_i = \frac{q_i!}{(q_i-1)!}$ , and similarly that $p_i = \frac{p_i!}{(p_i-1)!}$ . Hence we have

$p = \left(\frac{p_1!}{(p_1-1)!}\right)^{e_1}\left(\frac{p_2!}{(p_2-1)!}\right)^{e_2}\left(\frac{p_3!}{(p_3-1)!}\right)^{e_3} \cdots$
and

$q = \left(\frac{q_1!}{(q_1-1)!}\right)^{f_1} \left(\frac{q_2!}{(q_2-1)!}\right)^{f_2}\left(\frac{q_3!}{(q_3-1)!}\right)^{f_3} \cdots$ .

Hence the quotient $\frac{p}{q}$ can be expressed as a quotient of products of factorials of primes.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

JBL

16123 posts

JBL

#19 h Feb 22, 2014, 3:14 PM • 2 Y

Y by NWskier, Adventure10

There is only one prime number $p$ with the property that $p-1$ is also prime.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Aris1998

151 posts

Aris1998

#20 h Mar 20, 2015, 4:14 PM • 2 Y

Y by Adventure10, Mango247

I have an alternative, which works for all except prime numbers. If somebody can check it that would be great. First, let

$x = \prod n_k!$

$y = \prod j_i!$

Since $a,b$ are both positive integers, it comes:

$\frac{a}{b} = \frac{x}{y} \implies a = b\cdot \frac{x}{y}$

Suppose this holds for: $\varphi = \{1, 2, 3, ... , a - 1 \}$

So, suppose:

$a -1 = b \cdot \frac{x}{y}$

Consider even $a$ . Since $a \ge 1$ it follows that:

$\frac{a}{2} \le a - 1$ Which means,

$a = 2! \cdot \frac{x}{y}$

Suppose $a$ was a non-prime odd. Let $q_k = \{3, 5, 7, 9 \}$

So that:

$\frac{a}{q_k} < n-1$ Hence,

$a = q_k \cdot \frac{x}{y}$ Of which, $q_k =o_l! Since it is an integer.

This works for all but prime odd. Any feedback?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

skyletter

204 posts

skyletter

#21 h Mar 31, 2015, 2:30 AM • 2 Y

Y by Adventure10, Mango247

Click to reveal hidden text

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

skyletter

204 posts

skyletter

#22 h Mar 31, 2015, 2:33 AM • 2 Y

Y by Adventure10, Mango247

Might my answer be right?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

JBL

16123 posts

JBL

#23 h Mar 31, 2015, 1:27 PM • 2 Y

Y by Adventure10, Mango247

Neither of the preceding two solutions makes any sense to me. The first never defines any of its notation nor hypotheses. The second sentence of the second solution is obviously false: how can 5 be written as a product of factorials?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Aris1998

151 posts

Aris1998

#24 h Mar 31, 2015, 1:42 PM • 2 Y

Y by Adventure10, Mango247

The induction hypothesis was for $n = \{1, 2, ... n-1\}$ also the notation is fairly simple.

$\prod n_k! = n_1! \cdot n_2!....$

What is wrong in my (first answer)?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

JBL

16123 posts

JBL

#25 h Mar 31, 2015, 3:20 PM • 2 Y

Y by Adventure10, Mango247

You do not define any of the symbols $a, b, x, y, n_k, j_i$ , nor say what role they have in the proof. You do not say "This is a proof by induction; my induction hypothesis is ..." Basically no line in your post has enough explanation for a person to decipher it.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Aris1998

151 posts

Aris1998

#26 h Mar 31, 2015, 4:01 PM • 1 Y

Y by Adventure10

@JBL, Sorry. Will you still consider checking it please? I'll describe the symbols.

$a, b$ are positive integer numbers that aren't prime. $n_k, j_i$ are positive integers. $x, y$ are factorial products. Then I used the hypothesis thatL

$a -1 = b\frac{x}{y}$

Meaning $a-1$ is a positive integer that can be written in that form.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Zachary_Stone

1 post

Zachary_Stone

#27 h Apr 9, 2015, 12:37 AM • 1 Y

Y by Adventure10

Okay, so I transferred my original post. Sorry about that. Anyways, during my practice for the Putnam I came across problem B1 from the 2009 exam. I came to a solution quickly but I had trouble expressing it with the clarity necessary to receive a full 10 points. My professor advised me to formally write it up, and so I did, but he seemed to think it needed more rigor to satisfy the strict grading. Anyways, I'm hoping I could get some suggestions on what score my proof would receive and how I must improve it to receive full credit.

Theorem: Show that any rational number may be expressed as a quotient of products of factorials of primes.

It is sufficient to prove the theorem for any prime, since rational numbers are ratios of integers, and integers are products of primes. Now, before we proceed via infinite descent, we will introduce a brief lemma.

Lemma: Let $k$ be a prime factor of $n!$ for composite $n$ . Then, $k!<n!$ .
Proof: Since $n$ is composite, it follows that $k\leq{n-1}$ . Therefore, $k!\leq{(n-1)!}<n!$ .

With this lemma, we may now prove the theorem of interest.

Proof: Consider $p_0!$ where $p_0$ is an arbitrary prime. Now, divide $p_0!$ by the factorials of the prime factors of $(p_0-1)!$ , denoted as $p_1!, p_2!,...,p_n!$ , (note that the $p_i$ 's aren't necessarily distinct) the result is
$\frac{p_0!}{p_1!p_2!...p_n!}=\frac{p_0}{(p_1-1)!(p_2-1)!...(p_n-1)!}.$
We assert that if one repeats this process by multiplying the numerator by the factorials of the prime factors of each $(p_i-1)!$ in the denominator, and so on, that the process will terminate with each term other than $p_0$ being $2!$ , at which point we may multiply the numerator or denominator by a sufficient number of $2!$ 's to produce $p_0$ . To see why this is true, note that $p_i-1$ is composite since $p_i$ is prime. Applying our lemma, each $p_i!$ for $p_i$ a prime factor of $(p_j-1)!$ is necessarily less than $(p_j-1)!$ , therefore after each step the largest number in either the numerator or denominator has decreased, and the process must terminate as intended.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

jasperE3

11279 posts

jasperE3

#29 h Aug 12, 2021, 3:30 AM

Y by

Call a rational number good if it can be written in such a way. Also, let $p_n$ denote the $n$ th prime.

Claim: All primes are good.
We use strong induction. The bases cases $2=2!$ and $3=\frac{3!}{2!}$ are trivial. For the induction step, note that $p_n!$ can be factorized into: a product of primes strictly less than $p_n$ , and $p_n$ itself. Then dividing $p_n!$ be the product of these primes gives that $p_n$ is good.

Since the set of good numbers is closed under multiplication and division, it suffices to check $1$ , which is obviously good.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Sagnik123Biswas

420 posts

Sagnik123Biswas

#30 h May 6, 2023, 8:24 AM

Y by

We first show any prime $p$ is expressible in this format via strong induction as follows:

Base Case: We can experiment with small cases to see this is true.

Inductive Step: Observe that $p = \frac{(p)!}{(p-1)!}$ . Now we know $(p-1)! = (p-1)(p-2)….$ . Each $i$ satisfying $1 < i < p$ can be prime factorized into factors less than $p$ . From here, our inductive hypothesis tells that each of these prime factors are expressible in the desired form. Thus, we can substitute for each $i$ the appropriate rational representation via first factorizing, and then using the desired form for each prime factor. Thus completes the inductive step.

Now any rational number can have its numerator and denominator prime factorized, and we can readily substitute.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Sreemani76

88 posts

Sreemani76

#31 h Apr 19, 2024, 3:48 PM • 1 Y

Y by PRMOisTheHardestExam

Its enough to show primes can be written in such manner, we don't need to have distinct factorials, so we take $p=p! / (p-1)!$ , now decompose numerator and denominator to primes.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

sanyalarnab

930 posts

sanyalarnab

#32 h May 2, 2024, 1:32 PM

Y by

Trivial?

Attachments:

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

chakrabortyahan

380 posts

chakrabortyahan

#33 h May 6, 2024, 11:43 AM

Y by

I remember posting this earlier for sure..why did I delete it...boyos hoye jachche...
bhery izzy poroblim $\blacksquare\smiley$

Attachments:

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Rohit-2006

231 posts

Rohit-2006

#34 h Dec 22, 2024, 4:13 AM

Y by

sanyalarnab wrote:

Trivial?

Amio same method e korechi...tai r post korlam na

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

pad

1671 posts

pad

#35 h Jan 25, 2025, 3:23 AM

Y by

It suffices to show primes $p$ can be written, since for any rational we just prime factorize the top and bottom and product the quotients for each prime.

Induct on primes $p$ , with $2 = 2!$ . Note $p = p! / (p-1)!$ , and the prime factorization of $(p-1)!$ only has primes less than $p$ , which can be written by induction, so we're done.

Z K Y