Менің білуімше • Константин Кнооп • «Элементтер» бойынша танымал ғылым тапсырмалары • Математика

Мен немен айналысамын деп ойлаймын

Тапсырма

Костя табиғи санды ойластырды K 1-ден 2013 жылға дейін және осындай жауап беруге мүмкіндік беретін сұрақтарға «иә» немесе «жоқ» деп жауап беруге дайын. Дегенмен, ол қате жауап беруге бірден емес (барлық жауаптар үшін) құқығы бар.

Саша Костяға 15 сұрақ қоя алмайды, жауаптарына сәйкес ол әрқашан болжамды нөмірді болжай алады. Көмек ол мұны жасайды.


1-кеңес

Әдетте мұндай тапсырмаларда «сұрақтар – салыстыру», яғни «Сіздің нөміріңіз осыдан аз» (немесе «осыдан артық») деп сұрауға тырысады. Дегенмен, Сашаға мұндай сұрақтарды шектеудің қажеті жоқ. Сұрақтардың неғұрлым жалпы түрі: Саша кез-келген сандарды жазады (1-ден 2013-ге дейінгі сандардың кейбірін қосады) және Костядан: «Сіз осы нөмірлердің бірін жоспарладыңыз ба?» Деп сұрайды.


2-кеңес

Егер Коста қателеспесе, Саша үшін 11 сұрақ жеткілікті еді (неге деп ойлаймын). Мәселен, Саша төрт сұраққа «қоймада» бар және ол сұрақ қоюға тырысуы керек, егер бір кезде Костяның жауаптары бір-біріне қайшы келсе, K стандартты түрде, қалған опциялардың санын екі есе азайтады.


Кеңес 3

Саша туралы алғашқы 11 сұраққа жауап беруге тырысыңыз, оларға жауап бергеннен кейін Саша «күдікті тізімде» 12 нөмір қалдыруы мүмкін – біреуі Костяны ұсынбаған және әрқайсысы мүмкін Сүйек қателігі үшін тағы бір нөмір.


Шешім

Алдымен 3-кеңесте ұсынылғандарды жасаймыз.

Мұны істеудің ең оңай жолы – екілік жүйені пайдалану. 2013 жылдан бастап 2-ден кем11 = 2048 болса, ықтимал ойластырылған сандардың кез келгенінің екілік жазбасы 11 саннан аспайды. Әр санның цифры 0 немесе 1 болғандықтан, Саша бірінші сұраққа тікелей жауап бере алады: «Бұл фигураның дұрыс екендігі рас па? i-m (оң жақта) нөмірленген екілік сан 1 болса?«Барлығы арқылы i 1-ден 11-ге дейін.

Егер Костя осы сұрақтардың біріне жауап беруде қате жасамаса, онда Саша жоспарланған санның барлық сандарын біледі, яғни ол нөмірді біледі K (Дегенмен, ол Костяның дұрыс емес екендігін білмегендіктен, ол болжанған нөмірді біледі деп ойламайды). Егер Костя қандай да бір сұраққа жауап беруде қате жасаса, бұл болжамды нөмірді білдіреді K кез келген битке жауап берілген сүйектерден ерекшеленеді.Бірақ мұндай сан тек бір ғана – және 11 битке кез келген қате жасалуы мүмкін болғандықтан, дәл 11 күдікті сан бар.

Алынған тізімнен 12 нөмірді белгілеңіз. K0, K1, … , K11 (бірінші – қателіктер болмаған жағдайда, қалғаны – тиісті сұраққа жауап беру қатесі болған жағдайда).

Саша қазір қалай әрекет етуі керек? Егер ол келесі сұрақты (сұрақ құрылымында 1-тармақты қараңыз) жиынтығы туралы сұраса d сандар (бәрібір, бірақ қосылмаған) K0; мысалы K1, … , Kd) және «иә» деп жауап берсеңіз, ол екі нәрсенің бірін білдіреді: олардың бірі d Бұл сұрақтың жауабында Костяның қателігі болды. Бірақ егер Костя дұрыс болмаса, ол тек болжауға болатын K0себебі басқа нұсқалар Kd+1, … , K11 Костя бұрынғы сұрақтардың жауабында қателескенін және екінші қате жасай алмайтындығын білдіреді! Мәселен, «иә» деген жауаппен Саша дәл қалады d + 1 нұсқасы және ол Костяның бұрынғы жауаптардың бірінде дұрыс емес екенін түсінеді. Осы сұрақтан кейін Саша қорықта тағы 3 сұрақ қалды, ол 8 нұсқаны жоспарланған санын болжай алады. Сондықтан, біз қоюға болады d + 1 = 8, яғни, d = 7 және 12-сұраққа тек «жоқ» деп жауап беріңіз.

Жауап «жоқ» дегеніміз Костяның шынымен сандарды ойлай алмайтынын білдіреді. K1, … , K7 (басқаша ол оның екінші қателігі еді). Мәселен, мұндай жауап кейін күдікті сандар тізімі 5 дейін төмендеді: K0, K8, K9, K10, K11. Жоғарыда айтылғандай дәлелдеңіз, 13-ші сұрақта Саша сандар туралы сұрауға болады K8, K9, K10: Егер жауап иә болса, ол төрт нөмірдің біреуін білуі керек K0, K8, K9, K10бұл үшін қалған екі сұраққа жеткілікті, ал күдікті тізімде «жоқ» деген жауап болған жағдайда ғана қалады K0 және K11.

Қазір (14 сұрақ) бір санды сұрастыру жеткілікті K11. Жоғарыда талданған жағдайдағыдай, «иә» деген жауап Костяның қате жібергенін білдіреді, содан кейін Саша соңғы, 15 сұраққа екі санның бірін табады. 15-сұрақтың «жоқ» деген жауапынан кейін сіз енді сұрай алмайсыз – Саша Коста ойлап тапты K = K0.


Кейінгі сөз

1. Екілік жүйені қолданусыз жасауға бола ма? Әрине, әрине.

Айта кетейік, Костя мен Саша арасындағы «ойын» әр сәтте жағдай («ойын күйі») екі санымен толығымен сипатталады [а; б]: а – Костяның әлі де қателеспеген жағдайда, болжауға болатын сандарының саны б – бұрынғы жауаптардың бірінде қате жіберген жағдайда, Костяның болжаған сандарының саны.Ойын басталады [2013; 0], бірақ ол «күдікті» нөмір жалғыз болып қалатын сәтте аяқталуы тиіс – яғни, мемлекетте [1; 0] немесе [0; 1].

Сашаның бірінші сұрағы көптеген жиынтыққа қатысты болсын d сандар Содан кейін «иә» деп жауап бергеннен кейін ойынның жаңа жағдайы [d; 2013 – d], және жауап кейін «жоқ» – [2013 – d; d] (бұл неге деп ойлаймын). Егер Саша 2013 нөмірін жиынтығын екі тең бөлікке бөлсе, онда ол мемлекеттердің бірін алады [1007; 1006] және [1006; 1007]. Екінші мәселе бойынша, ол осы бөліктердің әрқайсысын жартысына дейін бөліп, [504; 1006] немесе [503; 1007] (мұнда төмендегідей 1007 сандар алынады: алдымен, бұл 504 нөмір б = 1007, ол Сашаға өзінің жинағына кірді, екіншіден, 503 нөмір а = 1006, ол ол жинаққа кіргізбеді – бірақ егер Костя бұл сұраққа жауап беруде қате жіберсе, онда бұл сандар оларға жасалуы мүмкін еді).

Сұрақ қоюды жалғастыра отырып, біз дәйекті түрде

[504; 1006] → [252; 755] → [126; 504] → [63; 315] → [32; 189] → [16; 111] → [8; 64] → [4; 36] → [2; 20] → [1; 11]

(немесе [503; 1007] → [251, 755]), бұл тізбектегіден аз.

Осылайша, біздің шешімімізде сипатталған «1 + 11» жағдай екілік жүйенің ешбір еске салусыз қол жеткізілуі мүмкін еді.Сонда [1; 11] → ([1, 4] немесе [0; 8]) → ([1, 1] немесе [0; 4]) → ([1, 0] немесе [0; 2]) → [0; 1].

2. Біздің шешімімізге сәйкес, 1-ден 2013 жылға дейінгі сандардың орнына Саша Костяға 0-ден 2047-ге дейінгі сандарды білуге ​​мүмкіндік береді және әлі де 15 сұраққа жауап бере алады. Дегенмен, бұл табиғи түрде жалпыланған мәселені жауапсыз қалдырады. Сашаға рұқсат етілсін 15 емес, бірақ N сұрақтар қойды. Қандай диапазонда (0-ден М) Костяға сандарды болжауға мүмкіндік берер ме, сонда бұл сұрақтар кепілдік берілген болжам үшін жеткілікті ме?

Бұл сұраққа толығымен жауап (дәлірек айтқанда, бұл жауаптың дұрыстығын дәлелдеу) бір қарағанда қарапайым сияқты қарапайым емес. Бұл келесідей жазылуы мүмкін: егер (мұнда [x] – санның бүтін бөлігі x, яғни ең үлкен бүтін сан x) анық М = с, ал егер с содан кейін тақ М = с – 1. Сонымен қатар, мәселе туралы мәлімдеме сәттен бастап оның толық шешімін алғанға дейін 20 жылдан астам уақыт өтті!

Мүмкін, алғаш рет жауаптардағы қателіктерді жасай білу қабілеті бар болжамды мәселені венгр тіліндегі 1961 жылғы мақалада тамаша венгер математикы Альфред Реньян тұжырымдаған. Бірнеше жылдан кейін (оның өмірбаянында, «Математика приключения») американдық математик Станислав Улам кеңінен танымал болды.

«Хокинс мен мен [Давид Хокинс, философ, кейінірек танымал ғылыми кітаптың авторы – Табиғат тілі. Ескерту аутентификация.] келесідей тапсырманы ойластырды: жиырма сұрақ ойынын өзгерту. Бір адам 1-ден 1 миллионға дейінгі ауқымда санайды (бұл 2-ден кем)20). Басқа адамға жиырма сұрақ қоюға рұқсат етіледі, олардың әрқайсысы бірінші қатысушыға тек «иә» немесе «жоқ» деп жауап беруі керек. Әлбетте, егер сіз бірінші сұрасаңыз, бұл нөмірді миллиондаған бірінші жартысында білуге ​​болады ма? Келесі сұрақта тағы да сандардың аралық интервалын және тағы басқаларын ажыратыңыз. Сайып келгенде, нөмірді журналға қарағанда аз деп санауға болады.21,000,000 рет Енді қатысушы бір-екі рет өтірік айтуға құқылы. Дұрыс жауап алу үшін қанша сұрақ туындайды? Әрине, біреуін табу үшін 2n сандар көп талап етіледі n өйткені, ол туралы айтылған кезде белгісіз. Жалпы бұл мәселе шешілмеген ».

Бір проблеманы шешу үшін Улам мәселесінің толық шешімі 1986 жылы Анджей Пелцке және 1990 жылы екі қате жіберілді. 10 жыл өткеннен кейін математиктер «үш қатеге құқық» мәселесін толығымен шеше алды. Тапсырмалар үшін bшамаментек жеке жекелеген істер көп қателіктермен шешілді және әлі де толық шешімдер табылған жоқ.

3. Егер сіз оңтайлы шешімдер мен ең аз сұрақтарды қажет етпесеңіз, онда барлығы оңайырақ болады. 1991 жылы Бүкілодақтық математикалық олимпиадада төмендегідей мәселе ұсынылды (авторлар – А. Анжан, И. Соловьев, В.Слитинский.)

Тергеуші қылмысты анықтауға кепілдік беретін куәдан жауап алудың жоспарын жасады. Ол «иә» немесе «жоқ» деп жауап беруге болатын сұрақтар қоюды жоспарлайды (бұл сұрақ алдыңғы сұрақтарға байланысты болуы мүмкін). Тергеуші барлық жауаптардың дұрыс екеніне сенеді, ол жауаптардың кез-келген нұсқасында 91 сұрақтан аспайтын деп есептейді. Тергеушінің қылмысты шешуге кепілдік беретін 105 сұрақтан аспайтын жоспарды жасай алатынын және егер бір сұрақтың дұрыс жауап берілмесе (бірақ барлық жауаптардың дұрыс болуы мүмкін болса) екендігін дәлелдеңіз.

Бұл мәселені шешу тағы бір идеяға негізделді: оған «бақылау сұрақтарын» қосу арқылы сұрақтардың бастапқы жоспарын өзгерту. Біріншіден, тергеуші бастапқы жоспардың алғашқы 13 сұрағын сұрайды, содан кейін 14-ші сұрақты «Сіз алдыңғы сұрақтар қатарында жатдыңыз ба?» Деп сұрайды.«Жоқ» деген жауап алғаннан кейін, ол әр сериядан кейін бақылау мәселесін қайталап, жоспардың 12, 11, 10, …, 1 сұрақтары бойынша сұрақ қоюды жалғастыра алады (сұрақтарға жауап жоқ, неге «жауап» деген сұрақтар сериялық сұрақтарға жауаптардың шын мәнінде болатындығына кепілдік береді). адал). Егер «иә» деген жауап басқару сұрақтарының біріне алынады, онда алдыңғы серия қайталанып, бақылау сұрақтары қойылмайды. Егер жауап «иә» болса, қабылданады kбақылау мәселесі, онда бастапқы жоспарға қосымша сұрауға тура келеді k + (14 – k) = 14 сұрақ. Айта кетейік, бақылау мәселесіне жауапта өтірік болуы мүмкін – бұл жағдайда қайталанатын серияларға жауаптар бірінші рет дәл солай болады.

Неліктен «жоспардың өзгеруі» оңтайлы стратегия емес және ең төменгі сұрақтарға жауап бермейді? Мысалы, тергеушінің бастапқы тапсырмасы 0-ден 2-ге дейінгі ауқымдағы болжамды санды болжауға тең болғандықтан91 – 1. Бірақ біз білетініміздей, 105 емес, тек 98 сұрақ жеткілікті: 298/99 > 298/27 = 291. Соған қарамастан, олимпиададағы ұсынылған өзгерістер жоспардың ұзақтығын арттырады N(N – 1) / 2 сұрақ артық емес N, яғни квадрат түбірінің реті бойынша түпнұсқалық ұзындығының екі есе. Жалпы, бұл да жаман емес.

4. Неліктен мұндай математиктер «ойыншық» міндеттерін жасайды? Өйткені, бұл мәселе кодтау теориясының классикалық мәселелеріне өте жақын және олармен тығыз байланысты (қараңыз: «Қате анықтау және түзету қатесі», Хамминг кодексі). Шынында да, біз сипаттаған ойында, Костя мен Саша сұрақтарға берілген сұрақтардың тізімін алдын-ала (Костяның болжамды нөмірін таңдағанға дейін) келісе алады (соның ішінде бірінші сұраққа «иә» деп жауап бергенде екінші сұрақ қойылады және оның қайсысы «жоқ» деп жауап беріп, келесі сұрақтар бойынша да келіседі). Бұл дегеніміз, Костя Сашаға тек 15 сұрақтың бірізділігін жіберуі мүмкін – немесе, қаласаңыз, 15 символдан тұратын «0» және «1» ретін білдіреді. Әрбір осындай дәйектілік үшін Саша Костяның жоспарларының санын біледі («қайта құру»), сондықтан Костяның қандай қателескені туралы сұрақтың жауабын анықтайды. Бұл бір қатені түзететін Хаммингтің коды.

1950 жылы Х. Хеммиңнің «Қателерді анықтайтын және түзеткен кодтар» атты мақаласы жарық көрді (түпнұсқасы, мысалы, PDF, 3.1 МБ). Сол кезде бастапқы деректерді компьютерге жинақталған карточкалар арқылы жүктеуге болады, ал пышақтардың кіріс құрылғылары соншалықты сенімді емес, бұл жеткіліксіз палубаның қатесіз оқылмауы мүмкін.Қате бар бағдарламаны іске қосу апатқа ұшырады, содан кейін есептеулер тоқтатылды, палуба қайтадан оқылып, ең нашар – машинаның толық тоқтауына дейін. Хамминг ойлап тапқан кодтар қателерді анықтауға ғана емес, оларды автоматты түрде түзетуге де мүмкіндік берді. Бұл нақты революция болды!

Содан бері, әрине, компьютерлік жүйелердің сенімділігі бірнеше есе өсті, алайда қателерді түзететін кодтар осыған байланысты танымал болмады: енді олар байланыс хаттамаларының негізін құрайды. Байланыс желілері біршама уақыт жақсарады, бірақ түзету кодекстеріне қажеттілік жетпейді: қателер – кез-келген адам қызметінің мәңгілік спутниктері.


Like this post? Please share to your friends:
Leave a Reply

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!: