Archive - Mar 8, 2008

Date

After 14 hours of Moody's Mega Math Challenge

Chao: Do we want to take picture of the team and stuff or something?
Basically Everyone: No one want to remember this night.

Aww... I wish there is a picture so I can remember this.
But I have a picture of the place after clean up.

I had one of the most fun time ever!
The feeling of deadline coming... the intense... it's like I'm playing extreme sports!
Moody's Mega Math Challenge, The M3 challenge, is a contest of 3-5 people teams using 14 hours to complete a mathematical modeling problem. I can't disclose the problem yet, some people have to take it tomorrow.
We used all 14 hours to work on the problem. lunch = pizza.
Intense! we had no experience in it and we still manage to get a 13 page stuff ready. In the end we become so frustrate. Everyone laughs at everything. Like have something to do with tiredness.

Some of the best quotes:

Peter: Why do you have a file called "evilplan" in your flash drive?
Chao: Don't open it! Just don't open it, it's too evil for this contest.

Chao: Corns can grow in space.

Chao: Following the current trend, questions getting harder each year. Next year, the question are going to involve giving a random person's name, we have to model a scenario to find the exact location of where he is at a certain time period exact to 1 ms.

7:01 am
Katie: I actually know these stuff. I'm glad we have this question.
around an hour later...
Katie: I'm totally NOT doing this next year.

Qing: Are you restating the questions?
Chao: No
Qing: Do it!

Chao: I learned so much from these data, some countries I never seen before, like Turkey.

Qing: Do you think they will really read all the sources? Would they really get bothered to check 200+ entries?
Chao: What are you talking about? They are mathematicians. They have no life.

Qing: Feels like we did nothing for the entire day.
Katie: We did something, not like we are talking about our hair or something.
Chao: My hair is great today, but I need better conditioner.
Peter: Now we can officially announce we talked about hair.

Peter: Corn don't just grow in space.

Chao: US should just conquerer the world, so everyone speaks the same language.

Chao: I hate math modeling, it's about using poor math technique on real life. I hate real life.

Katie: If Ms Fraser ask me about this on Monday, "how was it?"
Qing: With that smile.
Katie: "I don't even want to talk about it"

Peter: You model basically says land come from no where.
Chao: Following the assumption, this model is complete correct.
Peter: By creating wormholes in space.

Peter: We could just assume that we are always right.

Chao: I can sabotage the other team by giving them the model I come up with.

Chao: We have to prepare for the presentation since we are totally winning this.
Qing: Are we having the assumption that we are better than everyone else?
Peter: If we win, we can make up stuff.
Chao: Yeah, about that butterfly creates wormholes so the physical world can be twisted and port land from other planets. I can find it for ya. Oh, it's not there, nvm, wikipedia delete it.

Chao: What does a Chinese cat eat? They get eaten by Chinese. Hahahahahahahaha

8PM
Chao: I can feel my own protein get digested....break down into amino acids...or because it's becoming protein oxide?

Eva:

Well, it's quite nice, we did our best. I hope we get something nice :)
Next year, it's going to be great... 2 amazing people who are not in the contest this year can join. Study It's going to be a STRONG team next year.
Sadly, Katie doesn't want to do it again, guess I have to find some other GPA 4.0 student.

But, I'm so happy I get so many frozen food at my house because my dad is going away for a week!

Working on a formula that generates all possible finite positive integer sequences

Three days ago, my pre-calc teacher gave assigned seat to the entire class. Of course no body knows the reason she did it. Possible assumption are the chatting problem, feng shui, the seating matches some mathematical sequence.

I like to go with the last one.

I had copy down the new seat formation, and did some play with it.
Original Copy

Sean Matt Marie John Amanda
Ryan Alex Thomas Yulia Greg
Katie Dana Brooke CJ Glenn
Gina Chao(Mgccl) Troy

I turned them into numbers. Where 1 is male and 0 is female. I heard feminist people say "why is female 0?". 1 is the multiple identity, 0 is the addition identity. There were no specific preference.

1 1 0 1 0
1 0 1 0 1
0 0 0 1 1
0 1 1

If I think the seats are connected, I can get a sequence
1,1,0,1,0,1,0,1,0,1,0,0,0,1,1,0,1,1
A problem soon arises, how can I generate a sequence like this one.
The most obvious one would be points on a polynomial, but that takes 18 coefficients to uniquely define this sequence. Really, who in this world ever use a polynomial with degree of 18 to describe a sequence with only 18 numbers.

Simon told me I could try to mod 2 a sequence and see if that would work, and he suggested me to use it on a geometric sequence. Thx, that's a great inspiration.
Of course, a geometric sequence with only integers is either all 1s or 0s after mod 2. So I have to mod another number first. Here is an general equation for that sequence.
a_n=(b^n\ mod\ z)\ mod\ 2
In the above equation, I use mod as a function, where
m\ mod \ n =m-n\lfloor \frac{m}{n}\rfloor
instead of using mod expressing congruence relation

For the sequence above, for z<100000, b as small as possible, result the below equation.
a_n=(41^n\ mod\ 13149)\ mod\ 2

This requires a lot of calculation on the computer, and I haven't find a fast way to compute it yet. But it seems like a possible compression algorithm, everything eventually becomes 2 numbers. Since anything in the computer are binary, so it can be turned into sequence of 1 and 0s. Or we can mod 2k, When k=3, we have sequences from 0 to 7. When 2k is larger than the string we try to compress, the result will be larger, because it's string itself and 1. My guess is when k becomes larger, the time complexity will decrease and the result's size will increase. It's also possible when k becomes larger, time complexity increases until a certain point. Need a LOT of math to prove it.
Few other hypothesis I need to prove:
1. Any finite sequence with positive integers can be generated this way
2. On average, storing the 2 numbers are smaller than storing the original sequence
3. The computational complexity is lesser than a polynomial rate when provided with a good algorithm

I don't have doubt the first one is true, but the 2nd one might be the real problem. The sequence above can be stored as 18 bits, but the result 2 numbers require 20 bits. b=61, z=1557 also works, and it's the smallest bits possible to generate the sequence. It requires 17 bits to store. Finding the smallest solution is another puzzle.

The current algorithm:
Test each prime number for b, and odd integers for z. Composite numbers can also work for b, but currently, the calculation find the composite numbers' possibility to turn out useful for the sequence are below the possibility of prime numbers. No proof yet.

Using it to compress a 1MB file will take a long time, I think it's in the 10^x years scale, x > 30.
Split a large file into small pieces and work on each one of them with this algorithm will eventually reduce it to a very small file, if the hypothesis 2 is true. But now I have to have a few more numbers(how many times the algorithm was applied, how large was the original file), but those ones can't be a big of deal when it's compressing a large file, both of them are in log(n) scale if the original size (bits, not the size of the number) is n.
Even if hypothesis 2 is not true, if we can find a large "magical partition", where each partition can be expressed by 2 numbers with less bits much smaller than the original partition no matter what the sequence is in the partition, the split a large file method still works.

It's best if this technique can work with other compression algorithms to form even smaller files.

If hypothesis 2 and 3 are both not true. maybe like what Simon said, this will be a encryption technique with a larger time complicity for encryption than cracking the encryption brutal force. Theoretically the worst encryption technique possible.

When I told my teacher about finding pattern in her seat changing system. she asked me what is the chance that she randomly placed people can correspond to a mathematical sequence defined like that(hypothesis 1). I think I will give her the answer soon.

Today is the Moody's Mega Math (M3Challenge) day, I will be working from 7AM to 9PM with my team of 5 students and compete for $20000 with 287 other teams. Pizza for lunch, yeah!

Honey Pot that kill bots