Question

Some Olympiad-like problems for fun, mates.

Answer 1

Prove that \(2222^{5555} + 5555^{2222}\) is divisible by 7.

What are the two last digits of \((((7^7)^{7})^7)...\) where the 7th power is taken 1000 times.

Answer 2

lol nice

Answer 3

And prove that for any integer n, the following inequality holds:\[(\frac{n}{e})^{n} < n! < n(\frac{n}{e})^n\]

All problems are taken from old USSR olympiads :-)

Answer 4

the first one involves sequences?

Answer 5

My solution (if it's correct) does not involve sequences, but nothing is against it. If you can do it, kudos to you :-)

Answer 6

The first two I would probably use modular arithmetic, but that might not be the fastest way.

Answer 7

people don't look in the meta-math section anymore :(
some of these questions may do well there, and I encourage those of you who like the kinds of problems to check that section, as it contains more of these types of problems.
I, for one, and terrible at this kind of thing :S

Answer 8

@FoolForMath "olympiad" problems!

Answer 9

From these 3, I could only do the first and the third, but I don't know if they are correct. The second is an old friend of mine that I can't understand how to solve :-(. And thanks for the heads up @TuringTest

Answer 10

@FoolForMath and @asnaseer are great at this kind of stuff

Answer 11

Let's start with 2 then :)

We know that \[7^4 =2401 \equiv 1\mod 100\]Thus, we need to find \[7^{1000} \equiv (-1)^{1000} \mod 4\]Since \(-1\) to any even power is 1, this is equal to 1. Since it's 1, the answer should be given by \(7^1 \equiv 7\mod 100\). There fore, I think the last two digits must be 07.

Answer 12

We need to find \(7^ {1000} \)?

Answer 13

I thought it's \(7 \times 7 \times \times 7 \cdots 1000 \) times

Answer 14

In the index of-course.

Answer 15

Is that not \(7^{1000}\)? Multiplying 7 by itself 1000 times?

Answer 16

That makes sense so far. :-). Is it 07 because it's 7 mod 100? Sorry for my not so great understanding of modular arithmetic, that's why I guess I never answered it, haha.

Answer 17

That would be exactly why it's 07.

Also, for the third problem, how is it true for \(n=1\)? Are we using \(e\) as the base of the natural logarithm?

Answer 18

I thought about that also, was double checking the problem. That's how it's written. I don't think it holds for 0 also, but I don't know. Maybe a typography error and it's meant a \(\ge \le\) instead of strictly less.

Answer 19

For the first one,

Lets find the individual modulo 7 first,

Using Euler Totient,

\(2222^6 \equiv 1 \pmod 7 \implies 2222^{5555} \equiv 2222^{5}\equiv 5 \pmod 7\)

Similarly,

\(5555^{2222} \equiv 5555^{2} \equiv 2 \mod 7 \)

Summing them up we will get \(2+5 \equiv 0 \pmod 7 \)

Answer 20

For the second one is it tetration, still I am not sure how "\( (((7^7)^{7})^7)... \) where the 7th power is taken 1000 times" becomes \(7^{1000} \) ?!

Answer 21

@FoolForMath That's a cute solution. Cleaner than mine, for sure :-). Thanks for it.

Answer 22

\[(((7^7)^7)^7)^{...7}\]Where there are 1000 sevens in the exponent becomes \[\large 7^{7\cdot7\cdot7\cdot...\cdot7}=7^{7^{1000}}\]Sorry if that was a little unclear.

Answer 23

Oh @KingGeorge I assumed something else.

Answer 24

Back to 3, though, I'm now pretty sure \(e\) is just some number since if it were the base of the natural log, 1, 2, 3, 4 all don't work.

Answer 25

It is important to note that \(2222 \equiv 3 \pmod 7 \) and \( 5555 \equiv 2^2 \pmod 7 \), so my solution is not that calculative as it might appear.

Answer 26

The worst part is that it's actually stated below the problem:
"where e = 2.718... is the limit of (1 + 1/n)^n as n -> infinity" I think they meant that after some integer n, the inequality holds, so instead of any it should be some (?).

Answer 27

It seems to start being true at \(n=7\).

Answer 28

too much intellectual mass debation

Answer 29

it hurts >.< lol

Answer 30

For the first one, my solution is the following:\[2222^{5555} + 5555^{2222} = (2222^{5555} + 4^{5555}) + (5555^{2222} + 4^{2222}) - (4^{5555} - 4^{2222})\]Consider the three terms in the parenthesis. The first one is divisible by 2226 = 7*318, therefore it's divisible by 7 (a^n + b^n is divisible by a + b if n is odd). Similarly, the second term is divisible by 7 because it's divisible by 5551 = 7*793 (a^n - b^n is divisible by a - b). The third term can be written as\[4^{2222}(4^{3333} - 1) = 4^{2222}(64^{1111} - 1)\] That is divisible by 7 because it's divisible by 63.

Answer 31

hax0r

Answer 32

Minor typo, I meant:\[(5555^{2222} - 4^{2222})\]

Answer 33

For the most part, I like that solution. The only thing I don't like about it that you have to know that 7 divides both 2226 and 555.

Answer 34

*5551

Answer 35

Yeah, that's my problem with it also. I think using modular arithmetic may be easier. I think the third one is just plain faulty by the book.

Answer 36

Well, with the modular arithmetic you still need to know 2222 mod 7 and 5555 mod 7 which is no easier. It's still fairly fast using long division, but there's no real advantage to your method except using slightly less pencil.