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\}$.
- 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 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?
- 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).
We can now note that if every chapter is good (ie. admits such a function because the core loop contains an even number of assert-false pages), the total number of functions is $2^c$, $c$ being the number of chapers.
No comments:
Post a Comment