- For which books does exist a function from the pages to $\{true, false\}$ that makes true the sentence written in each page?

- If such a function exists, how many different functions make the job?

Update (08/04/2008): Solution posted! (show solution)

Long and diligent search has not revealed a counterexample.

Can you read the following maths?

$$\sum\frac{1}{n^s} = \prod\frac{1}{1-1/p^s}$$

If not, to see the equations, you either need

Mozilla or a MathML plugin for IE/Win. You will also need to install some fonts.

If not, to see the equations, you either need

Mozilla or a MathML plugin for IE/Win. You will also need to install some fonts.

i created this blog with the purpose of collecting ad discussing with other people the most beautiful (and possibly not too difficul) problems that i come across, you may want to contribute suggesting us the nicest problems that you encountered!

There are strange boring books. In every page of those books there is only one sentence saying: 'the sententence at page $p$ is $X$', where $p$ is a positive integer less or equal of that book lenght -in pages- and $X$ belong to $\{true, false\}$.

Update (08/04/2008): Solution posted! (show solution)

Let's call*chapter* a minimal collection of pages such that any page points to a page of the same chapter. We can define the required function independently on all chapters, and every such a good function is also a good function within each chapter. So the question is, when does a chapter admit such a function?

- For which books does exist a function from the pages to $\{true, false\}$ that makes true the sentence written in each page?

- If such a function exists, how many different functions make the job?

Update (08/04/2008): Solution posted! (show solution)

Let's call

- Note that we can iteratively remove any page that is not referred by any other page. Its truth value will be later defined as the same or the opposite of the value of the page it points to (respectively if this is a assert-true of assert-false page), and this is the only way to keep the function coherent while re-adding the page we removed.
- Let's do so till when there is no more unreferred page, and note that we got a loop (in facts, every page is pointed to by exactly one page, because in the graph there is the same number of arrows as pages, and we are considering a connected graph). Let's call this loop the core loop of the chapter.
- A loop admits a truth function precisely when the number of assert-false page is even, and if so there are two different such function (just define one page as true or false, and any other page will have to be defined accordingly in a univocal way).

Subscribe to:
Post Comments (Atom)

## No comments:

Post a Comment