Author Topic: TT's Maths Thread (Read 137785 times) Tweet Share

TrueTears · « **Reply #630 on:** January 05, 2010, 12:00:28 am »

Quote from: brightsky on January 04, 2010, 10:23:41 pm

Lemme have a crack at question 1.

First, let $X = 4444^{4444}$ .

$\because 10^4 > 4444$

$\therefore (10^4)^{4444} > 4444^{4444}$

$\implies 10^{17776} > 4444^{4444}$

...meaning that X must have less than or equal to 17776 digits in it.

Not quite, should have 17776+1 digits in it.

brightsky · « **Reply #631 on:** January 05, 2010, 12:03:11 am »

Quote from: TrueTears on January 05, 2010, 12:00:28 am

Quote from: brightsky on January 04, 2010, 10:23:41 pm
Lemme have a crack at question 1.

First, let $X = 4444^{4444}$ .

$\because 10^4 > 4444$

$\therefore (10^4)^{4444} > 4444^{4444}$

$\implies 10^{17776} > 4444^{4444}$

...meaning that X must have less than or equal to 17776 digits in it.
Not quite, should have 17776+1 digits in it.

How so?

TrueTears · « **Reply #632 on:** January 05, 2010, 12:03:56 am »

How many digits does $10^1$ have?

How many digits does $10^2$ have?

.
.
.

How many digits does $10^{17776}$ have?

brightsky · « **Reply #633 on:** January 05, 2010, 12:04:57 am »

Ahh I see. :p

TrueTears · « **Reply #634 on:** January 05, 2010, 01:21:43 pm »

Quote

3. Suppose $a,b,c,d$ are integers with $0 \le a \le b \le 99, 0 \le c \le d \le 99$ . For any integer $i$ , let $n_i = 101i+1002^i$ . Show that if $n_a + n_b$ is congruent to $n_c+n_d \pmod {10100}$ then $a=c$ and $b=d$ .

If $a \equiv b \pmod {xy}$ then that implies $a \equiv b \pmod {x}$ and $a \equiv b \pmod {y}$ . I know it works from experimentation but how to prove this?

Does it have anything to do with if $a \equiv b \pmod {n}$ iff $a \equiv b \pmod {p_i^{e_i}}$ for each $i$ in n's PPF?

kamil9876 · « **Reply #635 on:** January 05, 2010, 02:08:38 pm »

TrueTears · « **Reply #636 on:** January 05, 2010, 05:37:14 pm »

Quote from: kamil9876 on January 05, 2010, 02:08:38 pm

$xy|(a-b) \implies x|(a-b)$

kamil9876 · « **Reply #637 on:** January 05, 2010, 08:17:26 pm »

symmetry, mate.

ie: xy=yx. or simply, y can play the role of x. x isn't any more special than y. in general if n|(a-b) and k|n then k|(a-b).

let n=xy. k can be either y or x.

TrueTears · « **Reply #638 on:** January 05, 2010, 09:05:02 pm »

Quote from: kamil9876 on January 05, 2010, 08:17:26 pm

symmetry, mate.

ie: xy=yx. or simply, y can play the role of x. x isn't any more special than y. in general if n|(a-b) and k|n then k|(a-b).

let n=xy. k can be either y or x.

Ah right so we can split up the congruence into:

$n_a+n_b \equiv n_c+n_d \pmod {101}$ or $n_a+n_b \equiv n_c+n_d \pmod {100}$

Over9000 · « **Reply #639 on:** January 05, 2010, 10:01:21 pm »

Quote from: brightsky on January 04, 2010, 10:23:41 pm

Lemme have a crack at question 1.

First, let $X = 4444^{4444}$ .

$\because 10^4 > 4444$

$\therefore (10^4)^{4444} > 4444^{4444}$

$\implies 10^{17776} > 4444^{4444}$

...meaning that X must have less than or equal to 17776 digits in it.

A sum of the digits of any number $n$ must be greater or equal to $9n$ . That is to say that, A (the sum of the digits of X) must have no more than 17776*9 = 159984 digits.

It is to note here that the number with the largest sum of digits below 159984 is 99999, which has a sum of 45. From this, we can see that B (the sum of the digits of A) must have no more than 5*9 = 45 digits.

Similarly, it is to note here that the number with the largest sum of digits below 45 is 39, which has a digit sum of 12. Hence, we can say that C (where C is the sum of the digits of B) must have less than or equal to 12 digits.

Remember now the divisibility test for 9. An integer is divisible by 9 if and only if the sum of its digits (in decimal notation), is divisible by 9. Quick proof for this is seen here, $10 \equiv 1 (\mod 9), 10^2 \equiv 1 (\mod 9), ..., 10^n \equiv 1 (\mod 9)$

That is to say that:

$N = a_n10^n + ... + a_110+ a_0 \equiv a_0 + a_1 + a_2 + ... + a_n \equiv 1 (\mod 9)$ , for any natural number N.

Hence, we can see that:

$X \equiv A \equiv B \equiv C (\mod 9)$

As 4444 = 9 x 493 + 7

$\therefore 4444 \equiv 7 \mod (9)$ [1]

Now lets do some tests with the number 7.

$7 \equiv -2 (\mod 9)$

$7^2 \equiv 4 (\mod 9)$

$7^3 \equiv 1 (\mod 9)$ [2]

From [1],

$4444^{4444} \equiv \7^{4444} (\mod 9)$

$\equiv 7^{3*1481+1} (\mod 9)$

$\equiv 7^{3*1481} . 7 (\mod 9)$

From [2],

$\equiv 7 (\mod 9)$

That means that, $C \equiv 7 (\mod 9)$ . Because C > 12, hence C must be 7.

Edit: I'm still learning how to use latex properly. Why is there a huge gap in the modulos? This is just a simple solution, there must be more elegant alternatives.

http://docs.google.com/viewer?a=v&q=cache:u88H1v0EWqcJ:school.maths.uwa.edu.au/~gregg/Olympiad/1995/congrsolns.pdf+It+is+to+note+here+that+the+number+with+the+largest+sum+of+digits+below+159984+is+99999,+which+has+a+sum+of+45.+From+this,+we+can+see+that+B+%28the+sum+of+the+digits+of+A%29+must+have+no+more+than+5*

page 5

i like gundamz

TrueTears · « **Reply #640 on:** January 06, 2010, 03:47:08 am »

Quote

3. Suppose $a,b,c,d$ are integers with $0 \le a \le b \le 99, 0 \le c \le d \le 99$ . For any integer $i$ , let $n_i = 101i+(100)(2^i)$ . Show that if $n_a + n_b$ is congruent to $n_c+n_d \pmod {10100}$ then $a=c$ and $b=d$

If $n_a + n_b \equiv n_c+n_d \pmod {10100}$

Then $n_a+n_b \equiv n_c+n_d \pmod {101}$ and $n_a+n_b \equiv n_c+n_d \pmod {100}$

Thus $101a+100(2^a) +101b+100(2^b) \equiv 101c+100(2^c) +101d+100(2^d) \pmod {101}$

$101(a+b-c-d) +100(2^a)+100(2^b) \equiv 100(2^c) + 100(2^d) \pmod {101}$

$101(a+b-c-d) \equiv 0 \pmod {101}$

$\implies 2^a + 2^b \equiv 2^c + 2^d \pmod {101} \cdots [1]$

$101a+100(2^a) +101b+100(2^b) \equiv 101c+100(2^c) +101d+100(2^d) \pmod {100}$

$101(a+b-c-d) +100(2^a)+100(2^b) \equiv 100(2^c) + 100(2^d) \pmod {100}$

But $100(2^a) \equiv 100(2^b) \equiv 100(2^c) \equiv 100(2^d) \equiv 0 \pmod {100}$

$\implies 101(a+b-c-d) \equiv 0 \pmod {100}$

$\implies a+b \equiv c+d \pmod {100}$

$\implies 2^{a+b} \equiv 2^{c+d} \pmod {101} \cdots [2]$ $\text{iff a+b = c+d}$ since $q \equiv q \pmod {n}$ for any $\text{n and some integer q}$ .

$[1] \times 2^a \implies 2^{2a} + 2^{a+b} \equiv 2^{c+a} + 2^{d+a} \pmod {101}$

$\implies 2^{2a} + 2^{c+d} - 2^{c+a} - 2^{d+a} \equiv 0 \pmod {101}$

$\implies 2^{2a} + 2^{c}2^{d} - 2^{c}2^{a} - 2^{d}2^{a} \equiv 0 \pmod {101}$

$\implies 2^{2a} - 2^{a}\left(2^c+2^d\right) +2^c2^d \equiv 0 \pmod {101}$

$\text{Let} \ x = 2^a \implies x^2 -x\left(2^c+2^d\right) +2^c2^d \equiv 0 \pmod {101}$

$\implies \left(x-2^c\right)\left(x-2^d\right) \equiv 0 \pmod {101}$

$\implies \left(2^a-2^c\right) \equiv 0 \pmod {101} \ \text{or} \ \left(2^a-2^d\right) \equiv 0 \pmod {101}$

$\implies 2^a \equiv 2^c \pmod {101} \ \text{or} \ 2^a \equiv 2^d \pmod {101} \ \text{iff a = c or a = d}$

$\text{If a = c} \ \implies 2^b \equiv 2^d \pmod {101} \ \text{iff b = d}$

$\text{Thus a = c and b=d}$

kamil9876 · « **Reply #641 on:** January 06, 2010, 12:30:14 pm »

I was thinking of another solution earlier:

I will steal two of your formulas as they are quite easy to derive:

Quote

$2^a + 2^b \equiv 2^c + 2^d \pmod {101} \cdots [1]<br />$

$a+b \equiv c+d \pmod {100} \cdots [2]$

The solution relies on the fact that $2^x \equiv 1 \mod 101$ iff $x\equiv 0 \mod 100$ . The verification of this requires some computation, (in fact by fermat's little theorem the smallest solution must be a divisor of 100, therefore it suffices to show that no other divisors, $d$ ,give $2^d\equiv 1$ .

Ie: we have established that the order of 2 mod 101, is 100.

Now we have:
$<br />2^a-2^c\equiv 2^d-2^b \mod 101$

$2^c(2^{a-c}-1)\equiv 2^b (2^{d-b}-1) \mod 101$ [3]

Now here is the crux move. Consider the following two statemnts:

a.) $a\equiv c \mod 100$
b.) $b\equiv d \mod 100$

Then either BOTH are true, or BOTH are false. We cannot have one without the other. This is a consequence of [2].
If both are true we are done(since this would imply $a=c$ and $b=d$ ), therefore suppose both are false. (hypothesis i)

then the factors $(2^{a-c}-1)$ and $(2^{d-b}-1)$ are both not congruent to 0 modulo 101, since $a-c \neq 0$ and $d-b \neq 0$ by hypothesis i.

Moreover $a-c=d-b \mod 100 \implies (2^{a-c}-1)\equiv (2^{d-b}-1) \mod 101$ but both factors are not 0 modulo 101 hence they are relatively prime to 101 because 101 is prime. Hence we can cancel them off from both sides in [3] to get:

$2^c \equiv 2^b \mod 101 \implies c \equiv b \mod 100$

which implies $d \equiv a mod 100$ . Hence $c=b$ and $d=a$ in this case as required.

hence the theorem is true assuming $2^x=1 mod 101$ has x=100 as the smallest positive solution, which can be verified by computation.

This doesn't seem like such a good putnam problem, i could solve it with some boring algebra (which i let you do for me) followed by some pretty obvious theorems in first year uni modular arithmetic/group theory, not to mention the ugly computation that awaits in verifying that 100 is indeed the order of 2 modulo 101.

TrueTears · « **Reply #642 on:** January 06, 2010, 12:32:17 pm »

Awesome kamil, do you know if my proof is valid or not?

kamil9876 · « **Reply #643 on:** January 06, 2010, 12:37:40 pm »

Yeah it is. Though I know it also assumes in many instancse, like my proof, that the order of 2 modulo 101 is 100.

zzdfa · « **Reply #644 on:** January 06, 2010, 02:47:22 pm »

nice. so the important part was ensuring the numbers were <100 so that $x \equiv y \mod 100 \iff x=y$

Search the forums now!

We have moved!

Author Topic: TT's Maths Thread (Read 137785 times) Tweet Share

TrueTears

Re: TT's Maths Thread

brightsky

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

brightsky

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

kamil9876

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

kamil9876

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

Over9000

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

kamil9876

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

kamil9876

Re: TT's Maths Thread

zzdfa

Re: TT's Maths Thread

Recent Posts

User:
Password: