Sunday 30 January 2011

Numerical Approximation

I rather not to say this is a standard / strict skill but it's just useful in MOs.

1) Why approximation?
When the answers are required to write in surd form, we can't exactly measure/calculate the answers in exact form and answer in surd (because it's irrational), therefore approximation helps us to check the answer.

2) What makes approximation accurate?
-Irrationality: The definition of irrational number is "can't be written in forms of p/q, where (p,q)=1. We often prove the irrationality of a certain number (especially in surd form) by assuming it in forms of simpliest fraction, and disprove by contradiction. Now consider a rt k lattice: Z[k^0.5].
All lattice can be written in forms of a + b k^0.5. You may notice that the lattices arranged quite far apart. These two properties are inimpotant:
i) Exist NO solution for a+b k^0.5 = c+d k^0.5 where a,c are distinct (b,d distinct)., i.e., exist unique pair for each lattice
ii) Approximately a+b k^0.5 ~ c+d k^0.5 (approximately equal, may less than 0.1), has a root that a,c has quite a large difference, so one of them is clearly be the answer.
For example, 2^0.5 - 1 = 0.41, while 11 2^0.5 - 15 = 0.55.
As a result, approximation for one and only answers seems accurate.

3) Approximation methods
- Bisection
This is one of the most famous approximation method. (as well as trisection, N-section...)
Method:
We are going to solve x from f(x) = y.
choose two integer (most proprably neighbouring integer), such that
f(N) < y, f(N+1) > y (inverted relationship if it has different behavior)
Then test f(N+0.5) > or < y, then use the next bounding to test x until a satisfied accuracy.
Of course, this is not available when the function doesn't behave monotonically.
-Numerical approximation
e.g. approximating root squares of numbers: 2011^0.5
Note that 45^2 = 2025 (this should be well known enough), while 44^2 = 45^2 - 89
2011 = 2025 - 14, so when it's rounded to nearest integer, we take 45 as the answer.
How about if we are going to estimate 1~2 d.p.?
When h is very small,
(x-h)^2 = x^2 - 2xh + h^2 ~ x^2 - 2xh.
Therefore, (x^2 - h)^0.5 ~ x - h/2x
Apply formula, (2025 - 14)^0.5  ~ 45 - 7/45 = 44.85
Exact answer: 2011^0.5 = 44.844
The error is quite small (0.06), which can be ignored for taking integer as an answer.

These are methods applied in physics quite frequently (like gravitation: g = g0(1-2h/x) ), but if it's used in mathematics properly, this is quite useful in check your answers.

This is a simple review of PC heat, HKMO heat 2011, so let's take their questions as a simple example:
1) An integer x, (x-12) and (x+19) are both perfect squares. Solve x, show that it's unique. (modified MO heat, ind. 5)
Firstly, N and N+31 are both perfect squares (x-12=N), then 2x+1 = 31, x = 15.
Check 225 = 15^2 = 237-12, 256=16^2 = 237+19.
Uniqueness: all difference of perfect square can be wrtitten in forms of 2kx+k^2. Check for 31, x is integer only when k is 1. Therefore there's only one answer.
2) given a+b = (2011^0.5 +2010 ^0.5) ^0.5, a-b = (2011^0.5 - 2010^0.5), find ab. (MO heat, ind. 3)
This is quite easy when you square both equations, and the answer is 2010^0.5 /2.
Now, let approximate the answer.
Note that identifying 2011^0.5 and 2010^0.5 by approximation is very risky, so we better write 2010^0.5 in terms of 2011^0.5.
As approximated, 2011^0.5 ~ 44.85
(2011 - 1)^0.5 ~ 44.85 - 1/2(48.5) ~ 44.84 (Exact: 44.833)
a+b = (44.85+44.83)^0.5 = (89.68) ^0.5, since this is quite far from 81 or 100, we are not going to use approximation, we use bisection to find that 89.68^0.5 ~ 9.47.
a-b = (44.85 - 44.83)^0.5 = (0.02)^0.5 = 0.141, we don't need approximation since this is quite well known that 2^0.5 = 1.41.
Solve a: a = (9.47+0.14)/2 = 4.805, b = 4.805 - 0.14 = 4.665
Multiply them, 4.805 * 4.665 = 22.42

We don't see anything special from this number, right? This question involves squares, so square this number:
22.42 ^2 = 502.6, it's quarter of 2010 (or 2011)!.

Therefore you deduce that the answer is somehow like 2011^0.5 /2, or 2010^0.5 /2, by checking you'll get the correct one.
3)Approximate [2011/5]+[2011/25]+[2011/125]+... (modified MO heat, gp. 7)
2011 is quite close to 2000 which is multiple of 125, so we expect that there won't be a big loss in [] reduction.
(*) ~ 2011 (1/5+1/25+...+1/625) -1
~ 2011 (1/4 - 1/3125) - 1
= 501.

Exercise:
1)Approximate (7-12^0.5 - (13-48^0.5)^0.5)^0.5, hence simplify the expression (MO heat, ind. 7)
2)Esimate x such that gamma(x) = 2011. (modified PC heat, E2)
3)Approximate tan 2011. (modified PC heat, E7)
4)An equilangular octagon has side length, 9,10,11,12,13,14,p,q prepectively, find pq. (modified PC heat, E14)
5)Approximate integrate (100cos5x/(1-cos10x) dx from 10/pi to 20/pi. (modified PC heat, E16)
6)ABC x BC = PQRST, where "each of its digits (except the leftmost digit), is greater than the digits on its left (like 123,24689)" is satisfied for ABC, BC and PQRST. solve PQRST.
7)i) Approximate (4956^0.5 - 3612^0.5)^2 to the nearest integer.
ii) Approximate (4959^0.5 - 3612^0.5)^2 to the nearest integer.  (modified PC09 final, D9)
8)Challanging questons
i) Compare the size of 6^0.5 and 2^0.5 +1.
ii) Compare 6^0.5 and 2^0.5 +1 by approximation.
iii) Compare the size of 303^0.5 and 16+2^0.5 by approximation.
iv) Study the relavent topics of approximation in pure maths, about approximating by differentiation, young's inequality and other skills, try (i),(ii) and (iii) again.
v) Define f: N->R, for an integer n, define S as a set that all elements are integer between [n^0.5] and [n^0.5]+1, note that [] here is the round up function.
f(n) = min{ |n^0.5 + 1 - x^0.5| } for all x in S. Describe f(n).
vi) Using the same set S. define another function g: N->N:
g(n) = x where x the x in min{ |n^0.5 + 1 - x^0.5| }.
now h: N->N is defined by h(n) = x-n. Describe h(n).
vii) Relate f(n), g(n) and h(n).
viii) Hence or otherwise, given 2^0.5 = 1.4142. Find the smallest integer, n>2 such that
I) |{n^0.5} - {2^0.5}| < 0.01
II) {{n^0.5} - {2^0.5}} < 0.01
III) |{n^0.5} - {2^0.5}| < 0.0001
IV) {{n^0.5} - {2^0.5}} < 0.0001
V) Prove that there exist no such integer n>2 that {n^0.5} = {2^0.5}.
({} is the decimal part function)

Warning: I am NOT encouring appoximating answers as a kind of answering skill in competitions or in exams. A standard calculation should ever be respected. Take this skill as fin and for checking answers only.

Thursday 27 January 2011

Symmetrical and chiral units of origami polyhedral model Ext 2

Proposition 4
When we are using a unique origami unit (mirror unit is permitted), it has a unique cumulation value, hence it's impossible to make a totally flat non-regular polyhedron, not even a semi-regular polyhedral (i.e., unique vertex composition expression).

The proposition is correct, and is incorrect, depends on which type of model you are making.
For a normal model, all units has 3 fold lines and are used up in the model. For non-regular polyhedron, each vertex polygon expression has more than one numbers, e.g. {6,6,5} or {6,5,5}, For a specified w-h ratio it has a specified cumulative value for a given n-gon. The cumulation value behaves monotonically so we can ensure that there's no repeated roots, hence for each verteices, flat polygon can't appear in all three sides of the vertex.

It's not correct when you are making an enlarged model.
Take Sonobe unit as example on cube. Cube, is of the same nature with regular tetrahedron by giving a specified cumulation value (6^-0.5), regular tetrahedron has configulration {3,3,3} while cube has {4.4,4}.
In enlarged cube, the verteices are 3-rings while the center part is (flat) 4-rings. however 3-4 ring pattern is flat.
Also in pol unit, 5-6 rings pattern are flat, using the pattern {6,6,5}, a 27-times enlarged icosahedron is produced instead of a turncated dodecahedron.

Proposition 5
We can use unit with different w-h ratio to produce all flat polyhedral.

I haven't do any experiment on this one (since the calculation work is too much), but I believe this is yes, regardless how you put different plugs into sockets. Also This violates the spirits of origami, right?

Tuesday 25 January 2011

Plan: Jan - Mar 11'

Mathematics
-Analysis of Hearts
-Extending origami geometrical theory
-Actual work of folding new origami model - showing the divide-dual nature
-different novels
Osu! mapping
-harassin' boss
-Statice (not static XD)
-rank : frozen rain, libera me, kokoro
Notes:
Carbon chemistry, maybe

I hope I can finish at least 90% of the above target. orz

Sunday 23 January 2011

Analysis of Hearts

1) Introduction
I'm not a bridge expert, but heart is one of my favourite... Hearts, being a popular game and an elementary practice for bridge players, someone just tell me to write something on hearts.
Poker games, are most likely linked with "luck". Without luck we can't win even one game.
Is that true?
Yes, but luck don't determine 100% of the win and lose.
Unlike Big2 game, Hearts and Bridge's win and loses are mostly likely to be determined by your skills.

Moreover, let's assume that the % of result are determined by luck (we don't have experimental result of this %, just a hypothetical data)
One claims that the % are as following: Big2 60%, Tenhou 40%, Hearts 10%, Bridge 2%
Without cheating, the "luck" is totally, independently, fairly random. It is in normal distribution.
"luck" can't be quantitized since each hand's "luck" is determined by the distribution of whole system instead of your identical hands. Make it easy that the standard deviation = "luck %"/6 and the mean is "luck %"/2, i.e., 99.7% data is included.
Consider Big2, the skill determines 40% of the results.
In order to give a fairer review we can look at 100 games.
When the skill is perfect, 100(0.4^100) = 1.60694* 10^-38 games can be won without anyluck, but this happens with the probability of 0.15% ^ 100 = 4.06 * 10^-283 !
Integrate the bad luck part (mean luck < theoratical mean)
It wons 2.24 * 10^-16 games, while the prob. is 0.5^100 = 7.88 * 10^-31
That is, even your luck is extremely bad, your skill helps you to win about square root of # of games played.

How about in a good luck?
The expected games won will be 100(0.4+x)^100 dx, by integrate from 0.3 to 0.6, the answer is 0.99!
That is, you must win at least one of the 100 games.

Note that when you're in a good luck, since the good combinations are limited, others will have relatively lower luck, and your chane to win is much higher. Then you will win more than the mean among the games in reality.

When you have no skill, even you are in very good luck (every game's "luck" is above mean, you chance would be 3.88 * 10^-23, much less than those with skills.

Even in such a gambling game we can see that skill determines a lot, then it's far more important in Hearts and Bridges. What makes Hearts intersesting is the passing round which determines most of the game.

2)Rules
Here's some rules that is important for the discussion of stragities:
-S Q worth 13 pts, each H worths 1 pt
-left pass, right pass, vertical pass, no pass
-shooting the moon (one eats all)
-Broken heart (H can't be played actively until one plays heart passively, unless you have no other suits)
-No pt should be given out in the first round
-Club 2 goes first in the first round.

3)Determination of your hand in the first glance - Passing skill
Passing determines the results a lot so it's quite important for you to plan what to pass to give you a safer hand, But before that we should know how to determine what is a good hand:
Defining
Good hand: Hands that tends to have no or low pts (0~4 pts), hands that surely shoot the moon (26 pts)
e.g. 1: S 9873 H J83 D 9832 C A4
This is quite safe as you don't have the risk to eat SQ, while the C A can be discarded in the first round.
Expected pts: 0
e.g. 2: S AJ9873 H QT2 D 93 C 32
This is quite safe as well since S A won't be forced out under the protection of 6 card S suit, the only potential points comes from the H suits.
Expected pts: 0~4
e.g. 3: S AQ8 D AJ H AKQJ10 C AKQ
With the 5 top cards in H suits, it's possible that you can pull out all hearts after pulling out your S Q and get yourself. The potential hazard comes from losing the active role while playing D J.
Expected pts: 26

Normal hand: Hands that may worth a number of pts (5~9 pts), Hands that may eat S Q with a few Hearts (13~15 pts)

e.g. 4: S JT92 H AT103 D J65 C AK
You can't discard both C A, K in the first turn, discard later is quite danger; if others play H, potentially this hand eats once.
Expected pts: 4~8
e.g. 5: S Q H A8732 D AK7653 C 8
Most probably you'll have to collect 13 pts from yourself, but you don't need to worry on the H and D suit under well-protection.
Expected pts: 13

Dangerous hand: Hands that eats a lot of Hearts, and potentially eats S Q (10~13, 16+ pts)

e.g. 6: S AQ3 H KJ D AQJT75 C 2
When you are required to play one of S, H or D suits, you can't throw away the active role easily. That potentially gives a large amount of points.
Expected pts: 8~9, or 16~20
e.g. 7: S AK97 H ---- D KQJ C JT7653
Cs are played in the first round, so it's also quite hard to throw away the active role.
Expected pts: Very high or very low

Gambling hand: Hands that may eat all OR a very high pts without eating all (24~26 pts)

e.g. 8: S AK765 H AQT987 D AK C -----
If H K does not appear, you can't eat all.
Expected pts: 24~26
e.g. 9: S AQ9 H A3 D AKJ6 C AQJ10
It's hard to collect Hs by such a small H card.
Expected pts: 23

4)Passing
Let's look at the use of different suits:
S - long suit is very good - to protect yourself from getting S Q without other choice.
H - long suit in your hand also prevents getting mroe pts
D - better shorten it if you only have 4 or less, a void suit would be useful in discarding other big cards.
C - one top C is safe which can be used in the first round.

It's quite important that we should not discard S suit.

Let's take the previous examples.
Suggestion:
Good Hand - discard D, C
Normal Hand - discard D C top cards, then shorten D suit
Dangerous Hand - upgrade to gambling hand or passing the A,Ks away
Gambling Hand - discard the smallest cards
 e.g. 1: S 9873 H J83 D 9832 C A4
discard D 98, C4 or H J D9 C4 - discarding one C gives you a voided suit, discarding D make you safe in D suit.
e.g. 2: S AJ9873 H QT2 D 93 C 32
discard H QT C 3 - the H suit is quite dangerous.
e.g. 3: S AQ8 D AJ H AKQJ10 C AKQ
Nothing should be discarded lol, I suggest S8, DJ and C Q.
e.g. 4: S JT92 H AT103 D J65 C AK
discard H A C AK, this gives you a chance to discard one unwanted card in the first round.
e.g. 5: S Q H A8732 D AK7653 C 8
discard H A8 C8, it'll be more dangerous if you recieve S AK without S Q.
e.g. 6: S AQ3 H KJ D AQJT75 C 2
discard H KJ C2 to produce two viod suit, as to avoid being the active role, and if you are in active, it has a chance to shoot the moon.
e.g. 7: S AK97 H ---- D KQJ C JT7653
discard D KQJ and hope you opponents send you some S.
 e.g. 8: S AK765 H AQT987 D AK C -----
discard S 765.
e.g. 9: S AQ9 H A3 D AKJ6 C AQJ10

discard H3 D J6.

Friday 21 January 2011

Symmetrical and chiral units of origami polyhedral model Ext 1

Recently I'm making a new polyhedral model by using a new unit, I don't know its name so just call it "polyhedral unit".
Some basic properties about the pol unit:
1) length-width ratio: 1 : rt3/2 (it's determined by (i) folding along center y-axis (ii) flip right-bottom corner to the center axis along the line from left-bottom corner)
2) 2 plugs, sockets in rhombus form
3) Representation: two triangular real, flat face on the polyhedral
4) Curvature: flat for single triangle and 6-ring
When we compare this with the Sonobe unit, we can find that pol unit has multi use: either form a triangular face itself, or forming polygon faces with positive curvature (this is the only function of Sonobe unit).

Then we'll have the following question:
Why can't Sonobe unit forms a single face itself? Both Sonobe and pol unit are chiral, but mirror unit of Sonobe unit is not needed to compose a polyhedral, why pol unit needs mirror units? What's the curvature limits and are there any other l-w ratio to compse other curvature, say making a flat pentagon?

1) Sonobe can't represent single face.
This is because polyhedral model requires regular polygons are faces. If irregular, it's easy to prove that the polyhedral can't close up without little help from elasticity of origami paper.
Single socket of Sonobe unit is right-angled icos. triangle, which don't form a regular faces except square. Therefore cube (dual of tetrahedron) and extended version of cube (all 4-ring, which is flat)
In divide-dual analysis, polyhedrals can be represented by triangles only, where each polygon is divided intro triangles, adjusted to a certain curavture (or flat) and this is the polyhedral that Sonobe model can form.
For 3-ring, they form triangle face which like the pol face, for 4-ring, it's flat. For 5-ring and 6-ring, They forms "external ring", which represents the vertex, or the base of a polygon. It's impossible for Sonobe unit to form 7 or higher rings with a strong bonding unless forces are given to hold the shape.

2) Sonobe model doesn't need mirror unit but pol unit needs.
We should identify a fact that, when Sonobe unit is made up to a shape of pol unit (by 5 Sonobe unit), we can see that the Sonobe unit are symmetrical while pol unit aren't. Therefore we need mirror unit of pol unit is needed.

3) Curvature
It forms an equilateral triangle, so by the formula as shown in by project,
C = (cos ^2 30 - sin ^2 30)^0.5 / 2sin30cos 30
    = (2/3)^0.5
and cumulation value can tends to infinity.

to be cont.

In order to extend my project done before I will try to ellaborate more on cumulation pattern, mirror rings pattern and flat pattern.

Thursday 13 January 2011

Physics: Optics

Optics
Light rays – a line with arrow on the line
Divergence of light ray – when we say a set of rays is parallel, they don't have intersection points; if it's converging, it'll have a intersection in front of the source (real); if it's virtual, it has a imaginary intersection point behind the source (virtual).
We observe objects when light from objects enter our eyes. Luminous object emits light so we see the object directly; wee see non-luminous object when it reflects lights into our eyes. Distant objects are assumed to be emitting/reflecting parallel light rays.
Law of reflection
1)       The incident ray, reflected ray, normal lies on the same plane.
2)       θi = θr, i.e., the angle of incidence is equal to the angle of reflection.
When the light rays are stroked on a curved mirror, the normal is perpendicular to the tangent of the curve at that point. e.g., when parallel rays are stroked on a coven mirror, they are all reflected and converge in front of the mirror.
Regular reflection occurs when the rays are reflected by a smooth surface, where the θi for all parallel rays are the same and sharp image can be formed. Diffuse reflection occurs when the rays are reflected by a rough surface, where the θi is not unique. Rays are reflected into different directions
Properties of the image: the object that we see through the mirror is not the real position of it, but we can imagine that the light rays from the object comes behind the mirror and we call that an image. They have the properties:
1)       Distance from image/object to the mirror is equal. i.e., image distance is equal to object distance.
2)       IO is perpendicular to the mirror.
3)       The image formed is laterally inverted, of the same size as the object and is virtual.
Applications: Periscope uses two plane mirror to receive image from distant position (like double-decked bus), the image is erect but not laterally inverted.
Refraction of light
Since light is a macroscopic view of EM waves, when it goes into different material, it will have different travelling speed, resulting in the refraction.
Assume the refractive index of light in vacuum is 1, where light travels in the highest speed there. The refractive index of air is almost 1 (1.0003). The refractive index of a certain medium X is given by ηX = speed of light in vacuum / speed of light in medium X.


Law of refraction:
1)       The incident ray, refracted ray, normal lies on the same plane.
2)       sin θi is proportional to sin θr
Refractive index can be also defined by ηX = sin θair / sin θX.
General form of Snell's law: η1sin θ1 = η2sin θ2.
A medium with higher refractive index is called optically denser medium, all medium are optically denser than vacuum so all medium has refractive index higher than 1.
A several phenomena can be explained by the refraction of light, like the rising of image when a glass block is placed on a plane surface, or a coin is placed into a cup of water, the real depth is different from the apparent depth.
Total internal reflection
By Snell's law, when one's refractive index is larger, there exist certain ranges of angle that the equation is not balanced. In this case total internal reflection happens.
Critical angle of medium X is given by: ηX sin c = η2sin 90˚, c = sin-1(1/ηX). It occurs when:  (1): Light ray is directed from optically denser to less dense medium; (2): θi > c
Under total internal reflection, it obeys the laws of reflection. Note that even the angle is smaller than critical angle, part of the light may still reflects, but when it exceeds the critical angle, all light rays are reflected.
Application
- Fish-eye view under the water (diver's view)
- Mirage: hot air is lower than the cold air during days, since hot air has lower density, it has a less refractive index. When light striking downwards, it has a continuous refraction, when the refractive index of a certain fraction of air is small enough, total internal reflection occur and observers can see the reflected image of the distant object on the ground, just like some water on the ground.
- Periscope by prisms: glass/Perspex prisms usually have critical angle smaller than 45˚. When two prisms are placed like plane mirrors, They can also form a periscope. Advantage: is that plane mirror in reality is composed by a thin glass layer and a reflecting layer. During reflection of plane mirror, the glass layer may produce multiple image but prisms dose not.
- Optical fibre, as well as cutting diamond in a suitable angle.
Lenses
-          Convex VS concave: convex lens is lens that is thicker in the middle part while concave lens is thinner in the middle part.
-          Cylindrical VS spherical
-          Converging VS diverging: When parallel rays pass through convex lens, they converge, when they pass through concave lens they diverge. Therefore they're called converging and diverging lens respectively.
-          Optical centre is the center of the lens
-          Principal axis passes through the optical center and perpendicular to the lens.
-          Principal focus is where parallel rays converge (or imaginary converging) when parallel rays pass through.
-          Focal length (f) is the distance between principal focus and the lens.
-          Focal plane is the plane that passes through principal axis and perpendicular to principal axis.
-          Thicker lens or lens with higher refractive index causes shorter focal length (light rays are converged in a more quicker way)
-          In the light ray diagram the figures shows the convex lens (left)and the concave lens (right).
Rules for light ray passes through lenses:
1)       Rays that passing through optical centre is not refracted.
2)       Rays that parallel to principal axis intersect or (imaginary intersection) at the principal focus. By reversibility of light, rays from principal axis is refracted to be parallel.
3)       For other rays: Firstly, construct a line parallel to the rays and passing through the optical centre. Then find the intersection between the line and the focal plane. The refracted light rays will pass through that intersection point.
The refracted image may not converge in front of the lens. Instead they virtually converge behind the lens, a virtual image is formed. Observers can still observe the image but it can't be caught by a screen.
Lens formula: 1/u + 1/v = 1/f, where u and v are object and image distance.
For f, it is positive for convex lens while negative for concave lens, v is positive when it is real while negative when it's virtual.
Linear magnification (m) = image height/object height = v/u
Nature of image formed
-          Real and inverted(v>0) VS virtual and erect (v<0)
-          Magnified (v>u or m>1), of the same size (v=u or m=1) or diminished (u>v or m<1)
Methods to determine focal length of lens:
1)       When s sharp image of a distant object is formed by a convex lens on a screen, the distance between the lens and the screen is the focal length of the lens.
2)       Attach a plane mirror to the convex lens and place them in front of an illuminated object. Move the lens-mirror combination until a sharp image is caught by the screen. The distance between the lens and the screen is the focal length of the lens.
3)       Using lens formula, obtaining different sets of (u,v), plot the graph of 1/v against 1/u (it gives y-intersection 1/f), m against v (it has y-intersection -1 and slope 1/f), v against u (intersect with line v=u at (2f,2f)).

Monday 10 January 2011

偽.SIMC回憶錄4.1

6:45a.m. , Day 4, NUS High School
相信每一個人都在準備報告而在作出最後努力吧。每隊都如同前幾日,在早餐時段(今天是三絲炒米)仍然打開電腦--當然不是打LF2,而是為簡報作最後衝刺。
上午八時,所有人進入了演講廳,找了幾個位置坐下準備,然後工作人員說明規則:上午一共有七節時間(每節三十五分鐘),當中有四節時間我們將要前往獨立的課室向一位評審作報告。其間簡報內容不得修改(簡報也事先上繳了),以免不同評審所接收的有差別。
第一個評審應該是中國人,我們去的課室從桌子椅子到擺設都很像,這給予我們一個比較舒適的環境,心情也稍為平靜下來。但很快,我們便體會到口述報告的難處:指示上說每次報告約為十五分鐘,加上問答環節才最多二十五分鐘,但很多時候直觀證明會比一種已知的演算法(例如今次大派用場的貪心演算法),在一個相對嚴謹的態度下每個規則都要加以證明,使時間嚴重不足。幸好,超時並不會扣分,加上評審的問題集中在第一二題,我們也自然地將重點放在頭兩題上。第三題的自由發揮上並不用太多證明,於是第三題似乎只用了兩分鐘時間……(後來,原來第三題是我們失分重點 orz)
第二個評審比較特別,是某位本地中學的校長,當地學生也沒有怠慢,千叮萬囑叫我們進去打招呼……果然有地位的人有特別特遇,今次我們的報告地點是電腦實驗室 (ICT Lab),注意這比普通電腦室高級,香港也沒多少學校有這等設施。Lab的後方坐著一位白髮蒼蒼的老人,大概就是我們的評審了吧。當然我們不會因為評審的不同在報告內容方面有所不同,但也變得更緊張了。更要命的是,白板在上一隊用完後有未刷過的痕跡,整個白板都用矩陣語言寫成,這倒給了我們不少壓力。當然,報告還算順利完成(事後我發現Lab太大,我畫的圖根本看不到)……
第三個評審同樣是個本地志授,我們這次的報告並沒有很待別的地方。然後我們有兩節休息的時間,可以回到演講廳作最後準備。我發現了我身後的地板有個隱藏的插頭,於是就拿了來充電,但其實我那部電腦並不是用來做簡報的那部電腦,當時我也沒有意識到這問題的嚴重性,後來卻差點帶來不可挽回的後果……
我們來到第四位評審的門外,看見裡面有一隊在報告(我第一個想法是:超時扣分?),再望了白板一眼,屆然是同樣的矩陣語言!那無疑是經過第二位評審的那一隊,那是來自北京市的某隊,似乎沒有學服,於是全西裝出戰;這是個頗有趣的地方,有不少學校根本沒有學服(以歐洲為甚),今天的指示要求學生穿校服,但沒有學校的隊伍服飾便各有不同:印尼隊選擇穿上民族服飾、英國隊便衣出戰、澳洲隊更只穿上球衣上陣……對愛面子的中國隊來說西裝應該是個不錯的選擇……嗯,下次試旗袍和中山裝?!?
同時,我們也注意到門外有一張SNMO (Singapore National MathO)的海報,這對我們這些奧數玩家來說有不少吸引力,事後我們也在網上找到那年的題目,其實都不難……
言歸正傳,我們進入第四位評審的課室裡報告,我們有題用直觀選擇法做了個比optimal solution少0.5的答案,然後我卻不心口快說了句"This is the best result obtained by our selection moethods.",評審卻可能對上一隊有答案有印象,反問一句"Are you sure this is the best solution",我心知大事不妙也只能硬著頭皮回答"This is the best result obtained by our trials under the selection methods"……
最後一次報告過程頗為驚險,先是投影器的線插不進,然後被挑Starbuck的logo不能隨便放上簡報(一笑置之?),做完簡報那一刻剛好沒電(我當時立刻後悔自己應該讓做簡報那部電腦充電……)
就這樣,四次報告總算有驚無險地完成了。

Saturday 8 January 2011

Physics : Wave II

Wave nature of light
Reflection and refraction are properties that can be performed by all matters including particles and waves, but only waves perform Interference and Diffraction
Diffraction: Usually we use a slit with width ~10λ to observe diffraction (for visible light, the width is usually 0.1mm). If it’s too narrow there’s not enough energy to pass through, it it’s too wide, no diffraction is exhibited. We can observe the diffraction of red light is more than blue light, so λred > λblue.
Interference: Young’s double-slit experiment: when light passes through the double-slit, a series of bright and dark fringe is observed.
Note that these experiments has to be done under very dark environment since the slit is so narrow that only a very small amount of energy is given out.
Quantitative interpretation
Consider the diagram; S is the initial source, while S1S2 is a double slit (with slit at S1 and S2). CX (usually denoted as D, and is 1m if not specified), the distance between two slits is denoted as a(usually 0.1mm). The calculation is based on the assumption that D>>a. Now denote Ym is the distance from the central maximum to the mth light fringe, the θ is the red angle. When D>>a, sinθ is approximately equal to tanθ. S1T and S2T is assumed to be parallel, so that S1R is assumed to be the path difference, that is, mλ.
Ym = Dtanθ = Dsinθ = Dmλ/a = m(Dλ/a). Distance between two successive light fringe = Dλ/a, which is independent of m, this explains why the fringes are equally spread.
Note that the interference is not complete except the central maximum since energy is lost proportional to path travelled, therefore non-zero path difference cause in different A of the two waves that they can’t add/eliminate completely.
Note that it can be used in other waves but the formula is no longer true since other waves has much larger λ, then a has to be much more larger, which makes D>>a no longer true. Also moonlight (single wavelength) source has to be used. If white light is used, then the result will be: white light (central max) – violet (1st order) – red (1st order) – violet (2nd order)…
Plane transmission grating – with many slits
It only allows plane waves (straight waves) and normal to the plane of grating to pass through.
Now consider the mth fringe, we have asinθ = mλ ≤ a, a/λ ≥ m, [m] is the last order of light fringe that can be observed.
Dual nature of light
In the grating experiment, the interference is limited because for those fringes that beyond the mmax, they do not belongs to the same package of photon produced by the source, so that they’re not coherence and they don’t interfere. This shows the particle nature of light, it can be quantified as photon.
At the same time, it’s a wave, the electromagnetic wave, which composes by perpendicular oscillating electric and magnetic field. It’s transverse waves and transmit energy like other waves. Their travelling speed in vacuum is 3*108ms-1. By v = fλ, the higher f, the shortest λ.
1)       Radio waves (λ: 10-1 to 104m) : broadcasting
2)       Microwaves (λ: 10-3 to 10-1m): heating, radar
3)       Infra-red (λ: 10-3 to10-6m), body emission, heat transfer
4)       Visible light (λ: violet 4*10-7 to red 7*10-7m) for illumination
5)       Ultraviolet (λ: 10-9 to 10-8m), for killing germs, UV light lamp (Hg lamp)
6)       X-rays (λ: 10-10m) medical dialog (project e- on heavy metals to produce X-rays)
7)       Gamma ray (λ: 10-12 m) kill cancer cell, sterilize food.
Sound waves
-          Speed of sound waves depends of nature and density of medium, e.g., 300ms-1 in air but 1500ms-1 in solid
-          Produced by longitudinal waves of particle, so it can’t pass through vacuum.
-          Detected by cathode ray oscilloscope (CRO) and microphone.
-          Exhibits properties of wave, e.g. refraction by a CO2 balloon.
-          Loudness of sound in terms of decibel (dB), 0dB is the threshold of hearing while 120dB is the threshold is pain. Audible sound pitch: 20-20000Hz (Note that there exist negative dB but human can’t hear it.)
-          Loudness depends on A, pitch of sound depends on f, quality of sound (note VS noise) depends on the regularity, and main note of a sound depends on the largest single wave produced by the source.
-          Application: detecting sea animals (sonar) since EM waves is absorbed by waters. Also we should use supersonic only since the sound waves with lower frequency diffracts too much so that too many energy is lost. Medical application and cleaning fragile objects.

Tuesday 4 January 2011

Physics: Waves I

I assume readers have basic optics knownledge (F3 level), and the optic topics will be disclosed later.

Wave motion
Wave transmits energy without transferring matter.
Transverse VS longitudinal wave – when transverse wave passes through a medium, it oscillate in a direction perpendicular to the direction of wave motion, while the motion of particle is parallel to direction of wave motion in longitudinal wave. Examples of transverse wave include water wave, EM wave, while longitudinal wave include sound wave. Long spring and slinky spring are used to perform transverse and longitudinal waves respectively.
Travelling waves carries the energy away while energy is stored up in stationery waves.
Description of waves
-          Crest and trough: In longitudinal waves, the most compressed position is called center of compression while the most rarefacted position is called the center of rarefaction.
-          Displacement (s): displacement from the center (equilibrium position – s=0)
-          Amplitude (A): max. displacement from equilibrium position.
-          Wavelength (λ): length between two neighbouring crest/trough/centers.
-          Frequency (f): Number of waves produced in 1s, in Hz, period (T) = 1/f.
-          v = s/t = λ/T = fλ, where v is the speed of waves, only depending on the medium.
-          Phase: stages of oscillation, when two particles in the waves has the same motion all the time then they’re in phase. If not, they’re out of phase. If they always have opposite motion, they’re out of phase exactly.
-          In transverse waves, all particles oscillate at the same f and A.
-          Waves can be described as s=cos (t+θ0), then consider s’ = v = sin (t+θ0), speed of particles maximized at equilibrium position, and momentarily at rest at crest and trough.
-          Displacement-distance graph (s-x) is the appearance of wave at an instant of time.
-          Displacement-time graph (s-t) is the motion of given particle in different time.
In longitudinal waves, s-x graphs can be plotted on a straight line rather than a wave. In other way using a curve shows the displacement from equilibrium position for each particle.
Speed of transverse wave in a taut string: v = (t/μ)0.5, μ is the linear density (kgm-1).
Speed of compressional waves in a long and thin solid: v = (E/ρ)0.5, E is the young modulus.
Observing waves: using ripple tank, water with detergents is used (to reduce surface tension), sponge in the boundary prevents the reflection of waves. In the waves crest are bright and trough is dark since crest acts as convex lens to converge lights. Straight bar is used to produce straight waves while dipper is used to produce circular waves.
In a diagram, wavefronts show the neighbouring particles which are in phase (and usually crest). Rays show the direction of travel of the wave (dotted arrow).
Reflection of waves
It obeys angle of incidence = angle of reflection. For circular waves, we can reflect the position of dipper through the barrier, and after the wave is reflected, it’s like the image of reflected dipper producing the circular waves (having center at reflected dipper).
When a string connected to a fixed end (or from a less dense to a more dense medium), the reflected wave has a π phase change (half a period), while there’s no change in free end (from a more dense to a less dense medium).
Refraction of waves
When a waves entering a shallower region, v decreases and f unchanged, therefore λ decreases. Consider straight waves, when it enters shallower region, v decreases, then the ray bends towards normal. When it enters a deeper region, v increases and it bends away from the normal. Convex and Concave shallow region act as convex and concave lens and converge / diverge rays respectively.
Diffraction of waves
When it passes through a barrier, the boundary of waves diffracts into straight line + curve or nearly a semi-circle (pass through a slit). Note that when λ increases or width of gap decreases, the degree of diffraction increases (a large curved wavefront produced.
Interference of waves
Coherent waves must be used to perform interference, or we can say same f and similar A. Also, there must be two sources, or straight waves passing through a double slit.
Superposition: when two waves meet, they add each other (i.e. cos(t+θ0)+ (t+θ1)), when they separate, they back to original state as if nothing has happened.
Consider two source, S1 and S2, consider a point X. Denote path difference Δλ = S1X ~ S2X (physics notation), = |S1X - S2X|, in terms of λ.
Now when Δλ = nλ where n is an integer, then it has a constructive interference since when Δλ is an integer, then the motion produced by the two waves are in phase, that is, the waves added up and reinforce to give a motion of doubled amplitude at that point.
If Δλ=(n+0.5) λ, where n is an integer, then it’s a destructive interference since motion produced by the two waves are out of phase exactly, then the two waves eliminated each other. Then that particle will have no motion at all (A=0).
In a diagram we can draw a line connecting all particles with the same path difference. Those who joins particles with constructive interference is called antinodal lines(maxima) while those who joins particles with destructive interference is called nodal lines(minima).
When the two sources are close together, the maxima and minima are closely packed while they spread widely when the two sources are farther apart.
When Δλ = nλ or = (n+0.5)λ, the antinodal/nodal lines related are the nth-order maximum/minimum. The line joining particles that Δλ=0 is called central maximum.
Stationery wave – waves that stay at fixed points. They’re usually with a fixed end. When the waves are reflected (note that it has a π phase change), it has superposition with the original wave. Different particle has different A. Those points which have no motions are called node. All particles inside two successive nodes are in phase (s:A is the same at any time) While particles in two sides of nodes are all out of phase exactly. λ of a stationery waves is given by 2*length between two successive nodes.

Sunday 2 January 2011

Mathematics : Cyclic Equations

Consider this (suspected ancient CE question)
Find value(s) of x, given a, b, c are real number satisfying
x = a/(b+c) = b/(a+c) = c/(a+b)
In my opinion this is quite hard in CE, even in senior olympiad level....
First of all, 3 equations, 4 unknowns, what you should think of is eliminating one of the variables.
Since x is what to be solved, we should not eliminate x, and the other three variables are in cyclic form so that they can't be eliminated. What should you do?

Consider the degree of the equations, they are degree zero, so that they are a proportion only.
Take an example, if (x,y,z) is a solution of (a,b,c), then (2x,2y,2z) can also be a solution.
Write k(a0,b0,c0) as the general solution of it. Then there exist a k such that k(a0,b0,c0) = (1,y,z).

Therefore, WLOG assume a=1, or you can assume a is a fixed constant.
Transform the equation like this: (a=1)
1+c = b^2+bc
b^2+b=c^2+c
The second equation shows the cyclic nature again. Consider x^2+x=y as a parabola, having y=-0.5 as the symmetrical axis, we should consider these two case:
1) b = c, which is obvious,
2) Consider the symmetrical axis, b+c=-1

For case 1, put b=c into 1+c=b^2+bc gives b = -0.5 or 1, -0.5 refers to b=c AND b+c=-1, so overlapped. Therefore b=c=1, a=b=c=1, x=1/(1+1) = 1/2

For case 2, 1/(b+c) = -1=x
Therefore x = 1/2 or -1, the corresponding (a,b,c) are: k(1,1,1), k(1,x,-1-x) AND their permutations. We should never forget the permutations in cyclic equations!

Here's another beautiful method to reach x = 1/2.
Rearrange the terms:
b+c = a/x
a+c = b/x
a+b = c/x
Sum them up: 2(a+b+c) = (a+b+c)/x, x = 1/2.
Why this method doesn't give x = -1? It's because both equations are divided by (a+b+c) is the last step, the dividing is correct ONLY IF a+b+c is non-zero. When x=-1, a+b+c = k(1+x-1-x) = 0 so it's wrong.

EDIT: Now, we may take a+b+c = 0 to sub. into the equation.
b+c = (-a) = a/x, x is obviously -1.
It seems that this solution satisfies the CE level, but it's still quite hard.

Another example from prelim 09':
t = u+1/v = v+1/w = w+1/x = x+1/u, where u,v,w,x, are distinct real and t is positive. Find t.
In the first thoughtyou may found the question extremely complicated. Also 5 unknowns with 4 eqautions, so you would like to assume u=1. However you should notice that there's more than one set of (u,v,w,x) satisfying t, but they are not linearly related. i.e., if (u0,v0,w0,x0) is one of the solution, k(u0,v0,w0,x0) (k is not 1) is not nessacarily be a solution. So a better way is to fix u as a constant, in another way, express v,w and x is the two fixed variables, u and t.
x = t-1/u = (ut-1)/u
w = t-1/x = (ut^2-t-u)/(ut-1)
v = t-1/w = (ut^3-t^2-2ut+1)/(ut^2-t-x)
Now sub. v into t = u+1/v, and rearrange the terms by a super hard factorization, we will get
t(t^2-2)(ut^2-u^2-1)=0
Note that the last term is non-zero, since the polynomial is parlindromic (refer to BAS note), it gives two roots of u which is reciprocal to each other, implies the existance of u+1/u = t = u+1/v, hence u=v which violates the given rule.
Therefore t = rtsq 2.

More to explore:
1) Find x if x = ab/(ac+bc) = bc/(ac+ab) = ac/(ab+bc)
2) Find x if x = a/(b+c+d) = b/(a+c+d) = c/(a+b+d) = d/(a+b+c)  (modified past IMO)
3) Find x if x = a^2/(b^2+c^2) = b^2/(a^2+c^2) = c^2/(a^2+b^2)
4) Find x if x = (a+b)/(c+d) + (a+c)/(b+d) + (a+d)/(b+c) + (b+c)/(a+d) + (b+d)/(a+c) + (c+d)/(a+b)
5) Find all integer solutions for (1) x+y+z = 3, (2) x^3+y^3+z^3 = 3  (HKMO 10, classical question)

fin.