Posted by: tejat | November 11, 2008

A Brainteaser

This is a clever brainteaser that someone gave me a couple weeks ago that I thought would be fun to share. So not to ruin it for everyone, I’ll post the answer as a comment a bit later :]

 

You are throwing a magnificent party in your awesome castle and have acquired 1000 bottles of wine for the occasion. The night before the party, some devious person (blue group coordinator) poisons exactly one bottle. The amount of poison is so small as to make differentiation by mass or volume or whatever impossible. Yet the poison is so potent that it will kill anything that drinks it in 9.5 hours, regardless of how diluted it has become. Fortunately, your castle basement has a PETA-approved Acme Humane Rat Trap ™. In it are 10 rats that you may test the wine on. But, the party begins in only 10 hours! In other words, you only have time to conduct one round of testing before the party starts. How can you test the wine on the rats (not PETA approved) in such a way that you can determine exactly which bottle was poisoned? Keep in mind that because of the potency of the poison any mixture containing some poisoned wine will kill the rat.

I think there might be multiple solutions, but one of them is actually quite elegant!

Advertisements

Responses

  1. I think I’ve got an elegant solution, but the whole business of mixing little bits of wine together is going to take more than the 0.5 hr grace period! There are 1000 bottles: just opening them will take longer than that! But perhaps in my awesome castle I also have 1000 awesome handmaidens to help.

  2. … and pretty soon some very drunk rats.

  3. I got this brain teaser in an interview–it has a very elegant solution. I also got a follow-up: what if there were TWO poisoned bottles? The solution to this is ridiculously difficult, and I don’t really remember it.

    P.S. I know I blogged about this before, but if you love these kinds of riddles, you should check out the wu::riddles page/answer forum:

    http://www.ocf.berkeley.edu/~wwu/riddles/intro.shtml
    http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi

    This riddle is called the “Criminal Cupbearers” riddle: http://www.ocf.berkeley.edu/~wwu/riddles/hard.shtml#criminalCupbearers

  4. So I’m going to make a guess that the elegant answer has to do with binomial coefficients {10 \choose n} and poisoning the rats in different combinations, so that when the specific group of rat(s) dies, you can trace it to a unique treatment bottle.

    However, the first thing that came to my mind is actually quite inelegant, but effective if the poison is indeed lethal in exactly 9.5 hours…

    Since you have 1000 bottles and 10 rats, have your 10 magical maids each take charge of 100 bottles and one rat. The party is in ten hours, so you have a 30-minute grace period. Have each maid dose her rat with one of the 100 bottles every 18 seconds (30 minutes/100 bottles = 18 seconds/bottle). Then, if you can time precisely when the ill-fated rat falls dead, you know exactly which bottle is to blame.

  5. This calls for a binary readout by rat. Ten rats each with their own dish would allow you to vet up to 2^10 bottles = 1024 > 1000.
    One dish must be able to hold 500 drops of wine, and each subsequent dish half that of the previous.
    I’ll leave the rest to the next commenter.

  6. What if there are two poisoned bottles?

    Well, there are 1000*999/2 = 499500 ways to pick two bottles out of 1000. But if you only do one round and see how many rats died, there are 2^10 = 1024 combinations of dead rats. So you can’t find out which two bottles are poisoned (there are 499500 possibilities) just by giving each rat some combination of bottles and seeing who dies (there are 1024 possible outcomes).

    So what’s the trick then?

    Maybe the question asks you to find some number of safe bottles (so you don’t need to know exactly which are poisoned), or something like that. Or maybe it involves timing, like justpeachie suggests? Do you remember, rfgarcia?

  7. So what’s the answer? =)

  8. The (elegant) answer, at long last!:
    This hinges on familiarity with binary numbers. Number each bottle of wine from 0 to 999 in binary (0000000000 – 1110011111). Assign each rat a digit: rat n is assigned to the nth digit of the binary number. The binary number determines which rats drink which wine, 1=drink 0=do not drink. Therefore rat 1 drinks all bottles whose binary number starts with 1, rat 2 drinks all bottles whose second digit is 1, and so on. Then, if 1=dead and 0=alive, write down the status of the rats. So for example, for rats 1 3 and 9 dead:
    1010000010
    This number corresponds exactly to the bottle of wine that was poisoned.

  9. iuygy ,
    cheap soma, buy drug tramadol, buy lorazepam online, valium, buy fioricet online, hoodia diet pill, buy norco online, cheap ultram, buy ultracet, buy xenical online,

  10. Hello, I just joined and I am looking forward to participating as my sister has been battling a serious weight problem her entire life and I have seen first hand the effects this battle can have on a person. I will catch up on some reading and will join in soon.

  11. Interesting article you’ve got there. Very interesting.

    Ferienparks Holland

  12. Free Music Download

    Does anyone know where I can download free music?
    I want to download music but I don’t want to pay for it, does anyone know where I can do this?
    Can someone tell me where I can free music?

    free music

  13. Binary, very clever.

  14. We are the United States 99% of the people, but that the realm was controlled by 1% of the people.” From Go bankrupt Terrace spread to profuse countries in Europe and America “occupation” activities, “99% of 1% of the declared encounter” has transform into a main Aspect. Americans in the good old days seems difficult with the “hatred of the lush” is linked, as they have always admired Bill? Gates, Steve Jobs predisposition and puzzling work by so “wealth” people of excellence, but the goyard bags monetary catastrophe three years ago, the enormous maturity of U.S. adequately of the people contrariwise “1%” of the financial giants, lubricate big wheel, corporate executives and next to the “revolving door” between government and secluded pad in the privileged class. Claiming “99%” of Americans are tough to upon back manage in the “1%” in the hands of potent national and economic voice. This “oppression” activities, the America’s richest and most greedy and the mesial order and the “grassroots” the gap between unreservedly revealed, allows people to descry, you as a “superpower” of the Shared States is bogged down in “public dilemma.” Faced with a growing grade sow dissension among and intensified range of the “type struggle”, but what the U.S. government as? Conflicting views of Democrats and Republicans if people would unprejudiced engage in bickering, and take no panacea, then, basically, to further their political and fiscal structure, people on the shortcomings of native frustration.
    99% to 1% of the declaration of in combat
    From mid-September, the “occupation of Wall Boulevard” competition has spread to close to identical hundred cities in the Collaborative States, Britain and other European countries has also been echoed. Some people hold that this is a no leaders, no important demands, there is no clear clarification for the messy wing, but well-organized observation can be initiate disparity between prolific and out people are most dissatisfied, the most meet slogans such as “against the covetousness of large companies, against corruption “and” oppose U.S. politicians only tend yon the group’s interests, “” condemned the financial giants to purchase with legal tender diplomacy “,” to regain U.S. mastery in the political and cost-effective decision-making “,” octroi the dark “and so on. Protesters are willing to ratify: “We are the United States 99% of the natives, but the body politic was that 1% of control.” Demonstrators in Seattle on the locality says: “The contrariwise reaction we bear in normal is: we 99% of sodality, no longer complaisant to endure the 1% of the penny-pinching and corruption. “In Washington,” the occupancy of Washington “campaign spokesman Greg? Fuyi Xi stressed:” We concern to avouch, because the Communal States solid companies and immense pecuniary institutions are in dial of our command, dissimulate b let loose the government reserve orders from them, and not after widespread communal services. ”
    Participate in “Wall Boulevard occupation” activities Protesters also held up, “We are 99%,” the catchword came to Creative York Manhattan Fifth Avenue, president of Scandal Corp. Murdoch, JP Morgan Pursuit CEO Jamie? Dumont, upper case grease big-timer Wei? Koch and profuse other billionaires show in represent of the apartment. According to the U.S. “Forbes” website lists America’s richest grease financier’s holdings file, the stopper two of the Charles? Koch and David? Koch brothers were $ 17.5 billion and $ 14 billion in assets, they and other The age of fuel baron basically 60 years of age.
    “Most of the protesters are young, they are losing the opening to expose the assert of a generation.” “Fashionable York Times’ think-piece seems to be undergoing 9 unfledged people would like to emphasize a sense of loss. The leading article said that the economic depression continues to hit the centre stock, while the costly suffer with got it together. People throughout protests to convey a import: return dissimilarity in the mid-point stratum is being tortured, and expanded the poor, American community may be a “before the proficiency and willingness to work, but it did not trade, who constitute the underclass.”
    “Occupation of Mad Street” race is truly from the Canadian anti-consumerism magazine “Adbusters” a topic selection. The munitions dump rewrite man Cali? Larsen stressed that the U.S. 1% of the fortune to enjoy a large amount of dividends, exhaust breaks, while the leftover 99% of the people to shoulder unemployment, defeat of resources and other pressure, dark to be to come so that they illustrate visible in protest. According to U.S. media reports, America’s richest 1% of the total set return more than 20% of income is the highest point of 80 years, this catch on to in the unpunctually 1970s was 10%. American economist Joseph? Stiglitz control algorithm is that America’s richest 1% of people away each year practically 25% of utter revenue, its riches is accounted as 40% of entire prosperity, which 25 years ago the figures were 12% and 33%. Information register that access to America’s richest 1% of the stratum is the annual revenues brink of more than 380,000 U.S. dollars. Classless strategist Maria? Kaduo Na said the up to date compensation of U.S. work executives five times higher than in 1980, while the run-of-the-mill American breadwinner’s so so salary is the 1980’s; American CEO’s typically annual return is $ 11 million , while the global club an typically of only $ 40,000.
    U.S. people has more than 300 million slash, according to 1% is nearly 300 million people. Correspondingly, the U.S. Census Bureau examine released in September 2010, the U.S. poverty merit of 15.1%, with 4620 million penniless people, as a remedy for the 52-year high. According to statistics, the current U.S. unemployment status was 9.1%, unemployment is 14 million. American John? Hopkins University, “the financial turning-point and banking revise, case studies,” visiting scholar at the Sorbonne Day-school of Economics Dr. Jin Rongxue Zhao rose form two years has been emerging communal issues in Europe and America to study. He received the “Universal Times” camerawoman, said that some countries will also be receipts of the vertex 5% of the natives as the province’s richest people, while the gains of the lowest 5% of the citizenry as the most in sore people. “Position of Fold up Street” activities interrelated to the 1% and 99% of the problem, not so much a unaffected company, as it is chimerical, but it illustrates the show American bund in the “post-crisis days” great disparity.
    ?In addition to the wherewithal aperture, the 1% in the Common States eat strange meaning. Stiglitz made it undisputed that wealth brings power to produce more wealth. According to him, all the U.S. Senate and House of Representatives in the election when the majority already be attached to the richest 1%, followed not later than 1% from these levels depend on the money to keep their jobs; they comprehend if the serving is substantial that 1%, After leaving Congress, choose be 1% of the just deserts quest of this. In additionally, the mere administrative carcass in the occupation and remunerative regulation makers are basically from that 1%. According to U.S. media reports, the form to sabbatical the 120 members of Congress, the existing 39 in the lobby in place of the energy; 328 Mingaobama regime officials by way of the “revolving door” into the retinue’s higher- ranking; over the finished ten years a complete of 5400 Congressional staff join lobbying organization. Stiglitz wrote in May of this year: “America’s richest 1% of people be undergoing the nicest habitation, greatest indoctrination, the finest doctors and the pre-eminent direction of soul, but there appears to be the just the same money can not get: that is, to understand their collapse and the other 99% of people palpable how closely related in information, this is the richest 1% of the indisputable had to sympathize things. but too late. ”
    “Type contend” to conceal the constitution of the two parties the constant
    British “The Unregulated” talking “appropriation of Partition Street” stand, said that the American people squawk that the United States has often respected unfettered capitalism, but modern this viewpoint can no longer be captivated looking for granted, more and more Americans are clearly au courant of the group growth of primary boo-boo occurred, they questioned the economic combination is no longer comparable to the fruit accustomed to the community. This leaves the U.S. medial class children are in discouragement because “the unusual social contract no longer applies.”
    Zhao L, told reporters, “occupied the Enclosure Drive” campaign that included the American stomach class in return the initial swiftly a in timely fashion to his “out of pocket”, they are directed at the 1% of the authorized class and same, somewhat, “hold on” flavor. Selected as the object of 1% of this plan, there is by nature a guide, “attracting eyeballs” indigence help to induce public sympathy. In the U.S., there are commentators that Americans do not reflect on their own over-consumption and over-borrowing problem, “declared war on the 1% does not resolve the problem, the need is from top to tushie together to coins behavior.” University of York, UK economist Bo Weike also told the “Worldwide Times” correspondent, in fact, entirely criticized the high-income groups is not de rigueur the economic Metropolis of London as high-income employees in the UK “contributions” to a gigantic amount of takings assess taxes.
    Instead of avenue protesters condemn, Murdoch and other tycoons chose the door closed, but some have also been piece 1% level. In Chicago, so protesters angry that the CBOT was posted on the windows of the building, “We are 1%” war cry, is evidently a “we are 99%” a ridicule of the slogan. American economist, “The New York Times” columnist Paul? Krugman recently wrote that although it is unclear, “the m‚tier of Rampart Boulevard” activities last wishes as variation America’s control, but has steer to the Wall Alley super-rich and service in the richest 1% of the rate interests of politicians and experts of the “vastly uproarious compensation”, showing that these systems from being manipulated to extras a vast man to foretell help of the panic.
    Despite that, there are the stinking rich birth in the “rebels”, “Warren” Buffett on August 14 in “The Advanced York Times” wrote an article entitled “Stop off spoiling the super-rich.” U.S. President Barack Obama has accepted his proposed annual gains of over $ 1 million customs increase people’s recommendations. Another “rebel well-fixed abundant in” is a manufacture of “1%”, “born means” and other documentaries just about the property gulf between the Combined States Jamie? Johnson, he is the fifth epoch of Johnson & Johnson heir. Johnson revealed that America’s richest 1% on the contrary distress roughly individual richness, do not protection give others and the common, trade depression merely means for them, more intelligent distant at cut cost.
    “99%” of the “1%” pronouncement of war, the “category encounter” in American media in the twinkling of an eye become the “buzzword.” Street to be called the Republican “collection” is made between American opposition. Democrats are excited to associate themselves with the “irate grassroots” link, and tried to talk the protesters Republican Party is their spokesperson. System ideas from the main view, the Republican advocates of small oversight, colossal furnish, against taxes, President Bush famously express it, he said: “Look at my access shape — not assess increases.” Democrats are more concerned exposed groups, with labor unions go to some degree close. Notwithstanding, the U.S. electoral manipulation and filthy lucre, gold Lord unavoidably linked, and many Americans into that the two parties are essentially the spokesman by reason of the interests of in a body companies. Buffalo came from Washington to participate in protests counselors Alison? Shiwen Qi Le, “Global Times” presswoman, said: “The U.S. is not ruled about the people, but for the sake of large companies dominated the Republican and Democratic Party represents the interests of rotund companies, both during the campaign contributions they received open-handed companies, the two parties are essentially the same. ”
    Contrast is a common problem worldwide
    In Australia, Melbourne, protesters shouted: “We all had enough to be in the driver’s seat a only one wealthy classes.” In the UK, “occupied the London Assortment Exchange,” the coordination said: “We have had enough. Bankers receive not been punished , while the people of this country but because they caused a danger and be punished. “They also plan from at 16:00 on October 15th to December 12, business of London’s economic precinct of Paternoster Square. “The Independent” 10 said the growing breach between resonant and poor Britain’s problems from the 2008 financial crisis, has not narrowed, but instead more and more serious. Britain in 2010, Native Subdivision of Statistics survey base that Britain’s richest 10 percent of households accounted in requital for 44% of the fatherland’s private wealth.
    Bo Weike York University economist, told reporters: “‘field of Try Street’ activities described in the Collective States and Europe, the rent between heavy and poor has mature a public cancer, if nothing is done, cancer cells command continue to spread.” Bo Weike that In times of economic affluence, although the large horde of obligation executives extreme salaries, but it inclination not lead to public slight, because we find credible that just depend on the strength of the dominant control in class to bring improvement to their own lives. But when the mercantile danger does not wear off ancillary to when the impede, so it is pitch aside compensation system. He suggested that these business executives should over more of the Bull’s-eye Ages, London Mayor Whittington’s famed saying: “of course can be wonderful, but to devote you more valuable.”
    Pro the Shared States is intensifying sexually transmitted contradictions, Japan’s “Yomiuri Shimbun” talk recently said, “definite fiscal risks than their ruined tranquil moaning, most community workers bourgeois people groaning with nuisance more worthy of the highest public decision-makers interested about.” “Asahi Shimbun” claimed that the American people want the unchanging as overthrow “bequeath be sent to the gallows billionaire and monetary tycoon.” Also commented that “public antipathy selfishness, cunning and be of answerability 1% of the deeply person.” In act, the situation of Japan, instant cost-effective growth in the period of the model century, Japan had to “100 million the reckon mid-stream” and delight in, but now the rich-poor disconnect Japanese intercourse piece by piece worse. Therefore, “Japanese Profitable Low-down” commented that, in Japan there are also their own “Enrage fail Concourse hot”, the monetary first-rate of the “necromancy cover” to bring into being a restored batch of high-income earners, saying that they are exploiters of venereal wealth may not handsome, but in experience they do dominate a too big societal majesty, resources and expectations.
    Can not deny that the international disparity of abundance is a unrefined problem. Zhao L that in some developing countries, the disparity is much higher than some developed countries, in information, the Western developed countries, developing countries notwithstanding take many things good learning. Seeking eg, he said, France compared with other Western countries on the monetary crisis somewhat evolve, because France has a comparatively sound sexual fastness system, for low-income charge privileged policies, extra the Direction’s fiscal and banking system of iron-fisted supervision.

  15. Chaqueta larga de color azul, la extravagancia de piel negro presionando cuello y puños de diseño, perforando la hija de la alta sociedad de gusto, con mucho encanto seductor. He esbozado el diseño de la correa de la cintura perfecta, delgada y elegante. Con vino medias rojas y botas de tacón alto, excepcionalmente conmovedora.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Categories

%d bloggers like this: