请教一道高中数学题

[Jenny_Hull]

Consider a chessboard with the two opposing corners removed, so that there are only 62 squares remaining.






Now we take 31 dominoes, which are shaped such that each domino covers exactly two squares.


Is it possible to arrange that 31 dominoes so that they cover all the 62 squares on the chessboard? If so, find an arrangement; if not, prove that no such arrangement is possible.

 

[月下独酌]

31x2=62.

 

[ccc]

chessboard

 

[Jenny_Hull]

chessboard

你太高了，我试了好半天，也没传上这个图形

 

[ccc]

Absolute proof: The mutilated chessboard problem

Science is operated according to the judicial system. A theory is assumed to
be true if there is enough evidence to prove it ‘beyond reasonable doubt’.
On the other hand mathematics does not rely on evidence from fallible
experimentation but, it is built on infallible logic. This is demonstrated by
the problem of the ‘mutilated chessboard’, illustrated in the figure below.

We have a chessboard with the two
opposing corners removed so that
there are only 62 squares remaining.
We now take dominoes shaped such
that each domino covers exactly two
squares. The question is: Is it
possible to arrange the dominoes so
that they cover the 62 squares on the
chessboard?

There are two approaches to the problem:
(1) The scientific approach
The scientist would try to solve the problem by experimenting, and after
trying out a few dozen arrangements would discover that they all fail.
Eventually the scientist believes that there is enough evidence to say that
the board cannot be covered. However the scientist can never be sure that
this is truly the case because there might be some arrangement that hasn’t
been tried which might do the trick. There are millions of different
arrangements and it is only possible to explore a small fraction of them.
The conclusion that the task is impossible is a theory based on experiment,
but the scientist will have to live with the prospect that one day the theory
may be overturned.
(2) The mathematical approach
The mathematician tries to solve the problem by developing a logical
argument which will derive a conclusion which is undoubtedly correct and
which will remain unchallenged forever. One such argument is the
following:
* The corners which were removed from the chessboard were both
white. Therefore there are now 32 black squares and only 30 white
squares.
* Each domino covers two neighbouring squares, and the
neighbouring squares are always different in colour, i.e. one black
and one white.
* Therefore, no matter how arranged, the first 30 dominoes laid on
the board must cover 30 white squares and 30 black squares.
* Consequently, this will always leave you with one domino and two
black squares remaining.
* But remember all dominoes cover two neighbouring squares, and
neighbouring squares are opposite in color. However the two
squares remaining are the same color and so they cannot both be
covered by the one remaining domino. Therefore, covering the
board is impossible!

This proof shows that every arrangement of dominoes will fail to cover the
chessboard!

___________________________
Questions
1) This text mentions scientists, as opposed to mathematicians. What kind
of scientists do you know?
2) How is science similar to the judicial system?
3) In order to solve the mutilated chessboard problem, will a scientist
explore all the possible arrangements?
4) Explain in your own word the difference between truth in math and
truth in science. In each case, what is the main tool to reach the ‘truth’?

Check your progress: The dominoes mentioned in all the questions below
are shaped such that each domino covers exactly two squares.
1) We have a chessboard with one corner removed. Is it possible to
arrange the dominoes so that they cover the mutilated chessboard?
2) We have a chessboard with two adjacent corners removed. Is it possible
to arrange the dominoes so that they cover the mutilated chessboard?
3) We have a chessboard with four black squares removed. Is it possible
to arrange the dominoes so that they cover the mutilated chessboard?
4) Create your own!

 

[Jenny_Hull]

31x2=62.

试了半天，好像是 no such arrangement is possbile. 但是不知道怎么证明。

 

[ccc]

试了半天，好像是 no such arrangement is possbile. 但是不知道怎么证明。

http://www.speakenglish.re/speakeng..._proof_-_Dominoes_on_Mutilated_chessboard.pdf

 

[ccc]

http://en.wikipedia.org/wiki/Mutilated_chessboard_problem
Mutilated chessboard problem

The mutilated chessboard problem is a tiling puzzle introduced by Gamow & Stern (1958) and discussed by Martin Gardner in his Scientific American column "Mathematical Games." The problem is as follows:

Suppose a standard 8x8 chessboard has two diagonally opposite corners removed, leaving 62 squares. Is it possible to place 31 dominoes of size 2x1 so as to cover all of these squares?

Most considerations of this problem in literature provide solutions "in the conceptual sense" without proofs. John McCarthy proposed it as a hard problem for automated proof systems. In fact, its solution using the resolution system of inference is exponentially hard.

Solution
The puzzle is impossible to complete. A domino placed on the chessboard will always cover one white square and one black square. Therefore a collection of dominoes placed on the board will cover equal numbers squares of each colour. If the two white corners are removed from the board then 30 white squares and 32 black squares remain to be covered by dominoes, so this is impossible. If the two black corners are removed instead, then 32 white squares and 30 black squares remain, so it is again impossible.

Gomory's theorem
The same impossibility proof shows that no domino tiling exists whenever any two white squares are removed from the chessboard. However, if two squares of opposite colors are removed, then it is always possible to tile the remaining board with dominos; this result is called Gomory's theorem, and is named after mathematician Ralph E. Gomory, whose proof was published in 1973. Gomory's theorem can be proven using a Hamiltonian cycle of the grid graph formed by the chessboard squares; the removal of two oppositely-colored squares splits this cycle into two paths with an even number of squares each, both of which are easy to partition into dominos.

 

[Ayin_Ottawa]

这让我想起小时候的一道题：

30个饺子分9人，每人只能有分到单数饺子，不能有双数的饺子。

困扰我N年，后来想通了。

 

[Jenny_Hull]

(2) The mathematical approach

The mathematician tries to solve the problem by developing a logical

argument which will derive a conclusion which is undoubtedly correct and

which will remain unchallenged forever. One such argument is the

following:

* The corners which were removed from the chessboard were both

white. Therefore there are now 32 black squares and only 30 white

squares.

* Each domino covers two neighbouring squares, and the

neighbouring squares are always different in colour, i.e. one black

and one white.

* Therefore, no matter how arranged, the first 30 dominoes laid on

the board must cover 30 white squares and 30 black squares.

* Consequently, this will always leave you with one domino and two

black squares remaining.

* But remember all dominoes cover two neighbouring squares, and

neighbouring squares are opposite in color. However the two

squares remaining are the same color and so they cannot both be

covered by the one remaining domino. Therefore, covering the

board is impossible!

高人呀，敬仰之情如滔滔江水！万分感谢！！！

 

[ccc]

高人呀，敬仰之情如滔滔江水！万分感谢！！！

你让我无地自容啊。:blowzy:

那是道名题，一搜就有答案了。

 

[stevenw]

又回想起当年的一些竞赛题了，好多无解。

 

[ccc]

老何，你怎么看？

 

[feige]

你让我无地自容啊。:blowzy:

那是道名题，一搜就有答案了。

要我看, 村长引用的那句话好象不是夸村长的.

 

[cucapila]

不能，因为要cover2个相邻的格子，需要一个黑的一个白的
对角拿走2个以后剩32个黑30个白（或者相反），配不成对了