annenberg media ♪ by:

era la agente de bienes raíces. un empresario de los estados unidos está interesado en comprar la gavia. pero... todavía no está en venta, ¿verdad? narrador: bienvenidos a destinos: an introduction to spanish. primero vamos a ver algunas escenas de este episodio. aquí jaime. tengo muy buenas noticias. angela ha llamado desde el hospital. dice que roberto se despertó y que está muy bien. ibueno, qué alegría! se te ve muy bien. por lo menos estás despierto. sí. la verdad es que sí me siento muy bien. y yo lo puedo comprobar. se comió dos desayunos. ay, a propósito ¿no queda algo por allí?

veo que la recuperación ha sido completa y rápida. también vamos a hablar un poco sobre el ballet folclórico de méxico. fundado por amelia hernández el ballet folclórico incluye música y danzas de diferentes regiones del país. ( se toca el jarabe tapatío ) ¿y carlos se fue así? ¿no te dio ninguna explicación? no, ninguna. ¿no lo has visto esta mañana? no, no he visto ni a carlos ni a gloria. captioning of this program is made possible by the annenberg/cpb project and the geraldine r. dodge foundation.

en el episodio previo raquel y arturo regresaron al hotel después de una reunión en la casa de pedro. había un mensaje para raquel. ellos, alarmados, llamaron en seguida a pedro. acabo de recibir tu mensaje. ¿ocurre algo? no te alarmes, raquel. es que dejaste tu cartera en mi despacho... en el bar, arturo le preguntó a raquel si había pensado en ellos, en su futuro. entonces, ¿no pensaste en mí en absoluto? claro que pensé en ti... y mucho. lo que no hice fue pensar en mí. mientras tanto, pedro, ramón y mercedes hablaban de los problemas económicos de la oficina en miami.

pedro y los demás no sabían que carlos los escuchaba. en casa de ramón, carlos habló seriamente con gloria. es hora de corregir esta situación. no puedo ocultar más la verdad. carlos: ihola! más tarde, carlos descubrió que gloria había desaparecido. ramón: ¿carlos? carlos, ¿adónde vas a estas horas?

no te lo puedo decir ahora. ramón, ¿puedo usar tu carro? por supuesto, pero ¿qué pasa con el tuyo? se lo ha llevado gloria. ¿gloria? ya te explicaré. no te lo puedo decir. bien, pero, ¿qué es lo que ocurre? yo sé que uds. saben todo de lo de las finanzas en miami. les debo a todos una explicación. pero ahorita necesito tu carro, por favor. está bien... pero me dejas confundido. ¿qué tiene que ver gloria en todo esto? te prometo que te lo explicaré más tarde. no te preocupes. hasta luego. al día siguiente, roberto se siente mucho mejor. mientras desayuna, angela termina de contarle la historia de sus abuelos rosario y fernando

y de la búsqueda de raquel. ¿y todo eso pasó mientras yo estaba enterrado en la excavación? iparece una telenovela! es como un sueño, ¿no? y pensar que papá creyó toda su vida que su padre había muerto... así que tú tampoco lo conoces. no, el abuelo está muy enfermo y lo han llevado a un hospital. pero sí he conocido al tío arturo que ha venido desde la argentina. es muy simpático. ¿cómo es arturo? ¿se parece a papá? no tanto. acuérdate que tienen padres diferentes. sí, claro. cuéntame más de él. es muy simpático. y, ¿sabes qué?

creo que él y raquel... como que... naturalmente. ino hay una telenovela completa sin un buen romance! oye, a propósito ¿no podrás conseguirme algo más de comer? ime muero de hambre! bueno, eso indica que ya estás bien. voy a llamar a raquel y a tío arturo para avisarles y veré qué puedo hacer por tu segundo desayuno. ¿no te dio ninguna explicación? no, ninguna. ¿no lo has visto esta mañana? no, no he visto ni a carlos ni a gloria. habrá que esperar que aparezcan para saber qué ocurre. bueno, tío. yo tengo que ir a la gavia a atender unos asuntos. ( teléfono suena )

¿bueno? sí, con ramón castillo... él mismo. ah... bueno, sí, podría ser. lo hemos pensado, pero todavía no lo hemos decidido. ajá... sí, yo tengo que salir esta misma tarde. voy a la gavia. como guste, podría verla allá. sí. el gusto es mío. buenos días. era la agente de bienes raíces. un empresario de los estados unidos está interesado en comprar la gavia. pero... todavía no está en venta, ¿verdad? no...

y no sabemos cómo saben que es posible que la vendamos. pero es bueno saber que hay alguien interesado en comprar la propiedad. creí que habíamos decidido esperar a que papá estuviera mejor. sí, mercedes por supuesto. pero esta agente quiere ver la propiedad y me parece bien saber cuál puede ser el precio. es verdad, mercedes. eso nos ayudará a la hora de decidir. bueno, entonces, hagan lo que quieran. yo voy al hospital a ver a papá. ¿no desayunas? ya desayuné más temprano. yo tengo que ir a la gavia. voy contigo. ¿van a la gavia? me gustaría ir con uds. un poco de aire fresco me haría bien. mercedes, ¿has visto a carlos o a gloria esta mañana? no. ¿por qué lo preguntas? bueno, es muy raro. anoche muy tarde... ¿no estás cansada? no has dormido. no, me siento bien. tal vez tú me puedas hacer un favor. sí, claro, dime. debo llamar a mi familia

en puerto rico para decirles que roberto está bien. comprendo. ¿quieres que yo los llame? si no es mucha molestia... ipor supuesto que no! yo llamo. y luego, me encuentro con arturo para ir juntos al hospital. los esperamos. hasta luego. hasta luego. ¿bueno? habla raquel rodríguez desde méxico. iah, sí, sí, raquel! aquí jaime. tengo muy buenas noticias. angela ha llamado desde el hospital. dice que roberto se despertó y que está muy bien.

ibueno, qué alegría! yo voy a verlo ahora. por favor, dígale que nos alegramos mucho de que esté bien. pregúntele si necesita algo. sí, se lo prometo. y dígale que le mando un abrazo. iah! y hay algo muy importante. el hombre interesado en el apartamento ha hecho una oferta. ¿para comprarlo? sí. es una buena oferta. angela debe decidir. pídale que se comunique conmigo. por supuesto, yo se lo digo. ah... y también hay que recordarle que lo hable con roberto. sí, por supuesto. angela, a veces, es un poco apresurada. comprendo. adiós, jaime. ( suspira )

buenos días. habla raquel rodríguez. ah, licenciada rodríguez ¿cómo está ud.? muy bien, gracias. ¿y ud.? también bien, gracias a dios. ¿se encuentra pedro? no, licenciada, él no se encuentra aquí ahora. ¿y ramón, o mercedes? tampoco están ellos. no hay nadie en la casa. bien, mire, tengo prisa. cuando se comuniquen dígales por favor que roberto, su sobrino de puerto rico está despierto que se encuentra bien. dígales también que yo salgo para el hospital para verlo. sí, licenciada, no se preocupe. en cuanto ellos se comuniquen conmigo, se los diré. bien, se lo agradezco. hasta luego.

( sin sonido ) buenos días. buenos días señorita. me gustaría saber si me pueden conseguir boletos para el ballet folclórico. sí, señorita ¿cómo no? el ballet folclórico de méxico es un espectáculo de fama internacional.

fundado por amelia hernández el ballet folclórico incluye música y danzas de diferentes regiones del país. ( se toca el jarabe tapatío ) ( se tocan trompetas y guitarras ) el ballet folclórico ha actuado en muchos países del mundo. este famoso espectáculo se ha presentado en los estados unidos,s, españa y otros lugares.

la sede permanente del ballet es este bello edificio el palacio de bellas artes. todo está arreglado. puede ud. recoger los boletos en la entrada de bellas artes. muchas gracias. a sus órdenes, señorita. ya estoy listo. ¿vamos? yo también. vamos. aproveché para pedir boletos para el ballet folclórico para nosotros y mis padres. ¿qué te parece? sólo supe anoche que venían tus padres y me sorprendió. así es mi mamá. ya la vas a conocer. iqué bueno que ya llegaron! ijuan! lupe iqué gusto! ique bueno que llegaron! ahoritita me les preparo algo de comer.

no gracias, lupita todavía es temprano. sí deben tener hambre después de venir manejando desde méxico. no es para tanto si no es tan largo el camino. van a ver, tengo unos tamales unos chilaquiles y unas empanadas. ahorita mismo les sirvo, ¿eh? lupe, la misma de siempre. o mejor. ojalá que nunca cambie. ilo mismo digo yo! además, ya se me antojan esos chilaquiles. pues, la verdad ia mí también! nos conoce como si fuera nuestra propia madre. bueno, pues, ¿qué esperamos? arturo: ven que te quiero decir algo. raquel, te quiero agradecer lo que has hecho. ¿cómo? encontrar a angela y a roberto. por fin podré resolver el conflicto.

no con angel, pero sí con sus hijos. vamos. te estarán esperando. roberto... ya te hablé mucho de raquel. ella estuvo conmigo todo el tiempo que estuviste en esta horrible excavación. yo también te estoy muy agradecido, raquel. con todo lo que me ha contado angela es como si te conociera de hace tiempo. y yo a ti. y ya te imaginarás que él es nuestro tío arturo. ies increíble! ¿increíble? ¿qué cosa? tenés la misma sonrisa de tu padre angel. de veras la misma sonrisa. bueno, se te ve muy bien. por lo menos estás despierto. sí, eso sí. la verdad es que sí, me siento muy bien. y yo lo puedo comprobar.

se comió dos desayunos. ay, a propósito ¿no queda algo por allí? veo que la recuperación ha sido completa y rápida. bueno, les he traído algunas cosas de buenos aires. pensé que les gustaría verlas. arturo: fue terrible. yo era muy chico y me impresioné mucho. mi padre estaba furioso. yo nunca olvidé esa pelea.

a la noche a mi padre le dio un ataque cardíaco y angel se fue. le escribía a mi madre durante unos años pero cuando ella murió no supe más nada de él. pobre papá. se habría sentido culpable de la muerte de tu padre. sí. así le escribí en las cartas a mi madre. doctora: buenos días. buenos días. doctora: veo que el paciente ya está mucho mejor. sí, sí. ya me siento bien con ganas de salir de aquí. vamos a ver. tal vez ya podamos enviarlo a su casa. si me permiten aprovecharé para llamar al hotel. tal vez pedro ya me haya enviado la cartera. es verdad.

bien, muchas gracias. pasaré a recogerla en cuanto pueda. hasta luego. ( suspira ) bueno. por fin el tío y los sobrinos están juntos. y yo me siento muy contenta por ellos. recuerdo muy bien el humor de angela de esta mañana cuando me llamó desde el hospital. ¿recuerdan uds.? ¿estaba ella animada o parecía estar cansada? ¿no estás cansada? no has dormido. no, me siento bien. angela estaba muy animada, muy contenta. ¿y qué quería ella que yo hiciera?

angela quería que yo llamara a su familia en san juan. entonces llamé y hablé con jaime. claro, él también estaba muy contento con la noticia de roberto. durante la conversación jaime me pidió un favor. el quería que yo le dijera algo a angela. ¿recuerdan qué quería que le dijera?

el hombre interesado en el apartamento ha hecho una oferta. ¿para comprarlo? sí. es una buena oferta. angela debe decidir. pídale que se comunique conmigo. cuando bajé, le pedí al recepcionista que me ayudara en algo. ¿en qué quería yo que me ayudara?

buenos días. buenos días. me gustaría saber si me pueden conseguir boletos para el ballet folclórico. sí, señorita ¿cómo no? finalmente arturo y yo vinimos aquí, al hospital y arturo conoció a roberto. no tardaron en hablar de angel. ies increíble! ¿increíble? ¿qué cosa? tenés la misma sonrisa de tu padre angel. de veras la misma sonrisa. yo los dejé un momento para llamar al h quería saber si pedro había dejado allí mi cartera. y sí, allí está.

bueno, debo regresar. se deben estar preguntando por qué tardo tanto. raquel regresa a la alegre reunión entre tío y sobrinos. ella no sabe lo que ha pasado en esta casa entre otro tío y sus sobrinos. pero uds. lo saben, ¿no? ¿y carlos se fue así? ¿no te dio ninguna explicación? no, ninguna. ¿no lo has visto esta mañana? no, no he visto ni a carlos ni a gloria.

era la agente de bienes raíces. un empresario de los estados unidos está interesado en comprar la gavia. ahora, ¿qué estará pasando en la casa de ramón? ¿encontró carlos a gloria? ¿adónde fue ell ipapá! hola. papá, ¿dónde está mamá? salió, carlitos. ¿tardará mucho en regresar?

no, hijito. no tardará mucho. se fue otra vez de viaje, ¿verdad? sí, carlitos está... de viaje. pero regresará pronto, ¿eh? ya les daré una explicación a todos. es hora de que sepan la verdad. ( suspira ) captioned by the caption center wgbh educational foundation

annenberg media ♪

for information about this and other annenberg media programs call 1-800-learner and visit us at www.learner.org. roberto, tu palabra es 'sipc'. ¿la podría usar en una oración, por favor? en el evento improbable de que su firma de corretaje cierre, sipc está ahí para protegerlo. sipc. c-i- lo siento, roberto. eso es incorrecto. lisa flores. lisa, tu palabra también es 'sipc'. ¿podría tenerla en otra oración por favor? los fondos de sipc están disponibles para satisfacer las reclamaciones de los clientes de firmas de corretaje hasta un máximo de $500,000 incluyendo hasta $100,000 por reclamos de eftivo 'sipc'

s-i-p-k. ¿no conoce a sipc - securities investor protection corporation? no importa. se lo deletrearemos. visite nos www.sipc.org.

>> so many places to go and so many ways to get there. sometimes there are too many choices. how do we count all those things and then organize them so that we can make sense of it all? by looking to the mathematical world of combinatorics. meet charlie, the regional claims adjuster for an insurance company. on the road as usual, visiting clients, solving problems, and trying to get to five different job sites as quickly and efficiently as possible so he can get home to his daughter

sarah's birthday party. his problem: finding the best way to organize his trip, taking into consideration the distance between each client, possible time spent with each client, and the most efficient route. sometimes the number of possibilities seems overwhelming, even when we're faced with only a few choices, but we have to make decisions anyway. did he make the right choice? let's count the ways. counting things seems so simple. children do it intuitively connecting a thing with fingers to say how many. it's the way we organize the stuff of our lives, from bugs to errands. and finding efficient and interesting ways to organize things and information is what the field of mathematics known as combinatorics is all about. >> children: [ in unison ] as i was going to st. ives, i met a man with seven wives. each wife had seven sacks -- >> hey, hey. hold on, kids. going somewhere are you? >> all: yeah. >> all right, well, make sure you return, okay?

>> all: okay. as i was going to st. ives, i met a man with seven wives. each wife had seven sacks... >> even with the fairly simple system of colored buttons, we've already organized information in a relatively sophisticated way. and we started with a common intuitive form of organization: the act of counting, or enumeration...enumerating, or listing, the children and then encoding that enumeration with these buttons. but there are lots of ways in which we could have assigned children to buttons, and they encode a variety of levels of information, each corresponding to counting different things about the children. abstractly, in using the buttons, i've turned the children into a mathematical object, a set. and the fact that it can be a little easier to count buttons in a jar -- or count properties of a set of objects -- than it is to count kids running around the neighborhood is just the smallest of hints at the power

of combinatorics. counting things, that's what combinatorics is all about. as an individual field of study, it's a relatively new one. and these days, with its strong connection to the world of computing, by providing insights into how to best organize and understand the power of the computer, it's incredibly important for modern technology. however, as cutting edge as the subject may be, its basic concerns go back to puzzles and problems from the earliest recorded evidence of mathematical thought. now, this is a facsimile of the rhind papyrus, copied around 1850 b.c. by the scribe ahmes from the now-lost text of an earlier dynasty. it was named after a scottish antiquarian, alexander henry rhind, who bought it in 1858 in luxor, egypt. in it, he found what amounts to a math textbook full of problems and solutions that addressed everyday issues, things like how to divide ten loaves of bread

equally among seven men and much of the algebra needed to build the pyramids. it also contains possibly the earliest written combinatorics problem, and it goes like this: seven houses contain seven cats. each cat kills seven mice. each mouse had eaten seven ears of grain. each ear of grain would have produced seven hekats of wheat. what is the total of all these? a fairly simple math problem... and a very pragmatic combinatorial argument for getting more cats. in fact, it's not that far removed from the st. ives riddle our children at the gate were talking about. both of these problems have elegant solutions by the recognition of the simple pattern of the powers of seven that we see. now, several centuries later, we find slightly more sophisticated kinds of problems and solutions in 6th-century b.c. india. the medical treatise sushruta samhita gives us this problem: how many combinations can be made out of six different tastes: bitter, sour, salty,

sweet, astringent, and hot? by taking them one at a time two at a time, three at a time and so on, we learn that there are in fact 63 combinations. this was important in ayurvedic medicine because it gave ancient physicians a way to work out which medical substance would best match a patient's ailments. now, there are two things that are going on here. on the one hand, we're asking for the number of possible combinations, or subsets, of the six different spices. this number, as we see, is 63, which is 2^6 - 1. now, notice the sixth power and six spices. there's a pattern here: number goes to power. the magic is that we're seeing a formula, a quick way to answer the question of how many combinations of spices without actually listing them. now, there's a more particular problem that was of interest to the indian doctors, and that was the individual questions of how many combinations of one spice how many of two, and so on and

so on. again, we could simply solve it by listing them all, but much more interestingly, there's a pattern, or a formula. and 300 years later, indian scholars wrote the algorithm for solving this, again without counting, an algorithm for finding that pattern, and in this gave us one of the earliest written statements of combinatorial rules and not simply problems. so we jump ahead now a few centuries and find mathematician and scientist blaise pascal, who in 1655 rediscovered this combinatorial rule in what was later named pascal's triangle. this triangular array of numbers is built in a fairly simple way. we start with a 1 at the top and imagine that there's a 0 on either side of the 1. we're going to call this row 0. now we add pairs of adjacent numbers and write their sum between them on the next row: 0 + 1 = 1, 1 + 1 = 2, 1 + 0 = 1.

we've completed row 1. now we go to row 2 and we do the same thing. we have a 0 and a 1, so beneath it we put a 1. now we have a 1 and a 1. in between them and beneath it we put a 2. now we have a 1 and a 0, and in between those and beneath it we put a 1. tacking zeroes onto either side, we've now built row 2. and so on and so on and so on. now lop off the zeroes on either side of the triangle. what you see there is what we've seen before, pascal's triangle. let's say it's your cousin louie's birthday and he's crazy about hats. you're considering a birthday gift of five hats, but you can only afford to buy two, and you can't decide which ones. so the problem is, how many different combinations of two hats are there, and that way you can know how many pairs you have to consider. when we're working with pascal's triangle, we can actually read this information off the triangle. so now what we need to do is go to row 5. and remember, we started numbering the rows by 0, so we

actually have to count down six rows to row 5. and again, the columns also start with 0, and we go in to the second column, which actually requires 0, 1, 2, so the third entry. and there it is. the number we find is 10, and that's the right answer. and this number, the number of ways to choose two things out of five things, a mathematician calls "5 choose 2." so 5 choose 2 is equal to 10. pascal didn't invent all the ideas behind this triangle. he did what all mathematicians do, he built on knowledge from an earlier time and then pushed the boundaries of that knowledge to give us something even more interesting and, as is often the case with mathematics, more useful. combinatorial problems and puzzles test our ability to think through problems and logically come up with efficient ways to organize information. >> kits, cats, sacks, and wives, how many were going to st. ives? >> so what's the answer to this riddle? let's find somebody who might help us figure it out.

so how do we make sense of the confusion caused by all these kids? well, i'm lucky to have here with me jenny quinn, who's a professor of interdisciplinary arts and sciences at the university of washington-tacoma. jenny, thanks for coming. >> thank you, dan. nice jar. >> well, here are these buttons, and as far as i'm concerned, one button per kid. and i happen to have their pictures here. >> okay. so what we have here are two sets of six things. >> six buttons, six photographs. >> so a set is just a collection of objects. what you did here was you created a bijection between the set of buttons and the set of kids, okay? >> sure. one button per child. >> one button per child. one thing from each set matched up, holding hands with something from the other set. and this gives us a lot of information, okay? >> yes. >> so it's a question of how much information we actually want to keep track of. >> i see, because we could

assign the buttons in many different ways, in fact. >> yes, because notice each one of these buttons is actually distinct. so if we paid attention to which button went to which child, we would be able to say, if one of the buttons were missing, what child that corresponded to. >> right, right. >> but we might not want to keep all that information because there are 720 possibilities of ways to match up buttons to kids. so we could choose to consider smaller subsets to pay attention to. now, a subset is a collection, a smaller collection of the entire set. and in fact, we could ask that the blue buttons create a subset and they go to the blue-shirted kids and the orange buttons go to a subset which go to the orange-shirted kids. >> so it's actually a bijection within a bijection. >> exactly. the problem with these kinds of bijections is, as the number of objects you're considering grows, the number of possibilities becomes unmanageable. and we have to learn how to keep

track of more information or we have to pinpoint the information that's really important to us. >> right, so in fact, there are many ways that we could have made this initial bijection between the buttons and the children, the buttons and the photographs? >> oh, absolutely. because there are six different buttons, we had a choice of six buttons to give the first person, then there would be five buttons left to give the second person, four buttons for the third, three, two, one. so the total number of ways of creating this bijection would be the product of all of those: 6 x 5 x 4 x 3 x 2 x 1, which is 6 factorial, or 720. >> and so if there had been more children, i would have needed more buttons, and this way in which you're counting seems to grow very, very quickly, right? >> yes, this is what we call a combinatorial explosion. >> combinatorial explosion. >> and it's in fact too much information for us to keep track of, so what we'd like to do instead is decide what information is most important to us. so combinatorics is going to help us organize our thoughts. >> so now these bijections that we've been constructing between

the buttons and the kids is in fact just the tip of the iceberg for combinatorics, which is there are much richer bijections, bijections that encode much more subtle correspondences, isn't that true? >> oh, absolutely. in fact, what we can do now is we can return to pascal's triangle and we can see how the information about uncle louie's hats is actually encoded in the triangle. >> and in the geometry and just moving around the triangle, is that right? >> absolutely. >> all right. >> if you recall, we were choosing two hats for uncle louie out of five, right? >> that's right. >> and it corresponds to that position 5 choose 2 right there. so imagine yourself starting at the top, at the 0-0 position. now, each time you take a step you're either going to go to the left or to the right. >> okay. >> and when you take a step to the left, that means the hat in that row is not selected. and each time you take a step to the right, it means that's one of the hats you're going to give

uncle louie. so starting from the top and going to the 5-2 position, it's going to take two steps to the right and three steps to the left to end up down in the 5-2 position. >> right, equal to 5 choose 2, as we discussed in the beginning. >> so this actually tells us a little bit more about the triangle itself and the construction of the triangle. because if you think about it, suppose you wanted to pick any position in the triangle and understand where it came from. let's call it "n choose k." >> n choose k for generally the nth row and the kth entry in. >> so the way to think about it is we're trying to create subsets of size k from n elements total. and the way we can think about it coming into this triangle through these paths is we either entered this cell from a path going from the right or a path coming from the left. so you can think about this particular cell as being created as the sum of two possibilities, either the -- for the row that it came before, either the

object was included or the object was excluded. so the way to include the object is n - 1 choose k - 1 ways, and the way to exclude the object is -- >> n - 1 choose k. >> exactly. >> so that actually encodes what mathematicians would call as a recurrence. >> exactly. >> so this recurrence that we derived really of n choose k is equal to (n - 1 choose k -1) + (n - 1 choose k) is actually an example of a very fundamental combinatorial principle, isn't that right? >> absolutely. and here's my favorite example of a principle, it's called the pigeonhole principle. >> ah, sounds great. >> and the reason it's my favorite is because it's very intuitive. so here's the example i'm going to show you. we have five pigeons and they are flying home. these are carrier pigeons, so they're flying to their home. there are only four homes. >> right, so somebody might get left out, is that right? >> unfortunately, if there are more objects than there are boxes and only one thing is in

a box, then there's stuff that doesn't get assigned. but to make that pigeon happier, we're going to say that everybody has to be put in a box. and what that's going to do is it's going to force that pigeon into some box that's already occupied. >> right, right. >> so the pigeonhole principle in this case is going to say that if there are five pigeons in four boxes, some box -- no matter how the pigeons distribute themselves among the boxes -- some box is going to contain at least two pigeons. >> right, so some box might actually have three pigeons, right? i mean, that's also possible. >> right, but the box with three pigeons also contains two. >> that's right. >> so that's at least two. and in fact, if we take the average of the number of pigeons to the number of boxes, okay what the pigeonhole principle says is some box contains at least the average. >> so the average number of pigeons per box here would have to -- would simply be the number of pigeons, which is five,

divided by the number of boxes which is four. >> but because we can't have a quarter of a pigeon in some box -- >> right, no pigeons are harmed during the making of this show. >> right. they're discrete objects. we have to round up. so that tells us we're going to get two pigeons per box in this case. >> right, at least two. so these basic principles that we've been outlining, these are numbers that are easy to compute. we've been finding formulas, in fact, computing the numbers of pairs of hats or computing things like the average for the pigeonhole principle. >> in particular because they're small. >> but as we get more possibilities, we begin to experience what we've been calling this combinatorial explosion, and we're going to see an example of that now as poor old charlie gets a new itinerary. so let's take a look. charlie seems to have found his solution. at least he's crossing one off and that's a start. except now his boss has called and added more stops to his itinerary. eight more, to be exact. now he's got 12 places to organize. and it's beginning to look like

there are so many possible ways to go, he'll never find an efficient route that will let him get home in time. poor charlie, he really seems to have his hands full here. he's suffering from what we were calling before combinatorial explosion. >> well, poor charlie doesn't have a prayer in the world of answering his question definitively, okay, but there are ways that we can cleverly approach a problem and organize the information so that we can reduce the amount of work that needs to be done. >> oh, is that right? >> here's an example for you. the setup is we have a keypad with ten digits and we want to input a three-digit code to unlock the door. >> okay. >> so if you were to do this in sort of a very natural methodical method, you'd put in 0-0-0, you'd put in 0-0-1. >> make your way through. >> and you test every number from 0 to 9-9-9, okay, and that might take you a while. >> and that's 1,000 codes, and i have to hit -- for each code, i

hit it three times, so that's 3,000 pushes, right? >> exactly. okay, now, if you use something called a de bruijn sequence, okay, this is a way of organizing this information so we really reduce the amount of work that we're going to do. we're going to cut the amount of work by a factor of 10. in a de bruijn sequence, we can organize the list of numbers in such a way that every three digits that we want to read is a different set, a different combination. so you might start with 0-0-0, test those first three, and then hit 1, that's going to be 0-0-1 is now going to be tested. >> i see, so i'm sort of sliding a window along. first it's 0-0-0, and then i would slide it one thing. in other words, i'd press a 1, so that would mean 0-0-1 is the next code that i was testing. >> exactly. and now by organizing it in this fashion, we've reduced the amount of work by a factor of 10. so if it took five hours to test all 1,000 numbers, it's now going to take on the order of 30

minutes. >> great, math to the rescue. >> so in fact, de bruijn sequences are not only useful to get into a door, it's also being used right now in genomic analysis. >> yes, genomics generally is a big user of combinatorial work the sort of discrete units of the genome, and we have an example of that here. let's watch. >> i'm terry gaasterland, and i'm a professor of computational biology at university of california-san diego. i am in the marine biology department, and i have collaborators in new york and i have collaborators here in oregon. you can think of dna in many different ways. if you're a computer scientist, you can think of it as ones and zeroes or you can think of it as four letters: a, c, g, and t. if you're a biologist, you think of dna as a long, complex molecule that is made of each of the compounds that a, c, g, and t represent.

a genome is the specific bundle of dna that's in a particular cell. so we can think of dna as being paragraphs, words, sentences where a genome would be the specific book that is you. dna sequencing is the process of trying to read the letters that are in the book. so sequencing is the process of fragmenting that dna into little tiny pieces and reading a little bit of each of the fragments. and now you've got all these 500-, 700-letter words and you need to fit them all back together. early on, when people started trying to sequence genomes people came up with the most interesting and innovative ways to do it. then there was the process of directed primer walking. so randomly go into the genome do a read, and then design a little probe that will put you at the end of that read, and

then keep reading. it turned out that the problem there is that genomes are very repetitive, so every one of these ran into combinatorial problems. and it turned out that the idea craig venter was really pushing nessed all of this combinatorics. take the whole entire genome chop it up into lots and lots and lots of little pieces, and take reads off every one of those, and do so many that you have enough information to fit those pieces back together. for any given book, if you will, you have multiple copies of the book, and one you're ripping in half at chapter one and the other you're ripping in half at chapter four. if you do enough of them, it will cohere into one. given this fragment and given this fragment, 200 bases overlap, so we'll put them together and see if we can put the next one in. and if those two overlap and then you have a third one that

comes in and it matches, you know you have it right. with a human genome, which is 3 billion a's, c's, g's and t's, you need to be a little smarter. so now you set all sorts of heuristics. so you say, "well, let's take every pair of reads that overlaps by at least, say, 100 letters," and they have the identical 100 letters. the problem is there's always sequencing error. for every one of those comparisons, you're computing all these details about it. so that is the problem that the computer has to solve as it's doing assembly of all of these pieces. when i first started in looking at genomes, the only genomes that were being sequenced were one-celled microbes, bacteria and archaea. proteins from one organism would have absolutely no match whatsoever in the next organism over, so there seemed to be proteins that were absolutely

unique to each of these organisms. so that made people step back and say, "well, we need to sequence more organisms and fill in all the holes and the gaps in this tree of life." so now we go from one-celled organisms to more complicated organisms with several or many cells or even with differentiated cells like a sea urchin or a human. gene by gene, we can look across the evolutionary tree and ask which gene in sea urchin goes with which gene in zebrafish and that goes with which gene in human? and by studying when that gene turns on and turns off during development or in maintenance of a healthy organism -- in sea urchin -- that tells us something about how it might be working in human. >> wow, so genomics, this is a particular example where combinatorics has really helped us. it's allowed us to simplify a

problem and it's really given us a purchase on how to do things. but there are actually problems which are combinatorial in nature which we still don't know how to solve, isn't that right? >> well, like charlie, for instance. >> poor charlie, yep. >> he's in what we call a traveling salesman problem. >> yes, he is. >> the idea being you're given a certain number of cities and you want to travel -- starting from one city, you want to travel to all the cities, getting back to where you started in the most economical fashion. now, if there are a small number of cities, the analysis is not difficult. so if charlie only had three cities, okay, there are only two possibilities: either he goes clockwise from where he is or he goes counterclockwise. >> so each route has a cost as well. >> each route has a cost. but now if we add a city to that, okay, his two choices... >> oh, i see, it's starting to grow. >> go to six, okay? if we add another city... >> okay, it's getting worse. >> it goes from 6 to 24. >> i'm seeing a pattern here. is there one, in fact?

>> oh, there absolutely is. if we jump to 10 cities, there are now over 350,000 possible organizations to his route. >> and that factorial number is coming in here again, isn't it? >> exactly, so 10 cities gives us 9-factorial possible routes. >> okay, 9 x 8 x 7 and so on. okay. >> if we jump to 25 cities... >> okay, that really looks like a problem. >> there are billions and billions of routes. and no matter how clever we are, there's no way we can look at every single one and find the best or fastest possible route. >> all right, well, jenny, this was great, thanks. >> my pleasure. >> so charlie is left with too many possible solutions, more than he can calculate with a simple map and a pad of paper, or even his laptop. but sometimes the path is clear, and sometimes the right way to organize information is the way that leads us home. >> hi, princess. >> daddy! >> ♪ happy birthday to you ♪ >> kits, cats, sacks, and wives,

how many were going to st. ives? yay! >> our lives are constructed out of seemingly endless possibilities. we make choices so we can be more efficient in what we do and where we go, so we can unlock the secrets of the human genome, or simply solve a math riddle. the answer to the riddle, by the way, is one. i'm the only one going to st. ives. the other combinations we'll save for another time. captions by lns captioning portland, oregon www.lnscaptioning.com