十个有趣的英文文字游戏(下)

Ambigram
    Ambigram是指把一个单词或短语写成对称的样子,这样从两个不同的角度看这个图形都能读出这个单词或短语。例如,下面一个图形就是单词Ambigram的Ambigram:
      

    ambigram.com的首页有个这样的图片:
      

    Wikipedia上有这样一个Ambigram:
      

    最后来看一个左右轴对称的Ambigram(献丑了):
      

    Erich Friedman教授为他的朋友创作了很多Ambigram。你可以在他的个人主页上看到。

Alphametic
    Alphametic是指,把一句话写成加法算式,每一个字母表示一个数字,那么这个“虫食算”有唯一解。最常见的Alphametic可能是这个:
    SEND + MORE = MONEY
    它的唯一解是9567 + 1085 = 10652

    另一些Alphametic如下:
    FIFTY + STATES = AMERICA
    TERRIBLE + NUMBER = THIRTEEN
    EARTH + AIR + FIRE + WATER = NATURE
    SATURN + URANUS + NEPTUNE + PLUTO = PLANETS

    1969年,有人发现了这样一个有趣的Alphametic:
    THREE + THREE + TWO + TWO + ONE = ELEVEN

    这样的Alphametic叫做Doubly-True Alphametic。可以证明上面这个Doubly-True Alphametic是合法的Alphametic中“最小的”一个。另外两个稍微大一点的Doubly-True Alphametic为:
    SEVEN + SEVEN + SIX = TWENTY
    EIGHT + EIGHT + TWO + ONE + ONE = TWENTY

Mnemonic
    Mnemonic本意是可以帮助记忆的句子。例如,我原来记together这个单词就记作We want to get her。再比如,arithmetic可以记作A Rat In Tom's House Might Eat Tom's Ice Cream(每个单词的首字母)。当然,也有一些专门搞笑的Mnemonic,比如Microsoft = Most Intelligent Customers Realize Our Software Only Fools Them,而Macintosh = Most Applications Crash. If Not, The Operating System Hangs。
    数学家George Pólya(就是Pólya置换定理的那个Pólya)曾说过一句经典的话:How I need a drink, alcoholic of course, after the heavy chapters involving quantum mechanics! 依次数出每个单词的字母个数,你会惊讶的发现它正好是圆周率的前15位。后来又有人在后面加上一句All of thy geometry, Herr Planck, is fairly hard,让圆周率长度增加到24位。另一些圆周率的Mnemonic如下:
    Can I have a large container of orange juice?
    May I have a white telephone, or pastel color?
    How I wish I could calculate pi faster.
    For a girl I loved contrived; by nature tough, her heart survived.

    下面这首诗给出了圆周率的前740位。其中10个字母的单词表示一个数字0,字母数大于10的单词则表示两位数。

Poe, E.
      Near a Raven

Midnights so dreary, tired and weary.
    Silently pondering volumes extolling all by-now obsolete lore.
During my rather long nap – the weirdest tap!
    An ominous vibrating sound disturbing my chamber's antedoor.
        "This", I whispered quietly, "I ignore".

Perfectly, the intellect remembers: the ghostly fires, a glittering ember.
    Inflamed by lightning's outbursts, windows cast penumbras upon this floor.
Sorrowful, as one mistreated, unhappy thoughts I heeded:
    That inimitable lesson in elegance – Lenore –
        Is delighting, exciting…nevermore.

Ominously, curtains parted (my serenity outsmarted),
    And fear overcame my being – the fear of "forevermore".
Fearful foreboding abided, selfish sentiment confided,
    As I said, "Methinks mysterious traveler knocks afore.
        A man is visiting, of age threescore."

Taking little time, briskly addressing something: "Sir," (robustly)
    "Tell what source originates clamorous noise afore?
Disturbing sleep unkindly, is it you a-tapping, so slyly?
    Why, devil incarnate!–" Here completely unveiled I my antedoor–
        Just darkness, I ascertained – nothing more.

While surrounded by darkness then, I persevered to clearly comprehend.
    I perceived the weirdest dream…of everlasting "nevermores".
Quite, quite, quick nocturnal doubts fled – such relief! – as my intellect said,
    (Desiring, imagining still) that perchance the apparition was uttering a whispered "Lenore".
        This only, as evermore.

Silently, I reinforced, remaining anxious, quite scared, afraid,
    While intrusive tap did then come thrice – O, so stronger than sounded afore.
"Surely" (said silently) "it was the banging, clanging window lattice."
    Glancing out, I quaked, upset by horrors hereinbefore,
        Perceiving: a "nevermore".

Completely disturbed, I said, "Utter, please, what prevails ahead.
    Repose, relief, cessation, or but more dreary 'nevermores'?"
The bird intruded thence – O, irritation ever since! –
    Then sat on Pallas' pallid bust, watching me (I sat not, therefore),
        And stated "nevermores".

Bemused by raven's dissonance, my soul exclaimed, "I seek intelligence;
    Explain thy purpose, or soon cease intoning forlorn 'nevermores'!"
"Nevermores", winged corvus proclaimed – thusly was a raven named?
    Actually maintain a surname, upon Pluvious seashore?
        I heard an oppressive "nevermore".

My sentiments extremely pained, to perceive an utterance so plain,
    Most interested, mystified, a meaning I hoped for.
"Surely," said the raven's watcher, "separate discourse is wiser.
    Therefore, liberation I'll obtain, retreating heretofore –
        Eliminating all the 'nevermores' ".

Still, the detestable raven just remained, unmoving, on sculptured bust.
    Always saying "never" (by a red chamber's door).
A poor, tender heartache maven – a sorrowful bird – a raven!
    O, I wished thoroughly, forthwith, that he&#
39;d fly heretofore.
        Still sitting, he recited "nevermores".

The raven's dirge induced alarm – "nevermore" quite wearisome.
    I meditated: "Might its utterances summarize of a calamity before?"
O, a sadness was manifest – a sorrowful cry of unrest;
    "O," I thought sincerely, "it's a melancholy great – furthermore,
        Removing doubt, this explains 'nevermores' ".

Seizing just that moment to sit – closely, carefully, advancing beside it,
    Sinking down, intrigued, where velvet cushion lay afore.
A creature, midnight-black, watched there – it studied my soul, unawares.
    Wherefore, explanations my insight entreated for.
        Silently, I pondered the "nevermores".

"Disentangle, nefarious bird! Disengage – I am disturbed!"
    Intently its eye burned, raising the cry within my core.
"That delectable Lenore – whose velvet pillow this was, heretofore,
    Departed thence, unsettling my consciousness therefore.
        She's returning – that maiden – aye, nevermore."

Since, to me, that thought was madness, I renounced continuing sadness.
    Continuing on, I soundly, adamantly forswore:
"Wretch," (addressing blackbird only) "fly swiftly – emancipate me!"
    "Respite, respite, detestable raven – and discharge me, I implore!"
        A ghostly answer of: "nevermore".

" 'Tis a prophet? Wraith? Strange devil? or the ultimate evil?"
    "Answer, tempter-sent creature!", I inquired, like before.
"Forlorn, though firmly undaunted, with 'nevermores' quite indoctrinated,
    Is everything depressing, generating great sorrow evermore?
        I am subdued!", I then swore.

In answer, the raven turned – relentless distress it spurned.
    "Comfort, surcease, quiet, silence!" – pleaded I for.
"Will my (abusive raven!) sorrows persist unabated?
    Nevermore Lenore respondeth?", adamantly I encored.
        The appeal was ignored.

"O, satanic inferno's denizen — go!", I said boldly, standing then.
    "Take henceforth loathsome "nevermores" – O, to an ugly Plutonian shore!
Let nary one expression, O bird, remain still here, replacing mirth.
    Promptly leave and retreat!", I resolutely swore.
        Blackbird's riposte: "nevermore".

So he sitteth, observing always, perching ominously on these doorways.
    Squatting on the stony bust so untroubled, O therefore.
Suffering stark raven's conversings, so I am condemned, subserving,
    To a nightmare cursed, containing miseries galore.
        Thus henceforth, I'll rise (from a darkness, a grave) — nevermore!

                        — original: E. Poe
                        — Redone by measuring circles.

Lipogram
    看看下面这句话有什么问题?

This is an unusual paragraph. I'm curious how quickly you can find out what is so unusual about it. It looks so plain you would think nothing was wrong with it! In fact, nothing is wrong with it! It is unusual though. Study it, and think about it, but you still may not find anything odd. But if you work at it a bit, you might find out! Try to do so without any coaching!

    答案:这段话里竟然没有一个字母e !
    Lipogram就是指的这样一个段落(甚至文章),里面缺少某个常用的字母。在所有的Lipogram中,写一个没有字母e的文章是最难的,因为字母e出现的频率最高。
    看一个比较长的Lipogram。下面这篇文章里硬是没有一个字母e!

Looking at this paragraph with confusion? I'll aid you slightly. Is any odd gap, lacuna or omission obvious to you? Got it now? No?

That's right – this is a lipogram – a book, paragraph or similar thing in writing that lacks a symbol, particularly (but not always) that symbol fifth in rank out of our 26 script-signs (found amidst 'd' and 'f'), which stands for a sound such as that in 'kiwi'. I won't bring it up right now, to avoid spoiling it. I could play with lipograms morning, noon and night. So it is with joy that I submit to you this location – truly, a loquacious location – for lipogram fanatics to join as a unit to glorify this form of wordplay.

As far as I know, this location has a distinct honour: it contains such an abundant quantity of words without using this taboo glyph that no WWW location can outmatch it. As of right now, it contains 1500 words without any hint of that symbol. Naturally, many long lipograms abound in print, including books, rhyming stanzas, and similar works of fiction. Most notably, La Disparition (A Void) by a famous author of a writing group known as Oulipo, stands out as a paragon of lipogrammaticity. I cannot aim to surpass it, but as a fan, I can look upon it with admiration.

Writing lipograms is, as you might think, a difficult task. In my lingo, 2/3 of all words contain that symbol which I am now avoiding, including many common pronouns and similar words commonly found in writing. Without using abbrvs., slang and odd jargon, which most purists scorn as cop-outs, it's darn tough to impart information in a stylistically satisfying way. Stripping paragraphs of particular symbols has a way of making looking at lipograms jarring. No doubt about it, a lipogram is a particularly arduous form of wordplay.

Having said this, acquiring a knack for lipogram composition isn't that hard, and may assist you in your non-lipogrammatic writing. Not to say that I'm without aid in this activity; my dictionary is always handy, as is a book with synonyms for words. And, notwithstanding any drawbacks flowing from passing many an hour looking for unusual ways to say ordinary things, it might aid your socialization skills. Chicks truly dig lipogrammatists, or so my old lady says.

Sadly, a handful of critics find lipograms ridiculous, ugly or without worth (as fiction or as wordplay). To such sorry saps, I say only that in constraining your thoughts and writing in a particular way aids in promoting branching paths of thought, thus amplifying vocabulary and instilling adroit linguistic skills among both young and old. By putting into praxis ways of thinking that wouldn't occur normally, lipograms call for authors to look at writing as an activity in ways that, frankly, wouldn't occur to such niggling adjudicators of linguistic conduct.

Withholding a symbol found in so many words has drastic symptoms that disallow many topics of discussion. (From this point on, I'll stick to talking about that sign I'm skipping right now). Using math is almost an impossibility; you can only main
tain 15 of all non-digital words for cardinal quantity up to 100, and hardly any at all past that point, though using digits is a good way out. You can go north or south, but talking about circumnavigating our world latitudinally is an impossibility. How can I possibly talk about various kinds of malt liquor, or parts of my body, without it? To top it all off, as an Anglo, strict prohibitions apply to naming of my own form of linguistic communication. I ought to thank my lucky stars that I'm not writing in lipogrammatic français, though, which holds on to only an octal portion of its original vocabulary.

But all is not lost. Surprisingly, profanity is mostly intact. As a practicing lipogrammatist, you'll find you want many such words, for it is a task so awkward as to call for cussing and cursing on a normal basis. A world map is truly a blissful oasis; my country (Canada) is totally satisfactory, as with most toponyms for nations (111 out of 186, by my count); with a bit of work, USA, UK, and so on, can still show up, and with twin island nations Trinidad and Tobago and Antigua and Barbuda (both with 17 glyphs) topping my list for prolongation. Musicians (particularly classical artists), astonishingly, hold firm as topics of discussion, with Bach, Bartok, Brahms, Chopin, Dvorak, Haydn, Holst, Liszt, Mozart, orff, Puccini, Rachmaninov, Rossini, Scarlatti, Schumann, Strauss, Stravinsky, Tchaikovsky and Vivaldi void of my lost non-consonant.

An additional branch of family Lipogrammatica consists of univocalics. This form of wordplay is akin to a lipogram, but contains a solitary sign that's not a consonant. To wit, a univocalic might omit 'a', 'i', 'o', and 'u' (but what about 'y'?). A univocalic has a sonorant quality that a lipogram lacks, so you must look at a lipogram, but contrarily, a univocalic is both auditory and visual, and has a strong sound if said aloud. Univocalic writing is hard to pull off, but if it's good, its payoff is gigantic.

另外推荐本Blog里的两个相关内容:
http://www.matrix67.com/blog/article.asp?id=104
http://www.matrix67.com/blog/article.asp?id=173

Matrix67收集整理
转贴请注明出处

十个有趣的英文文字游戏(上)

Crossword
    Crossword我就不用多废话了,这应该是最流行的英文文字游戏。和大多数人想象的不同,构造一个Crossword谜题非常难。真正的Crossword谜题里的空格比你想象的更多,整个填字区域要做到中心对称,而且通常每个Crossword需要有一个特定的主题。去年有一个记录片叫Wordplay,很不错(我给它打了8分)。记录片里介绍了很多和Crossword有关的文化,包括出谜人、解谜人、俱乐部、比赛等很多内容。
    下面是一个以数学为主题的Crossword,大家没事可以做做。答案在本文最后面。

  
Across

1. Cut corners
5. The __ plane, or S(7)
9. Hydrogen
14. Large reptile
16. Column
17. Gives the slope of a tangent to a curve
19. Book by Zienkiewicz and Taylor, abbr.
20. Divide
21. Sin reciprocal
22. The playing field, in nim
25. "I saw Blanusa's paper __ after it appeared." — Tutte
26. pronoun
27. Hydroxyl group bonded to a doubly-bonded carbon atom
28. (e^z – e^(-z))/2
29. Bar
30. The sphinx is a __-tile
31. __-digit
32. Fit
35. A type of map projection
38. The ___ hypothesis is independent of Zermelo-Fraenkel-Choice
39. Floor coverings, frequently symmetrical
40. Graph theorist Hai Peng
41. Angle
42. Branch or Dedekind
43. Math __ (where to find a prof)
44. 2, 4, 6, 30, 32, 34, 36, 40, 42 …
46. Art __
47. Computer Algebra: Systems and Algorithms for Algebraic Computation editor
48. MAA president Graham
49. Rule
50. As opposed to LHS
51. The gamma function has these at negative integers
57. Puzzle creator van Deventer
58. Tries
59. Paris river
60. Philosopher Descartes
61. Charts

Down

1. Saturnine
2. Director of Ulugh Beg's observatory
3. 3-30 KHz, as heard by "whistler" receivers
4. An OOPL or tower.
5. Plow
6. Supped
7. Proof of existance, without a specific example
8. Hermite orthogonal polynomial
9. Stat
10. GTE rival
11. Quasi-conformal enemy of Edmund Landau
12. (23/9)^5 and 109, for example
13. Ergo
15. Pilot stunt: "pulling ___"
18. Faraday theory, later proven by Arrhenius
22. Peace prize winner Shimon
23. J of ___ and Appl
24. The Inverse Variational Problem in Classical Mechanics author
25. The "sampling" function
26. A searching method for Ramsey numbers
28. "What I give form to in daylight is only one per cent of what I have __ in darkness." — Escher
29. boxers
31. High school math
32. Add-with-carry, inverse congruential, rule 30, dice, etc.
33. Chaos and Fractals author Dietmar
34. Graphica author Michael
36. ICOSAHOM editor Andrew
37. Focus, for example
42. Triangle part studied by Kimberling
43. In anatomy, away from the origin
44. More than 1500 math papers have his name
45. Where Set theory: On the structure of the real line was written
46. Actor Knotts
47. Number theorist Peter
49. Sported
50. Theorem
52. Cylinder
53. O'__ group (order 460815505920)
54. Skater Midori
55. Mind plotter
56. It's better than angle-angle-side

Anagram
    Anagram是指调整一个单词或短语的字母顺序后组成另外一个单词或短语,通常前后两者的关系有点讽刺意味。比如,《达芬奇密码》上就有一个:
    O, Draconian devil! Oh, lame saint! = Leonardo da Vinci, The Mona Lisa

    经典的Anagram非常有意思。看下面几个Anagram:
    Listen = Silent
    Dormitory = Dirty Room
    Desperation = A Rope Ends It
    Mother-in-law = Woman Hitler
    A telephone girl = Repeating "Hello"
    The country side = No City Dust Here

    一些Anagram有可能很长。比如这一个:
    To be or not to be: that is the question, whether tis nobler in the mind to suffer the slings and arrows of outrageous fortune.
    = In one of the Bard's best-thought-of tragedies, our insistent hero, Hamlet, queries on two fronts about how life turns rotten.

    另一个有趣的Anagram是这样:
    Eleven plus two = Twelve plus one

Pangram
    Pangram是指这样一种句子,它虽然不长,但包含了所有26个英文字母。Pangram常用于打字机测试和字体演示。大家最熟悉不过的是Windows字体演示时所用的Pangram:
    The quick brown fox jumps over the lazy dog.

    而Macintosh的字体演示则是使用的这个Pangram:
    Cozy lummox gives smart squid who asks for job pen.

    另一个比较常见的Pangram如下:
    Pack my box with five dozen liquor jugs.

    当然,有人肯定想问,有没有最短的Pangram?当然有。有的Pangram只有26个字母(每个字母恰好用一次),这样的Pangram叫做Perfect pangram。比如下面这一个:
    New job: fix Mr. Gluck's hazy TV, PDQ!

Autogram
    Autogram又叫做Self-enumerating Sentence,是指一句话的内容描述的正是这句话本身。下面是一些常见的Autogram:
    This sentence contains five words.
    This sentence contains thirty-six letters.
    There are fourteen vowels in this sentence.

    1982年,Scientific American月刊上刊登出一个Autogram杰作:

Only the fool would take trouble to verify that his sentence was composed of ten a's, three b's, four c's, four d's, forty-six e's, sixteen f's, four g's, thirteen h's, fifteen i's, two k's, nine l's, four m's, twenty-five n's, twenty-four o's, five p's, sixteen r's, forty-one s's, thirty-seven t's, ten u's, eight v's, eight w's, four x's, eleven y's, twenty-seven commas, twenty-three apostrophes, seven hyphens and, last but not least, a single !

    另一个类似的Autogram如下:

This autogram contains five a's, one b, two c's, two d's, thirty-one e's, five f's, five g's, eight h's, twelve i's, one j, one k, two l's, two m's, eighteen n's, sixteen o's, one p, one q, six r's, twenty-seven s's, twenty-one t's, three u's, seven v's, eight w's, three x's, four y's, and one z.

Palindrome
    Palindrome是指这样一种单词或句子,从左往右和从右往左读都是一样的。例如,单词eye, noon, level, racecar, redivider都是Palindrome。一些比较长的句子也可能是Palindrome,比如USACO上曾出现过这样一个Palindrome:
    Madam, I'm Adam.

    另一些有趣的Palindrome如下:
    Never odd or even.
    Was it a cat I saw?
    Step on no pets!
    Dammit, I'm mad!
    Rise to vote, sir.
&nbs
p;   God lived as a devil dog.
    A man, a plan, a canal — Panama!

    1814年,当拿破仑被流放到Elba岛时,拿破仑曾说过:
    Able was I ere I saw Elba.

    这里有一份号称世上最长的Palindrome。

Alphamagic Square
    1986年,一个叫Lee Sallows的电子工程师发现了这样一个3阶幻方:
5       22      18
28      15      2
12      8       25

    初看之下这个幻方似乎没有什么特别之处。然而,把它转换成文字后:
five            twenty-two      eighteen
twenty-eight    fifteen         two
twelve          eight           twenty-five

    再数一下每个单词的字母个数,我们可以得到一个新的幻方,它恰好由3到11这9个数字组成:
4       9       8
11      7       3
6       5       10

Matrix67收集整理
转贴请注明出处

      

魔方问题新进展:26步足以破解任何魔方

    最近,波士顿Northeastern大学的计算机科学家Daniel Kunkle证明了任何一个魔方可以在26步以内解开。这个结果打破了以往所有的记录。在解魔方的处理过程中,他构造了一些非常具有启发性的算法,这篇文章将简单地介绍一下这些算法。
    一个魔方大约有4.3 x 10^19种可能的初始状态,再牛的机器也不可能搜索完所有的可能。因此Kunkle和他的指导员Gene Cooperman想出了一些对魔方状态进行分类筛选的策略。
    Kunkle和Cooperman首先运用了一个小技巧将问题进行简化。如果魔方的每个面全是一种颜色,我们就认为魔方被解开,不管哪一面是哪一种颜色。换句话说,相互之间可以通过颜色置换得到的初始状态都是等价的。这样,“本质不同”的初始状态就减少到10^18种。
    接下来,他们开始观察一类更简单的问题:如果只允许180度转动(half-turn),有多少状态可以被解决。在10^18种状态中,只有大约15000种状态可以仅用180度旋转来破解。对于普通计算机来说,这个数目也不大,只需要不到一天的时间就可以搜索出解开所有15000多个魔方各自需要的最少步数。他们发现,这类初始状态中任何一个都可以在13步以内解决。
    然后他们需要做的就是找出,需要多少步才能把任意一种状态转化为这15000种特殊状态中的一个。为了完成这一工作,首先他们把所有的初始状态划分为若干个等价类,每个等价类里的状态都可以仅用180度转动互相得到。这样,同一个等价类中如果任一状态可以变换为其中一种特殊状态,同样的转动步骤也可以使该等价类的其它所有状态都变成特殊状态。最后他们找到了1.4 x 10^12个不同的等价类,需要解决的状态数由最初的4.3×10^19减少到1.4×10^12。但无论如何,10^12仍然是一个恐怖的数字。
    现在他们用了一台超级计算机来完成这个工作,并且使用了一些很有技巧性的决策来加速搜索过程。计算机需要耗费大量的时间读取硬盘上的数据,为了加快速度,Kunkle和Cooperman将数据巧妙地进行了处理,使得数据的排列正好与计算机读取的顺序相符,这样就节省了搜索硬盘的时间。
    “这种方法可以应用在任何一个组合问题上”,Kunkle说。他提到了西洋跳棋、国际象棋、航班安排和蛋白质摺叠等一系列问题。一种类似的组合学方法最近被用于寻找西洋跳棋的最优策略中。
    63小时的计算后,超级计算机得到的答案是,任何一种状态都能在16步以内转化为15000种特殊状态。而这些特殊状态又只需要13步达到最终状态,因此这种方法最终得到的结论是:29步以内可以解决任何一个魔方问题。
    但这个数字还不足以创造出新的记录,去年瑞典就曾经得到过27步内解决魔方问题的结论。Kunkle和Cooperman意识到,要想打破这个记录,他们还需要削减3步才行。
    应用他们现有的算法,只有8×10^7个状态集合还不能做到26步以内出解。再次对这些相对较少的状态进行搜索,最终他们找到了26步以内解决所有魔方的方法。
    7月29日他们在ISSAC(International Symposium on Symbolic and Algebraic Computation,国际符号和代数计算会议)上公布了这一结果。
    现在Kunkle和Cooperman希望把最大步骤数减少到25。他们认为他们可以对所有需要26步的状态进行暴力搜索来寻找更优的方案。
    虽然他们已经获得了很大的成功,但这一结果很可能还有改进的空间。许多学者认为20步以内足以解决任何魔方,但现在没有人能够证明。

Matrix67翻译,原文地址
做人要厚道,转贴请注明出处

另外两种证明素数无穷多的方法

    我们已经知道,素数有无穷多个。当时我们用的是最普遍的证明方法:

假设存在最大的素数P,那么我们可以构造一个新的数2 * 3 * 5 * 7 * … * P + 1(所有的素数乘起来加1)。显然这个数不能被任一素数整除(所有素数除它都余1),这说明我们找到了一个更大的素数。

    这里,我们将再提供两种新的证明方法,来自cut-the-knot两篇新文。

用Fermat数证明素数无穷多
    Fermat数是指形为2^(2^n)+1的数,我们把2^(2^n)+1记作F(n),其中n可以取所有自然数。显然所有的Fermat数都是奇数。一会儿我们将看到任两个Fermat数都是互素的,也就是说,每一个Fermat数的每一个素因子都与其它Fermat数的素因子不同。这也就说明,素数个数有无穷多。
    引理1:F(0) * F(1) * F(2) * … * F(n-1) = F(n) – 2, n>=1
    证明:数学归纳法。F(0)=3且F(1)=5,那么k=1时显然成立。假设k=n成立,则当k=n+1时:
    F(0) * F(1) * F(2) * … * F(n)
  = ( F(0) * F(1) * F(2) * … * F(n-1) ) * F(n)
  = ( F(n)-2 ) * F(n)
  = ( 2^(2^n)-1 ) * ( 2^(2^n)+1 )
  = 2^(2^(n+1))-1
  = F(n+1)-2

    引理2:对任意两个不相等的自然数n和m,有F(n)和F(m)互素。
    证明:假设t同时整除F(n)和F(m),m<n。根据引理1,有:
    F(n)=F(0) * F(1) * F(2) * … * F(m) * … * F(n-1) – 2
    这说明t可以整除
    F(0) * F(1) * F(2) * … * F(m) * … * F(n-1) – F(n) = 2
    注意到2只有两个因数1和2。前面说过Fermat数都是奇数,因此不可能被2整除。这样,t只能为1,这就证明了两个数互素。

用*-集合证明素数无穷多
    *-集合是一个正整数集合{a1, a2, … an},使得对所有不相等的i和j都有ai-aj整除ai。
    引理1:对所有n>=2,都存在一个大小为n的*-集合。
    证明:数学归纳法。{1,2}显然是一个大小为2的*-集合。假设{a1, a2, … an}是一个*-集合。定义b0为a1*a2*…*an(即所有ai的乘积)。对所有不超过n的正整数k,令bk=b0+ak,那么{b0, b1, b2, …, bn}就是一个大小为n+1的*-集。

    引理2:假设{a1, a2, … an}是一个*-集合。对所有不超过n的正整数i,定义fi=2^ai+1,那么f1, f2, …, fn两两互素。
    证明:显然fi都是奇数。假设fk和fm(fk>fm)可以被同一个素数p整除,那么p也只能是奇数。p可以整除fk-fm即2^am * ( 2^(ak-am)-1 )。由于p是奇数,那么它只可能是整除2^(ak-am)-1。
    如果有s整除t,那么2^s-1整除2^t-1。于是,根据*-集合的定义,2^(ak-am)-1整除2^ak-1。那么p就可以整除2^ak-1。但p也能整除2^ak+1,于是我们得出p整除2,这与p为奇数矛盾。

    定理:素数有无穷多个
    证明:根据引理1和2,对任意大的n,都存在大小为n的集合,里面的数两两互素,即至少存在n个不同的素因子。这就说明了素数的个数可以任意多。

OI/MO必备:巨牛无比的公式、定理速查表

    数学考试时我最怕的就是三角函数,几十个公式我一个都背不到。那时我有了制作公式定理表的想法。经过反复尝试,我那张表已经设计得非常合理了,表里的内容也初具规模。我复印了几份给我的几个同学,反映都还不错,其它的同学听说了都想来找我要一份。当初我以为我那张表已经很牛了,今天终于发现我错了。
    刚才偶然发现一份非常牛的公式定理表,满满写了10页,不但包含有完整的三角公式、微分表、积分表,还有排列组合公式、概率公式、质数表、杨辉三角等等,甚至还有主定理、图论概念等东西。想要公式定理手册的OI/MO牛不用再去买中学数理化的口袋书了,你真正需要的东西那上面根本没有;这10页的速查表才是真正为你设计的,打印一份随身携带更能体现你nerd/geek的身份……
    点击这里下载(pdf, 154KB) 请勿直接链接到此文件