Logic+ 04: UNIZOR.COM - Math+ & Problems - Logic

Notes to a video lecture on http://www.unizor.com

Logic+ 04

Problem A

A traveler has to stay in some city for 7 days. A restaurant owner near a hotel where a traveler stays does not accept credit cards, and a traveler has no local currency to pay for food.

However, a traveler has a silver chain of 7 links, and a restaurant owner agreed to take one chain link for each dinner.

What is the minimum number of chain links that must be cut open to be able to pay for each dinner separately?

Answer A
Only one link needs to be cut open, link #3.


Problem B

Same as Problem A, but the number of days is N, and the number of links in a chain is the same N.


Answer B

Assume, a traveler cuts open only K links (K must be small relatively to N).
Then he can pay for 1, 2, 3,..., K dinners using only these links.

For the next dinner he needs a segment of chain that contains K+1 links.
With this additional segment of chain he can pay for K+1, K+2,..., 2K+1 dinners.

For the next dinner he needs a segment of 2K+2 links.
Using K individual links that were cut, a segment of a chain with K+1 links and another segment with 2K+2 links a traveler pay for any number of dinners from 1 to K+(K+1)+(2K+2)=4K+3.

For the next dinner he needs a segment of 4K+4 links.
Using K individual links that were cut, a segment of a chain with K+1 links, a segment with 2K+2 links and a segment with 4K+4 links a traveler pay for any number of dinners from 1 to K+(K+1)+(2K+2)+(4K+4)=8K+7.

For the next dinner he needs a segment of 8K+8 links.
Using K individual links that were cut, a segment of a chain with K+1 links, a segment with 2K+2 links, a segment with 4K+4 links and a segment with 8K+8 links a traveler pay for any number of dinners from 1 to K+(K+1)+(2K+2)+(4K+4)+(8K+8)=16K+15.

Let's generalize it.
When K links were cut, it separated a chain into K+1 segments as follows.

Segment #1 should have
K+1 links in it.
Segment #2 should have
2K+2=2·(K+1) links in it.
Segment #3 should have
4K+4=4·(K+1) links in it.
Segment #4 should have
8K+8=8·(K+1) links in it.
Segment #5 should have
16K+16=16·(K+1) links in it.
etc.
The last segment #(K+1) should have 2^K·(K+1) links in it.

All individual links that were cut splitting a chain into segments and all segments listed above allow to pay for the following number of dinners.
K +
+ (K+1) +
+ 2·(K+1) +
+ 4·(K+1)+
+...+
+ 2^K·(K+1) =
= K + (2^K+1 −1)·(K+1) =
= (K+1)·2^K+1 − 1

If N=(K+1)·2^K+1−1 then the minimum number of links to cut is K.
If N is not such a number, we have to find K such that (K+1)·2^K+1−1 is greater than N. That K is the minimum number of links to cut.