Mars

问题参见http://www.cut-the-knot.org/gproblems.shtml

这是一个很有意思的问题：四个旅行者A，B，C，D沿着各自所在的直线，以自己一定的速度前进。这四条直线既没有两条互相平行，也没有三条交于一点。结果， A在路上碰到了B，C，D，B在路上除了遇到A外，也遇见了C，D。证明：C和D也一定曾经相遇过。

进一步地讨论表明，如果N个旅行者沿着各自所在的直线，以自己一定的速度前进。这N条直线既没有两条互相平行，也没有三条交于一点。如果， 第一个和第二个旅行者相遇，并且他们各自还遇到其他所有旅行者。那么任何两个旅行者都会相遇。

问题很有趣，而且这两个问题是相互等价的。问题解决后，我的体会是后者更容易解决。（很多时候都是这样，一般化命题要比特殊化命题要容易一些。有机会，我会多举一些这样的例子。）

解决这个问题的关键是，这些旅行者始终都处在同一条直线上，并且随着时间的推移，所有这种直线是相互平行的。

另外，还有一些可以考虑的问题：

1、如果已知问题条件中所有的相遇的时间，你能求出其他任何两个旅行者的相遇时间吗？

2、如果把这些相遇时间排成序列 ，有多少种不同的可能呢？

Share This

PEN收集了相当多初等数论问题。大多数问题取自世界各地的各类数学竞赛：IMO，APMO，APMC，Putnam等等，也有部分问题来自各种数学杂志，例如MM，AMM等。作者希望尽力维护这个问题集，任何人发现书中的错误（包括符号、拼写错误），或者是书中没有收录，但有趣、有挑战性的问题，都可以发给两位作者：Peter Vandendriessche 和 Hojoo Lee。

PEN（PDF格式）按照章节， 将数论问题分为：整除性理论、Zn上的算术、素数和合数、有理数和无理数、丢潘图方程、数论函数、整数序列、组合数论等部分，内容详尽，大家可以到PEN论坛参与讨论。问题难度不一，是不错的参考和练习资料。

另外，Project Pen （Blog）专门讨论Pen中问题的解答，很不错！

我完成的问题列表（部分问题97年以前就做过），其中红色表示问题困难，

A3 A5 A6 A7 A8 A9 A11 A13 A14 A15 A18 A20 A21 A22 A23 A26 A27 A30 A31 A43 A44 A47 A55 A56 A57 A75 A76 A77 A83 A84 A85 A86 A87 A94

E23

F3 F4 F5 F6 F7 F8 F16

G2 G3 G8 G9 G11

H11

有机会把问题的按有趣、困难程度分分类。

Share This

Firebug是我最喜欢的Firefox插件，我想也应该是所有页面开发、设计人员最钟爱的工具之一。回想起最初的开发历程，在IE下调试Javascript和CSS的痛苦历历在目，虽然尝试了很多工具：HttpWatch, IE Watch, DevelopToolbar, Fiddler，但总是觉得不是很顺手。 后来很长一段时间使用Maxthon调试Javascript，可以很方便地编写脚本与当前页面交互，使用PageView查看页面文档结构，感觉颇为方便，直到去年的某一天，我遇见了令人怦然心动的Firebug。

在Firebug之前，Firefox的插件Javascript Debugger, Web Developer都是非常优秀的页面调试、开发工具。但从方便使用、界面友好性来说，我更喜欢Firebug。功能也非常强大，我用的比较多的功能有：

1. 调试Ajax：在IE下开发Ajax，你是不是对请求是不是已经返回，返回的内容是什么感到有些困惑？是不是还在使用alert来查看信息？如果使用Firebug调试Ajax，你就不会有这样的困惑。在Firebug下，你可以清晰地看到发送的Ajax请求和参数，请求是否超时或者返回错误，以及正确的返回内容（XML或者JSON）。
2. 查看页面DOM结构：IE下的插件提供的DOM Tree Inspector的功能，和Firebug差不多，你可以用鼠标点击页面元素，DOM Tree则迅速定位到该元素，或者你也可以浏览DOM Tree，页面上的对应元素也会高亮显示。
3. 调试和修改CSS：FIrebug可以告知你非常详细的CSS信息，包括该页面元素的该样式来自哪个CSS定义的，哪些定义的CSS没有作用，更酷的是，你可以随时修改CSS，添加属性，页面会立即更新。你是不是觉得这种方式调试CSS非常方便呢？
4. 调试Javascript代码：能够调试Javascript代码，一直是我的梦想。你是不是一样已经厌倦了alert，这种方式不但粗鲁，而且不便于调试异步程序。Firebug可以设置break point，你可以单步调试，提供watch窗口，方便的查看所有变量和对象属性，也可以使用console.log记录调试日志。Oh，My God！
5. 调试页面加载性能：调试页面性能也是头疼的事情，在IE里，我根本就不知道文件加载了多长时间，是不是需要优化。Firebug不但列出了所有这些信息，还包括加载顺序，另外，基于Firebug的插件YSlow甚至会恰当的提醒你，需要优化的地方和规则。

这里几乎列出了Firebug的所有功能，它也满足了我的所有需求。如果你还没有使用，就赶紧尝试一下！

Share This

这些问题都属原创，但部分问题可能属成题，哪位知道的，给俺指出来。我查到了，也会在这里加上备注。

数 论

问题1 一根长为m*n的木棍，标上它的所有m等分点和n等分点,其中m与n都是自然数且互素，这样，这个木棍被分成了m+n-1段，现在将这些小段交替染上红色和蓝色，问红色小段的总长度和蓝色小段的总长度相差多少？

问题2 满足下列三个条件的数是哪些呢？1）它是3的倍数；2）二进制下，它的各位中一共有3个1；3）它是某个自然数的4次方。

几 何

代 数

问题1 在区间[0， 1]中随机选取n个点，其中最大者与最小者相差x_n，求x_n的数学期望。

问题2 a₀=0, a_n+1 = a_n/2 + sqrt(1 + a_n²/4)。证明：lim a_n/sqrt(n) = sqrt(2)。

问题3 这部分包含两个问题：

i）证明：存在全体自然数的一个排列，是的任意前k的和是k的倍数。

ii） 定义如下序列{a_k}:a₁ = 1,递归地定义a_k：a_k是满足 k|a₁+…+a_k的不同于a₁,a₂,…,a_k-1得最小自然
数，那么
1){a_k}是N（自然数集合）的一个排列；
2)证明: a_k = [α*k]*k - [α*(k-1)]*(k-1) + 1， 其中α是满足α^2 + α = 1的正实数，[x]是Gauss函数；
3){F_[n]}是Fibonacci数列，那么a_F[2k-1] = F_[2k]，a_F[2k] = F_[2k-1]。

问题4 互不相等的实数x₁，…，x_n满足：a = x₁+1/x₂ = x₂+1/x₃ = … = x_n-1+1/x_n = x_n+1/x_1。证明：a = 2*cos(k*pi/n)，其中0<=k<n ，(n,k)=1

组 合

问题1 这部分包含四个小类似或者相关的问题：

i) a₁，a₂，…，a₁₀满足：1) 总和是 1000; 2) a₁ = 1; 3) a_k-1 <= a_k <= 2a_k-1;
则任意1<=s<= 1000都可以表示为a₁，a₂，…，a₁₀中某些的和。

ii) a₁，a₂，…，a₁₀满足：1) 总和是 1000; 2) a1 = 1; 3) a_k-1 <= a_k <= 1 + a₁ + a₂ + … + a_k-1;
则任意1<=s<= 1000都可以表示为a₁，a₂，…，a₁₀中某些的和。

iii)证明：ii)是充要的

iv) a_k∈N,k=1,2,…,n,满足：sigma(a_k) = 2n,a₁<=a₂<=…<=a_n,那么{a₁,…,a_n}，可以表示所有1~2n的数，当且仅当(a₁,a₂,…,a_n) 不是 (2,2,…,2)或者(1,1,…,1,n+1)

—最后一次编辑时间20080318—

Share This

最近在项目中遇到一个十分令人困惑的问题：在搜索页面，用户指定文档修改的日期来搜索文档时，要么找不到文档，要么就是找到似是而非的文档。而在数据库中，指定日期的文档明明是存在的。煞是苦恼哇！

是什么东东在作祟呢？解读了Lucene源代码类DateTools之后豁然开朗。一切都用从Calendar谈起。java.util.Calendar是各种日期相关计算常用的类，功能甚是强大。另一个常用的类是java.util.Date，但其中的大部分函数从JDK 1.1开始就不再推荐使用了。

考虑一种非常极端的系统分布情形：我们的数据库在Fiji（GMT+12），应用系统部署在San Francisco（GMT-8）的Linux服务器上，而用户却遍布世界各地。比如A，Beijing（GMT+8）的用户；B，NewYork（GMT-5）。这里我们不考虑夏令时时间调整。

2008年03月07日，NewYork时间21:00，B向系统发布了一篇水文《3.7 mm’s Day》。一个小时后，B想重新修改这篇文章，于是他在系统中查找20080307发表的文章，却发现文章不见了！！！
于是，他十分着急地告知在Beijing的A，请他确认一下文章。A此时正是Beijing时间2008年03月08日11:00。于是，A打开浏览器，进入检索系统，查找日期是20080308发表的文章。（在A看来，这篇文章是03月08日发布的）A坚定地告知B，文章好好地在那里呢。

这之间到底是发生了什么问题？

用户发表文章时（20080307 21:00 GMT-5，NewYork ），服务器本地时间是（20080307 18:00 GMT-8, SanFrancisco）。它会向数据库写入数据，数据库本地时间是（20080308 14:00 GMT+12, Fiji），同时在本地更新Lucene索引。用户检索数据，是通过查询Lucene的索引来获得结果。

A，B两个用户检索文章时，分别使用20080307和20080308去查询，显然只有一个人会成功检索到。而这个人却不是发表文章的人？？？因为，索引文件里写的日期是20080308。这个日期既不是从应用服务器所在时区的时间计算得来的，也不是从数据库服务器所在时区获得的。那它是根据什么计算的呢？

由于客户端用户与服务器用户处在不同的时区，每个人看到的时间都是不一样的，但是存储在服务器上的文章及其创建时间是唯一的。在索引中，我们要用一个与时区无关的时间来表示文章的时间，那么格林威治时间（Greenwich Mean Time）就是不二之选了。

在上面的例子中，A发表文章的时间恰是格林威治时间20080308午夜2:00。Lucene正是使用这个时间来创建被索引的日期项。（参见源代码org.apache.lucene.document.DateTools，设置TimeZone为GMT）。导致上面这个问题的根本原因是客户端部分没有考虑用户的时区差别。

要解决这个bug，可以遵循下面的规则：

1. Lucene对时间和日期做索引时，至少要使用DateTools.Resolution.HOUR以上精度；
2. 客户端需根据用户所在的时区，在发送请求时，修改时间参数为GMT时间，也要至少精确到HOUR以上：DateFormat.toUTC(new Date(), ‘hour’)，对应的脚本程序如下所示，其中关于时间的函数可以参考“http://www.webreference.com/javascript/reference/core_ref/date.html”：

   DateFormat = {	//date format is MM/dd/yyyy
   /**
    * string like 'MM/dd/yyyy' to date object
    */
   parse: function(localDate) {
   	var d = new Date();
   	var ds = localDate.split('/');
   	d.setMonth(parseInt(ds[0])-1);
   	d.setDate(parseInt(ds[1]));
   	d.setYear(parseInt(ds[2]));
   	d.setHours(0);
   	d.setMinutes(0);
   	d.setSeconds(0);
   	return d;
   },
   /**
    * date object to UTC string.
    */
   toUTC: function(d, format) {
   	var s = '';
   	if ('year' == format) {	//yyyy
   		s = d.getUTCFullYear();
   	} else if ('month' == format) {	//yyyyMM
   		s = d.getUTCFullYear()
   			+ this._patch(d.getUTCMonth()+1, 2);
   	} else if ('day' == format) {	//yyyyMMdd
   		s = d.getUTCFullYear()
   			+ this._patch(d.getUTCMonth(), 2)
   			+ this._patch(d.getUTCDate()+1, 2);
   	} else if ('hour' == format) {	//yyyyMMddHH
   		s = d.getUTCFullYear()
   			+ this._patch(d.getUTCMonth()+1, 2)
   			+ this._patch(d.getUTCDate(), 2)
   			+ this._patch(d.getUTCHours(), 2);
   	} else if ('minute' == format) {//yyyyMMddHHmm
   		s = d.getUTCFullYear()
   			+ this._patch(d.getUTCMonth()+1, 2)
   			+ this._patch(d.getUTCDate(), 2)
   			+ this._patch(d.getUTCHours(), 2)
   			+ this._patch(d.getUTCMinutes(), 2);
   	} else if ('second' == format) {//yyyyMMddHHmmss
   		s = d.getUTCFullYear()
   			+ this._patch(d.getUTCMonth()+1, 2)
   			+ this._patch(d.getUTCDate(), 2)
   			+ this._patch(d.getUTCHours(), 2)
   			+ this._patch(d.getUTCMinutes(), 2)
   			+ this._patch(d.getUTCSeconds(), 2);
   	} else if ('millisecond' == format) {//yyyyMMddHHmmssSSS
   		s = d.getUTCFullYear()
   			+ this._patch(d.getUTCMonth()+1, 2)
   			+ this._patch(d.getUTCDate(), 2)
   			+ this._patch(d.getUTCHours(), 2)
   			+ this._patch(d.getUTCMinutes(), 2)
   			+ this._patch(d.getUTCSeconds(), 2)
   			+ this._patch(d.getUTCMilliseconds(), 3);
   	}
   	return s;
   },
   _patch: function(s, len) {
   	s = ''+s;
   	if (s.length < len) {
   		s = '0'+s;
   	}
   	return s;
   }
   }

Share This

纸牌大家都常玩，洗牌里面学问多多。大家总是期望多次洗牌后，牌的分布变得随机。D. Aldous、P. Diaconis的分析结果表明，要达到“比较完美”的洗牌效果，至少需要洗5次，要达到“完美”洗牌，则需要7次，同时更多次数不会有太多改进。

我们这里考虑的洗牌更加理想化。简单的洗牌方式是将牌分成数目相同的两堆（每堆27张），然后交错洗牌。具体的说就是：1～54张牌，分别从1到54编号。洗牌按照如下步骤：a）分作两堆，一堆编号是1～27，另一堆是28~54；b）交错洗牌：牌1处在位置2，牌2处在位置4，……，牌27处在位置54，牌28处在位置1，牌29处在位置3，……，牌54处在位置53。说得稍微数学一点，就是：如果K<28，牌K处在位置2K；否则，牌K处在位置2K-55。这样做，经过一次洗牌后，所有牌的位置都发生了变化。一个好的洗牌应该尽量让牌随机排布，这里的洗牌方式是不是很完美呢？实际上经过20次同样的洗牌操作，你会沮丧的发现，所有的牌都回到了初始位置。这种洗牌非常糟糕！

考虑另一种理想的洗牌方式：始终采用同样的洗牌操作，而且每次处于K位置的牌总会放到对应的M位置。比如，如果第一次洗牌的时候，将第7张牌放在了20张牌的位置，那么在后面的洗牌过程中，始终将当前第7张牌放在了20张牌的位置。尽管，设置不同的K，M，洗牌方式变化很大，但是一旦K和M的对应关系确定了，总有一天，牌的位置会恢复到和初始状态一样。

一个有趣的问题是，一副54张的牌，最多需要洗多少次才会恢复初始状态，达到这个最大值的洗牌方式又有多少种呢？（分别是360360，54，过段日子，有时间了详细论述）

Share This

表单是用户与服务器交互的重要途径。表单控件行为将直接影响用户体验，我们需要深入了解表单和表单控件。

一、表单控件

常见的表单控件包括按钮、单选或者多选框、文本等。

1. 按钮（button） ：表单会自动识别<input type=”submit”/>和<input type=”reset”/>为提交按钮和重置按钮。顾名思义，点击该按钮，其默认行为是提交表单或者重置表单控件的值。一般提交、重置按钮都不多于一个。如果你希望在表单提交之前做些验证，只有验证通过才会提交表单，可以实现submit的click方法，返回值如果是false，表单就不会提交：

   $('input[@type="submit"]').click(function() {
     if (!check_ok) {
         alert("Check Failed! Dont Submit.");
         return false;
     } else {
         return true;
     }
   })

   而在提交或者重置后面的处理，可以在表单的属性onsubmit和onreset中实现。除了这两个特殊的按钮外，我们还可以在表单中添加最普通的按钮（push button，一般是<input type=”button”/>或者<button/>），用脚本定义它们的行为。推荐使用<button/>，因为它的表现形式更加丰富。

2. 复选框（checkbox）：复选框的状态只有两种，checked或者unchecked。在表单提交时，只有状态是checked的复选框状态会发送给服务器，对应的参数值为“on”，很特别，不是yes也不是true。
3. 单选按钮（radio button）：单选按钮一般是具有相同name属性值的一组按钮，不过它们之间具有排他性，用户要么一个也不选择，要么只能选择其中一个。表单提交时，状态是checked的按钮，它的属性value的值作为服务器参数值。
4. 单选或多选列表（menu）：列表对应的HTML标签是<select/>，我们可以设置它是多选或者单选，显示为下拉框还是列表框。表单提交时，多选列表框将会把所有选择的<option/>的value值用逗号(comma)分隔组成一个长字符串发送给服务器。
5. 文本框（text input）：最常见的文本框是<input type=”text”/>，不过它只能单行编辑。表单提交时，它的属性value的值作为参数值。另一个常用的多行编辑文本框是<textarea/>，与<input/>不同的是，表单提交，将会把innerText作为参数值。
6. 文件框（file select）：这个控件<input type=”file”/>用于上传文件到服务器。为了安全起见，浏览器不允许使用脚本修改该控件的属性value等。
7. 隐藏域（hidden）：有时候我们不希望用户修改某些参数的值，在页面上，这些控件或者参数对用户是不可见的，隐藏域<input type=”hidden”/>就可以恰到好处地达到这个目的。我们可以将参数值作为隐藏域属性value的值。
8. 对象（object）：不常用，暂不讨论。

表单提交时，服务器端获得参数名称与页面表单控件的属性name是一一对应的。所有控件都具有初始值和当前值。初始值由控件属性“value”初始的值决定（<textarea/>，初始值由该标签内部的内容决 定，即<textarea>initial_value_here<textarea/>；<object/>初始 值由<object/>节点初始化过程决定）；当这些控件属性的值被Javascript修改或者被用户修改时，初始值是不会发生变化的，所以当用户reset表单时，所有控件的当前值将被设置为初始值。

二、 表单

最常见的表单用法是：<form name=”some_form” action=”action_path” method=”POST|GET”/>。

1. method：method默认是GET。使用GET方法提交，所有的参数都以URL的形式发送给服务器，优点是用户或者调试都可以一目了然，缺点自然是不能隐藏参数，另外，就是URL的长度不能太长。例如IE规定URL长度不能超过2048+35=2083个字节(虽然RFC 2616: Hypertext Transfer Protocol — HTTP/1.1 并没有此规定)。对于POST，则没有对参数长度的限制要小很多，一般复杂的表单数据尽量使用POST方法。
2. action：表单提交后，将会交由服务器来处理，处理逻辑由action指定；
3. name：name属性常用于脚本中获取该表单元素；
4. onsubmit, onrese：事件。在表单提交或者重置后会运行对应的脚本；
5. accept-charset：指定服务器端接受的字符集编码，不常用。

另一种常见的表单用法是上传文件：<form name=”some_form” action=”action_path” method=”POST|GET” enctype=”multipart/form-data” accept=”MIMES”/>

1. enctype：指定上传到服务器端的数据编码方式，默认值是”application/x-www-form-urlencoded”。如果要上传文件，必须设置为”multipart/form-data”（参见RFC 2388:Returning Values from Forms: multipart/form-data）；服务器端也需要使用特殊的方法获得request中的文件数据，常用的有Apache Commons FileUpload。
2. accept：用来限定客户端上传的文件类型，值是用逗号分隔的MIME Type，比如”image/png,image/gif”。

Share This

一个简单的的二次方程你可以这样做，还可以那样做，而且有四个解。着实让人难以理解。这次讲得例子更加不可思议：2^X=X。可能吗，这是超越方程，老老实实用数值方法？按常理出牌，就缺少了很多乐趣。循规蹈矩做事情不是我们的风格！

这个方程和以前一样，找满足同余方程2^X≡X(mod 10ⁿ)的整数解。

不过这个方程确实是有些困难的，你牛的话，另说！可以尝试一下n=1,2,3这些简单情形。这里，我们也先给出问题的解：

n=1的时候，有两组解X≡14(mod 20), X≡16(mod 20)。
n>=2时，恰有一组解，而且解的形式为X≡X_n(mod 10ⁿ)，下面给出计算X_n的算法：
step1. X₂ = 36;
step2. X_n+1 = 2^X_n mod 10ⁿ⁺¹
这样可以得到X₃ = 736, X₄ = 8736, … …

有了算法，证明也不太繁，就不说了（其实真实的原因是“Mars发现一个绝妙的证明，但是这里空白太小，写不下”）。
但是计算器是没法满足这里计算的需要的（如果编程序，倒是很方便，而且速度快），在网上找了一个大整数计算器，将就用了。
//计算了一下X₃₆₀（此X360非彼X360）：
90864032603899870131537628336658436847486191414440397801
86719944644055340240243583302228112137883668786525668075
67807965732988916890861556848395955536540916260996042992
69691927189062503623574424769420495363221080797961763483
96814510511517357545924365469352001738442256888719022509
40179898553892709121212828416286245701455286968726001598
53338098615075353432948736

这里的一个推论就是：对任何n>=2，存在唯一的n位数m（可以以数字零开头），使得2^m 的末n位就是m。
有趣的是，这里2不是本质的，只要a不是10的倍数，一样有下面的结论成立：对任何n>=2，存在唯一的n位数m（可以以0开头），使得a^m的末n位就是m。

思考一下，对于给定的a，n，你能告诉我怎么求出所有的m吗？

Share This