Author Topic: Fun questions :) (Read 115242 times) Tweet Share

zzdfa · « **Reply #255 on:** August 10, 2009, 11:57:35 pm »

lawl well done guyz

i had some really messy shit with binomial expansion and stuff, still cbf working out the details
my mistake was to immediately write it in the form x^2-kx+1=0, $x=\frac{k\pm\sqrt{k^2-4}}{2}$ for some integer k
and then I was like aha! $x^{-1}=\frac{k\mp\sqrt{k^2-4}}{2}$

and then i was trying to show that $\left(\frac{k+\sqrt{k^2-4}}{2}\right)^{\!n} +\left(\frac{k-\sqrt{k^2-4}}{2}\right)^{\!n}$ is integer.

i've developed this really bad habit of not bothering to try special cases first to get a feel for the problem =(
edit: oic it's the same as kamil's first solution but with even more complication....
how long do you get to do the 3 questions in VNMO?

kamil9876 · « **Reply #256 on:** August 11, 2009, 12:03:09 am »

lol whatever you want its just a normal thread. Just gave the name as a parody

Quote

i've developed this really bad habit of not bothering to try special cases first to get a feel for the problem =(

Yeah I found that does help with problem solving, though I really like some of your jumps at generalising stuff, you had some nice solutions before. (especially with that fraction equation problem, there I used trying special cases and came up with a less neat way of finding the solution and then giving a proof).

zzdfa · « **Reply #257 on:** August 11, 2009, 12:03:57 am »

lmao i thought it was vietnam national mo

kamil9876 · « **Reply #258 on:** August 11, 2009, 12:05:12 am »

hahaha that's what my mates think I'm talking about when I mention VN(actually refering to Vcenotes) in a convo sometimes.

Also: when I was a noob here once and saw this in a post "VN community get's the highest ENTER scores" I thought there were some claims of racial superiority here.

kamil9876 · « **Reply #259 on:** August 23, 2009, 05:32:26 pm »

$a$ and $b$ are integers greater than one such that $gcd(a,b)=1$

Prove that:

$\sum_{i=1}^{b-1} \left \lfloor{\frac{ia}{b}} \right \rfloor=\sum_{i=1}^{a-1} \left \lfloor{\frac{ib}{a} \right \rfloor$

and find the value of this common sum.

Tip:Try be creative with this one and try the unexpected.

zzdfa · « **Reply #260 on:** August 23, 2009, 07:29:05 pm »

$\text{Clearly, } \gcd(a,b) = 1 \implies \left\lfloor\frac{a}{b}(i-1)\right\rfloor<j\leq \left\lfloor\frac{ai}{b}\right\rfloor \rightarrow \left\lfloor\frac{bj}{a} \right\rfloor = i-1$ ∎

better now?

kamil9876 · « **Reply #261 on:** August 23, 2009, 08:33:29 pm »

Quote from: zzdfa on August 23, 2009, 07:29:05 pm

$\gcd(a,b) = 1 \implies \left\lfloor\frac{a}{b}(i-1)\right\rfloor<j\leq \left\lfloor\frac{ai}{b}\right\rfloor \rightarrow \left\lfloor\frac{bj}{a} \right\rfloor = i-1$ ∎

I don't understand it :buck2:

Proof by intimidation?

kamil9876 · « **Reply #262 on:** August 23, 2009, 08:57:33 pm »

zzdfa · « **Reply #263 on:** August 23, 2009, 09:48:23 pm »

Set $A(i)=\left\lfloor\frac{a}{b}i\right\rfloor$ and $B(i)=\left\lfloor\frac{b}{a}i\right\rfloor$

This is true for all $i\leq b$ :
if $A(i-1)<j\leq A(i)$ then $B(j) = i-1$
if you're having trouble with the intuition behind the above, try seeing why this is true first:

$j\leq A(i) \rightarrow B(j) \leq i-1$

We can see that as j ranges over 1,2,3...,a-1,
$A(i)-A(i-1)$ gives the number of times $B(j)=i-1$ , for each $i\leq b$
call this value k(i).
so now we got:

$\sum_{j=1}^{a-1}B(j) =(a-1-A(b-1))(b-1)+ \sum_{i=1}^{b-1}k(i) (i-1)\$

from there, you can do the diagonally thingy

Quote from: zzdfa on July 18, 2009, 07:49:52 pm

[img]http://img23.imageshack.us/img23/3407/sumsz.jpg[/img

SEE HOW AWESOME SIGMA NOTATION IS!!!

to show that the above equals
$ (a-1)(b-1)-\sum^{b-1}_{i=1}A(i)$

hence

$(a-1)(b-1)=\sum^{b-1}_{i=1}A(i)+\sum_{j=1}^{a-1}B(j)$

ok so it seems like I haven't proved that S_a = S_b

its probably hidden in there somewhere, but im too tired atm to see

dcc · « **Reply #264 on:** August 23, 2009, 09:52:24 pm »

any proof which uses 'clearly' in it is destined to fail

kamil9876 · « **Reply #265 on:** August 23, 2009, 11:55:46 pm »

my proof:

if x and y are two natural numbers then $\left \lfloor \frac{x}{y} \right \rfloor$ is equal to the number of multiples of y less than or equal to x.

Take all the numbers $ai$ and $bj$ for the all the i<b-1 and j<a-1 and put the former in a set, A and the latter in a set B. let $S_a=\sum_{i=1}^{b-1} \left \lfloor{\frac{ia}{b}} \right \rfloor$ and $S_b=\sum_{i=1}^{a-1} \left \lfloor{\frac{ib}{a} \right \rfloor$ .

To compute $S_a$ what we need to do is take a number from set A and count how many numbers there are in set B that are less than that number (it cannot possibly be equal to some number in B since gcd(a,b)=1). Do this for all numbers in set A and then add the counts together. (test this algorithm out yourself; perhaps by putting all the numbers from both sets on one number line and labelling the ones from A and B differently).
Similair procedure for S_b

Now we see that what we are actually doing is taking every possible pair of the form (ai, bj) and deciding whether it contributes to $S_a$ or S_b. This is decided by whether ai<bj (remember, cannot possibly be equal so one is going to be bigger than the other).

Now lets call C the set of pairs (ai,bj) that contribute to $S_a$ (that is, ai>bj), and D the set of pairs (ai,bj) that contribute to S_b (that is, aj<bj).

We wish to prove that C and D have the same number of elements. The proof of this was inspired by a lemma that came from plotting the ai's and bj's on cartesian plane, but I'll spare you the boredom.

If $a(b-i)<b(a-j)$ then $ai>bj$ and the converse is true.

What this means is that if (ai, bj) is in C then (a(b-i), b(a-j)) is in D and vice versa.

This means that each pair in C has a unique partner in set D, and each pair in set D has a unique partner in set C. So the two sets have same number of elements, in other words there is a bijection between the two.

Exenstion: Find the value of these sums in terms of a and b.

zzdfa · « **Reply #266 on:** August 24, 2009, 12:37:36 am »

(a-1)(b-1)/2

i realized that in my proof, you actually get (a-1)(b-1) = s_a+s_b

alternatively take the cartesian product of your two sets A and B and divide by 2.

kamil9876 · « **Reply #267 on:** August 24, 2009, 12:58:33 pm »

kamil9876 · « **Reply #268 on:** August 28, 2009, 08:54:24 pm »

I don't like inequalities much but...

prove that for all $a,b,c,d \in R^+$ such that $abcd=1$ :

$6 \geq ab + ac + ad + bc + bd + cd$

and hence generalise the inequality for $a_1, a_2.... a_{2n} \in R^+$

/0 · « **Reply #269 on:** August 28, 2009, 09:16:16 pm »

am gm

$\frac{ab+ac+ad+bc+bd+cd}{6} \geq \sqrt{abacadbcbdcd}=\sqrt{a^3b^3c^3d^3} = (abcd)^\frac{3}{2}=1$

$ab+ac+ad+bc+bd+cd \geq 6$

Search the forums now!

We have moved!

Author Topic: Fun questions :) (Read 115242 times) Tweet Share

zzdfa

Re: Fun questions :)

kamil9876

Re: Fun questions :)

zzdfa

Re: Fun questions :)

kamil9876

Re: Fun questions :)

kamil9876

Re: Fun questions :)

zzdfa

Re: Fun questions :)

kamil9876

Re: Fun questions :)

kamil9876

Re: Fun questions :)

zzdfa

Re: Fun questions :)

dcc

Re: Fun questions :)

kamil9876

Re: Fun questions :)

zzdfa

Re: Fun questions :)

kamil9876

Re: Fun questions :)

kamil9876

Re: Fun questions :)

/0

Re: Fun questions :)

Recent Posts

User:
Password: