Пятница... Опять задачки ;)

← →
default © (2004-05-01 22:06) [120]

можно сделать так
есть у нас пять карт
В Д Т K 9
пусть кодируем Т(пусть это будет туз бубей)
предварительно задаётся некий порядок на 52 картах
в результате чего для 4 карт В Д К 9 можем написать к примеру
2 3 4 1
1)первой картой задаём масть
1 - черви, 2 - буби, ...
для нашего случая первой картой будет 2
2)второй картой задаём номер карты в данной масти
оставшиеся три карты в соотв-ии с принятым порядком
запишем как 2 3 1
1-2..5
2-6..9
3-10..14 (11-валет, 12-дама и тд.)
для нашего случая второй картой будет 3
3) перестановкой последних двух карт задаём номер карты
в нужном отрезке(пункт 2)
но перестановкой 2 карт можно задать 4 комбинации!
а у нас есть отрезок в пункте 2 в котором находятся 5 номеров!
как быть?!недостаёт информации!но у нас же есть магия помошника!
он просто не будет в качестве карты-загадки брать, к примеру, тузы, ведь среди 5 карт хоть одна имеет другой ранг(то есть пяти тузов для нашего случая быть не может!)!всё задача решена!

← →
default © (2004-05-01 22:12) [121]

"второй картой задаём номер карты в данной масти"
точнее номер отрезка в котром лежит карта-загадка

← →
Sha © (2004-05-01 22:47) [122]

2 default

Нельзя ли поянить на примере?
Скажем выпали туз пик, туз крестей и 2,3,4 червей.

← →
default © (2004-05-01 22:58) [123]

Sha © (01.05.04 22:47) [122]
ok хоккей досмотрю и приведу

← →
Sha © (2004-05-01 23:08) [124]

2 default

Все понял. Отличное рещение. Поздравляю!

← →
Sha © (2004-05-01 23:41) [125]

2 default

Кажется, я поторопился с поздравлениями...

Как я понял, твое решение выглядит так:

Помощник откладывает в сторону любую карту удовлетворяющую единственному условию: есть еще хотя бы одна бОльшая карта той же масти. Заметим, что при таком выборе отложенная карта не может быть тузом.
Эту бОльшую карту он отрывает первой, указывая фокуснику масть.
Далее из трех оставшихся карт для кодирования одного из трех диапазонов, которым может принадлежать отложенная карта (2..5,6..9,10..К), соответственно выбирается
младшая, средняя или старшая. Эта карта открывается второй.
И наконец, парой оставшихся карт кодируется смещение (0..3)
загаданной карты внутри диапазона.

Проблема в том, что возможно всего два расположения двух последних карт: (младшая,старшая) и (старшая,младшая), - а этого недостаточно для кодирования 4-х смещений :(

← →
default © (2004-05-02 00:01) [126]

мда...когда писал "но перестановкой 2 карт можно задать 4 комбинации!" думал почему-то о 2 битах...
таким способом не удастся задать 8 карт, опять не хватает инф-ции...

← →
default © (2004-05-02 00:04) [127]

да когда стал писать пример тоже это увидел, одни расстройства(в шутку)

← →
default © (2004-05-02 00:13) [128]

даже не 8, а куда больше...

← →
Sha © (2004-05-02 09:25) [129]

> default © (02.05.04 00:01) [126]
> мда...когда писал "но перестановкой 2 карт можно задать 4 комбинации!" думал почему-то о 2 битах...

Я почему-то тоже :)

← →
SergP © (2004-05-02 10:52) [130]

SergP © (30.04.04 18:13)

> Когда гиря находилась в лодке она под действием силы тяжести
> выталкивала столько же воды, сколько находясь на дне (Закон
> Архимеда)

М-да.... Однако.... :-))) Это может быть верным только если плотность гири равна плотности воды....

Думкин © (30.04.04 18:21)

> [100] SergP © (30.04.04 18:13)

Нет. И при меньше и равно. Правда...есть одно но - найдите.

Вы не правы...
При меньше гиря будет выталкивать столько же воды если она будет не на дне, а плавать на поверхности. Но если же она будет на дне (например кто-то ее там держит), то количество выталкиваемой воды будет разным (за исключением случая когда уровень воды таков что плавающая гиря будет касаться дна).

← →
Sha © (2004-05-03 09:23) [131]

Если кому трудно крутить в уме алгоритм Sha © (01.05.04 15:03) [115], то вот исходники для решения задачи #2.
Все по-честному, без обмана.

(* Sha 2004 Демонстрационная программа, доказывающая возможность следующего фокуса. Из колоды в 52 карты помощник извлекает наугад 5 карт, показывает зрителям и смотрит сам, после чего выбирает одну из них и прячет. Остальные 4 карты выкладывает в ряд на столе. Затем приходит фокусник и, глядя на лежащие карты, называет спрятанную. Обозначим масти символами m1, m2, m3, m4. Количество извлеченных карт каждой масти обозначим c1, c2, c3, c4, причем c1 + c2 + c3 + c4 = 5. Количество карт, оставленных помощником, обозначим d1, d2, d3, d4, причем d1 + d2 + d3 + d4 = 4 и d1<=c1, d2<=c2, d3<=c3, d4<=c4. Не ограничивая общность рассуждений, можем считать, что выполняются неравенства c1>=c2, c1>=c3, c3>=c4 и масти m1 и m2 одного цвета, а масти m3 и m4 - другого. в противном случае перенумеруем наши масти. Флажкам f1, f2, f3, f4 будем присваивать значение 1, если сооветствующая масть может содержать отложенную карту и 0 в противном случае. Идея решения состоит в том, чтобы выбрать 2 масти, содержащие не менее 3-х из 5-ти извлеченных карт и спрятать одну этих трех карт. При этом выбор этих мастей должен быть сделан таким образом, чтобы по мастям 4-х открытых карт фокусник смог однозначно определить 2 выбранные нами масти. Т.к. в двух мастях 26 карт и не менее 2-х карт из них уже открыты, то нам остается закодировать номер одной карты из 24. Мы делаем это, располагая 4 открытых карты одним из 4!=24 способов, и тем самым сообщаем фокуснику порядковый номер искомой карты в активном подмножестве карт. Правила определения фокусником масти отложенной карты: 1. Цвет тройки. Если оставлены 3 или больше карт одной масти, то искомая карта имеет тот же цвет, что эти карты. 2. Масти разноцветных пар. Если оставлены пара карт одной (красной) масти и пара карт другой (черной) масти, то искомая карта имеет одну из этих мастей. 3. Цвет одинокой пары. Если оставлены 2 карты разных мастей одного цвета и пара карт одной масти другого цвета, то искомая карта имеет тот же цвет, что и пара карт. 4. Масти разноцветных карт. Если оставлены 2 карты разных мастей разного цвета и пара карт произвольной масти, то искомая карта имеет ту же масть, что и одна из непарных карт. Правила выбора карты помощником: Помощник должен отложить такую карту, чтобы фокусник мог воспользоваться для ее угадывания одним из приведенных правил. Это всегда возможно (см. таблицу). Правила действий помощника и фокусника -------------------------------------------------------------------------------- извлеченные оставленные где искать правило -------------------------------------------------------------------------------- c1 c2 c3 c4 d1 d2 d3 d4 f1 f2 f3 f4 5 0 0 0 4 0 0 0 1 1 0 0 цвет тройки 4 1 0 0 3 1 0 0 1 1 0 0 цвет тройки 4 0 1 0 3 0 1 0 1 1 0 0 цвет тройки 3 2 0 0 3 1 0 0 1 1 0 0 цвет тройки 3 1 1 0 3 0 1 0 1 1 0 0 цвет тройки 3 0 2 0 2 0 2 0 1 0 1 0 масти разноцветых пар 3 0 1 1 2 0 1 1 1 1 0 0 цвет одинокой пары 2 1 1 1 2 0 1 1 1 1 0 0 цвет одинокой пары 2 2 1 0 2 1 1 0 0 1 1 0 масти разноцветных карт 2 1 2 0 2 1 1 0 0 1 1 0 масти разноцветных карт -------------------------------------------------------------------------------- *) unit ShaCardU; interface uses Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, StdCtrls; type TForm1 = class(TForm) Button1: TButton; Label1: TLabel; Label2: TLabel; procedure NewCards; procedure HideCard; procedure FindCard; procedure Button1Click(Sender: TObject); procedure FormCreate(Sender: TObject); end; var Form1: TForm1;

← →
Sha © (2004-05-03 09:24) [132]

implementation {$R *.dfm} const Captions: array[0..2] of string= ("Новый расклад","Спрятать","Угадать"); var Edits: array[0..5] of TEdit; type TCardSet= set of 0..51; TRule= record c, d, f, no: integer; end; const Rules: array[0..9] of TRule=( (c:$05000000; d:$04000000; f:$01010000; no:0), //0 цвет тройки (c:$04010000; d:$03010000; f:$01010000; no:0), //1 цвет тройки (c:$04000100; d:$03000100; f:$01010000; no:0), //2 цвет тройки (c:$03020000; d:$03010000; f:$01010000; no:0), //3 цвет тройки (c:$03010100; d:$03000100; f:$01010000; no:0), //4 цвет тройки (c:$03000200; d:$02000200; f:$01000100; no:1), //5 масти разноцветых пар (c:$03000101; d:$02000101; f:$01010000; no:2), //6 цвет одинокой пары (c:$02010101; d:$02000101; f:$01010000; no:2), //7 цвет одинокой пары (c:$02020100; d:$02010100; f:$00010100; no:3), //8 масти разноцветных карт (c:$02010200; d:$02010100; f:$00010100; no:3)); //9 масти разноцветных карт Permutations: array[0..23] of integer= ( $00010203, $00010302, $00020103, $00020301, $00030102, $00030201, $01000203, $01000302, $01020003, $01020300, $01030002, $01030200, $02000103, $02000301, $02010003, $02010300, $02030001, $02030100, $03000102, $03000201, $03010002, $03010200, $03020001, $03020100); //Показать карты procedure ShowCards(Count: integer); const Names: array[0..12] of string= ("2","3","4","5","6","7","8","9","10","В","Д","К","Т"); Kinds: array[0..3] of string= ("ч","б","п","к"); var i, t: integer; begin; for i:=0 to Count-1 do begin; t:=Edits[i].Tag; if (t>=0) and (t<52) then Edits[i].Text:=Format("%s %s",[Names[t div 4],Kinds[t mod 4]]); end; for i:=Count to High(Edits) do Edits[i].Text:=""; end; //Подсчет количества карт каждой масти и сортировка procedure CountCards(var m, n: integer; Count: integer); var mb: array[0..3] of byte absolute m; //количество карт каждой масти nb: array[0..3] of byte absolute n; //номера мастей b: byte; //временная переменная для обмена байтов i: integer; //временная begin; //Подсчет карт каждой масти m:=0; for i:=0 to Count-1 do inc(mb[Edits[i].Tag mod 4]); //Сортировка мастей n:=$03020100; if mb[3]<mb[2] then begin; b:=mb[3]; mb[3]:=mb[2]; mb[2]:=b; b:=nb[3]; nb[3]:=nb[2]; nb[2]:=b; end; if mb[1]<mb[0] then begin; b:=mb[1]; mb[1]:=mb[0]; mb[0]:=b; b:=nb[1]; nb[1]:=nb[0]; nb[0]:=b; end; if (mb[3]<mb[1]) or (mb[3]=mb[1]) and (mb[2]<mb[0]) then begin; b:=mb[3]; mb[3]:=mb[1]; mb[1]:=b; b:=nb[3]; nb[3]:=nb[1]; nb[1]:=b; b:=mb[2]; mb[2]:=mb[0]; mb[0]:=b; b:=nb[2]; nb[2]:=nb[0]; nb[0]:=b; end; end; //Определение активного подмножества карт procedure DefineCardSet(var cs: TCardSet; Kind1, Kind2: integer); var i, t: integer; //временные begin; //Метим масти, которым может принадлежать загадка cs:=[]; for i:=0 to 51 do begin; t:=i mod 4; if (t=Kind1) or (t=Kind2) then include(cs,i); end; //Стираем метки у открытых карт for i:=0 to 3 do exclude(cs,Edits[i].Tag); end; //Сортировка открытых карт, результат - несортированные упакованные номера открытых карт function PackAndSortCards(var Sorted: integer): integer; var eb: array[0..3] of byte absolute Sorted; //номера открытых карт b: byte; //временная переменная для обмена байтов i, t: integer; //временные begin; Result:=0; for i:=0 to 3 do Result:=(Result shl 8) + Edits[i].Tag; Sorted:=Result; repeat; t:=0; for i:=0 to 2 do if eb[i]>eb[i+1] then begin; inc(t); b:=eb[i]; eb[i]:=eb[i+1]; eb[i+1]:=b; end; until t=0; end; //Сгенерировать новый расклад procedure TForm1.NewCards; var i, j, t, ct: integer; begin; for i:=0 to 4 do begin; repeat; ct:=0; t:=Random(52); for j:=0 to i-1 do if Edits[j].Tag=t then inc(ct); until ct=0; Edits[i].Tag:=t; end; ShowCards(5); Edits[4].Color:=clWindow; Label1.Caption:=""; Label2.Caption:=""; end; //Выбрать и спрятать одну из 5 карт procedure TForm1.HideCard; const RuleNames: array[0..3] of string= ("Цвет тройки", "Масти разноцветных пар", "Цвет одинокой пары", "Масти разноцветных карт"); var m: integer; mb: array[0..3] of byte absolute m; //количество карт каждой масти n: integer; nb: array[0..3] of byte absolute n; //номера мастей e: integer; eb: array[0..3] of byte absolute e; //номера открытых карт x: integer; xb: array[0..3] of byte absolute x; //перестановка i, t: integer; //временные RuleLine: integer; //номер расклада Kind1, Kind2: integer; //возможные масти Index: integer; //порядковый номер карты-загадки в подмножестве cs: TCardSet; //меченые карты begin; //Подсчет количества карт каждой масти и сортировка CountCards(m,n,5); //Определение номера расклада RuleLine:=0; for i:=1 to High(Rules) do if Rules[i].c=m then RuleLine:=i; //Определение возможных мастей t:=Rules[RuleLine].c-Rules[RuleLine].d; Kind1:=0; while not odd(t) do begin; t:=t shr 8; inc(Kind1); end; t:=Rules[RuleLine].f-(Rules[RuleLine].c-Rules[RuleLine].d); Kind2:=0; while not odd(t) do begin; t:=t shr 8; inc(Kind2); end; Kind1:=nb[Kind1]; //Масть карты-загадки Kind2:=nb[Kind2]; //Вторая возможная масть //Загадаем карту for i:=0 to 3 do begin; t:=Edits[i].Tag; if t mod 4=Kind1 then begin; Edits[i].Tag:=Edits[4].Tag; Edits[4].Tag:=t; break; end; end; //Определим активное подмножество карт DefineCardSet(cs,Kind1,Kind2); //Определяем порядковый номер загаданной карты в подмножестве (начиная с 0) i:=0; Index:=0; t:=Edits[4].Tag; while true do begin; if i=t then break; if i in cs then inc(Index); inc(i); end; //Сортировка открытых карт PackAndSortCards(e); //Располагаем открытые карты в порядке соответствующем Index x:=Permutations[Index]; for i:=0 to 3 do Edits[i].Tag:=eb[xb[i]]; //Показываем ShowCards(5); Edits[4].Tag:=-1; //Сотрем номер загаданной карты для большей скрытности Edits[4].Color:=clBtnFace; Label1.Caption:=Format("Расклад %d",[RuleLine]); Label2.Caption:=RuleNames[Rules[RuleLine].no]; end;

← →
Sha © (2004-05-03 09:25) [133]

//Угадать загаданную карту. procedure TForm1.FindCard; var m: integer; mb: array[0..3] of byte absolute m; //количество карт каждой масти n: integer; nb: array[0..3] of byte absolute n; //номера мастей e, ePacked: integer; eb: array[0..3] of byte absolute e; //номера открытых карт x: integer; xb: array[0..3] of byte absolute x; //перестановка i, t: integer; //временные RuleLine: integer; //номер расклада Kind1, Kind2: integer; //возможные масти Index: integer; //порядковый номер карты-загадки в подмножестве cs: TCardSet; //меченые карты begin; //Подсчет количества карт каждой масти и сортировка CountCards(m,n,4); //Определение номера расклада RuleLine:=0; for i:=1 to High(Rules) do if Rules[i].d=m then RuleLine:=i; //Определение возможных мастей t:=Rules[RuleLine].f; Kind1:=0; while not odd(t) do begin; t:=t shr 8; inc(Kind1); end; Kind2:=Kind1; t:=t and (-256); while not odd(t) do begin; t:=t shr 8; inc(Kind2); end; Kind1:=nb[Kind1]; //Первая возможная масть Kind2:=nb[Kind2]; //Вторая возможная масть //Определим активное подмножество карт DefineCardSet(cs,Kind1,Kind2); //Сортировка открытых карт ePacked:=PackAndSortCards(e); //Вычисляем порядковый номер загаданной карты в подмножестве Index:=0; while true do begin; x:=Permutations[Index]; t:=0; for i:=0 to 3 do t:=(t shl 8) + eb[xb[i]]; if ePacked=t then break; inc(Index); end; //Отсчитываем загаданную карту i:=0; while true do begin; if i in cs then begin; if Index=0 then break; dec(Index); end; inc(i); end; //Показываем Edits[5].Tag:=i; ShowCards(6); end; procedure TForm1.Button1Click(Sender: TObject); var t: integer; begin; t:=Button1.Tag; case t of 0: begin; t:=1; NewCards; end; 1: begin; t:=2; HideCard; end; 2: begin; t:=0; FindCard; end; else exit; end; Button1.Tag:=t; Button1.Caption:=Captions[t]; end; procedure TForm1.FormCreate(Sender: TObject); var i: integer; begin; Button1.Tag:=0; Button1.Caption:=Captions[0]; for i:=0 to 5 do begin; Edits[i]:=TEdit.Create(Self); with Edits[i] do begin; Parent:=Self; Top:=16; Width:=33; Left:=8+40*i; ReadOnly:=true; end; end; Edits[5].Color:=clBtnFace; Label1.Caption:=""; Label2.Caption:=""; Self.Caption:="АРМ фокусника"; Randomize; end; end. --------------- object Form1: TForm1 Left = 189 Top = 102 Width = 260 Height = 130 Caption = "Form1" Color = clBtnFace Font.Charset = DEFAULT_CHARSET Font.Color = clWindowText Font.Height = -11 Font.Name = "MS Sans Serif" Font.Style = [] OldCreateOrder = False OnCreate = FormCreate PixelsPerInch = 96 TextHeight = 13 object Label1: TLabel Left = 8 Top = 64 Width = 32 Height = 13 Caption = "Label1" end object Label2: TLabel Left = 8 Top = 80 Width = 32 Height = 13 Caption = "Label2" end object Button1: TButton Left = 88 Top = 48 Width = 153 Height = 25 Caption = "Button1" TabOrder = 0 OnClick = Button1Click end end

← →
MBo © (2004-05-03 12:02) [134]

>Sha
Вау! :)
Я тоже думал о реализации [114-116] для исследования ;)

Я прорабатывал еще такой вариант - для раскладов типа 5 в 0 или 4 в 1 используем ключ по масти, а для раскладов с наличием 3-4 мастей - используем тот факт, что при этом карты более равномерно распределены по общему интервалу 1-52, и, возможно, удастся однозначно удалять промежуточные карты (но это пока только в голове)

← →
2963 (2004-05-03 12:19) [135]

to MBo
Классные задачки...где взял не подскажешь?
или выложи еще...

>2963
>где взял не подскажешь?
большинство запомнилось из Гарднера, Перельмана, еще каких-то книг, что-то в инете встречал.
>или выложи еще...
В прошлую пятницу был еще набор задачек.

MBo © (03.05.04 12:02) [134]

Похожие мысли занимали и мой досуг.
Оказывается, задача #2 допускает обобщение на случай загадывания
одной из m+1 карт, извлеченных из колоды, содержащей 2*m!+m карт m мастей.
Решение настолько простое, что найти его может даже школьник.
Не хочу лишать тебя удовольствия :)

Не знаю, прочитал ли кто предыдущий пост.
Там был намек на другой вариант решения, более красивый. Его легко нащупать для m=2 и m=3.

Ниже приводится решение задачи Sha © (04.05.04 11:49) [137] и ее частного случая - задачи #2.
Желающие решить задачу самостоятельно могут уменьшить яркость своих мониторов :)

Среди m+1 карт m мастей обязательно должны найтись 2 или более карт одной масти. Мысленно расположим все возможные карты данной масти по окружности в порядке старшинства (аналогично тому, как это сделано на циферблате часов) и как-нибудь пометим карты, присутсвующие в выборке. Вычислим расстояние (по ходу часовой стрелки) от каждой помеченной карты до следующей. Т.к. общее количество карт одной масти, равное (2*m!+m)/m=2*(m-1)!+1, является длиной окружности, а количество карт этой масти в выборке не менее двух, то минимальное расстояние между картами d лежит в интервале 1<=d<=(m-1)!
Помощник первой открывает карту, имеюшую минимальное расстояние до следующей карты, загадывает эту самую следующую карту и, располагая рядом с первой остальные выбранные (m-1) карт одним из (m-1)! способов, сообщает фокуснику расстояние до загаданной карты.

>Sha © (05.05.04 10:56) [138]
Вот где сила, как оказалось - в циклическом заворачивании мастевого пространства :)))

И нетривиально, конечно, то, что не нужно все m карт использовать для указания дистанции - такое "ухудшение" даже в голову не приходило ;(

MBo © (05.05.04 13:04) [139]

Еще один интересный вопрос.
Оба решения предполагают одинаковый размер колоды для 2-х и 4-х мастей. Так ли это будет для 6, 8 и более мастей?

MBo © (05.05.04 13:33) [141]

Например, если колода состоит из 4 мастей, то оба решения дают ответ для количества карт в каждой масти меньшего или равного 13 или количества карт в колоде <= 52. Т.е. максимальная мощность колоды совпадает для этих решений.

Вопрос: а каково максимальное количество карт в колоде в случае 6 мастей для каждого из этих решений?

Пятница... Опять задачки ;) Найти похожие ветки