wu :: forums
« wu :: forums - High Buildings and Street Vendors »

Welcome, Guest. Please Login or Register.
Mar 28th, 2024, 10:08am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   hard
(Moderators: SMQ, william wu, Eigenray, towr, ThudnBlunder, Icarus, Grimbal)
   High Buildings and Street Vendors
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: High Buildings and Street Vendors  (Read 2381 times)
Pietro K.C.
Full Member
***





115936899 115936899    
WWW

Gender: male
Posts: 213
High Buildings and Street Vendors  
« on: Oct 17th, 2002, 10:24pm »
Quote Quote Modify Modify

  I'm sure there is some crypto-theoretical official solution to this, but how about the following.
 
   The problem doesn't state the kind of money used. So we could conceive of n-money, which is very similar to ordinary money. In real life, every bill/coin/currency has some serial number that uniquely identifies it, as a means to prevent forging (though enhanced by many others, like special paper, but that is beside the point). For n-money in general, there would be n identical copies of each bill/coin/currency, i.e. n instances of a given serial number. For n-money to be valid, we could agree that ALL n identical copies have to be presented together, otherwise it's worth nothing. So if I had a 3-money 10-dollar bill of serial number 125123627, and tried to buy an ice cream with it, I would be kicked out of the ice cream store. The next customer, a bit surprised, would then present 3 identical 5-dollar bills of serial number 234623099, and walk out with his sundae.
 
   For the problem at hand, I suppose 2-money would suffice. It would go like this. The street vendor announces the price of his product, and the customer would place one copy of each bill/coin/currency required to pay for it on the basket, and lower it. The vendor would take that, place his product on the basket, and raise it. The customer would take the product, place the remaining copies of 2-money bills/coins/currency on the basket, and lower it again, thus paying the vendor.
 
   This works unless someone is deliberately evil (i.e. acts to cause loss without gain to himself). Because, if the vendor walks away with one copy of each 2-money bill, he will gain nothing; the customer will never put the remaining bills in circulation, as they are worth nothing, and hence the vendor has no chance of using the bills he has to ever buy anything. Hence, the vendor will place his product on the basket, as he wants the remaining copies of 2-money. The customer, in receiving the product, has no reason (other than being evil) to not put the remaining copies on the basket, for the same reasons listed above. And so he does, and transaction is complete.
 
   Of course, if someone IS evil, the customer could just put the required money in an envelope, lower an empty basket, have the vendor put his product in the basket, and duct-tape the envelope to his end of the rope. Thus, when raising the basket, the money will lower, and each will get his due at the same time. Or an even cleverer solution would be to just have two baskets. Smiley
 
   Any other solutions?
« Last Edit: Oct 17th, 2002, 10:26pm by Pietro K.C. » IP Logged

"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
Eric Yeh
Senior Riddler
****





   
Email

Gender: male
Posts: 318
Re: High Buildings and Street Vendors  
« Reply #1 on: Oct 18th, 2002, 10:25am »
Quote Quote Modify Modify

Pietro,
 
In your solution, why wouldn't the customer keep the product after hes received it, and not lower the other half of the money?
 
BTW, I think a more realistic (or say, implementable) way to think of the "n-money" is as a series of bitstrings (randomly chosen with n-1 degrees of freedom) to have an xor equal to a lock combination or some such.
 
I don't think I understand the specification of the problem, as I'm pretty sure it's impossible in my model (e.g., that the baskets can be interpreted as anything where only one person has control until it is delivered to the other person, and delivery can be viewed as instantaneous).  Any clarifications are appreciated.
 
Best,
Eric
IP Logged

"It is better to have puzzled and failed than never to have puzzled at all."
Eric Yeh
Senior Riddler
****





   
Email

Gender: male
Posts: 318
Re: High Buildings and Street Vendors  
« Reply #2 on: Oct 18th, 2002, 10:52am »
Quote Quote Modify Modify

Actually, upon reflection, I suppose that my model is solveable with some ugly technology assumptions.  I will tell it first in a "fantasty setting" much unlike the world we currently live in, but one that is actually potentially convertible to something we could implement today.  I tell it the other way to make it cleaner, and because it is actually how I think of it.  I also think of it as the "purest" form of the solution.
 
(Even so, it is too far-fetched to be the real soln, so I think the real answer is either that it's impossible, or I am misinterpreting something  Wink )
 
I have two magical transparent boxes A and B such that B opens (automatically) iff A opens, and A opens iff it is opened with a key.  They are otherwise unopenable.  Furthermore, a box can be instantly recalled by its owner at any time; this action also brings back its contents iff it is currently closed.
 
One person has Box A and the key; the other has Box B.  The first person send his goods in Box A; the other person then inspects the goods (goods must be verifiable by sight for this to work) and upon satisfaction sends his goods in Box B.  The first person verifies the goods and upon satisfaction sends the key.  When the second person unlocks Box A, both goods are released simultaneously and even a malicious recall no longer retains the goods.  If either party wants to back out at any time, they simply recall their box.
 
I will leave details of transferring to the real world to the reader.  It can be done without too much trouble by the use of codes, wires, and chains.  Details about how to ensure that both players have access to the appropriate box need also be addressed carefully, but wo much difficulty.
 
But hmmm, the more I think about it, the more I suspect the intended question is simply to prove why the fair transfer cannot be done...
 
Best,
Eric
« Last Edit: Oct 18th, 2002, 10:56am by Eric Yeh » IP Logged

"It is better to have puzzled and failed than never to have puzzled at all."
Pietro K.C.
Full Member
***





115936899 115936899    
WWW

Gender: male
Posts: 213
Re: High Buildings and Street Vendors  
« Reply #3 on: Oct 18th, 2002, 11:35am »
Quote Quote Modify Modify

  You're right, Eric, my model needs one little correction to work.
 
   The basic flaw is that a vendor could take one copy of 2-money and use it later to get himself a product from some other vendor. Or that the customer could use each of the copies of his 2-money bills to get two different products at different times.
 
   So we suppose that, in addition to having identical serial numbers, each 2-money copy is labeled either A or B, next to its serial number.
 
   It would go like this. Assume both customer and vendor are honest. The customer lowers the A copy of his bills for the vendor to see. He checks it out and lets them go back up. The customer retrieves his A-bills and puts the corresponding B-bills in he basket. The vendor checks to see if they correspond to the A-bills he has seen previously (the serial numbers of which he could have jotted down on paper). If not, abort sale. If they do, he takes the B-bills, puts the product in the basket and raises it. The customer takes the product and puts the A-bills in, then lowers the basket. Transaction is complete.
 
   Now assume that customer and vendor may not be honest, but are not evil (in that they will only be dishonest to benefit themselves). It is clear that the vendor has no reason other than evilness to take the customer's money without giving him the product, as NOW there is no way he could use it for his own benefit (because of the checking stage in trade). Likewise, the customer has no reason other than evilness to not lower the A-bills, as he can never use them again. SO non-evil people would be forced to undergo honest transaction.
 
   Now suppose there are evil people. We then impose that customers or vendors who have been wronged never put the single copies of bills they have in their hands in circulation, ever again (this need not even be a rule, as it could only disadvantage them). Further, we require that, for each time someone has been wronged, they wrong two people. Yeah, baby, law of the jungle. This would discourage evil behavior, because (supposing the town has a finite number of inhabitants, which is not altogether unreasonable) "what goes around, comes around" would be guaranteed. If someone were evil, he would be wronged at least twice in return, and in an extreme case, the economy would go bankrupt, with everyone having just one copy of each 2-money bill.
 
   Come to think of it, maybe in that case people would start accepting single copies of 2-money as currency, or conducting barter, which would again be prone to evil. Man, evil people really suck.
 
   Maybe you're right, and we're really supposed to prove that it can't be done.
IP Logged

"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
Eric Yeh
Senior Riddler
****





   
Email

Gender: male
Posts: 318
Re: High Buildings and Street Vendors  
« Reply #4 on: Oct 18th, 2002, 12:50pm »
Quote Quote Modify Modify

Hehe, it was kinda funny reading your, Pietro.  It very much had the tone of having the solution all the way to the last paragraph, and suddenly rapidly converts to agreement that there may not be a solution.  Don't get me wrong -- I think your solution is very nice for the non-evil case, as you call it.  Me, I always start off suspecting the worst.  It is pretty clear to me that with my model of the problem, it is not possible: my "fantasy" solution, though almost implementable, has a couple of important holes, and in general illustrates my idea of what the pf of impossibility would be.
 
Best,
Eric
IP Logged

"It is better to have puzzled and failed than never to have puzzled at all."
Garzahd
Junior Member
**





    mlahut


Gender: male
Posts: 130
Re: High Buildings and Street Vendors  
« Reply #5 on: Oct 23rd, 2002, 3:11pm »
Quote Quote Modify Modify

I don't think the problem sufficiently specifies what "trust" means. Specifically, can the customer guarantee that the vendor will give him the correct goods, or can the vendor guarantee that the customer's money isn't counterfeit? I'm assuming yes; you're just looking out a window at each other; you should be able to see what's going on. You've got good eyesight.
 
I've got two ideas for answers to this, though both are rather unscientific and lame.
 
1) Someone buys a new basket and attaches it to the pulley too, at the opposite end.  So both cash and goods trade hands at the same time. A second basket is cheating? Then tape the bills to the rope.
 
2) Vendor develops some method of keeping the rope from moving (maybe he's real heavy and can step on it). He sends the goods most of the way up, then holds the rope until the customer pitches the money out the window. Vendor runs and catches it, thus releasing the rope so customer can get his goods.
 
Both of these can be clearly foiled with (say) counterfeit money, which goes back to my question of how untrustworthy people can get. Actually, the existing solutions can be foiled with counterfeit money too.
IP Logged
Eric Yeh
Senior Riddler
****





   
Email

Gender: male
Posts: 318
Re: High Buildings and Street Vendors  
« Reply #6 on: Oct 23rd, 2002, 3:42pm »
Quote Quote Modify Modify

Garz,
 
(Is that better, or Garzy?  Wink )
 
I don't know that I quite agree with your assumptions, though  
they are of course as good as mine.  But realistically speaking, it would seem that you should be able to identify counterfeits only within a certain distance, at least, which it seems we can assume is at least smaller than the height of the building (else the latter would be almost unnecessary).
 
Previous solns??  And here I was under the impression it was pretty much decided there was none.
 
Can the original poster please clarify the questions that have arisen??
 
Some other responses:
 
1)  First of all, I think a second basket is fair game.  However, in my model, which I believe to be reasonably realistic, you would have to assume that the two baskets cannot be exchanged atomically.  One person has to "get" a basket first, and at that point the other person could stop the [a/de]scent of the other.  Physically sepaking, my assumption is that both people have "equal stength", hence either can immobilize any basket at any time.
 
2)  As I mentioned, I agree the basket can be immobilized.  However, I have a problem anyway:  First, you need some assumption about the "throwing precision" of the buyer.  But even assuming it is 100%:  1)  Suppose he throws it directly to the vendor.  The vendor can catch it and not release the basket.  2)  Suppose he throws it purposely far from the vendor.  Then the vendor will have to move to inspect it, thus releasing the rope even if it is counterfeit or not enough.  Doesn't it also seem unrealistic that moving forces the vendor to release the basket?  Why doesn't he clamp it, or cut the rope or some such?  Even if all this works out, there is a problem of the buyer "stalemating" the basket and not returning it, even if not acquiring it for himself.  To me, this seems to be a general problem with the riddle specification.
 
Thoughts?
 
Best,
Eric
IP Logged

"It is better to have puzzled and failed than never to have puzzled at all."
Chronos
Full Member
***





   
WWW Email

Gender: male
Posts: 288
Re: High Buildings and Street Vendors  
« Reply #7 on: Oct 30th, 2002, 1:01pm »
Quote Quote Modify Modify

Some more thoughts:  What's the "real-world" solution to this problem?  Why, simply, if one party cheats the other, then the other calls the police on him.  But this requires some method of proof of the transaction:  Otherwise it's just one's word against the other's, and the cop doesn't know who to believe.  So you need some system of receipts.
 
I think that this becomes equivalent to Pietro's n-money solution, but it's easier to implement in the real world.  Unfortunately, it's also still vulnerable to thoughtless malice, where one party tries to screw the other for no good reason.
IP Logged
Eric Yeh
Senior Riddler
****





   
Email

Gender: male
Posts: 318
Re: High Buildings and Street Vendors  
« Reply #8 on: Oct 30th, 2002, 1:25pm »
Quote Quote Modify Modify

Again, my understanding for problems of this sort is that you always assume "thoughtless malice".  After all, otherwise there would be essentially no malice at all.
 
I once again request clarification from the author wrt my previous questions.
 
Thanks,
Eric
IP Logged

"It is better to have puzzled and failed than never to have puzzled at all."
SWF
Uberpuzzler
*****





   


Posts: 879
Re: High Buildings and Street Vendors  
« Reply #9 on: Nov 2nd, 2002, 7:46pm »
Quote Quote Modify Modify

I have is a way that uses test tube type transparent containers for transporting the cash and product.  At the customer end of the rope there is one of these test tubes with the open end upward, and at the proper distance along the rope (not at the other end) is an inverted test tube with the open end facing downward.  These tubes would be maybe 1 foot diameter and a couple of feet long such that the item inside can be seen, but the contents cannot be removed until the open end of the tube is accessible.
 
The vendor loads his product into the inverted tube.  Of course, the inverted tube needs something inside to prevent the product from falling out, but that should be easy.  The vendor allows the customer to pull the product up to her window so she can see it is inside the tube.  The vendor hangs on tight to prevent the cutomer from pulling the extra couple of feet needed to access the product through the opening in the bottom of the tube.  While the customer was raising the vendor tube, she kept her empty tube on the floor inside the window while accumulating rope.
 
At that point the customer has her tube and extra rope piled on the floor, remember that the rope runs over a pulley high above them both.  If satisfied with the product, she puts cash in her tube and lowers it until there is no more slack in the rope.  The distance between the tubes was designed so at this point, the vendor can see inside and barely reach the closed base of the cash tube, while gripping his end of the rope which prevents customer from pulling the product up the rest of the way.
 
If vendor is also satisfied, he pulls the cash tube down the rest of the way, which raises the product filled tube a few feet.   At that point, both will have access to the tube contents.
 
If at the beginning the customer decides not to pay, there could be a stalemate with each gripping on the rope with the product stuck outside the customer's window.  Could probably come up with something to break tug of war, such as a timer that cuts the rope near the pulley if a transaction is taking too long.
IP Logged
Eric Yeh
Senior Riddler
****





   
Email

Gender: male
Posts: 318
Re: High Buildings and Street Vendors  
« Reply #10 on: Nov 2nd, 2002, 8:44pm »
Quote Quote Modify Modify

SWF,
 
Ye, I agree that this is basically a reasonable real-world implementation of the abstract soln I mentioned in reply 2; it basically requires 1) an atomic exchange mechanism including inspection of merchandise and 2) the ability for either party to halt said exchange at any point in time.  In my model of the problem, these conditions are necessary and sufficient for a soln to the problem.
 
My worry is that these conditions are not actually implementable in a reasonable way with the simple rope scenario.  Any semi-sensible soln (such as yours, or some others I have considered) require some heroic assumptions about issues such as equality of strength and validation of merchandise by simple observation.  Alas, these are fairly unbelievable assumptions...
 
BTW, some specific real-world comments/questions about your model (almost silly since they are clearly not the focus of the problem):  1)  I agree the time out is critical (as per my point 2) above), but where do you cut the rope?  If you cut it at the pulley, the customer could just grab both pieces of the rope (certainly at least the one near him, since it has to be within reach for him to open in the "working" case), and then just pull the tube up.  2)  You need the bottom of the lower tube to be a fixed distance from the top of the object in the upper tube, since the lower tube merely needs to be opened at the bottom while for the upper tube the customer needs to be able to reach inside to the top of the object.  With variable height objects, this becomes a problem.
 
Best,
Eric
IP Logged

"It is better to have puzzled and failed than never to have puzzled at all."
SWF
Uberpuzzler
*****





   


Posts: 879
Re: High Buildings and Street Vendors  
« Reply #11 on: Nov 3rd, 2002, 10:56am »
Quote Quote Modify Modify

I did not interpret this question as requiring resolution of how to validate merchandise by visual observation.  If that were the case, why even confuse the issue with the rope?  When I buy an apple face to face with a vendor, I don't know if it real, wax, or poisoned, and he doesn't know if I am paying with legal tender.
 
I agree there is probably no foolproof method, but it was amusing to think about the logic of how to do this, which is what I believe is the intent of the problem.  There will always be ways to nitpick flaws in a proposed method.  For example, the customer could have a pair of long-armed tongs and rope cutting tools to steal the merchandise when it is in front of her window.  Or if malicious, she could use a high powered laser to burn the merchandise through the transparent tube, and not send down any cash.  If even more malicious, she could tie a piano to the rope and push it out the window, thus stealing the merchandise and rocketing the vendor from the ground.
 
Still, I will propose solutions to some of the objections to this method.
 
Equality of strength assumption:  Have the rope pass through a braking mechanisms, two at vendor station and one at the customer's window.  The person at each brake could then control the brake at will.  Of course, it is assumed nobody is strong enough to move the rope when it is braked, and that operating the brake does not depend on strength.  The vendor needs a brake at each end of the rope: one to stop customer from pulling the product up before sending down cash, and one to prevent customer from trying to pull back the cash tube.  Or maybe just use one brake on the vendor's end and have a ratcheting type mechanism on each tube so they can move in just one direction.  I guess those methods could lead to each allowing infinitesmal jolts of motion with the customer gaining access to the product tube while the vendor still has a tiny bit to go before being able to extract the cash.
 
Rope cutting and problem with variable height objects:  Each tube would hold its contents inside a transparent cylinder which is inside the test tube.  Both would be the same distance from from the open end of the tube independent of the size of the object inside of them.  Never mind the rope cutting idea.  Instead the cyliner would drop out of the bottom of the product tube when the timer has expired.  It could possibly be designed to slowly slide down the rope, to avoid a malicious customer from dropping fragile merchandise for fun.
IP Logged
Eric Yeh
Senior Riddler
****





   
Email

Gender: male
Posts: 318
Re: High Buildings and Street Vendors  
« Reply #12 on: Nov 3rd, 2002, 12:45pm »
Quote Quote Modify Modify

SWF,
 
As I said before, I find your soln very reasonable, so I apologize if I've misconveyed that in any way.  Do I think it's as good a soln as any I've thought of or seen here?  Sure.  Does that mean I think it's a good soln?  No, for many of the reasons you've pointed out yourself.  Do I think there is actually a good soln?  No, I believe the problem is fundamentally flawed, or, in simplified form, not a very interesteing question.  But do I understand that it is clearly not worth making any further objections, even if I have reservations?  Absolutely, I think your soln is about as workable as they come.
 
In my defense re: visual inspection:  I believe that in a case where the reality is so vastly different from what is [perhaps] proposed, a problem should specify if such a feature is allowable.  Otherwise, it is certainly interpretable as requiring physical inspection to determine authenticity (yes, I understand per your apple example that this is still flawed, but I would consider it far far closer to the reality).  Perhaps I am simply too biased; in all problems of this nature (exchange of objects or information involving potenially malicious counterparties) I have previously encountered, the soln is always 100% precise through the use of codes and other mathematical constructs.
 
Best,
Eric
IP Logged

"It is better to have puzzled and failed than never to have puzzled at all."
SWF
Uberpuzzler
*****





   


Posts: 879
Re: High Buildings and Street Vendors  
« Reply #13 on: Nov 5th, 2002, 6:44pm »
Quote Quote Modify Modify

Rereading the question, I see that my original suggestion may be invalid because the question implies there is only one basket.  How about this:
 
The basket moves up and down between ground level and the customer periodically, and its motion is out of the control of both customer and vendor.  Permanently attached to the basket are two transparent boxes with special locks.  These locks are such that on ground level either one, but not both may be opened.  These locks are reset each time the basket goes up and comes back down.  When at the customer's window, only the box that was not opened by the vendor may be opened.  If the vendor opened neither then customer may open either one.
 
In this way, vendor can load a box with his wares.  Customer can put in something she wants to trade in the other box.  Vendor can then take his wares back or accept the trade, then customer gets contents of the other box.
IP Logged
James Fingas
Uberpuzzler
*****





   
Email

Gender: male
Posts: 949
Re: High Buildings and Street Vendors  
« Reply #14 on: Nov 8th, 2002, 2:09pm »
Quote Quote Modify Modify

Here is another way of implementing the exchange, which requires two transparent baskets, A and B. When they're in their normal position (A at the customer, B at the vendor), they open freely. Either the vendor or the customer can pull the rope and switch A for B. When A and B are in the switched position, then they can only open when both parties agree to open them--the two locks are interlocked.
 
1) First of all, the customer and vendor yell back and forth (or exchange Post-It notes) to decide what they will exchange.  
 
2) When they have decided, then they put their goods in their basket, and switch the baskets.  
 
3) If they are both happy, they both open the boxes, and the transaction is over. If not, then they switch the baskets back to their normal positions and renegotiate. Maliciousness could enter here if one person decided that they would hold the rope and prevent the other from reclaiming their goods after a failed transaction, but this is a waiting game with no payoff for the malicious person.
 
The advantage of this scheme is that it speeds up legitimate transactions, while ensuring that both people have access to the baskets before either can get the goods out.
IP Logged

Doc, I'm addicted to advice! What should I do?
Crassworm
Guest

Email

Re: High Buildings and Street Vendors  
« Reply #15 on: Jan 24th, 2005, 2:27pm »
Quote Quote Modify Modify Remove Remove

Here's another way to do it with transparent boxes.
 
The vendor and the customer both must have two locks that only he or she has the key to.
 
The customer places the money in a transparent box, locks it with one of the locks, and lowers it down.  The vendor then locks that box again with his lock, being careful not to let the locks intersect.  The vendor also places the product into the second box, and locks it with his second lock.
 
Next, the basket gets hoisted up; the customer unlocks the first box and takes the lock back, and locks the second box with his second lock.  The basket is lowered.
 
Now, the vendor has the first box with the money in it with only his lock on it. He unlocks it, and takes the money.  He also unlocks the second box, leaving only the customers lock on it. The box is hoisted back up.
 
This solution ensures that neither the customer nor the vendor ever has access to an unlocked box, or a box only with his or her lock on it, that is not meant for him or her to have.
IP Logged
River Phoenix
Guest

Email

Re: High Buildings and Street Vendors  
« Reply #16 on: Jun 20th, 2005, 7:23pm »
Quote Quote Modify Modify Remove Remove

Why don't they both just put up a lot of collateral with a third party?
 
Maybe the rope is woven from dollar bills.
IP Logged
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board