wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> The anguish of a student in love (a math student) 
        
(Message started by: MitkoS on Mar 30^th, 2010, 11:44pm)

Title: The anguish of a student in love (a math student)
Post by MitkoS on Mar 30^th, 2010, 11:44pm

A math student fell in love in the beautiful and rich princess of the local realm. But her father (the king) was rigid and slightly evil. He hated his accountants because they lied to him a little bit. He hated also the software engineers because his computer systems regularly go down. He had a kind of phobia of these people.
The princess had just grown up enough to start looking for partners. The king had just announce the news that in three days there will be an exam for a spouse candidates of his daughter and the exam was to be in math.
Our student was firstly happy but then he started wondering if he had to go because the king, tortured by his phobia, had defined the following criteria:

- The number N between 8000 and 9999 will be given;
- The last NON-zero digit of the number N! (factorial of N) should be found
- The candidates can use only a pencil and sheets of paper, no electronic calculators, no laptops
- An hour will be given for solving and calculating
- The one who is not able to calculate correct the digit, will be hanged
- The one who answers correctly first, wins the princess and the realm

Our student had three days to decide whether to go to the exam or not.
Do you think he will go? … He is a famous excellent grader, but will this help him in his decision to go there?

--------------
NOTES
1. Clarification:
8! = 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 = 40320
The "last NON-zero digit" of 40320 is 2
2. My English is not perfect, but I hope, the text in this riddle is understandable

Title: Re: The anguish of a student in love (a math stude
Post by towr on Mar 31^st, 2010, 2:37am

[hide]The simplest approach I've found is the one given in the description of sequence [/hide][hide]A008904[/hide] (http://www.research.att.com/~njas/sequences/A008904)[hide] in the on-line encyclopedia of integer sequences: write n in base 5, then multiply d_i!*2^i*d_i modulo 10 (where d_i is the ith digit from the back counting from 0), finally multiply by 6 and take the last digit.
For example, n = 9576₁₀ = 301301₅, gives (1!*2^0*1) * (0!*2^1*0) * (3!*2^2*3) * (1!*2^3*1) * (0!*2^4*0) * (3!*2^5*3) * 6 = 6 (mod 10)
[/hide]

Title: Re: The anguish of a student in love (a math stude
Post by MitkoS on Apr 16^th, 2010, 11:14pm

It was my first post in Wu :: forums, I was so excited, so I forgot to tell that the evil king stopped the electricity in the kingdom immediatelly after he announced the news for the exam. ;D

And you have three days to prepare yourself for the exam without any Internet access. Of course, if you know in advance some facts concerning this matter, you can take a pencil and sheets of paper and prove these facts to yourself. But if you don't know anything in advance, you have three days to find some method to pass the exam with the same conditions: no Internet access, only pencil and sheets of paper. Your target is to prove yourself that the method you will use in the exam is absolutelly correct and you will not be hanged

Title: Re: The anguish of a student in love (a math stude
Post by MitkoS on Apr 27^th, 2010, 2:49pm

This riddle was published simultaneously in a local math forum and in a local folum for logic and fun at 08-Jan-2010. The next evening (09-Jan-2010) the author posted in these forums he has made a wrong conclusions and he doesn't has a solution for this riddle. And he will be hanged if he doesn't find a solution for the next two days.
But the next evening (10-Jan-2010) a correct mathematical solution was found and developed in the local logic forum. (It was a teamwork - the author and his friend.)
In the local math forum, this riddle was unsolved.

Title: Re: The anguish of a student in love (a math stude
Post by singh_sukhu on Jul 21^st, 2010, 7:09am

The first trick to use when N is very large is to group up numbers
with the same last digits. Eg for 1000000!, after dividing out all of
the 5s from 1000000!, you get the product of all numbers NOT divisible
by 5 up to 1000000, times the product of all numbers NOT divisible by
5 up to 200000, times the product of all numbers NOT divisible by 5 up
to 40000, and so on to 8000, 1600, 320, 64, 12, and 2 (for the same
reason that the number of 5s in 1000000! is 200000 + 40000 + 8000 +
1600 + 320 + 64 + 12 + 2). But the last 3 digits of the product of
all of the numbers from 1 to 999 not divisible by 5 is the same as the
last three digits of the product of all of the numbers from 1001 to
1999 not divisible by 5, and so on. Figure out what this number is,
and then you can do blocks of 1000 numbers at once. If this number is
M, then you get

M^1000 * M^200 * M^40 * M^8 * M = M^1249

times the smaller products (up to 600, 320, 64, 12, and 2) which
require less work. Of course, computing the last 3 digits of M^1249
can be done quickly with modular exponentiation.

Actually, you should do all of this mod 5^3 (rather than 10^3), so
that you can also divide by 2^249998 mod 5^3. Then, since the number
of 2s in 1000000! is a lot more than 3 more than the number of 5s, you
can divide by 2^3 mod 5^3, and then multiply the result by 2^3 mod
10^3 to get the last three digits of 1000000!/10^249998.

More methods at :
http://www.research.att.com/~njas/sequences/A008904
http://www.mathpages.com/home/kmath489.htm