Un des “problèmes plaisans et délectables” de Claude Berge

详细信息    查看全文

• 作者：David Avis and Antoine Deza
• 关键词：Berge moves ; Berge sorting
• 刊名：Discrete Mathematics
• 出版年：2006
• 出版时间：6 October 2006
• 年：2006
• 卷：306
• 期：19-20
• 页码：2299-2302
• 全文大小：169 K

文摘

Between 1962 and 1966 Claude Berge edited a series of columns that appeared in the Revue Française de Recherche Opérationnelle, entitled Problèmes plaisans et délectables, in homage of the 17th century work of Bachet. Each of these columns gives a new problem, along with solutions for earlier problems supplied by readers. The last of these columns contains a sorting problem, problem 41, in which we are given a string of black"" href=""/science?_ob=MathURL&_method=retrieve&_udi=B6V00-4KFMMFW-1&_mathId=mml37&_user=10&_cdi=5632&_rdoc=5&_handle=V-WA-A-W-WD-MsSAYZW-UUA-U-AAZCBUZCBE-AAZWYYDBBE-VBBCDAUY-WD-U&_acct=C000050221&_version=1&_userid=10&md5=b4298ab33ca0c240271016e1f7f4f146"" title=""Click to view the MathML source"">n alternately white and black pegs on a one-dimensional board consisting of an unlimited number of empty holes. We are required to rearrange the pegs into a string of consecutive white and black pegs, using only moves which take a pair of adjacent pegs to two vacant adjacent holes. With black"" href=""/science?_ob=MathURL&_method=retrieve&_udi=B6V00-4KFMMFW-1&_mathId=mml38&_user=10&_cdi=5632&_rdoc=5&_handle=V-WA-A-W-WD-MsSAYZW-UUA-U-AAZCBUZCBE-AAZWYYDBBE-VBBCDAUY-WD-U&_acct=C000050221&_version=1&_userid=10&md5=cabe9f9588abf4b17795d054d0544a44"" title=""Click to view the MathML source"">h(n) denoting the minimum number of moves needed to obtain a string of white pegs followed by black pegs, Berge gives the values black"" href=""/science?_ob=MathURL&_method=retrieve&_udi=B6V00-4KFMMFW-1&_mathId=mml39&_user=10&_cdi=5632&_rdoc=5&_handle=V-WA-A-W-WD-MsSAYZW-UUA-U-AAZCBUZCBE-AAZWYYDBBE-VBBCDAUY-WD-U&_acct=C000050221&_version=1&_userid=10&md5=728cdd50a0c5d2f825cacc36240e2b7a"" title=""Click to view the MathML source"">h(5)=3, black"" href=""/science?_ob=MathURL&_method=retrieve&_udi=B6V00-4KFMMFW-1&_mathId=mml40&_user=10&_cdi=5632&_rdoc=5&_handle=V-WA-A-W-WD-MsSAYZW-UUA-U-AAZCBUZCBE-AAZWYYDBBE-VBBCDAUY-WD-U&_acct=C000050221&_version=1&_userid=10&md5=7cf6f2f98475d0382973f9dc6ad2ec3d"" title=""Click to view the MathML source"">h(6)=3 and black"" href=""/science?_ob=MathURL&_method=retrieve&_udi=B6V00-4KFMMFW-1&_mathId=mml41&_user=10&_cdi=5632&_rdoc=5&_handle=V-WA-A-W-WD-MsSAYZW-UUA-U-AAZCBUZCBE-AAZWYYDBBE-VBBCDAUY-WD-U&_acct=C000050221&_version=1&_userid=10&md5=cf75137b1419314ffd21aa6fa0821295"" title=""Click to view the MathML source"">h(7)=4 and asks the reader to determine whether or not the function black"" href=""/science?_ob=MathURL&_method=retrieve&_udi=B6V00-4KFMMFW-1&_mathId=mml42&_user=10&_cdi=5632&_rdoc=5&_handle=V-WA-A-W-WD-MsSAYZW-UUA-U-AAZCBUZCBE-AAZWYYDBBE-VBBCDAUY-WD-U&_acct=C000050221&_version=1&_userid=10&md5=446438f7055bd1970537df204e139238"" title=""Click to view the MathML source"">h(n) is increasing. This was the last issue of the Revue, and as far as we can tell, no solution has been published. In this note we offer a solution to problem 41 by showing that black"" href=""/science?_ob=MathURL&_method=retrieve&_udi=B6V00-4KFMMFW-1&_mathId=mml43&_user=10&_cdi=5632&_rdoc=5&_handle=V-WA-A-W-WD-MsSAYZW-UUA-U-AAZCBUZCBE-AAZWYYDBBE-VBBCDAUY-WD-U&_acct=C000050221&_version=1&_userid=10&md5=12519bb28235424d58089b22a52f145d"" title=""Click to view the MathML source"">h(n)=n/2 for black"" href=""/science?_ob=MathURL&_method=retrieve&_udi=B6V00-4KFMMFW-1&_mathId=mml44&_user=10&_cdi=5632&_rdoc=5&_handle=V-WA-A-W-WD-MsSAYZW-UUA-U-AAZCBUZCBE-AAZWYYDBBE-VBBCDAUY-WD-U&_acct=C000050221&_version=1&_userid=10&md5=c804b6d949fa4d39878de2935515f262"" title=""Click to view the MathML source"">n5.

Résumé

Dans une rubrique de la Revue Française de Recherche Opérationnelle intitulée Problèmes plaisans et délectables en hommage à l’œuvre du 17ème siècle de Bachet, Berge proposa en 1966 un problème d’ordonnancement de black"" href=""/science?_ob=MathURL&_method=retrieve&_udi=B6V00-4KFMMFW-1&_mathId=mml45&_user=10&_cdi=5632&_rdoc=5&_handle=V-WA-A-W-WD-MsSAYZW-UUA-U-AAZCBUZCBE-AAZWYYDBBE-VBBCDAUY-WD-U&_acct=C000050221&_version=1&_userid=10&md5=aa3bda275070df976c38b6cadf21afaf"" title=""Click to view the MathML source"">n jetons alternativement noirs et blancs à l’aide d’un coup qui déplace black"" href=""/science?_ob=MathURL&_method=retrieve&_udi=B6V00-4KFMMFW-1&_mathId=mml46&_user=10&_cdi=5632&_rdoc=5&_handle=V-WA-A-W-WD-MsSAYZW-UUA-U-AAZCBUZCBE-AAZWYYDBBE-VBBCDAUY-WD-U&_acct=C000050221&_version=1&_userid=10&md5=d6ea03324f7a4cb592b0fafd6dcf4389"" title=""Click to view the MathML source"">2 jetons adjacents. Notant black"" href=""/science?_ob=MathURL&_method=retrieve&_udi=B6V00-4KFMMFW-1&_mathId=mml47&_user=10&_cdi=5632&_rdoc=5&_handle=V-WA-A-W-WD-MsSAYZW-UUA-U-AAZCBUZCBE-AAZWYYDBBE-VBBCDAUY-WD-U&_acct=C000050221&_version=1&_userid=10&md5=51b60075193caf77013f2d9397a5baee"" title=""Click to view the MathML source"">h(n) le nombre minimum de coups nécessaires pour obtenir une séquence de jetons blancs suivis de jetons noirs, Berge montre que black"" href=""/science?_ob=MathURL&_method=retrieve&_udi=B6V00-4KFMMFW-1&_mathId=mml48&_user=10&_cdi=5632&_rdoc=5&_handle=V-WA-A-W-WD-MsSAYZW-UUA-U-AAZCBUZCBE-AAZWYYDBBE-VBBCDAUY-WD-U&_acct=C000050221&_version=1&_userid=10&md5=48522884f66fcd80734a444f6f42e909"" title=""Click to view the MathML source"">h(5)=3, black"" href=""/science?_ob=MathURL&_method=retrieve&_udi=B6V00-4KFMMFW-1&_mathId=mml49&_user=10&_cdi=5632&_rdoc=5&_handle=V-WA-A-W-WD-MsSAYZW-UUA-U-AAZCBUZCBE-AAZWYYDBBE-VBBCDAUY-WD-U&_acct=C000050221&_version=1&_userid=10&md5=89a2fd46edce4740c6e2f9aa1792d19c"" title=""Click to view the MathML source"">h(6)=3 et black"" href=""/science?_ob=MathURL&_method=retrieve&_udi=B6V00-4KFMMFW-1&_mathId=mml50&_user=10&_cdi=5632&_rdoc=5&_handle=V-WA-A-W-WD-MsSAYZW-UUA-U-AAZCBUZCBE-AAZWYYDBBE-VBBCDAUY-WD-U&_acct=C000050221&_version=1&_userid=10&md5=c4553ad67773f653ae72e6885ccd9911"" title=""Click to view the MathML source"">h(7)=4 et semble indiquer que la fonction black"" href=""/science?_ob=MathURL&_method=retrieve&_udi=B6V00-4KFMMFW-1&_mathId=mml51&_user=10&_cdi=5632&_rdoc=5&_handle=V-WA-A-W-WD-MsSAYZW-UUA-U-AAZCBUZCBE-AAZWYYDBBE-VBBCDAUY-WD-U&_acct=C000050221&_version=1&_userid=10&md5=914db62bf9be52f25a9c3c0ac5b37d90"" title=""Click to view the MathML source"">h(n) est croissante. Dans cette note nous montrons que black"" href=""/science?_ob=MathURL&_method=retrieve&_udi=B6V00-4KFMMFW-1&_mathId=mml52&_user=10&_cdi=5632&_rdoc=5&_handle=V-WA-A-W-WD-MsSAYZW-UUA-U-AAZCBUZCBE-AAZWYYDBBE-VBBCDAUY-WD-U&_acct=C000050221&_version=1&_userid=10&md5=061e902a323e049c52c52c0e0a9062f5"" title=""Click to view the MathML source"">h(n)=n/2 pour black"" href=""/science?_ob=MathURL&_method=retrieve&_udi=B6V00-4KFMMFW-1&_mathId=mml53&_user=10&_cdi=5632&_rdoc=5&_handle=V-WA-A-W-WD-MsSAYZW-UUA-U-AAZCBUZCBE-AAZWYYDBBE-VBBCDAUY-WD-U&_acct=C000050221&_version=1&_userid=10&md5=bdb72aba9adcabc9a5262816c8d70c4e"" title=""Click to view the MathML source"">n5.