Find The Value Of The Floor Function

Algebra Level 5

Find $\left\lfloor \frac{33}{29}\times \frac{41}{37}\times \frac{49}{45}\times \cdots \times \frac{2009}{2005}\times \frac{2017}{2013} \right\rfloor .$

Details and assumptions

The function $\lfloor x \rfloor: \mathbb{R} \rightarrow \mathbb{Z}$ refers to the greatest integer smaller than or equal to $x$ . For example $\lfloor 2.3 \rfloor = 2$ and $\lfloor -5 \rfloor = -5$ .

The answer is 8.

5 solutions

A Brilliant Member
Jan 7, 2014

In this solution, we use telescoping series & inequalities to approach the problem. The motivation is that: we cannot calculate the fraction exactly at hand, & that is not asked for. We can approximate it, at best, to get an exact floored value. We will make the required value less than and greater than 2 fairly close values, which are easy to calculate, since they telescope. This is fairly a standard technique in such a problem involving a fraction whose numerators & denominators are in A.P.

Note that $I = \frac{33}{29} \cdot \frac{41}{37} \cdot \frac{49}{45} \cdots \frac{2009}{2005} \cdot \frac{2017}{2013}$

$< \frac{29}{25} \cdot \frac{37}{33} \cdot \cdots \frac{2013}{2007}$ .

Multiplying $I$ to both sides we see that the right side telescopes to $\frac{2017}{25}$ , thereby $I < \sqrt{\frac{2017}{25}}$ .

Similarly, $I > \frac{37}{33} \cdot \frac{45}{41} \cdots \frac{2013}{2009} \cdot \frac{2025}{2017} \Rightarrow I^2 > \frac{2025}{29} \Rightarrow I > \sqrt{\frac{2025}{29}}$ .

Using the above estimates, we see: $\lfloor I \rfloor = \boxed{8}$ .

nice one singh

Amritpal Singh - 7 years, 4 months ago

a good one

Malay Pandey - 7 years, 3 months ago

Santanu Banerjee
Jan 3, 2014

That's Cheating

Let $A = \frac {33}{29} \times \frac {41}{37} \times \ldots \times \frac {2017}{2013}$ and $B = \frac {37}{33} \times \frac {45}{41} \times \ldots \times \frac {2013}{2009}$

Notice that, by comparing the individual terms, we have $\frac {29}{25} \times B > A$ and $\frac {2021}{2017} \times B < A$

So we have:

$B \times \frac {2021}{2017} < A < \frac {29}{25} \times B$

$AB \times \frac {2021}{2017} < A^2 < \frac {29}{25} \times AB$

$\frac {2021}{29} < A^2 < \frac {2017}{25}$

$69 < A^2 < 81$

$8 < A < 9$

Hence $\lfloor A \rfloor = \boxed{8}$

Kyle Dulay - 7 years, 5 months ago

I was waiting for an answer like this...thanks Kyle.

I had a solution with the Gamma-function $\Gamma(x)$ .

$\large \frac{33}{29} \times \frac{41}{37} \times \ldots \times \frac{2017}{2013} =$ $\large \frac{( \frac{2017}{8})! / ( \frac{25}{8})!} {( \frac{2013}{8})! / ( \frac{21}{8})!} =$ $\large \frac{( \frac{2017}{8})! ( \frac{21}{8})!} {( \frac{2013}{8})! ( \frac{25}{8})!} =$

$\large \frac{ \Gamma(1+\frac{2017}{8}) \Gamma(1+\frac{21}{8})} {\Gamma(1+\frac{2013}{8}) \Gamma(1+\frac{25}{8})} \normalsize = 8.63571857...$

with $\Gamma$ -functions calculated using Mathematica.

Ronald Overwater - 7 years, 5 months ago

Beautifully presented.....awesome!

Eddie The Head - 7 years, 5 months ago

Well said, Kyle. This is basically what I did (except I was less formal).

Peter Byers - 7 years, 5 months ago

How did u managed to get

$\frac{2021}{29} < A^2 < \frac{2017}{25}$

from $AB \times \frac{2021}{2017} < A^2 < \frac{29}{25} \times AB$ ? I know you multiplied both sides by $\frac{2017}{29}$ , but what about the $AB$ ?

Fan Zhang - 7 years, 5 months ago

$AB = (\frac {33}{29} \times \frac {41}{37} \times \ldots \times \frac {2017}{2013})(\frac {37}{33} \times \frac {45}{41} \times \ldots \times \frac {2013}{2009})$

$AB = \frac {33}{29} \times \frac {37}{33} \times \frac {41}{37} \times \frac {45}{41} \times \ldots \times \frac {2013}{2009} \times \frac {2017}{2013}$

$AB = \frac {2017}{29}$

I didn't multiply $\frac {2017}{29}$ to the leftmost and rightmost sides (which I can't do without also multiplying the middle part by it), but rather I substituted it for $AB$ .

Kyle Dulay - 7 years, 5 months ago

We can find upper bound by AM-GM $\prod_{i = 3}^{251} \frac{8i + 9}{8i + 5} \leq \frac{\left(\sum_{i = 3}^{251} \frac{8i + 9}{8i + 5}\right)^{249}}{249^{249}} = \frac{\frac{1}{2^{249}} \cdot \left(498 + \psi\left(\frac{2021}{8}\right) - \psi\left(\frac{29}{8} \right )\right)^{249}}{249^{249}} \approx 8.88$ where $\psi(z)$ is Digamma function.

Jan J. - 7 years, 5 months ago

What is that?

A Brilliant Member - 7 years, 5 months ago

lol

Muhammad Shariq - 7 years, 5 months ago

did anybody has manual solution

Ben will - 7 years, 5 months ago

Check Kyle's......

Eddie The Head - 7 years, 5 months ago

Well,here's a method,but it doesn't give us 8.[ EDIT: Thanks to A Joshi for spotting a mistake.I have corrected it,but this unfortunately gives an worse approximation]

There are 248 expressions in the numerator and 248 in the denominator.All the fractions are of the form $\dfrac{x+4}{x}$ .Since the terms aren't too big but there are way too many terms,we can approximate $\dfrac{x+4}{x}$ as $1.01$ . Therefore,the whole expression becomes

$1.01\cdot 1.01........1.01=(1.01)^{248}$

which is approximately $11.79$ .This gives us something close,but not the answer we are looking for.I am sure this method can be improved a bit to give us a closer value.

Rahul Saha - 7 years, 5 months ago

There are not 24 but 248 expressions !

A Joshi - 7 years, 5 months ago

Thank you,I have edited my earlier comment and made some suitable changes.Unfortunately,this gives us an worse approximation.

Rahul Saha - 7 years, 5 months ago

Well, considering $\lim_{x \to 0} \frac{x+4}{x} = \infty$ and $\lim_{x \to \infty} \frac{x+4}{x} = 0$ I don't think this is a good way to estimate.

Hao Tang - 7 years, 5 months ago

Your second limit is incorrect - $\lim_{x \rightarrow \infty} \frac{x+4}{x}=\lim_{x \rightarrow \infty} 1+\frac{4}{x}=1$ .

Muhammad Shariq - 7 years, 4 months ago

Kyle, How did you get that $\frac {29}{25} \times B > A$ ? (and the second inequality)

Elliot Gorokhovsky - 7 years, 5 months ago

We have the ff. inequalities:

$\frac {29}{25} > \frac {33}{29}$

$\frac {37}{33} > \frac {41}{37}$

until

$\frac {2013}{2009} > \frac {2017}{2013}$

Multiply all the left-hand sides and all the right-hand sides of the inequalities to get:

$\frac {29}{25} \times \frac {37}{33} \times ... \times \frac {2013}{2009} > \frac {33}{29} \times \frac {41}{37} \times ... \times \frac {2017}{2013}$

$\frac {29}{25} \times B > A$

The proof for the second inequality is similar.

Kyle Dulay - 7 years, 5 months ago

Thanks!

Elliot Gorokhovsky - 7 years, 5 months ago

Why did u multiply by A ?

Ravishankar Shukla - 7 years, 5 months ago

Forretrio Wong
Jan 3, 2014

By estimation with the claim $\frac{33}{29}\times \frac{41}{47}\times ... \times \frac{8n+9}{8n+5} \sim O(\sqrt{n})$ .

Notice that $\frac{n+8}{n+4}\frac{n+4}{n} = (\frac{n+4}{n})^2 + O(n^{-2})$ but can we do better?

Consider $\frac{n+8+k}{n+k} - (\frac{n+4}{n})^2 = \frac{(16+8k)n+16k}{n^2(n+k)}$ so that if we set $k=-2$ we get an error term of $O(n^{-3})$ . When we multiply the error term the degree is increased by 2 since we have $n^2$ such error term.

$\prod_{i=3}^{n} \frac{8i+9}{8i+5} = \prod_{i=3}^{n} \sqrt{\frac{8i+11}{8i+3}}+O(i^{-3})$

$= \prod_{i=3}^{n} (\sqrt{\frac{8i+11}{8i+3}}+O(i^{-3/2})) = \sqrt{\frac{8n+11}{27}}+O(\sqrt{n})$

So that $[\frac{33}{29} \times \frac{41}{37} \times ... \times \frac{8n+9}{8n+5}]\approx [\sqrt{\frac{2019}{27}}] = \boxed {8}$

Please note that it still yield error of order $\sqrt{n}$ that is very bad for such estimation but it is rather small (about $\sim 0.0002603 \sqrt{n}$ ) so it can be neglected for such a small $n$ .

Should be $\sqrt{\frac{8i+11}{8i+3} + O(i^{-3})}$ , sorry.

Forretrio Wong - 7 years, 5 months ago

"#include <iostream>

int main()

{

double x = 1;
for(double i = 33; i<=2017; i+=8)

{ x=x*(i/(i-4)); }

cout << x;

system("pause"); return 0;

}

Olexandr Zavalistyi - 7 years, 5 months ago

haha nice way of doing it

Satya Teja Chikatla - 7 years, 4 months ago

i also did it in the same way

Priyesh Pandey - 7 years, 2 months ago

Can you explain why it is O(sqrt (n)) ??

Eddie The Head - 7 years, 5 months ago

It's because we have $n^2$ such error terms so we multiply $n^2$ to the error term inside the product. I used $i$ inside but this is also related to $n$ the number of terms so it becomes $O(\sqrt{n})$ .

If you are talking about the initial claim, it follows from the above calculation that the final result is about a constant times $\sqrt{n}$ . However, I must admit that I didn't 'prove' that it is really asymptotically equal to $O(\sqrt{n})$ . To do this, we need an even better estimate, but that would make our calculation inconvenient.

Forretrio Wong - 7 years, 5 months ago

include < iostream > using namespace std;

int main() { double x = 1; for(double i = 33; i<=2017; i+=8) { x=x*(i/(i-4)); } cout « x; system("pause"); return 0; } so answer is [8,63572]=8 :)

Александр Поддубный - 7 years, 5 months ago

Ron van den Burg
Jan 18, 2014

Let $A=\frac {37.45...2021}{33.41...2017} < B = \frac {33.41...2017}{29.37...2013} < C = \frac {29.37...2013}{25.33...2009}$

Thus $A.B < B.B < C.B$ . Now $A.B = \frac {2021}{29}$ and $C.B=\frac {2017}{25}$ . The result follows from $8 < \sqrt {A.B} < B < \sqrt {C.B} <9$ .

Budi Utomo
Jan 3, 2014

(1,25)^249 = 8, ... So, the answer is 8

WHY 1.25

MNS Muzahid - 7 years, 5 months ago

Ya, how did you get that?

Elliot Gorokhovsky - 7 years, 5 months ago

ok.. i use assumtion that (33/29)...(2017/2013) = 1,12 ...(249)...1,001 = | (1,25)^249 | = 8. [ n = 249]

Budi Utomo - 7 years, 5 months ago

(1.25)^249 = 1.35x10^24....so not between 8 and 9!

(1.00839)^249= 8.008, (1.00886)^249 = 8.993

Ronald Overwater - 7 years, 4 months ago

India me esa nahi chalta hai

Purvam Modi - 7 years, 3 months ago

If we recast the product in the form : (1+4/29)(1+4/37)...the natural log could be expanded in taylor series for ln(1+x) which can be approximated by the first term x resulting in a series of the form 4/29 + 4/37 +......248 terms. . I was also wondering if we could approximate the sum involved by an integral of the form : 4*$ dx / (29+8x) with x ranging from 1 to 248. The difference between the above integral and the discrete sum would most possibly be less than 1 , in fact it may be even lesser than euler's constant which is approximately 0.5

Sundar R - 7 years, 3 months ago

Find The Value Of The Floor Function

The answer is 8.

5 solutions

0 pending reports