Paradoxes and Ironies!!!!

[Thiru Narayanan]

This ought to be simple as with the value of each bit in a byte,
like 1,2,4,8,16,32,64,128,256,and the rest of the coins.
THIRU
Hope, not everybody is aware of this one.
There are 1000 coins and 10 bags. Fill the bags with these coins in such a way that if I ask you a random number ranging from 1 to 1000, you should be able to give me the bag/s equalling the number of coins asked for. Not a coin more, not a coin less ie. no manipulation of removing or adding according to the number. So figure out how many coins each bag will contain.

[Sahir Shibley]

Nanhesru,
Regarding your fractal problem. I think the solution is mentioned in a book called "The expert's guide to Delphi 3 " . I may have read the chapter on fractal landscapes two years ago, but I dont have even the faintest recollection of it now. So if I make an attempt( without referring to the book , of course), will it be considered a fair win or cheating ?
[This message has been edited by Sahir Shibley (edited May 03, 2001).]

[Nanhesru Ningyake]

Sahir, I didn't know this problem was related to fractals. Go ahead work on the solution, just don't write a program for it

[Jim Yingst]

Sahir- is writing Java code to find the answer cheating? Not in this discussion group it isn't. But consider - what if we change the problem as follows:

• Instead of dollars and cents, pretend we use dollars and mils, where 1000 mils = one dollar.
• Instead of 20 cents, use a difference of 891 mils.
• Instead of increasing the value of the original check by a factor of 2, use a factor of 10.
What's the answer then?

[This message has been edited by Jim Yingst (edited May 03, 2001).]

[Jim Yingst]

Eager Beaver- for the 10 boxes problem, do we have access to a scale, which will tell us the total weight? Or do we still just have a balance, which merely tells us which of two sides is heavier? If it's a scale, 1 weighing will suffice. For a balance, three balancings will be necessary. But if there were only 9 boxes, then two balancings would suffice.

[Mapraputa Is]

Frank, LOL... It was a great idea about two gets and one put... Except now you probably joined Jim in Angela�s �too deep thinkers� list. I would create a reserve account in advance

[Mapraputa Is]

Frank... Your idea was so universal...
10 boxes problem: we don�t need weighing at all.
Algoritm:
1) Open all boxes
2) for each box: leave one ball inside, put 9 other on the ground near the box (do not mix balls! )
3) for each heap: put one ball in each of other 9 boxes
4) now all our boxes have the same weight = no need to find �odd box�.
5)
Jim, do not beat me, it was a joke.
Jim, what do you mean by �one weighing�? The scale were loaded with N boxes only once or scale�s value was taken once?

[This message has been edited by Mapraputa Is (edited May 03, 2001).]

[Jim Yingst]

One weighing = put a set of objects on the scale and read the total weight (once). You don't get to look at the scale as you put objects on one at a time.

[Mapraputa Is]

But we can look at the scale when we unload boxes, right?

[James Lechte]

EagerBeaver,
just back on the truck, the bridge and sparrow the 10 miles of gas consumption would most certainly outweigh the sparrow would it not?
cheers James

[Mapraputa Is]

AAAAAhhhh...
Map actially read a puzzle. Before she just tried to solve it. For some reason she decided that there are 10 balls in each box and we should weigh boxed, not balls. Now it's too easy again... Maybe. Or not. Jim, is it important how many balls are there in each box? I mean will it affect your solution somehow?

[Jim Yingst]

Actually Map, there is a minimum number of balls required for my solution. If there are not enough balls, then more weighings will be needed. As long as the minimum is present, then it doesn't matter how many more there are. I won't say just what the minimum conditions are, for that would make the answer too obvious - but I suspect you know it already.

[Frank Carver]

I've just looked at EB's "10 Boxes" problem. That one really is too easy, so I won't post the answer here.
As for the programmer's hats, I still can't come up with a way to save them all, but it does occur to me that even if each programmer is limited to speaking just the single word representing his guess at the colour of his hat, there is still tons of spare bandwidth for extra information. Perhaps when the programmers get together they decide that they will speak the name of their guess, but speak it in English if the hat in front is red, French, if the hat in front is white, and German, if the hat in front is black. If they are limited to using English (boy, this is a tough company to work for), then they can spend a few minutes practicing and speak their guess in a "Russian" accent for a red hat in front, "New York" accent for white hat in front and so on.
Once the guy at the back makes his guess, the programmer in front then knows his colour, and the effect will ripple forward to the front of the row. I still think that the one at the back can only know his colour if he also knows something about the quantities or proportions of the different coloured hats.
The more you look at this, the more it looks like an interesting idea for a "team building excercise". The 100 programmers would have to talk to each other - could this ever happen in real life?

[Colin Russell]

Eager
Answer to the forest question - halfway. After that you're walking out of the forest.

[hemanth kumar]

Originally posted by Eager Beaver:
Hi Guys,
Here comes another puzzle.....
A giant truck gets loaded to its max capacity and tips the scale on the weigh bridge at 10 tons. It starts from point A and after traversing a distance of 10 miles arrives at a bridge on river kiev. The board reading 'WARNING : VEHICLES NOT TO EXCEED TOTAL WEIGHT OF 10 TONS. 1 gram (CGS system) MORE AND THE BRIDGE COLLAPSES.' has been ignored by our careless driver. When he is about to get on the bridge a sparrow comes from nowhere and perches atop the truck and stays there while the truck traverses the bridge. Surprise of surprises the bridge remains intact and the truck is happily on its way. How did this miracle happen!!

eagerbeaver.
PS : Hope u all have seen sparrows.
[This message has been edited by Eager Beaver (edited May 02, 2001).]
[This message has been edited by Eager Beaver (edited May 02, 2001).]

Well when it moves 10 Miles, It looses some fuel. So the truck weighs less by the time it reaches the Bridge
Is this right?
Oops . Somebody has already answered this puzzle

[This message has been edited by hemanth kumar (edited May 04, 2001).]

[Anonymous]

Hi Jim,
You may use a scale or a spring balance. A traditional balance (one held by the blind lady statue in courts) could also be used and as long as you do not change the number of balls placed on one side of the balance it would be counted as one weighing.
Sahir,
Try to arrive at a lesser number of weighing. 3 tries is too many!!
Colin,
Forest puzzle....you have once again demonstrated your knack for solving such posers!!
Thiru,
Your answer to (A-X)(B-X)....(Z-X) is correct.

And to all those who have answered the TRUCK/BRIDGE puzzle.....'fuel consumed' was the right answer.
Thanks to all those who have taken a keen interest in this thread.
eagerbeaver.

[Mapraputa Is]

Ok, I revised my notion of an elegant solution. New one: a puzzle is a good puzzle if regardless of time spent to solve it, there is a significant gap between expected and actual complexity of solution. 10 boxes is a good puzle: one would expect about 3-5 weighings so the answer �one� makes an elegant solution.
The more you look at this, the more it looks like an interesting idea for a "team building excercise". The 100 programmers would have to talk to each other - could this ever happen in real life?
Frank, you hit the point! Of course, that's the most difficult part. Mapraputa, for example, would say <quote>�yellow with purple polka dots�</quote> because she never pay attention to requirements. Jim, of course, would tell his color without any extra information from those behind

[Judy Herilla]

6 Gold Bars measuring twice problem:
1st time:
3 bars on each side will tell you which set of 3 contains lighter bar
2nd time:
take 1 bar on each side of scale:
a. if they are equal, the one you did not way is the lightest
b. if one is lighter it is the lightest

[Stevie Kaligis]

Hello deep thinker Detective !
Here is the real puzzle,
f.y.i...Sherlock & Poirot is still working on it...
-----------------------------------------------------------
Murder in the Black Castle
It was a dark night, heavy with wind and rain, when three lone knights, strangers to each others, chanced to meet in front of a black and gloomy castle.They were suspicious of each other, but, as was their custom, they approached the castle and sought refuge for the night.
The three knights were greeted by a sour-faced servant who explained that the master had retired for the evening but that their needs would be met. The three starngers were then provided food and shown to separate room.
Sometime during the night a murder was commited.
The crime can be considered somewhat unusual, as not only the culprit unknown, but the identity of the victim is also unclear.
Fortunately, the list of possible culprits and victims can be narrowed to five :
a. the servant
b. the master
c. and the three knights.
Given the following clues, who was the victim and who was the culprit ???

1. If the knight in room 1 was culprit, the knight in room 3 was the victim.
   
2. If the knight in room 2 was the victim, the servant was the culprit.
   
3. If the knight in room 3 was the victim, the knight in room 2 was the culprit.
   
4. If the servant was the culprit, the victim was the knight in room 3.
   
5. The servant was not available until the next morning, and was not able to provide an alibi.
   
6. If the knight in room 3 was the culprit, the knight in room 2 was the victim.
   
7. If the knight in room 2 was the culprit, the servant was the victim.

----------------------------------------------------------
enjoy the puzzle & solve the case dude...
stevie

[Paul Ralph]

The master killed the Knight in room 1.
Not that tricky, but interesting. Was clue 5 thrown in just for fun?
Paul R

[Nanhesru Ningyake]

Jim, Sahir, EB... did you solve the Triangles problem? I will post the answer tomorrow.

[Jim Yingst]

Actually no. I couldn't see an elegant way to reduce the problem (at least, not sufficiently elegant to motivate me to follow through with all the math) and moved on to other things. Would be interested in seeing the solution though.

[Eager Beaver]

Hey Nanhesru,
I did spend a whole evening in reclusive contemplation and came up with a way to calculate the number of triangles down to level 4. However i could not formulate expression that could take care of the larger inverted triangles(having more than 5 triangles within).These inverted triangles increase in arithmetic progression.....but have not elegant solution for them....shucks..(:-(. I have given up and looking forward to your post.
eagerbeaver.

[Mapraputa Is]

Nanhesru, iInstead of giving an answer, why don't you give us an idea where to find? I tried a few tricks, but nothing worked. Here is the best I could do.
For not to count triangles more than once, let's count �basic� one-level triangles separately. Their number on each level is x = x + l*l (if l means level) � it was the easiest part Next go composite triangles in normal direction � these propagate as
level1 0
level2 1
level3 2 + 1
level4 3 + 2 + 1
level5 4 + 3 + 2 + 1
...
if use Y as a number of these triangles, it will give us:
start with n =0; y=0;
then for each level
n = n + l - 1
y = y + n
Then the worst part, inverted triangles
level4 1
level5 2
level6 3 +1
level7 4 +2
level8 5 +3 +1
level9 6 +4 +2
level10 7 +5 +3 + 1
...
if to denote them as Z, then we have a bunch of auxiliary variables:
i = 1 - i
k = k + i
m = m + k
z = z + k
and it�s ugly enough plus I probably already made a mistake somewhere I had a couple of brilliant ideas (like treat each triangle as a half of rhomb or to count a triangle as a function of itself) but they did not work � what a pity...

[Sahir Shibley]

I thought one of you guys would solve it in flash so I did not try. Besides I am in one my lethargic moods. Map, you need to approach it from a different perspective, once you do that it is a piece of cake. How do do you create a fractal . You start with an equilateral triangle, then you join the midpoints of the triangle. Now you have an inverted triangle inside the original triangle. You have divided the original triangle into four triangles. The total number of triangles is 5 including the original triangle. You divide it again you have 4 upright triangles at the base. Try drawing the traingles and you can see the relationship with this problem.
Cheers
Sahir

[Nanhesru Ningyake]

Map, you are on the right track. I have spent sweet hours trying to find patterns in these triangles. And I was rewarded; I found some beautiful relations emerging...
Here's how i proceeded to analyze it. Here's a table which lists the number of triangles of size 1 to n, for a level n. (In this counting I don't discriminate between normal and inverted triangles. Just the size matters.)
How to read the table:
- Level 2 has 4 size1 triangles, and 1 size2 triangle, giving you T(n) of 5.
- Level 4 has 16 size1 triangles, 7 size2 triangles, 3 size3 triangles, and 1 size4 triangle, giving you T(n) of 27.
<pre><big>
1 2 3 4 5 6 7 8 9 10 TOTAL
1 1 1
2 4 1 5
3 9 3 1 13
4 16 7 3 1 27
5 25 13 6 3 1 48
6 36 21 11 6 3 1 78
7 49 31 18 10 6 3 1 118
8 64 43 27 16 10 6 3 1 170
9 81 57 38 24 15 10 6 3 1 235
10 100 73 51 34 22 15 10 6 3 1 315
</big></pre>
And some more samples:<pre><big>
n T(n)
11 411
12 525
13 658
14 812
15 988</big></pre>
Do you recognize some patterns? One simple pattern is, for a level n, number of triangles of size1 is n² (That is, n*n). That's cute right? Can you prove (geometrically) why that's true
When you recognize more patterns, try to put that into an equation. So you would first arrive at a summation (sigma) equation. Then solve this to get the final answer!

[Nanhesru Ningyake]

Sahir, this should be easy for you. Can you write a recursive function to solve the above problem?

[Mapraputa Is]

Sahir, fractals was the first idea that came into my mind. It took me a while to get rid of it. I think it will not work in this case (if only on micro-level), because we need do calculate tr.numbers on each level, not just finally cover n-level triangle with smaler ones. By the way, fractal variant is here: http://www.ac.biola.edu/~jeremyb/CompGraphics/Triangles.html
enjoy!
One simple pattern is, for a level n, number of triangles of size1 is n2 (That is, n*n). That's cute right? Can you prove (geometrically) why that's true
well, lets see a composite triangle as a half of rhomb. Number of triangles of size1 is twice as many as rhombes of the same size, but our �big� triangle includes only half of rhomb, so 2 * � * n ²

[Mapraputa Is]

Aha, if we count x (i,j) as a recursive function of hmmm... some previous x(i,j) � then it works... But it still doesn�t look very elegant... Nanhesru, how ugly the final function should be?

[Jim Yingst]

If n is even, then the total number of triangles is n * (2 * n + 1) * (n + 2) / 8.

[Mapraputa Is]

I counted x (i,j) as a function of x(i-1, j-1)
x (i,j) = f (i, j)
where f (i, j) is:
if j = 1, f (i, j) = i * i;
else
k = i - 2*j + 2;
if k < 0, f (i, j) = x(i-1, j-1) <br /> if k > 0, f (i, j) = x(i-1, j-1) - k
if produces correct result, except it is more obscure than Ugly Three-step Algorithm

[Mapraputa Is]

Actually what is �ugly� is arguable.
Look at this ugly code. The result can be seen here or
here

[Nanhesru Ningyake]

Jim, you got it! You are now Jim "The Boss" Yingst
The complete equation, for even, and odd values of 'n' is:
T(n) = floor [n * (2 * n + 1) * (n + 2) / 8]
(I can hear you thinking, duh, why didn't I think of using floor for odd numbers )
Could you briefly describe how you arrived at this solution?
Map, your recursive equation looks right. How are the values of i and j related to n, the level of the triangle... I was wondering.

[Jim Yingst]

First I considered how many upright triangles of size k could be found in a structure of size n. By upright I mean all sides are parallel to the outsides of the structure; for triangles oriented the opposite way I use the term inverted. Anyway, the number of upright triangles is (n-k+1)(n-k+2)/2. This can be seen by considering the number of places where you can locate one particular corner - you get a series of the form 1 + 2 + 3 + ... + (n-k+1). Use the fact that 1 + 2 + 3 + ... + x = x*(x+1)/2 to get the number of upright triangles.
Now consider inverted triangles of size k. This is a bit harder to see, but again look at possible locations for just one corner, and you can see it's a triangular area with side length n-2k+1. Which means that the number of points in that triangle, and hence the number of inverted triangles of length k, is (n-2k+1)(n-2k+2)/2. But this formula only works for 2k <= n. Well, actually it's OK for 2k = n+1 and 2k = n+2 as well, since those yield zero, but after that it gives meaningless results. There are zero inverted triangles with size k > n/2 - this can be easily verified graphically. At this point I decided to only worry about even values of n for simplicity - obviously the odd values would follow a similar formula, but who needed the extra work?
So, to get the total number of triangles we need to sum two series:
sum(k=1...n) [ (n-2k)(n-2k+1)/2 ] + sum(k=1...n/2) [ (n-2k+1)(n-2k+2)/2 ]
In order to combine these, I needed both series to use the same set of indices, so I rewrote the first one by defining u = 2k:
sum(k=1...n) [ (n-2k)(n-2k+1)/2 ] = sum(u=1...n/2) [ (n-u+2)(n-u+3)/2 + (n-u+1)(n-u+2)/2 ]
The first term handles the odd values of k; the second handles the even ones. Once that's done, rename u to k -- we can call the index anything we want, and now it has the same range of values as the k in the inverted triangle formula, so we can combine them. The total number of triangles is now
sum(k=1...n/2) [ (n-2k+2)(n-2k+3)/2 + (n-2k+1)(n-2k+1)/2 + (n-2k+1)(n-2k+2)/2 ]
What follows after this is a lot of messy algebra. Eventually I got it to the form
1/2 * sum(k=1...n/2) [(3n^2 + 11n + 10) - (12n + 22)k + 12k^2]
This groups into three sums. The first is just a constant, added N = n/2 times. The second is a constant times 1+2+3+...N, which we know the formula for. And the last is a constant times 1^2 + 2^2 + 3^3 +...+ N^2, which I looked up rather than derive, and that evaluates to N(N+1)(2N+1)/6. Substitute these formulas in, do some more algebra, and it eventually simplifies to n(n+2)(2n+1)/8

[Mapraputa Is]

How are the values of i and j related to n, the level of the triangle
i = level, j = size
To print your �level� X �size� table:
x (level,size) = f (level, size)
where f (level, size) is:
if size = 1, f (level, size) = level * level;
else
k = level - 2*size + 2;
if k < 0, f (level, size) = f(level-1, size-1) <br /> if k > 0, f (level, size) = f(level-1, size-1) - k
But Jim already expressed all this as one formula

[This message has been edited by Mapraputa Is (edited May 10, 2001).]

[Colin Russell]

Taking this thread way back down, I've got a very simple puzzle for you.
How many beans can you put into an empty sack?

[Nanhesru Ningyake]

Jim, that's radical. A math whiz friend of mine in India had easily derived that equation (he's the type who writes papers in international math journals). I never got that far... had a pretty ugly solution myself
Map, your recursive solution is cool, quite elegant, actually!

[Mapraputa Is]

How many beans can you put into an empty sack
One.
Jim, see - Map also can solve something

[Jim Yingst]

You're assuming you can't put in multiple beans simultaneously...

[Mapraputa Is]

"...because without this assumption, there's no elegant solution possible..."