Самая сложная задача в мире

Име­ют­ся три раз­ра­бот­чи­ка: бэкенд (А), фрон­тенд (В) и фул­стек (С). Пер­вый все­гда гово­рит прав­ду, вто­рой все­гда лжёт, а тре­тий все­гда отве­ча­ет слу­чай­ным обра­зом, то есть может как соврать, так и ска­зать прав­ду. Нуж­но за три вопро­са выяс­нить, кто из них кто.

Огра­ни­че­ния и усло­вия:


  • про­грам­ми­сты отве­ча­ют толь­ко фра­за­ми «Надо поду­мать» и «Зави­сит от ситу­а­ции». Одна из этих фраз озна­ча­ет «да», дру­гая — «нет», но мы зара­нее не зна­ем, какая где;
  • один и тот же вопрос двум раз­ра­бот­чи­кам зада­вать нель­зя (но задать два вопро­са одно­му раз­ра­бот­чи­ку — мож­но);
  • не обя­за­тель­но зада­вать вопро­сы каж­до­му раз­ра­бот­чи­ку, мож­но все три вопро­са задать одно­му;
  • вы сами реша­е­те, кому и в каком поряд­ке зада­вать вопро­сы;
  • нель­зя зада­вать фило­соф­ские вопро­сы, на кото­рые нель­зя отве­тить одно­знач­но «Да» или «Нет»;
  • нель­зя зада­вать такие вопро­сы, на кото­рые невоз­мож­но отве­тить.

Решение


Наша зада­ча — одно­знач­но опре­де­лить бэкен­да и фрон­тен­да, что­бы мето­дом исклю­че­ния най­ти фул­с­те­ка.

Слож­ность зада­чи в том, что мы не зна­ем, что озна­ча­ют их отве­ты. Если мы что-то спро­сим и нам отве­тят «Надо поду­мать», то как мы пой­мём, это «Да» или «Нет»? Полу­ча­ет­ся, что нам нуж­но зада­вать такие вопро­сы, что­бы уже с пер­во­го отве­та понять, что на самом деле озна­ча­ет их «Зави­сит от ситу­а­ции» или «Надо поду­мать».

Но тра­тить один вопрос из трёх толь­ко что­бы выяс­нить это — глу­по. Надо ещё полу­чить какую-то инфор­ма­цию о том, кто перед нами (или кого перед нами точ­но нет). Зна­чит, пер­вый вопрос дол­жен состо­ять из двух частей — дать нам новую инфор­ма­цию о раз­ра­бот­чи­ке и одно­вре­мен­но с этим уста­но­вить, что у них озна­ча­ет «Зави­сит от ситу­а­ции» и «Надо поду­мать».

Напри­мер, сфор­му­ли­ру­ем вопрос так «Если я спро­шу у тебя „Про­грам­мист В — это фул­стек?“, ты отве­тишь мне „Зави­сит от ситу­а­ции“?»

Общая схе­ма состав­ле­ния подоб­ных вопро­сов такая: мы фор­му­ли­ру­ем какой-то вопрос про дру­го­го про­грам­ми­ста и спра­ши­ва­ем, если бы ответ был вер­ным, ты бы отве­тил вот так-то? Такие вопро­сы помо­гут понять, что за про­грам­мист сто­ит перед нами, и, что самое важ­ное, даст нам допол­ни­тель­ную инфор­ма­цию про вто­ро­го про­грам­ми­ста.

Что­бы понять, как рабо­та­ют такие вопро­сы и поче­му их нуж­но исполь­зо­вать, давай­те раз­бе­рём, как на них отве­ча­ют бэкенд и фрон­тенд. Фул­с­те­ка пока раз­би­рать смыс­ла нет — он отве­ча­ет абсо­лют­но ран­дом­но, и как трак­то­вать его отве­ты, рас­ска­жем поз­же.

Напри­мер, вот вопрос: «Если я спро­шу у тебя „Раз­ра­бот­чик В — это фул­стек“, ты отве­тишь мне „Зави­сит от ситу­а­ции“?»

Если пра­виль­ный ответ на задан­ный нами вопрос — «Да», то нам отве­тят «Зави­сит от ситу­а­ции», а если пра­виль­ный ответ — «Нет», то нам отве­тят «Надо поду­мать».


Доказательство

Автор зада­чи пони­мал, что это утвер­жде­ние нуж­но чем-то дока­зать, поэто­му он сра­зу после тек­ста зада­чи при­вёл дока­за­тель­ства сво­ей право­ты. Сле­ди­те вни­ма­тель­но за логи­кой отве­тов.

1. Допу­стим, что «Зави­сит от ситу­а­ции» озна­ча­ет «Да», а «Надо поду­мать» озна­ча­ет «Нет»:


  • Мы спра­ши­ва­ли у бэкен­да, и он отве­тил «Зави­сит от ситу­а­ции». Посколь­ку он все­гда гово­рит прав­ду и вер­ный ответ на наш вопрос — «Зави­сит от ситу­а­ции», он озна­ча­ет «Да».
  • Мы спра­ши­ва­ли у бэкен­да, и он отве­тил «Надо поду­мать». Посколь­ку он все­гда гово­рит прав­ду и вер­ный ответ на наш вопрос — «Надо поду­мать», то он озна­ча­ет «Нет».
  • Мы спра­ши­ва­ли у фрон­тен­да, и он отве­тил «Зави­сит от ситу­а­ции». Посколь­ку он все­гда лжёт, то на наш вопрос он отве­тит «Надо поду­мать». Полу­ча­ет­ся, что пра­виль­ный ответ на вопрос — «Зави­сит от ситу­а­ции», кото­рый озна­ча­ет «Да».
  • Мы спра­ши­ва­ли у фрон­тен­да, и он отве­тил «Надо поду­мать». Так как он все­гда лжёт, то на наш вопрос он отве­тит «Зави­сит от ситу­а­ции». Полу­ча­ет­ся, пра­виль­ный ответ на вопрос — «Надо поду­мать», кото­рый озна­ча­ет «Нет».

2. Пред­ста­вим обрат­ное: «Зави­сит от ситу­а­ции» озна­ча­ет «Нет», а «Надо поду­мать» озна­ча­ет «Да»:


  • Мы спра­ши­ва­ли у бэкен­да, и он отве­тил «Зави­сит от ситу­а­ции». Посколь­ку он все­гда гово­рит прав­ду и вер­ный ответ на наш вопрос — «Надо поду­мать», то его ответ озна­ча­ет «Да».
  • Мы спра­ши­ва­ли у бэкен­да, и он отве­тил «Надо поду­мать». Посколь­ку он все­гда гово­рит прав­ду и вер­ный ответ на наш вопрос будет «Зави­сит от ситу­а­ции», то его ответ озна­ча­ет «Нет».
  • Мы спра­ши­ва­ли у фрон­тен­да, и он отве­тил «Зави­сит от ситу­а­ции». Так как он все­гда лжёт, полу­ча­ет­ся, что вер­ный ответ на наш вопрос — «Надо поду­мать», и его ответ озна­ча­ет «Да».
  • Мы спра­ши­ва­ли у фрон­тен­да, и он отве­тил «Надо поду­мать». Посколь­ку он все­гда лжёт, то вер­ный ответ на наш вопрос — «Зави­сит от ситу­а­ции», и полу­ча­ет­ся, что его ответ озна­ча­ет «Нет».

Это безум­но слож­ное на пер­вый взгляд дока­за­тель­ство мате­ма­ти­че­ски вер­ное. Мы к нему ещё вер­нём­ся, когда будем рас­ска­зы­вать про мате­ма­ти­че­скую логи­ку и про то, как она рабо­та­ет в жиз­ни.

Если вы три раза про­чи­та­ли это, но так ниче­го и не поня­ли — это нор­маль­но, тогда про­сто поверь­те, что дока­за­тель­ство вер­но


Конец доказательства

Теперь мы можем это исполь­зо­вать для того, что­бы выяс­нить, кто из них кто.

1. Сна­ча­ла зада­дим вто­ро­му раз­ра­бот­чи­ку вопрос: «Если я спро­шу у тебя „Пер­вый раз­ра­бот­чик — это фул­стек?“, ты отве­тишь мне „Зави­сит от ситу­а­ции“?»

Если вто­рой раз­ра­бот­чик отве­ча­ет «Зави­сит от ситу­а­ции», зна­чит, либо он фул­стек и отве­ча­ет абсо­лют­но ран­дом­но, либо он не фул­стек, а на самом деле пер­вый раз­ра­бот­чик — фул­стек. В любом вари­ан­те, тре­тий остав­ший­ся раз­ра­бот­чик — это не фул­стек.

Если же вто­рой отве­ча­ет «Надо поду­мать», то либо он фул­стек и отве­ча­ет слу­чай­ным обра­зом, либо он не фул­стек, а это озна­ча­ет, что пер­вый раз­ра­бот­чик — тоже не фул­стек. В любом вари­ан­те, пер­вый раз­ра­бот­чик — это не фул­стек.

2. По пер­во­му вопро­су нам ста­ло понят­но, кто из них НЕ фул­стек. Спро­сим у него: «Если я спро­шу у тебя: „Ты — фрон­тенд?“, ты отве­тишь мне „Зави­сит от ситу­а­ции“?» Посколь­ку он не фул­стек, ответ «Надо поду­мать» озна­ча­ет, что он бэкенд, а ответ «Зави­сит от ситу­а­ции» озна­ча­ет, что он фрон­тенд.

3. Спро­сим у это­го же раз­ра­бот­чи­ка «Если я у тебя спро­шу: „Про­грам­мист, кото­ро­му я зада­вал свой пер­вый вопрос — фул­стек?“, отве­тишь ли ты „Зави­сит от ситу­а­ции“?» Если отве­тят «Зави­сит от ситу­а­ции» — то пер­вый, у кого мы спра­ши­ва­ли, будет фул­сте­ком, а если нам отве­тят «Надо поду­мать», то фул­сте­ком будет про­грам­мист, с кото­рым ещё не гово­ри­ли.

Послед­ний раз­ра­бот­чик опре­де­ля­ет­ся мето­дом исклю­че­ния.

Если вы прочитали решение и всё поняли с первого раза — снимаем шляпу.

22:47